EN ไทย

16.5 Memory Allocator

เฟส 16 · Engine Programming (C++ ลึก, ไม่บังคับ) · เวลาเรียน: 20–35 h

allocator เองที่เอนจินพึ่ง — arena, pool, stack และ free-list — พร้อม scratch memory ต่อเฟรมและการ tracking การ alloc

ในบทเรื่อง memory ของ C คุณเรียนไปแล้วว่าค่าทุกตัวอยู่ที่ไหนสักแห่งเสมอ: บน stack (เร็ว อัตโนมัติ หายไปทันทีที่ฟังก์ชัน return) หรือบน heap (อยู่ได้นานเท่าที่คุณต้องการ แต่คุณต้องขอมันจากระบบปฏิบัติการด้วยอะไรทำนอง malloc และต้องคืนมันเองด้วย) คุณยังเรียนไปแล้วด้วยว่า pointer ก็แค่ตัวเลขตัวหนึ่ง — ที่อยู่ของ byte หนึ่งในหน่วยความจำ บทนี้จะเอาสองไอเดียนั้นมาใช้แก้ปัญหาที่ปฏิบัติจริงมาก: การเรียก malloc กับ new ตรง ๆ นับพันครั้งต่อวินาที ตลอดทั้ง session ที่เล่นเกม คือสิ่งที่เกมที่จะ ship จริงทำไม่ได้เด็ดขาด คุณกำลังจะสร้างเครื่องมือที่ engine จริงใช้แทน: allocator (โค้ดชิ้นเล็ก ๆ ที่จัดการ block หน่วยความจำให้คุณ) ที่ขอหน่วยความจำจาก OS แค่ครั้งเดียว แล้วแจกจ่ายมันเองต่อจากนั้น เร็วและคาดเดาได้

1. ทำไมไม่ใช้ malloc/new ทุกที่ไปเลย?

malloc กับ new เป็นเครื่องมืออเนกประสงค์ มันต้องรองรับทุกขนาด เรียกจาก thread ไหนก็ได้ ปล่อย (free) ในลำดับไหนก็ได้ ตลอดอายุของโปรแกรม ความอเนกประสงค์นั้นมีราคาที่ต้องจ่าย และมันเสียค่าใช้จ่ายกับคุณสามทาง:

มาดูค่าใช้จ่ายด้านความเร็วกันตรง ๆ นี่คือโปรแกรมเล็ก ๆ ที่รันได้จริง ทำแค่ allocate แล้ว free ซ้ำ ๆ แล้ววัดเวลาที่ใช้:

#include <chrono>
#include <cstdio>

int main() {
    const int COUNT = 2000000;

    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < COUNT; i++) {
        int* p = new int[16];   // 64 bytes each
        p[0] = i;                // touch it, so the compiler can't optimize the alloc away
        delete[] p;
    }
    auto end = std::chrono::high_resolution_clock::now();

    double ms = std::chrono::duration<double, std::milli>(end - start).count();
    printf("2,000,000 new/delete pairs: %.2f ms\n", ms);
    return 0;
}

รันบนโน้ตบุ๊กทั่ว ๆ ไปโดยปกติจะปริ้นท์ประมาณนี้:

2,000,000 new/delete pairs: 58.31 ms

ตัวเลขที่แน่นอนขึ้นอยู่กับ CPU, allocator ของ OS ที่คุณใช้ และโปรแกรมอื่นที่รันอยู่ — นั่นแหละคือประเด็น มันคาดเดาไม่ได้ แต่รูปแบบโดยรวมจะเหมือนกันทุกที่: ไม่กี่สิบนาโนวินาทีต่อการเรียกหนึ่งครั้งบวกกันไปเรื่อย ๆ เร็วมาก และภายใต้ load จริง — หลาย thread แย่ง lock ของ heap เดียวกัน กับ fragmentation ที่ทำให้การค้นหาชิ้นว่างช้าลง — ตัวเลขนั้นจะแย่ลงไปอีก และแย่ลงในแบบที่คุณคาดเดาล่วงหน้าได้ยาก ความคาดเดาไม่ได้นี่แหละคือศัตรูตัวจริงของโค้ดที่ต้องทำเวลาให้ทันงบเฟรมคงที่ทุก ๆ เฟรม

Fragmentation: หน่วยความจำว่างที่ไม่ได้ "ว่าง" จริง

นี่คือส่วนที่แย่ลงตามระยะเวลาที่เกมรัน ไม่ใช่ตามจำนวน allocation ต่อเฟรม ลองนึกภาพ heap หลังเล่นเกมมาสักพักใหญ่ ๆ: object หลายขนาดถูก allocate แล้ว free ไปในลำดับที่ไม่เหมือนกับลำดับที่ขอมาเลย

Heap after minutes of gameplay (blocks shown in the order they sit in memory) [ A: used 40 ][ gap: free 20 ][ B: used 30 ][ gap: free 50 ][ C: used 25 ][ gap: free 15 ][ D: used 10 ][ gap: free 10 ] total heap size = 200 bytes total FREE bytes = 20 + 50 + 15 + 10 = 95 bytes largest SINGLE free gap = 50 bytes (right after B) New request: "give me 64 contiguous bytes for a mesh buffer" 95 bytes are free somewhere in the heap ... but every single gap is smaller than 64. The allocator has to say: FAILED: out of memory even though the heap is less than half full. This is fragmentation.

"ว่าง" ไม่ได้แปลว่า "ใช้ได้" allocator แจกจ่ายได้แค่ช่วง byte ที่ต่อเนื่อง (contiguous) ไม่ขาดตอนเท่านั้น — มันเอาช่องว่าง 20 byte สามช่องที่แยกกันมาต่อกันเป็น 60 byte ไม่ได้ ทุกครั้งที่เกม allocate แล้ว free object หลายขนาดในลำดับที่ต่างจากลำดับที่มันเข้ามา มันจะทิ้งช่องว่างแบบนี้ไว้ ตลอด session สองชั่วโมง ด้วย object ชั่วคราวนับพันทุกขนาดที่ผ่านเข้าออก heap เดียวกัน ช่องว่างพวกนี้จะสะสมจนกระทั่งแม้แต่ allocation เล็ก ๆ ก็ล้มเหลวได้ — ไม่ใช่เพราะหน่วยความจำหมด แต่เพราะหน่วยความจำที่ต่อเนื่องหมด

Common mistake เชื่อตัวเลข "bytes free" (เช่นจาก task manager หรือสถิติ heap ง่าย ๆ) ว่าเป็นหลักฐานว่า allocation จะสำเร็จ ตัวเลขนั้นคือผลรวม (sum) ของช่องว่างทุกช่อง สิ่งที่ตัดสินจริง ๆ ว่าจะสำเร็จหรือล้มเหลวคือขนาดของช่องว่างเดี่ยวที่ใหญ่ที่สุด ซึ่งอาจเล็กกว่าผลรวมมาก heap อาจรายงานว่า "ว่าง 10 MB" แต่ก็ยังตอบสนอง request 1 MB ไม่ได้

2. ไอเดียหลัก: ขอ block ใหญ่ก้อนเดียว แล้วจัดการเอง

