Alokator kustom

Alokator arena dan pool yang dibangun dengan tangan.

Daftar isi

Alokator di Odin hanyalah proc yang menaikkan pointer atau mengembalikan memori sesuai aturannya sendiri, sehingga alokator khusus dapat dibangun dengan tangan tanpa berkas pustaka tambahan. Topik ini membahas anatomi Allocator dan mode permintaannya, pembuatan alokator arena, yaitu alokator linear yang memakai satu buffer tunggal, kelemahannya, serta konsep pool untuk elemen berukuran sama beserta contoh yang berjalan. Setelah topik ini, alokator arena dan pool dapat ditulis, didaftarkan pada context, dan dipilih sesuai pola alokasinya.

Anatomi Allocator dan mode permintaannya#

Nilai Allocator pada base:runtime hanya berisi dua field, yaitu procedure berupa proc alokator dan data berupa pointer ke keadaannya. Semua operasi memori mengalir melalui satu tanda tangan yang sama, dan arah permintaannya ditentukan oleh nilai Allocator_Mode. Mode .Alloc meminta blok baru yang diisi nol, .Alloc_Non_Zeroed meminta blok baru tanpa pengisian nol, .Free melepaskan satu blok, .Free_All mengosongkan seluruh alokator, .Resize dan .Resize_Non_Zeroed mengubah ukuran blok lama, sedangkan .Query_Features melaporkan mode mana saja yang didukung. Proc alokator mengembalikan slice byte serta Allocator_Error, dan parameter #caller_location membuat setiap alokasi membawa lokasi sumbernya. Membangun alokator berarti menulis satu proc dengan tanda tangan itu, lalu membungkusnya dalam nilai Allocator yang dipasang pada context.

make menghitung ukuran dan alignment berdasarkan informasi tipe pada saat kompilasi, lalu meneruskan keduanya ke proc alokator aktif sebagai mode .Alloc. Itulah sebabnya alokator kustom tidak perlu mengetahui tipe apa pun, cukup ukuran byte dan batas alamatnya. Proc query_features pada paket core:mem memanggil mode .Query_Features untuk memperoleh himpunan mode yang didukung alokator, dan kode pustaka memakai hasilnya untuk menyesuaikan perilaku, misalnya pelacak alokasi yang memeriksa dukungan .Free_All pada alokator penopangnya sebelum pemasangan.

odin Contoh: tanda tangan proc alokator

// tidak-dijalankan
arena_sederhana_proc :: proc(
        allocator_data: rawptr,
        mode:           runtime.Allocator_Mode,
        size:           int,
        alignment:      int,
        old_memory:     rawptr,
        old_size:       int,
        loc :=          #caller_location,
) -> ([]byte, runtime.Allocator_Error)

Arena sederhana yang dibangun dengan tangan#

Arena memakai satu buffer dan satu pointer offset. Setiap permintaan alokasi digeser maju ke batas alignment, yakni kelipatan alamat yang dituntut tipe datanya, lalu offset naik sebesar ukuran permintaan ditambah padding-nya. Permintaan yang melebihi sisa buffer dikembalikan sebagai .Out_Of_Memory, bukan panic, sehingga pemanggil bisa menanggapinya. Mode .Free tidak didukung karena arena tidak mencatat alokasi satu per satu, dan itulah sifat yang membuat alokasinya sangat murah. Program berikut membangun arena berukuran 64 byte, mendaftarkannya sebagai alokator context, lalu mencoba alokasi yang melebihi kapasitas, pelepasan tunggal, dan pengosongan menyeluruh.

odin arena-sederhana.odin

package main

import "base:runtime"
import "core:fmt"
import "core:mem"

// arena berukuran tetap: satu buffer tunggal dan satu penunjuk offset
Arena_Sederhana :: struct {
        buffer: []byte,
        offset: int,
        puncak: int,
}

// proc alokator dengan tanda tangan yang sama seperti runtime.Allocator_Proc
arena_sederhana_proc :: proc(
        allocator_data: rawptr,
        mode:           runtime.Allocator_Mode,
        size:           int,
        alignment:      int,
        old_memory:     rawptr,
        old_size:       int,
        loc :=          #caller_location,
) -> ([]byte, runtime.Allocator_Error) {
        a := (^Arena_Sederhana)(allocator_data)
        switch mode {
        case .Alloc, .Alloc_Non_Zeroed:
                // geser pointer ke batas alignment, lalu naikkan offset
                akhir := uintptr(raw_data(a.buffer)) + uintptr(a.offset)
                ptr := runtime.align_forward_uintptr(akhir, uintptr(alignment))
                padding := int(ptr - akhir)
                if a.offset + padding + size > len(a.buffer) {
                        return nil, .Out_Of_Memory
                }
                a.offset += padding + size
                a.puncak = max(a.puncak, a.offset)
                if mode == .Alloc {
                        mem.zero(rawptr(ptr), size)
                }
                return mem.byte_slice(rawptr(ptr), size), nil
        case .Free_All:
                // seluruh arena dikosongkan sekaligus: offset kembali ke nol
                a.offset = 0
                return nil, nil
        case .Query_Features:
                set := (^runtime.Allocator_Mode_Set)(old_memory)
                if set != nil {
                        set^ = {.Alloc, .Alloc_Non_Zeroed, .Free_All, .Query_Features}
                }
                return nil, nil
        case .Free, .Resize, .Resize_Non_Zeroed, .Query_Info:
                return nil, .Mode_Not_Implemented
        }
        return nil, nil
}

main :: proc() {
        arena := Arena_Sederhana{buffer = make([]byte, 64)}

        // daftarkan arena sebagai alokator context untuk lingkup ini
        ctx_awal := context
        context.allocator = runtime.Allocator{
                procedure = arena_sederhana_proc,
                data      = &arena,
        }

        angka := make([]i32, 2)
        angka[0], angka[1] = 7, 9
        fmt.println("angka dari arena:", angka, "offset:", arena.offset)

        // permintaan melebihi kapasitas buffer dilaporkan sebagai error
        boros, err := make([]byte, 128)
        fmt.println("alokasi 128 byte berhasil:", boros != nil, "error:", err)

        // satu alokasi tidak dapat dilepaskan satu per satu
        gagal := delete(angka)
        fmt.println("error delete pada arena:", gagal)

        // seluruh arena dikosongkan dalam satu langkah
        ferr := free_all(context.allocator)
        fmt.println("error free_all:", ferr, "offset sekarang:", arena.offset)

        context = ctx_awal
        fmt.println("puncak penggunaan arena:", arena.puncak, "byte")
}

bash

# sumberkan lingkungan sandbox jalur odin bila belum tersedia
[ -f /home/kal/my-project/tools/env.sh ] && source /home/kal/my-project/tools/env.sh
# jalankan program dari dalam folder topik
odin run arena-sederhana.odin -file

text Keluaran

angka dari arena: [7, 9] offset: 8
alokasi 128 byte berhasil: false error: Out_Of_Memory
error delete pada arena: Mode_Not_Implemented
error free_all: None offset sekarang: 0
puncak penggunaan arena: 8 byte

Field puncak mencatat pemakaian tertinggi yang pernah tercapai, yaitu 8 byte untuk dua i32, dan nilainya tetap tersimpan setelah free_all mengosongkan arena. Nilai semacam ini menjadi bahan pengukuran ketika ukuran buffer arena harus ditetapkan untuk proyek nyata. Paket core:mem juga menyediakan arena yang sudah jadi melalui mem.Arena beserta mem.arena_init dan mem.arena_allocator, sehingga arena buatan sendiri dapat dibandingkan perilakunya dengan arena bawaan yang dibahas pada topik sistem context.

Kelemahan arena dan jawaban dari pool#

Arena tidak dapat melepaskan alokasi satu per satu, sehingga pola pemakaiannya adalah mengumpulkan alokasi yang lahir dan mati bersama, misalnya seluruh data satu frame. Kebutuhan berbeda muncul ketika elemen yang sama dilepas dan dibuat ulang terus-menerus, dan jawabannya adalah pool, yaitu alokator yang membagi buffer menjadi slot berukuran sama dan mengelola slot kosong melalui free list, yakni rantai slot kosong yang menyimpan pointer ke slot berikutnya di dalam slotnya sendiri. Alokasi hanya membongkar satu slot dari kepala rantai, dan pelepasan hanya menempelkan slot kembali. Keduanya berlangsung dalam waktu tetap tanpa pencarian. Perhitungan indeks slot dari selisih alamat adalah hal yang hanya mungkin karena seluruh slot berukuran sama, dan ukuran slot yang dipilih kelipatan alignment menghilangkan ruang terbuang untuk penyesuaian alignment di dalam slot. Program berikut memakai empat slot berukuran 32 byte, melepaskan slot pertama, lalu membuktikan slot itu dipakai ulang dan pool yang sudah habis mengembalikan nil.

odin pool-slot.odin

package main

import "core:fmt"

UKURAN_SLOT :: 32
JUMLAH_SLOT :: 4

// pool slot tetap: seluruh elemen berukuran sama
Pool_Slot :: struct {
        buffer:    []byte,
        slot_size: int,
        kepala:    int, // indeks slot kosong pertama, -1 berarti habis
}

// rantai slot kosong: slot i menyimpan indeks slot i+1 di dalam dirinya
pool_baru :: proc(p: ^Pool_Slot, buffer: []byte, slot_size: int) {
        p.buffer = buffer
        p.slot_size = slot_size
        n := len(buffer) / slot_size
        for i in 0..<n - 1 {
                (^int)(rawptr(&buffer[i * slot_size]))^ = i + 1
        }
        (^int)(rawptr(&buffer[(n - 1) * slot_size]))^ = -1
        p.kepala = 0
}