ทางแก้ที่ game engine แทบทุกตัวใช้พูดง่าย ๆ คือ: เลิกเรียก malloc/new ระหว่างเล่นเกมไปเลย แทนที่จะทำแบบนั้น ตอน startup ให้ขอหน่วยความจำก้อนใหญ่ก้อนเดียวจาก OS ด้วยการเรียกครั้งเดียว — มากกว่าที่ต้องใช้จริงสำหรับสิ่งเดียวมาก แต่เป็นจำนวนคงที่ที่รู้แน่นอน จากนั้นเป็นต้นไป ทุกระบบในเกม (physics, audio, rendering, AI) จะขอหน่วยความจำจากโค้ดของคุณเอง และโค้ดของคุณก็แค่ทำเลขคณิตกับ pointer ง่าย ๆ เพื่อแจกจ่ายชิ้นส่วนของ block นั้น ไม่มีการเรียก OS อีกเลย ไม่มี lock อีกเลย ไม่มีเซอร์ไพรส์อีกเลย ตลอดอายุที่เหลือของโปรแกรม

#include <cstdlib>
#include <cstdio>

class MemoryArena {
public:
    void Init(size_t sizeBytes) {
        base = static_cast<unsigned char*>(std::malloc(sizeBytes));
        capacity = sizeBytes;
        used = 0;
    }

    void Shutdown() {
        std::free(base);
        base = nullptr;
    }

    unsigned char* base = nullptr;
    size_t capacity = 0;
    size_t used = 0;
};

int main() {
    MemoryArena arena;
    arena.Init(64 * 1024 * 1024); // 64 MB, ONE malloc call for the whole game

    printf("Reserved %zu bytes from the OS in a single call.\n", arena.capacity);
    printf("From here on, every game system asks THIS object for memory,\n");
    printf("never malloc/new directly.\n");

    arena.Shutdown();
    return 0;
}

Reserved 67108864 bytes from the OS in a single call.
From here on, every game system asks THIS object for memory,
never malloc/new directly.
Startup (once, at the very start of the program): OS heap ------------------------------------------------ malloc(64 MB) -- ONE call, ONE trip to the OS | v Engine-owned block: [ 64 MB ] base base+64MB During gameplay (every frame, thousands of times): No more calls to malloc/new/the OS at all. The engine hands pieces of THIS block to whoever asks, using plain pointer math (an offset and a size), and takes them back the same way -- entirely under YOUR control.

ทุกอย่างที่เหลือในบทนี้คือกลยุทธ์ที่ต่างกันในการสับ block ก้อนนั้น: วิธีตัดสินใจว่าจะแจก byte ไหนต่อไป และวิธีรู้ว่าเมื่อไหร่จะเอามันกลับมาใช้ซ้ำได้ ข้อมูลของเกมแต่ละแบบมีอายุ (lifetime) ต่างกัน (ต่อเฟรม, ต่อด่าน, ต่อ object, ตลอดกาล) และแต่ละกลยุทธ์ด้านล่างนี้ถูกออกแบบมาให้เข้ากับ lifetime แบบใดแบบหนึ่งโดยเฉพาะ

3. Alignment: ทำไม byte ต้องเรียงให้ตรงแนว

ก่อนจะสร้าง allocator ตัวไหนก็ตาม มีเลขคณิต pointer อยู่ชิ้นหนึ่งที่ทุกตัวต้องใช้: alignment (การจัดแนว) alignment หมายความว่าที่อยู่นั้นเป็นจำนวนเท่าของตัวเลขบางตัว ปกติจะเป็นเลขยกกำลังสอง (4, 8, 16...) CPU ไม่ได้อ่านหน่วยความจำทีละ byte มันอ่านเป็นก้อนขนาดคงที่ (word) และคำสั่งฮาร์ดแวร์ (โดยเฉพาะคำสั่ง SIMD ที่ทำงานกับ 16 byte พร้อมกัน) มักจะบังคับเลยว่าข้อมูลต้องเริ่มที่ที่อยู่ที่ align แล้วเท่านั้น

#include <cstdint>
#include <cstdio>

uintptr_t AlignUp(uintptr_t address, size_t align) {
    // align MUST be a power of two (4, 8, 16, ...)
    return (address + align - 1) & ~(align - 1);
}

int main() {
    printf("alignof(int)    = %zu\n", alignof(int));
    printf("alignof(double) = %zu\n", alignof(double));

    uintptr_t addr = 1001; // pretend this is a raw byte address
    printf("1001 aligned to 4  -> %llu\n", (unsigned long long)AlignUp(addr, 4));
    printf("1001 aligned to 16 -> %llu\n", (unsigned long long)AlignUp(addr, 16));
    return 0;
}

alignof(int)    = 4
alignof(double) = 8
1001 aligned to 4  -> 1004
1001 aligned to 16 -> 1008

AlignUp เป็นเทคนิคที่ควรเข้าใจ ไม่ใช่แค่ท่องจำ: align - 1 คือชุดของบิต 1 ต่อกัน (สำหรับ align = 16 คือ 0b1111) การบวกมันเข้ากับ address ดันค่าให้เลยขอบเขตถัดไป แล้วการทำ AND กับ ~(align - 1) (บิตต่ำเหล่านั้นถูกกลับด้านและ invert) จะเคลียร์บิตต่ำลงมา ปัดผลลัพธ์ลงมาเป็นจำนวนเท่าที่ใกล้ที่สุดของ align ที่เท่ากับหรือมากกว่าที่อยู่เดิม allocator ทุกตัวในบทนี้ใช้สูตรนี้เป๊ะ ๆ

A 4-byte int, and a CPU that reads memory in 4-byte words Aligned (int placed at address 8, a multiple of 4): word0: [ . . . . ] addr 0-3 word1: [ . . . . ] addr 4-7 word2: [ X X X X ] addr 8-11 <- the whole int in ONE word, ONE read Misaligned (int placed at address 6, NOT a multiple of 4): word1: [ . . X X ] addr 4-7 <- half the int lives here word2: [ X X . . ] addr 8-11 <- the other half lives here The CPU must read word1 AND word2, then shift and stitch the bytes together. Two reads instead of one -- slower on most CPUs, and on some hardware (older ARM chips, some SIMD instructions, atomics on many platforms) it is not "slower," it is a hardware fault: the program crashes.
Tip การ align ไปที่ตัวเลขใหญ่กว่าที่ต้องการ (เช่น align ทุก allocation ไปที่ 64 byte "เผื่อไว้ก่อน") ก็ไม่ได้ฟรีเหมือนกัน — มันเปลือง padding byte ในทุก ๆ allocation และเมื่อมี object เล็ก ๆ นับพันตัว มันบวกกันเป็นเยอะได้ ให้ align ตามที่ข้อมูลต้องการจริง ๆ: alignof(T) สำหรับ type T หรือ 16 สำหรับข้อมูล vector แบบ SIMD ไม่ต้องมากกว่านั้น

4. Linear (Arena) Allocator: กระแทก pointer ไปข้างหน้า

allocator ที่ง่ายที่สุดเท่าที่จะเป็นไปได้เก็บตัวเลขแค่ตัวเดียว: offset ภายใน block เริ่มที่ 0 Alloc(size) จะ align offset ตรวจว่าที่ว่างพอไหม แล้วส่งคืน pointer ที่ offset ปัจจุบัน จากนั้นขยับ offset ไปข้างหน้าอีก size เท่านั้นเอง — ไม่มีการค้นหา ไม่มี bookkeeping ต่อ allocation นี่เรียกว่า linear allocator หรือ arena และการกระทำนี้มักถูกเรียกว่า "bump pointer" (กระแทก pointer)

#include <cstdint>
#include <cstddef>

class LinearAllocator {
public:
    void Init(void* memory, size_t sizeBytes) {
        base = static_cast<unsigned char*>(memory);
        capacity = sizeBytes;
        offset = 0;
    }

    void* Alloc(size_t sizeBytes, size_t align = 8) {
        uintptr_t current = reinterpret_cast<uintptr_t>(base) + offset;
        uintptr_t aligned = (current + align - 1) & ~(align - 1);
        size_t padding = aligned - current;

        if (offset + padding + sizeBytes > capacity) {
            return nullptr; // out of space in this arena
        }

        offset += padding + sizeBytes;
        return reinterpret_cast<void*>(aligned);
    }

    void Reset() {
        offset = 0; // "free" EVERYTHING in one step -- no per-object work at all
    }

private:
    unsigned char* base = nullptr;
    size_t capacity = 0;
    size_t offset = 0;
};

malloc จะส่งคืนหน่วยความจำที่ align อย่างน้อย alignof(std::max_align_t) เสมอ ซึ่งบนเครื่อง 64-bit ทั่ว ๆ ไปคือ 16 byte — ดังนั้นถ้าเราใช้ malloc เป็นฐานให้ arena นี้ offset 0 ก็จะเข้ากับ 8-byte alignment อยู่แล้ว นั่นทำให้เรา trace offset ที่แน่นอนซึ่งการเรียกเป็นลำดับจะคืนกลับมาได้:

#include <cstdlib>
#include <cstdio>

int main() {
    unsigned char* memory = static_cast<unsigned char*>(std::malloc(256));
    LinearAllocator arena;
    arena.Init(memory, 256);

    void* a = arena.Alloc(40);
    void* b = arena.Alloc(30);
    void* c = arena.Alloc(60);

    printf("a offset = %td\n", (unsigned char*)a - memory);
    printf("b offset = %td\n", (unsigned char*)b - memory);
    printf("c offset = %td\n", (unsigned char*)c - memory);

    arena.Reset();
    void* d = arena.Alloc(10);
    printf("d offset after Reset() = %td\n", (unsigned char*)d - memory);

    std::free(memory);
    return 0;
}

a offset = 0
b offset = 40
c offset = 72
d offset after Reset() = 0

ไล่ดูด้วยมือ: a เริ่มที่ offset 0 (align อยู่แล้ว) ใช้ไป 40 byte offset จึงกลายเป็น 40 b เริ่มที่ 40 (40 เป็นจำนวนเท่าของ 8 อยู่แล้ว ไม่ต้องมี padding) ใช้ไป 30 byte offset กลายเป็น 70 c เริ่มที่ 70 — แต่ 70 ไม่ใช่จำนวนเท่าของ 8 จึงต้องแทรก padding 2 byte เพื่อไปถึง 72 แล้วใช้ไปอีก 60 byte offset กลายเป็น 132 พอเรียก Reset() offset ก็สแนปกลับไป 0 ทันที ทำให้ d เริ่มที่ตำแหน่งเดียวกับที่ a เคยเริ่ม

LinearAllocator over one frame (256-byte arena, bump pointer) base base+256 | | v v [--- a: 40 ---][--- b: 30 ---][pd][----- c: 60 -----][ ... free ... ] 0 40 70 72 132 256 ^ offset (next Alloc starts here) Alloc() never searches anything -- it checks "does offset + size fit inside capacity?" and moves offset forward. That IS the entire cost of one allocation: an add and a compare. Reset() sets offset back to 0. It does NOT walk the block calling destructors or freeing individual objects -- everything allocated since the last Reset() is gone at once. That is exactly what you want for memory that only needs to live for one frame.

นี่คือ allocator ที่ควรหยิบใช้เมื่อไหร่ก็ตามที่ข้อมูลแค่ต้องอยู่รอดในเฟรมเดียว: scratch transform สำหรับ render pass, buffer ชั่วคราวสำหรับการค้นหา pathfinding, การ format string สำหรับ debug overlay ขอ block ครั้งเดียวตอน startup Alloc() จากมันตลอดทั้งเฟรม แล้ว Reset() ตอนต้นเฟรมถัดไป fragmentation ไม่ใช่แค่ไม่น่าจะเกิดที่นี่ — มันเกิดขึ้นไม่ได้เลย เพราะไม่มีอะไรถูก free ทีละชิ้นเลย มันคือ all-or-nothing ซึ่งก็เป็นข้อจำกัดของมันด้วยเช่นกัน

Tip สังเกตว่าไม่มี method Free(void* ptr) เลย — นั่นตั้งใจ ไม่ใช่ลืมใส่ ถ้าคุณพบว่าตัวเองอยากจะ free แค่ allocation เดียวออกจาก linear allocator แปลว่าคุณต้องการเครื่องมือคนละแบบ: stack allocator หรือ pool allocator ซึ่งกำลังจะมาถัดไป

5. Stack Allocator: LIFO พร้อม Marker

stack allocator คือ linear allocator ที่มีลูกเล่นเพิ่มมาอย่างหนึ่ง: คุณสามารถบันทึก offset ปัจจุบันไว้เป็น marker ยังคง allocate ต่อไปได้ แล้วภายหลังค่อยดึง offset กลับไปที่ marker นั้น — free ทุกอย่างที่ allocate หลังจากมัน ในขั้นตอนเดียว โดยไม่แตะต้องอะไรที่ allocate ไว้ก่อนหน้า ข้อแม้อยู่ในชื่อของมันเอง: มันทำงานได้แบบ LIFO เท่านั้น (Last In, First Out เข้าทีหลังออกก่อน กฎลำดับเดียวกับที่ call stack เองก็ใช้) คุณต้อง free marker ในลำดับย้อนกลับจากที่คุณเอามันมา

#include <cstdint>
#include <cstddef>

class StackAllocator {
public:
    using Marker = size_t;

    void Init(void* memory, size_t sizeBytes) {
        base = static_cast<unsigned char*>(memory);
        capacity = sizeBytes;
        offset = 0;
    }

    void* Alloc(size_t sizeBytes, size_t align = 8) {
        uintptr_t current = reinterpret_cast<uintptr_t>(base) + offset;
        uintptr_t aligned = (current + align - 1) & ~(align - 1);
        size_t padding = aligned - current;

        if (offset + padding + sizeBytes > capacity) {
            return nullptr;
        }

        offset += padding + sizeBytes;
        return reinterpret_cast<void*>(aligned);
    }

    Marker GetMarker() const {
        return offset;
    }

    void FreeToMarker(Marker marker) {
        offset = marker; // everything allocated AFTER this marker is gone
    }

private:
    unsigned char* base = nullptr;
    size_t capacity = 0;
    size_t offset = 0;
};

#include <cstdlib>
#include <cstdio>

int main() {
    unsigned char* memory = static_cast<unsigned char*>(std::malloc(256));
    StackAllocator stack;
    stack.Init(memory, 256);

    void* levelData = stack.Alloc(64);              // lives for the whole level
    StackAllocator::Marker frameMark = stack.GetMarker();

    void* pathBuffer = stack.Alloc(48);              // this frame's scratch work
    printf("offset with pathBuffer alive: %zu\n", stack.GetMarker());

    stack.FreeToMarker(frameMark);                   // done with this frame's scratch
    printf("offset after FreeToMarker:    %zu\n", stack.GetMarker());

    void* nextFrameBuffer = stack.Alloc(20);         // reuses the bytes pathBuffer used
    printf("nextFrameBuffer offset:       %td\n", (unsigned char*)nextFrameBuffer - memory);

    std::free(memory);
    return 0;
}