// mengambil slot dari kepala rantai tanpa mencari
pool_ambil :: proc(p: ^Pool_Slot) -> rawptr {
        if p.kepala == -1 {
                return nil
        }
        ptr := rawptr(&p.buffer[p.kepala * p.slot_size])
        p.kepala = (^int)(ptr)^
        return ptr
}

// slot dilepaskan kembali ke depan rantai dalam waktu tetap
pool_lepas :: proc(p: ^Pool_Slot, ptr: rawptr) {
        indeks := int((uintptr(ptr) - uintptr(raw_data(p.buffer))) / uintptr(p.slot_size))
        (^int)(ptr)^ = p.kepala
        p.kepala = indeks
}

// nomor urut slot untuk keperluan pelaporan
indeks_slot :: proc(p: ^Pool_Slot, ptr: rawptr) -> int {
        return int((uintptr(ptr) - uintptr(raw_data(p.buffer))) / uintptr(p.slot_size))
}

main :: proc() {
        p: Pool_Slot
        pool_baru(&p, make([]byte, UKURAN_SLOT * JUMLAH_SLOT), UKURAN_SLOT)

        a := pool_ambil(&p)
        b := pool_ambil(&p)
        fmt.println("slot pertama:", indeks_slot(&p, a), "slot kedua:", indeks_slot(&p, b))

        pool_lepas(&p, a)
        c := pool_ambil(&p)
        fmt.println("slot ketiga memakai ulang slot pertama:", indeks_slot(&p, c) == 0)

        d := pool_ambil(&p)
        e := pool_ambil(&p)
        fmt.println("slot keempat:", indeks_slot(&p, d), "slot kelima:", indeks_slot(&p, e))

        f := pool_ambil(&p)
        fmt.println("permintaan pada pool yang habis:", f == nil)
}

bash

# sumberkan lingkungan sandbox jalur odin bila belum tersedia
[ -f /home/kal/my-project/tools/env.sh ] && source /home/kal/my-project/tools/env.sh
# jalankan program dari dalam folder topik
odin run pool-slot.odin -file

text Keluaran

slot pertama: 0 slot kedua: 1
slot ketiga memakai ulang slot pertama: true
slot keempat: 2 slot kelima: 3
permintaan pada pool yang habis: true

Memilih antara arena, pool, dan heap#

Pemilihan alokator mengikuti bentuk alokasinya, bukan selera. Arena paling efektif bila semua alokasi mati bersama, pool paling efektif bila elemen berukuran sama lahir dan mati bergantian, sedangkan heap default paling fleksibel untuk ukuran yang acak dan umur pakai yang tercampur.

Dalam praktiknya, pola tersebut sering dipakai berdampingan dalam satu program. Satu arena melayani seluruh bahan kerja satu putaran dan dikosongkan dengan free_all di akhir putaran, beberapa pool melayani entitas yang jumlahnya naik-turun, misalnya antrean tiket loket yang slotnya dilepas dan diambil kembali, dan heap default menangani sisanya yang bentuk dan umur pakainya tidak beraturan. Ketiganya dibandingkan dalam tabel berikut.

Alokator	Pola alokasi	Pelepasan tunggal	Biaya alokasi
Arena	Banyak blok kecil mati bersama	Tidak didukung	Menambah pointer saja
Pool	Elemen berukuran sama bergantian	Didukung, dalam waktu tetap	Membongkar satu slot
Heap default	Ukuran acak, umur tercampur	Didukung per blok	Pencatatan per blok

Ringkasan#

Allocator hanya menyimpan proc dan pointer keadaannya, dan seluruh operasi memori dikendalikan oleh nilai Allocator_Mode pada satu tanda tangan proc.
Arena buatan sendiri menaikkan offset dengan alignment, melaporkan .Out_Of_Memory, dan mengosongkan diri melalui .Free_All, sedangkan .Free dikembalikan sebagai Mode_Not_Implemented.
Pool memakai free list di dalam slot untuk alokasi dan pelepasan elemen berukuran tetap dalam waktu tetap.
Pilihan alokator mengikuti pola umur pakai data: mati bersama untuk arena, bergantian berukuran sama untuk pool, dan acak untuk heap default.

Referensi#

Overview — Odin Documentation — Panduan resmi dengan bagian Allocators dan struktur nilainya.
Paket core:mem — Referensi pustaka Odin — Dokumentasi Allocator, Allocator_Mode, dan arena bawaan mem.Arena.
Repositori Odin — Odin Lang — Sumber resmi compiler dan pustaka core untuk membaca implementasi core:mem.