offset with pathBuffer alive: 112
offset after FreeToMarker:    64
nextFrameBuffer offset:       64

levelData เอา 64 byte แรกไป marker จึงถูกบันทึกไว้ที่ offset 64 pathBuffer เอาไปอีก 48 byte ดัน offset ไปที่ 112 พอเรียก FreeToMarker(frameMark) offset ก็สแนปกลับไปที่ 64 ทันที — levelData ไม่ถูกแตะต้อง แต่ 48 byte ที่ pathBuffer ใช้อยู่ก็กลายเป็นว่างอีกครั้ง แน่นอนว่า allocation ถัดไป nextFrameBuffer เริ่มที่ offset 64 พอดี: byte ชุดเดียวกันเป๊ะกับที่ pathBuffer เพิ่งใช้ไป

StackAllocator: LIFO with markers Alloc(levelData, 64) ------------------> offset = 64 marker = GetMarker() ------------------> marker = 64 (saved!) Alloc(pathBuffer, 48) ------------------> offset = 112 [---- levelData: 64 ----][---- pathBuffer: 48 ----][ ... free ... ] 0 64 112 256 ^ marker FreeToMarker(marker) --> offset snaps back to 64 [---- levelData: 64 ----][ ......... free (reclaimed) ......... ] 0 64 256 ^ next Alloc() starts here again Rule: only roll back to a marker once EVERYTHING allocated after it is also considered dead. Free markers in the reverse order you took them -- that is what LIFO means.
Common mistake เอา marker A มา แล้ว allocate ต่ออีกและเอา marker B มา แล้วเรียก FreeToMarker(A) ทั้ง ๆ ที่โค้ดที่อื่นยังถือ pointer เข้าไปในช่วงระหว่าง A กับ B อยู่ โดยคาดว่ามันจะยังใช้ได้ต่อ มันจะไม่ใช้ได้ — การดึงกลับไปเลย A จะ free ทุกอย่างหลังจากมันหมด รวมถึงทุกอย่างที่ B กำลังชี้อยู่ด้วย ไม่ว่าคุณจะตั้งใจเก็บมันไว้หรือไม่ก็ตาม ถ้าคุณต้องการ free อะไรโดยไม่เรียงลำดับ stack allocator คือเครื่องมือที่ผิด ให้ไปใช้ pool allocator ในหัวข้อถัดไปแทน

6. Pool Allocator: Block ขนาดคงที่กับ Free List

allocator สองตัวข้างต้นไม่เหมาะกับกรณีที่พบบ่อยนี้เลย: object ขนาดเท่ากันจำนวนมาก — กระสุน, particle, ศัตรู — ที่ถูกสร้างและทำลายตลอดเวลา ในลำดับที่ไม่เกี่ยวอะไรเลยกับตอนที่มันถูกสร้าง pool allocator ถูกสร้างมาเพื่อเรื่องนี้โดยเฉพาะ มันสับ block ออกเป็น N slot ขนาดคงที่ไว้ล่วงหน้า และเก็บ free list ไว้: ห่วงโซ่ของ slot ที่ว่างอยู่ตอนนี้ เชื่อมกันเป็นสาย Alloc() จะ pop หัวของ list นั้นออกมา; Free() จะ push slot กลับไปที่หัว ทั้งสองอย่างเป็น O(1) — ไม่มีการค้นหาเลยแม้แต่น้อย

#include <cstddef>

class PoolAllocator {
public:
    void Init(void* memory, size_t blockSize, size_t blockCount) {
        // Each FREE block's first few bytes store a pointer to the NEXT
        // free block. That's the whole trick: the free list lives INSIDE
        // the free memory itself, at zero extra storage cost.
        unsigned char* p = static_cast<unsigned char*>(memory);
        this->blockSize = blockSize;
        freeList = reinterpret_cast<FreeBlock*>(p);

        for (size_t i = 0; i < blockCount - 1; i++) {
            FreeBlock* block = reinterpret_cast<FreeBlock*>(p + i * blockSize);
            block->next = reinterpret_cast<FreeBlock*>(p + (i + 1) * blockSize);
        }
        FreeBlock* last = reinterpret_cast<FreeBlock*>(p + (blockCount - 1) * blockSize);
        last->next = nullptr;
    }

    void* Alloc() {
        if (!freeList) {
            return nullptr; // pool is full
        }
        FreeBlock* block = freeList;
        freeList = freeList->next;   // pop the head
        return block;
    }

    void Free(void* ptr) {
        FreeBlock* block = static_cast<FreeBlock*>(ptr);
        block->next = freeList;      // push back onto the head
        freeList = block;
    }

private:
    struct FreeBlock {
        FreeBlock* next;
    };
    FreeBlock* freeList = nullptr;
    size_t blockSize = 0;
};

#include <cstdio>

struct Bullet {
    float x, y, z;
    float speed;
};

int main() {
    unsigned char memory[sizeof(Bullet) * 4];
    PoolAllocator bullets;
    bullets.Init(memory, sizeof(Bullet), 4);

    void* b0 = bullets.Alloc();
    void* b1 = bullets.Alloc();
    void* b2 = bullets.Alloc();
    printf("allocated 3 of 4 slots\n");

    bullets.Free(b1);              // b1 dies, e.g. it hit something
    printf("freed the middle slot (b1)\n");

    void* b3 = bullets.Alloc();    // reuses b1's slot immediately
    printf("b3 == b1? %s\n", (b3 == b1) ? "yes" : "no");

    void* b4 = bullets.Alloc();    // the last remaining free slot
    void* b5 = bullets.Alloc();    // pool is now full
    printf("b5 == nullptr? %s\n", (b5 == nullptr) ? "yes" : "no");

    return 0;
}

allocated 3 of 4 slots
freed the middle slot (b1)
b3 == b1? yes
b5 == nullptr? yes
PoolAllocator: 4 fixed-size slots, singly linked free list Right after Init() -- every slot is free, chained in memory order: freeList --> [slot0] --> [slot1] --> [slot2] --> [slot3] --> null After Alloc() x3 (slot0, slot1, slot2 handed out as b0, b1, b2): freeList --> [slot3] --> null [slot0: USED] [slot1: USED] [slot2: USED] [slot3: free] After Free(b1) -- slot1 is pushed back onto the FRONT of the list: freeList --> [slot1] --> [slot3] --> null [slot0: USED] [slot1: free] [slot2: USED] [slot3: free] The next Alloc() pops [slot1] again -- reused instantly, no search, no fragmentation possible, because every slot is exactly the same size.

comment ใน Init() คุ้มค่าที่จะอ่านซ้ำ: byte ของ slot ที่ว่างเองถูกเอามาใช้ซ้ำเป็นที่เก็บ pointer "next" ของ free list ไม่มีใครมองหน่วยความจำนั้นเป็น Bullet จริง ๆ ในตอนที่มันยังว่างอยู่ ดังนั้นการเขียน pointer ลงไปตรงนั้นจึงปลอดภัย — และมันหมายความว่า free list ไม่เสียหน่วยความจำเพิ่มเลยนอกเหนือจาก slot เอง นี่แหละคือเหตุผลที่ pool allocator เป็นเครื่องมือมาตรฐานสำหรับกระสุน, particle, และศัตรู: สร้างและทำลายมันในลำดับไหนก็ได้ เร็วเท่ากับ push/pop ของ linked-list ไม่มี fragmentation เลย เพราะ slot ที่ว่างจะมีขนาดพอดีเป๊ะสำหรับ object ชนิดเดียวกันตัวถัดไปเสมอ

7. General-Purpose Free-List Allocator แบบคร่าว ๆ

บางครั้งคุณต้องการสิ่งที่ตรงข้ามกับ pool: object หลายขนาด free ในลำดับที่คาดเดาไม่ได้ ที่ไม่ใช่แค่ scratch data สำหรับเฟรมเดียว — เช่น การโหลดและปลดโหลด asset ตอนผู้เล่นเดินทางระหว่างด่าน สำหรับกรณีนี้คุณต้องการ general-purpose free-list allocator ซึ่งเก็บ list ของ block ที่ว่างไว้ แต่ละอันมี tag ขนาดของตัวเองกำกับ:

struct FreeBlockHeader {
    size_t size;
    FreeBlockHeader* next;
};

Alloc(size) จะไล่ list นี้หา block ที่ใหญ่พอ (กฎที่ง่ายที่สุดคือ first-fit เอาอันแรกที่พอดี; best-fit เอาอันเล็กที่สุดที่ยังพอดี แลกเวลาค้นหากับพื้นที่ที่เสียเปล่าน้อยลง) ถ้า block ที่เลือกมาใหญ่กว่าที่ขอมาก มันจะถูกแบ่งเป็นสอง ส่วนที่เหลือใส่กลับเข้า free list Free(ptr) เอา block กลับเข้า list — และที่สำคัญคือตรวจด้วยว่าเพื่อนบ้านที่อยู่ติดกันในหน่วยความจำว่างด้วยหรือเปล่า ถ้าใช่ก็รวมมันเข้าเป็น block ใหญ่ก้อนเดียว ขั้นตอนการรวมนี้เรียกว่า coalescing และมันคือแนวป้องกัน fragmentation หลักที่ general-purpose allocator มี

Coalescing on Free(): merge adjacent free neighbors into one block Before freeing B (B sits between free A and used C in memory): [free A: 32][used B: 16][used C: 40][free D: 24] Free(B) -- check neighbors in MEMORY order (not allocation order): left neighbor (A) is free --> merge with it right neighbor (C) is USED --> cannot merge After: [ free A+B: 48 ][used C: 40][free D: 24] One 48-byte free run instead of two separate 32- and 16-byte runs. Coalescing REDUCES fragmentation, it does not eliminate it: D is still a separate free block from A+B (C sits between them), so a request for 60 contiguous bytes still fails here, even though 48 + 24 = 72 bytes are free overall.

ถ้าฟังดูคล้าย ๆ กับคำอธิบายว่า malloc เองทำงานภายในยังไง — ก็ใช่แล้ว general-purpose free-list allocator เป็น general-purpose จริง ๆ ซึ่งนั่นก็คือเหตุผลว่าทำไมปัญหาความเร็วและ fragmentation ในหัวข้อ 1 ถึงเกิดกับมันด้วยเหมือนกัน แค่ถูกบรรเทาลงบ้างด้วย coalescing engine ก็ใช้ pattern นี้เหมือนกัน แต่จะกันมันออกจาก path ที่ร้อนแรงและทำงานทุกเฟรม สงวนไว้ใช้กับสิ่งที่เปลี่ยนแปลงไม่บ่อยนัก: โหลด asset ทั้งด่าน ไม่ใช่ spawn กระสุนนัดหนึ่ง

8. Double-Buffered Frame Allocator

engine สมัยใหม่ทำงานแบบ pipelined (เป็นสาย pipeline): ในขณะที่ GPU ยังวาดเฟรม N อยู่ (อ่าน vertex buffer, constant, และข้อมูลต่อเฟรมอื่น ๆ ที่คุณส่งให้มัน) CPU มักจะเดินหน้าไปสร้างเฟรม N+1 แล้ว ถ้าคุณ reset arena ตัวเดียวตอนต้นทุกเฟรม คุณจะเขียนทับหน่วยความจำที่ GPU ยังอ่านไม่เสร็จ — race condition ที่แสดงออกมาเป็นภาพกระพริบหรือ geometry เพี้ยนบนจอ ทางแก้คือ: เก็บ arena ไว้สองอัน แล้วสลับว่าอันไหน "live" อยู่ในแต่ละเฟรม

#include <cstdlib>

class FrameAllocator {
public:
    void Init(size_t sizeBytes) {
        bufferA.Init(std::malloc(sizeBytes), sizeBytes);
        bufferB.Init(std::malloc(sizeBytes), sizeBytes);
    }

    void BeginFrame() {
        usingA = !usingA;     // swap which buffer is "live"
        Current().Reset();    // safe: the OTHER buffer is what the GPU
                               // might still be reading from
    }

    void* Alloc(size_t sizeBytes, size_t align = 8) {
        return Current().Alloc(sizeBytes, align);
    }

    int CurrentIndex() const { return usingA ? 0 : 1; } // for debugging only

private:
    LinearAllocator& Current() { return usingA ? bufferA : bufferB; }

    LinearAllocator bufferA;
    LinearAllocator bufferB;
    bool usingA = false;
};

#include <cstdio>

int main() {
    FrameAllocator frameAlloc;
    frameAlloc.Init(1024);

    for (int frame = 0; frame < 4; frame++) {
        frameAlloc.BeginFrame();
        frameAlloc.Alloc(64); // e.g. this frame's transform matrices
        printf("frame %d writes into buffer %d\n", frame, frameAlloc.CurrentIndex());
    }
    return 0;
}

frame 0 writes into buffer 0
frame 1 writes into buffer 1
frame 2 writes into buffer 0
frame 3 writes into buffer 1
Double-buffered frame allocator across 4 frames Frame 0: CPU writes into buffer 0 | GPU: (nothing to read yet) Frame 1: CPU writes into buffer 1 | GPU: reads buffer 0 (frame 0's data) Frame 2: CPU writes into buffer 0 | GPU: reads buffer 1 (frame 1's data) ^ | buffer 0 is safe to Reset() and reuse here -- the GPU finished reading frame 0's copy of it a whole frame earlier, in "Frame 1" Frame 3: CPU writes into buffer 1 | GPU: reads buffer 0 (frame 2's data) With only ONE buffer, "Frame 1: CPU writes" would be overwriting the exact bytes the GPU is still reading from "Frame 0" -- a race that shows up as flickering or garbage geometry on screen.

รูปแบบนี้ขยายต่อได้: บาง engine ใช้ buffer สามอันหรือมากกว่า ("triple buffering") ถ้า CPU สามารถวิ่งนำหน้า GPU ได้มากกว่าหนึ่งเฟรม แนวคิดหลักเหมือนเดิม — อย่า reset buffer ที่ผู้อ่าน (GPU, render thread, network thread หรืออะไรก็ตาม) อาจยังอ่านไม่เสร็จ

9. การติดตาม Allocation แยกตาม Subsystem

เมื่อคุณมี allocator กำหนดเองหลายตัวทำงานพร้อมกัน — physics arena หนึ่งตัว, audio pool หนึ่งตัว, rendering frame allocator หนึ่งตัว, AI scratch buffer หนึ่งตัว — มันเริ่มยากที่จะตอบคำถามง่าย ๆ ว่า: เมื่อการใช้หน่วยความจำรวมค่อย ๆ เพิ่มขึ้นตลอด session สองชั่วโมง ใครกันแน่ที่ใช้มันอยู่? ทางแก้คือ tag ทุก allocation ด้วย subsystem เจ้าของ แล้วเก็บผลรวมเล็ก ๆ ต่อ tag ไว้

#include <cstdio>

enum class MemoryTag {
    Physics,
    Audio,
    Rendering,
    AI,
    Count // not a real tag -- just gives the array a size
};

struct MemoryTracker {
    size_t usedBytes[(int)MemoryTag::Count] = {};

    void Track(MemoryTag tag, size_t bytes) {
        usedBytes[(int)tag] += bytes;
    }

    void Untrack(MemoryTag tag, size_t bytes) {
        usedBytes[(int)tag] -= bytes;
    }

    void PrintReport() const {
        const char* names[] = { "Physics", "Audio", "Rendering", "AI" };
        for (int i = 0; i < (int)MemoryTag::Count; i++) {
            printf("%s: %zu bytes\n", names[i], usedBytes[i]);
        }
    }
};

int main() {
    MemoryTracker tracker;

    tracker.Track(MemoryTag::Physics, 4096);      // a rigid body pool
    tracker.Track(MemoryTag::Audio, 65536);        // a decoded music buffer
    tracker.Track(MemoryTag::Rendering, 1048576);  // this frame's arena
    tracker.Track(MemoryTag::AI, 2048);            // pathfinding scratch

    tracker.PrintReport();
    return 0;
}

Physics: 4096 bytes
Audio: 65536 bytes
Rendering: 1048576 bytes
AI: 2048 bytes
Memory report, taken one moment into a play session Physics [#### ] 4,096 B Audio [###### ] 65,536 B Rendering [####################] 1,048,576 B AI [# ] 2,048 B A per-subsystem report like this is how you catch "wait, why is Audio using 40 MB now?" BEFORE a two-hour session runs out of memory -- without it, all you can see from outside is one growing number for the entire heap, with no way to tell which system is responsible.

ใน engine จริง ขั้นตอนนี้ไม่ใช่ขั้นตอนแยกที่ต้องทำมือ — allocator แต่ละตัว (arena, pool, frame allocator) จะพก debug name และ tag ของตัวเองติดตัวไปด้วย รายงาน high-water mark และการใช้งานปัจจุบันของตัวเอง แล้ว memory profiler (เครื่องมือใน editor หรือในเกมสำหรับดูข้อมูลนี้ ซึ่งคุณจะเห็นตัวอย่างที่เป็นรูปธรรมในหัวข้อ 11) จะอ่านข้อมูลนั้นแบบ live ระหว่างเกมรันอยู่ เวอร์ชันข้างบนคือไอเดียเดียวกันแค่ย่อส่วนลงมา: รู้ว่าใครเป็นเจ้าของทุก byte ไม่ใช่แค่รู้ว่ามี byte เท่าไหร่

10. เทคนิค Debug: Guard Bytes กับ Poison Pattern

allocator ที่เขียนเองให้โอกาสคุณจับบั๊กหน่วยความจำคลาสสิกสองแบบได้แบบถูก ๆ — บั๊กที่บทเรื่อง C แนะนำให้คุณรู้จักผ่าน AddressSanitizer ไปแล้ว แต่ตอนนี้คุณจับมันได้ด้วย byte เพิ่มไม่กี่ byte จาก bookkeeping ของคุณเอง อยู่ภายใน allocator ของคุณเอง โดยไม่ต้องใช้เครื่องมือภายนอกเลย

Guard Bytes: จับ Buffer Overrun

buffer overrun คือโค้ดเขียนเลยขอบเขตหน่วยความจำที่มันได้รับ ทำให้สิ่งที่อยู่ถัดจากมันเสียหาย ทางแก้: วาง pattern คงที่เล็ก ๆ ของ byte เพิ่ม (guard บางทีเรียกว่า canary) ไว้ทั้งก่อนและหลังพื้นที่ใช้งานของทุก allocation ทันที ถ้าโค้ดเขียนเลยขอบเขต allocation ของตัวเองเมื่อไหร่ มันจะทำ guard เสียหายก่อน — และการตรวจ guard ก็บอกคุณได้ทันทีว่าเกิดเรื่องนี้ขึ้น

#include <cstring>

const unsigned char GUARD_PATTERN = 0xFE;
const size_t GUARD_SIZE = 4;

void* GuardedAlloc(LinearAllocator& arena, size_t sizeBytes) {
    unsigned char* mem = static_cast<unsigned char*>(
        arena.Alloc(GUARD_SIZE + sizeBytes + GUARD_SIZE));
    if (!mem) return nullptr;

    std::memset(mem, GUARD_PATTERN, GUARD_SIZE);                          // front guard
    std::memset(mem + GUARD_SIZE + sizeBytes, GUARD_PATTERN, GUARD_SIZE); // back guard

    return mem + GUARD_SIZE; // hand back a pointer to the USABLE region only
}

bool CheckGuards(void* userPtr, size_t sizeBytes) {
    unsigned char* mem = static_cast<unsigned char*>(userPtr) - GUARD_SIZE;
    for (size_t i = 0; i < GUARD_SIZE; i++) {
        if (mem[i] != GUARD_PATTERN || mem[GUARD_SIZE + sizeBytes + i] != GUARD_PATTERN) {
            return false; // something wrote past the edge of its allocation
        }
    }
    return true;
}

#include <cstdio>

int main() {
    unsigned char memory[256];
    LinearAllocator arena;
    arena.Init(memory, sizeof(memory));

    int* healthArray = static_cast<int*>(GuardedAlloc(arena, 3 * sizeof(int)));
    healthArray[0] = 100;
    healthArray[1] = 80;
    healthArray[2] = 50;

    printf("guards OK before overrun? %s\n", CheckGuards(healthArray, 3 * sizeof(int)) ? "yes" : "no");

    healthArray[3] = 999; // BUG: one element past the end -- into the back guard

    printf("guards OK after overrun?  %s\n", CheckGuards(healthArray, 3 * sizeof(int)) ? "yes" : "no");
    return 0;
}

guards OK before overrun? yes
guards OK after overrun?  no

healthArray มีแค่ 3 int ดังนั้น healthArray[3] จึงเขียน 4 byte เข้าไปตรงจุดเริ่มต้นของ back guard พอดี ทำให้ pattern 0xFE 0xFE 0xFE 0xFE บางส่วนถูกเขียนทับด้วย byte จาก 999 CheckGuards สังเกตเห็นความไม่ตรงกันและคืนค่า false — จับ overrun ที่ถ้าไม่มี guard byte จะทำให้สิ่งที่ allocator แจกให้ไปตัวถัดไปเสียหายแบบเงียบ ๆ

Poison Pattern: จับ Use-After-Free

บั๊กคลาสสิกอีกแบบคือ use-after-free: อ่านหรือเขียนผ่าน pointer หลังจากหน่วยความจำที่มันชี้ไปถูก free ไปแล้ว (หรือสำหรับ arena คือหลังจาก Reset() ยกหน่วยความจำนั้นให้คนอื่นไปแล้ว) ทางแก้: ทันทีที่หน่วยความจำถูก free ให้เขียนทับทุก byte ของมันด้วย poison pattern ที่ชัดเจนและจำได้ทันที — นิยมใช้ 0xDD

void PoisonFree(unsigned char* mem, size_t sizeBytes) {
    std::memset(mem, 0xDD, sizeBytes); // 0xDD 0xDD 0xDD ... everywhere
}

0xDD ถูกเลือกมาโดยเฉพาะเพราะมันไม่เกิดขึ้นเองตามธรรมชาติในข้อมูลเกมจริง: ในฐานะ int 32-bit 0xDDDDDDDD คือ -573785174, ในฐานะ float มันคือขยะที่ไม่มีความหมาย และในฐานะ pointer มันก็ชัดเจนว่าไม่ใช่ที่อยู่ที่ใช้ได้ ทันทีที่ debugger แสดง 0xDDDDDDDD อยู่ในตัวแปรที่ควรจะเป็น เช่น ค่า health คุณจะรู้ทันที: นี่คือหน่วยความจำที่ free ไปแล้ว และมีบางอย่างอ่านมันหลังจากที่มันควรจะหยุดอ่านไปแล้ว

Guard bytes around one allocation, and poison after Free() While ALIVE: [FE FE FE FE][ ... your 12 bytes of int[3] ... ][FE FE FE FE] front guard usable memory back guard If code writes healthArray[3] (one element past the end): [FE FE FE FE][ ... your 12 bytes ... ][E7 03 00 00] front guard usable memory ^ guard OVERWRITTEN CheckGuards() now returns false After Free() / PoisonFree(): [DD DD DD DD DD DD DD DD DD DD DD DD DD DD DD DD] every byte of the freed region -- unmistakably "dead" if read later
Tip เก็บโค้ด guard-byte กับ poison-pattern ไว้หลัง compile-time switch (#ifdef DEBUG_MEMORY) เพื่อให้มันไม่เสียค่าใช้จ่ายอะไรเลยใน final build ที่ optimize แล้ว ประเด็นทั้งหมดของเทคนิคพวกนี้คือมันเป็นตาข่ายนิรภัยช่วงพัฒนา — byte เพิ่มและการตรวจเพิ่มที่คุณยินดีจ่ายตอนกำลังทำเกม แต่ build ที่ ship จริงไม่มีเหตุผลต้องแบกมันไปด้วย

11. เชื่อมโยงกับ Unity: Allocator.Temp, TempJob, และ Persistent

คุณแทบจะไม่ต้องเขียน class อย่าง LinearAllocator เองใน gameplay code ปกติของ Unity เลย — managed heap กับ garbage collector จากบทเรื่อง C# จัดการ object ทั่วไปให้คุณอยู่แล้ว และนั่นก็คือเหตุผลว่าทำไม C# ถึงรู้สึกง่ายกว่า C++ ในการใช้งานประจำวัน แต่มีที่หนึ่งที่สำคัญมากใน Unity สมัยใหม่ที่ไอเดียทั้งบทนี้โผล่มาตรง ๆ เรียกชื่อตรง ๆ เลย: Unity.Collections (native container อย่าง NativeArray) กับ Job System constructor ของ native container ทุกตัวจะให้คุณเลือก Allocator และตัวเลือกทั่วไปสามแบบก็ตรงกับ allocator ที่คุณเพิ่งสร้างมาเป๊ะ ๆ

using Unity.Collections;
using UnityEngine;

public class NativeArrayDemo : MonoBehaviour
{
    void Update()
    {
        // Allocator.Temp: behaves like a StackAllocator marker taken and
        // freed right here, in this one call -- it never crosses a frame.
        NativeArray<float> scratch = new NativeArray<float>(64, Allocator.Temp);
        for (int i = 0; i < scratch.Length; i++)
        {
            scratch[i] = i * 2f;
        }
        Debug.Log("scratch[10] = " + scratch[10]);
        scratch.Dispose(); // must happen before this frame ends
    }
}

scratch[10] = 20

using Unity.Collections;
using Unity.Jobs;
using UnityEngine;

public struct DoubleJob : IJob
{
    public NativeArray<float> data;

    public void Execute()
    {
        for (int i = 0; i < data.Length; i++)
        {
            data[i] *= 2f;
        }
    }
}

public class TempJobDemo : MonoBehaviour
{
    void Start()
    {
        // Allocator.TempJob: safe to hand to a job that might not finish
        // this exact frame -- Allocator.Temp is NOT allowed to cross into
        // a job at all.
        NativeArray<float> data = new NativeArray<float>(4, Allocator.TempJob);
        data[0] = 1f; data[1] = 2f; data[2] = 3f; data[3] = 4f;

        DoubleJob job = new DoubleJob { data = data };
        JobHandle handle = job.Schedule();
        handle.Complete();

        Debug.Log("data[2] = " + data[2]);
        data.Dispose(); // we allocated it, so we must dispose it
    }
}

data[2] = 6
What you built in C++ Unity's equivalent StackAllocator (section 5) --> Allocator.Temp bump-pointer, LIFO, one frame one call/frame, per-thread, MUST Dispose() before the frame ends, cannot cross into a scheduled Job Pool / short-lived arena --> Allocator.TempJob (sections 6 and 8) survives a few frames, safe to hand to a scheduled Job Free-list allocator (section 7) --> Allocator.Persistent general-purpose, long-lived general-purpose, long-lived, slowest of the three, YOU Dispose() it when truly done
Common mistake allocate NativeArray ด้วย Allocator.Temp แล้วส่งมันไปให้ Job.Schedule() ใน editor ระบบ safety ของ Unity จะ throw exception ทันที — Temp ไม่มีวันได้รับอนุญาตให้ข้ามผ่าน job boundary เลย ด้วยเหตุผลเดียวกันเป๊ะ ๆ กับที่คุณจะไม่มีวันถือ pointer เข้าไปในพื้นที่ StackAllocator หลังจากดึง marker กลับผ่านมันไปแล้ว: หน่วยความจำสามารถถูกเอาคืนได้ทันทีที่ฟังก์ชันปัจจุบัน return และ job ที่ schedule ไว้อาจยังไม่เริ่มรันจนกว่าจะถึงทีหลัง

ทั้งหมดนี้ไม่ได้แปลว่าคุณควรจะไปเขียน arena มือเองใส่ไว้ใน MonoBehaviour ธรรมดา managed heap กับ GC คือเครื่องมือที่ถูกต้องสำหรับ gameplay object ทั่วไป และการไปสู้กับมันด้วย allocator ของคุณเองข้างใต้จะไม่ช่วยอะไรเลย ไอเดียพวกนี้จะสำคัญขึ้นมาตอนที่คุณเรียกโค้ด Unity.Collections หรือ Job System ตรง ๆ — หรือถ้าสุดท้ายคุณไปเขียน engine code แทนที่จะเป็น game code ด้วย C++

12. Glossary

13. Exercises

Exercise 1 heap ขนาด 300 byte มี block เรียงในหน่วยความจำแบบนี้: used 50, free 40, used 70, free 90, used 20, free 30 คำนวณ: (a) จำนวน byte ว่างทั้งหมด, (b) ขนาดของช่วงว่างต่อเนื่องเดี่ยวที่ใหญ่ที่สุด, และ (c) request 85 byte ต่อเนื่องจะสำเร็จหรือไม่ และเพราะอะไร
Show answer

(a) byte ว่างทั้งหมด: 40 + 90 + 30 = 160 byte

(b) ช่วงว่างต่อเนื่องเดี่ยวที่ใหญ่ที่สุด: 90 byte (ช่องว่างระหว่าง block "used 70" ตัวที่สอง กับ block "used 20")

(c) request 85 byte ต่อเนื่องสำเร็จ: 85 น้อยกว่าหรือเท่ากับช่องว่างเดี่ยวที่ใหญ่ที่สุด (90 byte) ดังนั้น allocator จึงตัด 85 byte นั้นออกจากช่องว่างนั้นได้ เหลือ 5 byte ของช่องว่างนั้นว่างต่อไปหลังจากนั้น มันจะล้มเหลวถ้า request เป็น เช่น 95 byte แม้ว่าจะมี 160 byte ว่างรวมทั้งหมดก็ตาม — เพราะไม่มีช่องว่างเดี่ยวไหนใหญ่ขนาดนั้น

Exercise 2 LinearAllocator เริ่มที่ offset 0 (สมมติว่า base pointer เองคือที่อยู่ 0 align กับทุกอย่างอยู่แล้ว เพื่อให้ตัวเลขง่าย) ไล่การเรียกสามครั้งตามลำดับ: Alloc(13, align=4), Alloc(6, align=8), Alloc(20, align=4) สำหรับแต่ละครั้ง ให้บอก offset ที่มันคืนกลับมา และค่าใหม่ของ offset ภายในหลังจากนั้น จำนวน byte ที่ใช้ไปทั้งหมดตอนจบ รวม padding ด้วย คือเท่าไหร่?
Show answer

ครั้งที่ 1: Alloc(13, align=4) — offset ปัจจุบันคือ 0 ซึ่งเป็นจำนวนเท่าของ 4 อยู่แล้ว padding จึงเป็น 0 คืน offset 0 offset ใหม่: 0 + 13 = 13

ครั้งที่ 2: Alloc(6, align=8) — offset ปัจจุบันคือ 13; จำนวนเท่าของ 8 ถัดไปที่เท่ากับหรือมากกว่า 13 คือ 16 padding จึงเป็น 16 - 13 = 3 คืน offset 16 offset ใหม่: 16 + 6 = 22

ครั้งที่ 3: Alloc(20, align=4) — offset ปัจจุบันคือ 22; จำนวนเท่าของ 4 ถัดไปที่เท่ากับหรือมากกว่า 22 คือ 24 padding จึงเป็น 24 - 22 = 2 คืน offset 24 offset ใหม่: 24 + 20 = 44

byte ที่ใช้ไปทั้งหมดตอนจบ: 44 (13 + padding 3 + 6 + padding 2 + 20 = 44) จาก 44 byte นั้น 5 byte เป็น padding ล้วน ๆ ที่เสียไปกับ alignment (3 + 2)

Exercise 3 ใช้ PoolAllocator จากหัวข้อ 6 (4 slot เชื่อมกัน slot0 -> slot1 -> slot2 -> slot3 โดย Init()) ไล่ลำดับนี้: 
void* a = bullets.Alloc();
void* b = bullets.Alloc();

bullets.Free(a);
bullets.Free(a);   // BUG: freeing the same pointer twice

void* c = bullets.Alloc();
void* d = bullets.Alloc();
void* e = bullets.Alloc();
c, d, และ e สุดท้ายชี้ไปที่ที่อยู่ไหน และเพราะอะไร? มีอะไรผิดพลาดกับ free list เจาะจงเนื่องจากการเรียก Free(a) สองครั้ง และทำไมมันถึงอันตราย?
Show answer

ไล่ free list ทีละขั้น หลัง Init(): freeList = slot0 -> slot1 -> slot2 -> slot3 -> null

a = Alloc()          // pops slot0.  freeList = slot1 -> slot2 -> slot3 -> null.  a = slot0
b = Alloc()          // pops slot1.  freeList = slot2 -> slot3 -> null.          b = slot1

Free(a)              // pushes slot0 onto the front:
                      // slot0->next = (old freeList) = slot2
                      // freeList = slot0 -> slot2 -> slot3 -> null

Free(a)  // BUG, again // pushes slot0 onto the front AGAIN:
                      // slot0->next = (old freeList) = slot0   <-- itself!
                      // freeList = slot0 -> slot0 -> slot0 -> ...  (a CYCLE)
                      // slot2 and slot3 are now UNREACHABLE -- lost

Free(a) ครั้งที่สองเขียนทับ pointer next ของ slot0 เป็นครั้งที่สอง และครั้งนี้ freeList เป็น slot0 อยู่แล้ว — ดังนั้น slot0->next จึงถูกตั้งให้เป็น slot0 เอง free list ตอนนี้กลายเป็นวงวน node เดียวที่ชี้กลับไปหาตัวเองตลอดกาล แย่ไปกว่านั้น link เดิม (slot0->next = slot2) หายไปแล้ว ดังนั้น slot2 กับ slot3 — ซึ่งว่างและไม่ได้ใช้อย่างถูกต้อง — จะเข้าถึงไม่ได้อีกเลยตลอดไป: memory leak ของ slot สองอันเต็ม ๆ

c = Alloc() pop หัว คือ slot0 ออกมา แล้วตั้ง freeList = slot0->next ซึ่งก็คือ slot0 อีกครั้ง — ดังนั้น freeList จึงไม่เปลี่ยนแปลงจริง ๆ c == slot0 เรื่องเดียวกันเกิดกับ d = Alloc() และ e = Alloc(): ทุกการเรียก pop slot0 ออกมาแล้ว list ก็วนกลับไปที่ slot0 ทันที ดังนั้น c, d, และ e จึงเป็นที่อยู่เดียวกันเป๊ะทั้งหมด

นี่คือเหตุผลที่ double-free อันตรายมากโดยเฉพาะกับ free list แบบ singly-linked ที่ intrusive: โค้ดของเกมคิดว่าเพิ่งได้ Bullet object อิสระสามตัว แต่การเขียนลง c->x กลับเขียนทับหน่วยความจำเดียวกันกับที่ d และ e ก็ใช้อยู่แบบเงียบ ๆ (กระสุนสามตัว alias slot เดียวกัน) ในขณะที่ slot ดี ๆ สองอันถูกทิ้งไว้แบบกำพร้าตลอดไป และไม่มีวันถูก allocate ได้อีกเลยตลอดที่เหลือของโปรแกรม

นั่นคือชุดเครื่องมือทั้งหมด: ทำไมการเรียก malloc/new ทุกที่ถึงช้าและคาดเดาไม่ได้เกินไปสำหรับเกมแบบ real-time และ fragmentation กัดกิน heap อย่างเงียบ ๆ ยังไงแม้ว่าจะมี byte "ว่าง" อยู่เยอะก็ตาม จากนั้นก็มา allocator สี่แบบที่เป็นรูปธรรม แต่ละแบบถูกออกแบบรอบ lifetime แบบหนึ่ง — arena ที่ free ทุกอย่างพร้อมกันสำหรับข้อมูลต่อเฟรม, stack allocator ที่เพิ่มการดึงกลับแบบ LIFO ด้วย marker, pool allocator ที่ให้ alloc/free แบบ O(1) สำหรับ object ขนาดเท่ากันอย่างกระสุนกับ particle, และ general-purpose free-list allocator สำหรับทุกอย่างที่เหลือ ใช้แต่น้อย alignment, double buffering, การติดตามแยกตาม subsystem, และ guard bytes/poison pattern เติมเต็มชุดเครื่องมือที่ engine จริง ๆ ใช้ ship เกม และใน Unity คุณจะเจอไอเดียพวกนี้อีกครั้งพอดีเป๊ะตอนที่คุณแตะ NativeArray กับ Job System — Allocator.Temp, TempJob, และ Persistent ไม่ใช่แนวคิดใหม่เลย แค่เป็นชื่อใหม่ของ allocator ที่คุณเพิ่งสร้างด้วยมือตัวเองนั่นเอง

← กลับไปหน้ารวมบท