3.2 การจัดการหน่วยความจำ

บทที่ 3.1 อธิบายไปแล้วว่าทำไม CPU ถึงแคร์เรื่องการจัดวางข้อมูลใน memory — cache line, locality และทำไมการวน loop บน array ที่อยู่ติดกัน (contiguous) ถึงเร็วกว่าการไล่ pointer ไปมาทั่ว heap บทนี้ต่อยอดจากตรงนั้นโดยตรง คุณจะได้เห็นว่าทำไม malloc กับ new ถึงไม่ใช่ของฟรี ทำไม compiler ถึงแอบเปลือง memory ด้วยสิ่งที่เรียกว่า padding ทำไมเกม engine จริง ๆ ถึงจัดข้อมูลใหม่เป็นรูปแบบที่เรียกว่า Struct-of-Arrays และวิธีเขียน custom allocator เล็ก ๆ ของตัวเอง — เทคนิคเดียวกับที่ engine อย่าง Unreal, native layer ของ Unity และสตูดิโอ AAA ส่วนใหญ่ใช้ เพื่อไม่ให้เกมสะดุด (stall) รอ memory กลางเฟรม

ทุกหัวข้อจะมีรูปแบบเดิมเหมือนบทก่อน ๆ คือ โค้ด C++ เล็ก ๆ ที่รันได้จริง ตามด้วย output จริง แล้วอธิบายเป็นภาษาง่าย ๆ ว่าเกิดอะไรขึ้น ลองพิมพ์ตัวอย่างแล้วรันดูเองด้วย

1. ทบทวน: Stack กับ Heap และทำไม new กับ malloc ถึงไม่ใช่ของฟรี

คุณเคยเจอ stack กับ heap มาแล้วในบท C ทบทวนสั้น ๆ เพราะทุกอย่างในบทนี้ขึ้นอยู่กับความเข้าใจตรงนี้

• stack เก็บตัวแปร local เป็นแบบ LIFO (last in, first out — เข้าหลังออกก่อน) ฟังก์ชันจะ push ตัวแปรของมันตอนเข้าฟังก์ชัน แล้ว pop ออกอัตโนมัติตอน return การจอง memory บน stack คือแค่ขยับ pointer ตัวเดียว (stack pointer) ขึ้นหรือลง ซึ่งใช้คำสั่ง CPU แค่ไม่กี่คำสั่ง เรียกได้ว่าแทบไม่มีต้นทุนเลย
• heap เก็บ memory ที่คุณขอเองด้วย new หรือ malloc แล้วต้องคืนเองด้วย delete หรือ free heap ไม่ใช่ pointer ตัวเดียวง่าย ๆ แต่ถูกจัดการโดย general-purpose allocator (ส่วนหนึ่งของ C++ runtime) ที่คอยเก็บว่า block ไหนว่าง block ไหนถูกใช้อยู่ ปกติใช้โครงสร้างข้อมูลแบบ free list (ลิสต์ของ block ที่ว่าง)

#include <cstdio>

struct Particle { float x, y; };

void makeOnStack() {
    Particle p{1.0f, 2.0f};                       // lives on the stack
    printf("stack particle at %p\n", (void*)&p);
}                                                   // p is destroyed here, instantly, automatically

void makeOnHeap() {
    Particle* p = new Particle{1.0f, 2.0f};        // lives on the heap
    printf("heap particle at %p\n", (void*)p);
    delete p;                                       // must free by hand, or it leaks
}

int main() {
    makeOnStack();
    makeOnHeap();
}

Output (address จริงจะต่างกันไปในแต่ละเครื่อง — เป็นเรื่องปกติ):

stack particle at 0x7ffde3a1c85c
heap particle at 0x55f2a1b0aeb0

ทั้งสอง particle ถูกสร้างและใช้งานเหมือนกันทุกอย่างจากมุมมองของคนเรียก แต่สิ่งที่เกิดขึ้นข้างในต่างกันมาก makeOnStack แค่ขยับ stack pointer ลงไป sizeof(Particle) ไบต์ตอนเข้าฟังก์ชัน แล้วขยับกลับขึ้นตอน return — ไม่มีการจดบันทึกอะไรเลย ส่วน makeOnHeap ต้องขอให้ allocator ค้นหา (search) ใน free list หา block ที่ใหญ่พอ ทำเครื่องหมาย ว่าถูกใช้แล้ว และตอน delete ก็ต้องทำเครื่องหมายว่างอีกครั้ง บางทีก็รวม block ที่ว่างติดกันเข้าด้วยกัน (merge) ถ้าโปรแกรมมีหลาย thread การค้นหานี้มักจะถูกป้องกันด้วย lock เพื่อไม่ให้สอง thread มาทำ free list พังพร้อมกัน — เป็นต้นทุนอีกอย่างที่ stack ไม่ต้องจ่ายเลย

ตลอดอายุการทำงานของโปรแกรมที่รันนาน ๆ (เกมอาจรันหลายชั่วโมง) การจองและคืน memory ขนาดต่าง ๆ ซ้ำไปซ้ำมาจะทิ้งช่องว่างของ memory ที่ไม่ได้ใช้กระจายอยู่ระหว่าง block ที่ถูกใช้งาน เรียกว่า fragmentation (การแตกกระจาย)

new/malloc ไม่ได้แย่ — คุณใช้มันตลอดเวลา และสำหรับโค้ดส่วนใหญ่มันคือทางเลือกที่ถูกต้องและง่ายที่สุด ปัญหาคือการเรียกมัน ทุกเฟรม ใน hot loop ("hot path" คือโค้ดที่รันบ่อยมาก เช่น รันครั้งเดียวหรือหลายครั้งต่อเฟรม) ตรงนั้นแหละที่การค้นหา, lock ที่อาจเกิดขึ้น, และ fragmentation ที่ค่อย ๆ สะสม เริ่มกินเวลาเป็นมิลลิวินาทีจริง ๆ หัวข้อถัดไปจะแสดงว่า engine ทำอะไรแทน

2. Alignment: ทำไม CPU ถึงแคร์ว่าข้อมูลเริ่มต้นที่ไหน

CPU จะไม่อ่าน memory ทีละไบต์ถ้าหลีกเลี่ยงได้ — มันอ่านเป็นก้อน (chunk) ขนาดที่พอดีกับแต่ละ type และต้องการให้ก้อนนั้นเริ่มที่ address ที่หารด้วยขนาดของ type ลงตัว ตัวเลขที่ต้องหารลงตัวนี้เรียกว่า alignment ของ type นั้น เช่น int 4 ไบต์ ต้องการเริ่มที่ address ที่หารด้วย 4 ลงตัว ส่วน double 8 ไบต์ ต้องการเริ่มที่ address ที่หารด้วย 8 ลงตัว การอ่านค่าที่เริ่มที่ address "ผิด" เรียกว่า misaligned access — บน x86 ปกติแค่เสียเวลาเพิ่มไม่กี่ cycle แต่บน CPU บางตัว (และบางคำสั่ง SIMD ที่คุณเจอในบท 3.1) อาจทำให้โปรแกรม crash ไปเลย

C++ บอก alignment ที่ type ต้องการได้ด้วย alignof:

#include <cstdio>

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

Output (ค่าทั่วไปบนเครื่อง 64-bit desktop หรือ console):

alignof(char)   = 1
alignof(int)    = 4
alignof(double) = 8

char เริ่มที่ address ไหนก็ได้ (alignment 1) int ต้องเริ่มที่ address ที่หารด้วย 4 ลงตัว double ต้องเริ่มที่ address ที่หารด้วย 8 ลงตัว compiler รับประกันเรื่องนี้ให้อัตโนมัติกับทุกตัวแปรและทุก member ของ struct — โดยการแทรกไบต์ที่ไม่ได้ใช้เข้าไปตรงที่จำเป็น นั่นคือ padding ซึ่งเป็นหัวข้อหลักของหัวข้อถัดไป

3. Padding: ทำไม sizeof ถึงใหญ่กว่าที่คุณคิด

เพราะทุก member ของ struct ต้องเริ่มที่ address ที่ตรงกับ alignment ของตัวมันเอง บางทีตัว compiler ก็ต้องเว้นช่องว่างระหว่าง member ช่องว่างพวกนี้เปลืองเปล่า ๆ — ไม่มีข้อมูลอะไรอยู่ในนั้น มันอยู่ตรงนั้นแค่เพื่อให้ member ถัดไปตกที่ address ที่ถูกต้องเท่านั้น ลองดู struct นี้:

#include <cstdio>

struct Bad {
    char   a;   // 1 byte
    double b;   // 8 bytes
    char   c;   // 1 byte
};

int main() {
    printf("sizeof(Bad) = %zu\n", sizeof(Bad));
}

Output:

sizeof(Bad) = 24

24 ไบต์ ทั้งที่ a, b, c รวมกันมีข้อมูลจริงแค่ 1 + 8 + 1 = 10 ไบต์ อีก 14 ไบต์หายไปไหน มาดูกัน:

a อยู่ที่ offset 0 b เป็น double ต้องเริ่มที่ address ที่หารด้วย 8 ลงตัว compiler เลยข้าม offset 1-7 ไป (เสีย 7 ไบต์เปล่า ๆ) แล้ววาง b ที่ offset 8 c ตามมาทันทีที่ offset 16 จากนั้นมีอีกกฎหนึ่งเข้ามา: ขนาดรวมของ struct ต้องหารด้วย alignment ของ struct เองลงตัว (ซึ่งคือ alignment ที่ใหญ่ที่สุดในบรรดา member ทั้งหมด — ในที่นี้คือ 8 จาก double) กฎนี้จำเป็นเพราะถ้าคุณสร้าง array ของ Bad ทุก element ใน array ต้อง align ถูกต้องด้วยเช่นกัน 17 หารด้วย 8 ไม่ลงตัว compiler เลย pad ไปจนถึง 24

4. จัดลำดับ Field ใหม่เพื่อลดขนาด Struct

เอา field สามตัวเดิม แค่เปลี่ยนลำดับ — field ที่ใหญ่ที่สุดขึ้นก่อน:

#include <cstdio>

struct Good {
    double b;   // 8 bytes
    char   a;   // 1 byte
    char   c;   // 1 byte
};

static_assert(sizeof(Good) == 16, "Good grew - check the field order again");

int main() {
    printf("sizeof(Good) = %zu\n", sizeof(Good));
}

Output:

sizeof(Good) = 16

b อยู่ที่ offset 0-7 (align อยู่แล้ว ไม่ต้อง pad ก่อนหน้า) a ตามมาที่ offset 8, c ที่ offset 9 ข้อมูลจริงรวมตอนนี้คือ 10 ไบต์ จบที่ offset 10 ปัดขึ้นไปที่ multiple ของ 8 ถัดไป (alignment ของ struct) ก็ได้ 16 field สามตัวเดิม ข้อมูลเดิม แต่ Good มีขนาด 16 ไบต์ แทนที่จะเป็น 24 ไบต์แบบ Bad — เล็กลงหนึ่งในสาม แค่จากการจัดลำดับใหม่ คูณการประหยัดนี้ด้วย game object เป็นล้าน ๆ ตัวที่อยู่ใน memory แล้วมันรวมกันเป็นไบต์จริง ๆ ที่ประหยัดได้ และ — สำคัญไม่แพ้กัน — cache line ที่ต้อง load น้อยลงเวลาวน loop ผ่าน array ของมัน (แนวคิด cache line จากบท 3.1)

กฎง่าย ๆ ที่จำได้: เรียง field จาก alignment มากไปน้อย (ประมาณว่า type ใหญ่ไปหา type เล็ก) แล้วจับ field ขนาดเท่ากันไว้ด้วยกัน บรรทัด static_assert ด้านบนก็เป็นนิสัยที่ดีเช่นกัน — มัน compile ไม่ผ่านถ้ามีใครมาเพิ่ม field ทีหลังแล้วทำให้ struct ใหญ่ขึ้นโดยไม่ตั้งใจ คุณจะรู้ทันทีแทนที่จะไปเจอใน profiler อีกหกเดือนถัดมา

5. Array-of-Structs กับ Struct-of-Arrays: ระบบ Particle

Padding พูดถึงการจัดวางของ object เดียว หัวข้อนี้พูดถึงการจัดวางของ object จำนวนมาก — particle เป็นพัน ๆ ตัวสำหรับการระเบิดหรือเอฟเฟกต์เวทมนตร์ ที่ต้อง update field เดียวกัน (position, velocity, เวลาที่เหลือ) ทุกเฟรม มีวิธีเก็บข้อมูลแบบธรรมชาติสองแบบ

Array-of-Structs (AoS): หนึ่ง struct ต่อหนึ่ง particle

นี่คือรูปแบบที่มือใหม่ทุกคนนึกถึงเป็นอันดับแรก — มันตรงกับวิธีที่คุณจะอธิบาย "particle หนึ่งตัว" ว่าเป็น object เดียว:

#include <vector>

struct Particle {
    float x, y, z;      // position
    float vx, vy, vz;   // velocity
    float life;         // seconds remaining
};

void updatePositions(std::vector<Particle>& particles, float dt) {
    for (Particle& p : particles) {
        p.x += p.vx * dt;
        p.y += p.vy * dt;
        p.z += p.vz * dt;
    }
}

โค้ดนี้ไม่มี output ที่พิมพ์ออกมาเอง — ให้ดูเป็น worked trace แทน Particle มี float เจ็ดตัว ตัวละ 4 ไบต์ alignment เท่ากันหมด (4 ไบต์) เลยไม่มี padding: sizeof(Particle) = 28 ไบต์พอดี std::vector<Particle> เก็บ particle ขนาด 28 ไบต์เรียงติดกันหมด — array เดียว แต่แต่ละ element คือ field ทั้งเจ็ดตัวที่ถูกแปะติดกันเป็นก้อนเดียว

Struct-of-Arrays (SoA): หนึ่ง array ต่อหนึ่ง field

กลับด้านมัน: แทนที่จะมี array เดียวของ particle-struct ให้เก็บ array แยกกันเจ็ดตัว หนึ่งตัวต่อหนึ่ง field ทุกตัวยาวเท่ากัน:

#include <vector>

struct ParticleSystem {
    std::vector<float> x, y, z;      // position, one array per axis
    std::vector<float> vx, vy, vz;   // velocity, one array per axis
    std::vector<float> life;         // seconds remaining
};

void updatePositions(ParticleSystem& ps, float dt) {
    size_t count = ps.x.size();
    for (size_t i = 0; i < count; ++i) {
        ps.x[i] += ps.vx[i] * dt;
        ps.y[i] += ps.vy[i] * dt;
        ps.z[i] += ps.vz[i] * dt;
    }
}

ข้อมูลของ particle ตัวที่ 5 ไม่ได้ถูกแปะติดกันอยู่ที่ไหนใน memory อีกต่อไป — x ของมันอยู่ใน array x ที่ index 5, vx ของมันอยู่ใน array vx ที่ index 5 เป็นแบบนี้ไปเรื่อย ๆ ทั้งสองแบบเก็บข้อมูลเหมือนกันทุกอย่างและได้ผลลัพธ์เดียวกันเป๊ะ ความต่างอยู่ที่การจัดวางใน memory ล้วน ๆ:

6. ทำไม SoA ถึงชนะ: Cache Line กับ SIMD

ย้อนกลับไปบท 3.1: CPU ไม่เคยดึงค่าเดี่ยว ๆ จาก RAM แค่ตัวเดียว — มันดึงมาทั้ง cache line เสมอ (ปกติ 64 ไบต์บน CPU ของ desktop กับ console) ว่าจะได้ประโยชน์จาก cache line แต่ละอันมากแค่ไหนขึ้นอยู่กับการจัดวางข้อมูลล้วน ๆ

#include <cstdio>

struct Particle { float x, y, z, vx, vy, vz, life; };

int main() {
    printf("sizeof(Particle) = %zu\n", sizeof(Particle));
}

Output:

sizeof(Particle) = 28

ลองไล่ updatePositions จากหัวข้อก่อนหน้าสำหรับทั้งสองแบบ สมมติ cache line ขนาด 64 ไบต์ และ particle 1,000 ตัว:

• AoS: การ update x ของ particle ตัวเดียวจะดึง footprint ทั้ง 28 ไบต์ของ particle นั้นเข้ามา ไม่ว่า loop นี้จะต้องการ vy, vz, หรือ life รอบนี้หรือไม่ก็ตาม — ไบต์พวกนั้นติดมาด้วยไม่ว่าจะใช้หรือไม่ สำหรับ particle 1,000 ตัว loop นี้จะแตะประมาณ 1,000 * 28 = 28,000 ไบต์ ราว 438 cache line
• SoA: array x คือ float 1,000 ตัวที่อยู่ติดกัน ไม่มีอะไรปนเลย loop เดียวกันแตะประมาณ 1,000 * 4 = 4,000 ไบต์ ราว 63 cache line — น้อยกว่า AoS ประมาณ 7 เท่า ตัวเลข 7 เท่านี้ไม่ใช่เรื่องบังเอิญ: Particle มี float 7 field ขนาดเท่ากัน แล้ว loop นี้ต้องการแค่ 1 ใน 7 ตัวนั้น

ช่องว่างนี้จะยิ่งกว้างขึ้นกับ particle struct ในโลกจริงที่มักมี color, texture index, animation frame และอื่น ๆ อีก — field ที่ loop นี้ไม่แตะต้องเลยแต่ AoS บังคับให้ลากติดมาด้วย

เรื่องนี้ยังโยงกลับไปที่ SIMD โดยตรง (single instruction, multiple data — คำสั่ง CPU คำสั่งเดียวที่ประมวลผลหลายค่าพร้อมกัน จากบท 3.1) คำสั่ง SIMD ต้องการ load float ที่อยู่ติดกัน 8 ตัวเข้า register เดียวแล้วบวกพร้อมกันในขั้นตอนเดียว array x แบบ SoA มีรูปร่างพอดีเป๊ะแบบนั้น — float 8 ตัวติดกัน load ตรง ๆ ได้เลย ส่วน layout แบบ AoS สลับ x ปนกับอีกหก field ทำให้การเอาค่า x 8 ตัวเข้า register เดียวต้องใช้คำสั่งพิเศษ (และช้ากว่า บางทีก็ไม่มีให้ใช้) ที่เรียกว่า "gather" แทนที่จะ load แบบติดกันตรง ๆ SoA ไม่ได้แค่เป็นมิตรกับ cache — มันคือ layout ที่โค้ด SIMD อยากเห็น

7. ทำไม Engine ไม่เรียก new/delete ใน Hot Path

เกมที่รันที่ 60 เฟรมต่อวินาที มีเวลาแค่ประมาณ 16.6 มิลลิวินาที ในการสร้างแต่ละเฟรม — physics, AI, animation, rendering ทุกอย่าง หัวข้อ 1 บอกไปแล้วว่า new/malloc แบบ general-purpose ทำอะไรอยู่ข้างใน: ค้นหาใน free list, อาจต้อง lock, บางทีก็ต้องขอ memory เพิ่มจากระบบปฏิบัติการ (system call ซึ่งช้ากว่าคำสั่งปกติมาก) เรียกครั้งเดียวไม่ได้แย่อะไร แต่จะกลายเป็นปัญหาเมื่อมันเกิดขึ้นเป็นร้อยเป็นพันครั้งต่อเฟรม

#include <vector>

struct Bullet { float x, y, vx, vy; };

void spawnBullet(std::vector<Bullet*>& bullets) {
    Bullet* b = new Bullet{};    // a heap allocation on the hot path
    bullets.push_back(b);
}

นี่คือ worked trace ไม่ใช่ output ที่พิมพ์ออกมา: ลองจินตนาการปืนกลที่ยิง 20 นัดต่อวินาที และแต่ละนัดก็ถูก delete อีกครั้งตอนหมดอายุ นั่นคือ 20 การจอง heap และ 20 การคืนต่อวินาทีจากอาวุธเดียว คูณด้วยศัตรูทุกตัวและผู้เล่นทุกคน ตลอดช่วงเวลาเล่นที่อาจยาวหลายชั่วโมง แต่ละครั้งอาจใช้เวลาแค่เสี้ยว microsecond — แต่มันสะสม มันอาจ spike แบบสุ่ม (การค้นหา worst-case ผ่าน free list ที่รกช้ากว่า average case มาก) และค่อย ๆ ทำให้ heap แตกกระจายมากขึ้นเรื่อย ๆ ยิ่งเกมรันนานเท่าไหร่ เฟรมที่ช้าไปเฟรมเดียวคือ อาการกระตุก (stutter) ที่ผู้เล่นสังเกตเห็นได้ทันที game engine แคร์กรณี เลวร้ายที่สุด ไม่ใช่แค่ค่าเฉลี่ย

ทางแก้ไม่ใช่ "ห้ามใช้ heap เลย" — แต่คือ "เลิกใช้ allocator แบบ general-purpose กับงานที่คุณรู้ pattern การจองล่วงหน้าอยู่แล้ว" ถ้าคุณรู้ว่ากลุ่มการจองชุดหนึ่งจะตายพร้อมกัน หรือคุณจองขนาดเดียวกันซ้ำ ๆ ตลอด คุณเขียน allocator ที่ทำมาสำหรับ pattern นั้นโดยเฉพาะได้ และมันจะเรียบง่ายกว่ามาก — เร็วกว่าและคาดเดาได้มากกว่า allocator แบบ general-purpose ส่วนที่เหลือของบทนี้จะสร้าง allocator สองแบบที่ engine ใช้กันบ่อยที่สุด

8. สร้าง Bump (Arena) Allocator

custom allocator ที่ง่ายที่สุดคือ arena allocator หรือเรียกอีกชื่อว่า bump allocator (หรือ "linear allocator") แนวคิดคือ: ขอ memory ก้อนใหญ่มาก้อนเดียวล่วงหน้า พอจะ "จอง" ก็แค่หยิบชิ้นที่ยังไม่ได้ใช้ถัดไปแล้วขยับ pointer ไปข้างหน้าให้พ้นมัน — นั่นคือ "bump" พอจะ "คืน" ก็ไม่ต้องคืนทีละชิ้น — แต่ทิ้งเนื้อหาทั้งก้อนพร้อมกันโดยขยับ pointer กลับไปจุดเริ่มต้น ไม่มีการค้นหา ไม่มี free list ไม่มีการจดบันทึกต่อการจองแต่ละครั้ง

#include <cstdio>
#include <cstdint>
#include <cstdlib>

class ArenaAllocator {
public:
    explicit ArenaAllocator(size_t sizeBytes) {
        m_begin   = static_cast<uint8_t*>(std::malloc(sizeBytes));
        m_current = m_begin;
        m_end     = m_begin + sizeBytes;
    }

    ~ArenaAllocator() {
        std::free(m_begin);
    }

    void* allocate(size_t bytes) {
        if (m_current + bytes > m_end) {
            return nullptr;              // arena is full
        }
        void* result = m_current;
        m_current += bytes;              // the "bump"
        return result;
    }

    void reset() {
        m_current = m_begin;             // "free" everything in one step
    }

private:
    uint8_t* m_begin;
    uint8_t* m_current;
    uint8_t* m_end;
};

int main() {
    ArenaAllocator arena(64);            // a tiny 64-byte arena

    void* a = arena.allocate(16);
    void* b = arena.allocate(16);
    void* c = arena.allocate(16);

    printf("a = %p\n", a);
    printf("b = %p\n", b);
    printf("c = %p\n", c);
    printf("b - a = %td bytes\n", (uint8_t*)b - (uint8_t*)a);

    arena.reset();                       // everything "freed" at once, no destructors run

    void* d = arena.allocate(16);
    printf("d = %p (same address as a: %s)\n", d, d == a ? "yes" : "no");
}

Output (hex address จริงของคุณจะต่างออกไป แต่ pattern จะไม่ต่าง):

a = 0x55f2a1b0aeb0
b = 0x55f2a1b0aec0
c = 0x55f2a1b0aed0
b - a = 16 bytes
d = 0x55f2a1b0aeb0 (same address as a: yes)

b - a = 16 bytes พิสูจน์ว่าการเรียก allocate แต่ละครั้งแค่ขยับ pointer ไปข้างหน้าตามขนาดที่ขอพอดี — ไม่มีการค้นหา ไม่มี metadata เขียนต่อการจอง แค่บวกเลขธรรมดา และหลัง reset() ตัว d ก็ตกลงที่ address เดียวกับ a เป๊ะ เพราะ reset() ไม่ได้ลบอะไรเลย — มันแค่ย้าย m_current กลับไปที่ m_begin เท่านั้น การ allocate ครั้งถัดไปเลยยื่น memory ก้อนเดิมนั้นให้อีกครั้ง

การจอง object จริง ไม่ใช่แค่ไบต์เปล่า ๆ

allocate() ให้แค่ไบต์ดิบ ๆ ที่ยังไม่ได้ initialize เท่านั้น — มันไม่รู้วิธีสร้าง Particle หรือเรียก constructor เพื่อสร้าง object จริงในหน่วยความจำนั้น ใช้ placement new: รูปแบบพิเศษของ new ที่สร้าง object ที่ address ที่คุณมีอยู่แล้ว แทนที่จะขอ memory ใหม่จาก heap

#include <cstdio>
#include <new>

struct Particle {
    float x, y, z;
};

int main() {
    ArenaAllocator arena(1024);

    void* mem = arena.allocate(sizeof(Particle));
    Particle* p = new (mem) Particle{1.0f, 2.0f, 3.0f};   // construct IN this memory

    printf("particle: %.1f, %.1f, %.1f\n", p->x, p->y, p->z);

    arena.reset();   // Particle's destructor is NOT called here
}

Output:

particle: 1.0, 2.0, 3.0

new (mem) Particle{...} ไม่ได้จอง memory เพิ่มเลย — มันแค่รัน constructor ของ Particle บนไบต์ที่ mem ชี้อยู่ ซึ่ง arena เป็นเจ้าของอยู่แล้ว วิธีนี้ใช้ได้ดีกับ Particle ที่ไม่ได้เป็นเจ้าของ resource อื่นเลย (ไม่มี heap pointer ของตัวเอง ไม่มีอะไรต้อง cleanup) แต่จะอันตรายกับ type ที่เป็นเจ้าของ resource (เช่น file handle หรือ heap allocation อีกอัน) เพราะ reset() ไม่เรียก destructor เลย — มันแค่ล้าง pointer กลับไปจุดเริ่มต้นเท่านั้น นี่คือการแลกเปลี่ยนที่ตั้งใจ: arena เหมาะกับข้อมูลที่ไม่ต้อง cleanup และมี lifetime ร่วมกัน ซึ่งครอบคลุมข้อมูลเกมจำนวนมหาศาล (particle, draw command ต่อเฟรม, ผลลัพธ์ query ของ AI ชั่วคราว)

9. รูปแบบ Per-Frame Scratch Allocator

พฤติกรรม "คืนทุกอย่างพร้อมกัน" ของ arena allocator เหมาะเป๊ะกับสถานการณ์ที่พบบ่อยมากในเกม: งานที่ต้องการแค่ใน เฟรมปัจจุบัน เท่านั้นแล้วทิ้งได้ทันทีที่เฟรมถัดไปเริ่ม engine เรียกสิ่งนี้ว่า per-frame scratch allocator (หรือ "frame allocator" หรือ "linear allocator" ที่ใช้ในลักษณะนี้โดยเฉพาะ)

รูปแบบคือ: สร้าง arena หนึ่งตัวตอนเกมเริ่ม ขนาดใหญ่พอสมควร (สองสามเมกะไบต์เป็นค่าปกติ) พอเริ่มต้นทุกเฟรม เรียก reset() ระหว่างเฟรม ระบบไหนก็ตามที่ต้องการ memory ชั่วคราวอายุสั้น ๆ — สร้างลิสต์ object ที่มองเห็นได้ในเฟรมนี้, format debug string, เก็บข้อมูล pathfinding ชั่วคราว — จองจาก arena ตัวเดียวกันนี้แทนที่จะเรียก new ไม่มีใครต้องเรียก free ทีละตัว พอเฟรมจบและเฟรมถัดไปเริ่ม reset() จะทิ้งทุกอย่างในขั้นตอนเดียว พร้อมเอาไปใช้ใหม่ได้เลย

เทียบกับต้นทุนของการเรียก new/delete สำหรับ scratch data แบบเดียวกันทุกเฟรม: ด้วย arena การจองทุกครั้งในเฟรมนี้แค่ขยับ pointer และการคืน scratch data ทั้งเฟรม ใช้แค่คำสั่งเดียว (m_current = m_begin) ไม่ว่าจะจองไปกี่ครั้งก็ตาม ไม่มีความเสี่ยง fragmentation ด้วย เพราะทุกอย่างใน arena มี lifetime เดียวกันหมด — ทุกอย่างตายพร้อมกันในจังหวะเดียวกัน ทุกเฟรม ตลอดไป นี่คือการแลกเปลี่ยนที่ general-purpose allocator ทำไม่ได้ เพราะมันไม่รู้ล่วงหน้าว่าการจองไหนจะถูกคืนพร้อมกัน

10. Pool Allocator: ช่องขนาดคงที่

arena มีจุดอ่อนอยู่หนึ่งอย่าง: คุณคืนแค่ชิ้น เดียว จากตรงกลางไม่ได้ — ทุกอย่างใช้ lifetime ร่วมกันหมด เกมเต็มไปด้วย object ที่ ไม่ได้ ใช้ lifetime ร่วมกัน: ศัตรูเกิดและตายในเวลาที่ไม่เกี่ยวข้องกัน กระสุนยิงออกไปและหมดอายุแยกกัน network packet มาถึงและถูกใช้ทีละตัว สำหรับ pattern แบบนี้ engine จะใช้ pool allocator

pool จะจองพื้นที่ล่วงหน้าสำหรับ ช่องขนาดเท่ากัน จำนวนคงที่ — เช่น พอสำหรับศัตรู 500 ตัว ช่องที่ว่างจะถูกร้อยเข้าด้วยกันเป็น free list ซึ่งเป็น linked list ที่สร้างอย่างชาญฉลาด อยู่ข้างในช่องที่ว่างเอง: ไบต์แรก ๆ ของแต่ละช่องที่ว่างจะเก็บ pointer ไปยังช่องว่างถัดไป เลยไม่ต้องใช้ memory เพิ่มเลยแค่เพื่อจดว่าช่องไหนว่าง

#include <cstdio>
#include <cstdint>
#include <cstdlib>

class PoolAllocator {
public:
    PoolAllocator(size_t slotSize, size_t slotCount) : m_slotSize(slotSize) {
        m_memory   = static_cast<uint8_t*>(std::malloc(slotSize * slotCount));
        m_freeList = nullptr;
        for (size_t i = 0; i < slotCount; ++i) {
            void* slot = m_memory + i * slotSize;
            *reinterpret_cast<void**>(slot) = m_freeList;   // store "next free" IN the slot
            m_freeList = slot;
        }
    }

    void* allocate() {
        if (!m_freeList) {
            return nullptr;                     // pool is full
        }
        void* slot = m_freeList;
        m_freeList = *reinterpret_cast<void**>(slot);
        return slot;
    }

    void deallocate(void* slot) {
        *reinterpret_cast<void**>(slot) = m_freeList;
        m_freeList = slot;
    }

private:
    uint8_t* m_memory;
    void*    m_freeList;
    size_t   m_slotSize;
};

struct Enemy { float x, y, z; int health; };   // 16 bytes - room enough for a pointer

int main() {
    PoolAllocator pool(sizeof(Enemy), 4);       // 4 slots, each big enough for one Enemy

    void* s0 = pool.allocate();
    void* s1 = pool.allocate();
    pool.deallocate(s0);
    void* s2 = pool.allocate();                 // reuses s0's slot

    printf("s0 = %p\n", s0);
    printf("s2 = %p (same address as s0: %s)\n", s2, s2 == s0 ? "yes" : "no");
}

Output:

s0 = 0x55f2a1b0af00
s2 = 0x55f2a1b0af00 (same address as s0: yes)

ทั้ง allocate() และ deallocate() เป็น O(1) — pop หรือ push หัวของ linked list ไม่ต้องค้นหาเลย ต่างจาก general-purpose allocator ตรงที่ pool ไม่มีวันแตกกระจาย (fragment) เพราะทุกช่องขนาดเท่ากันหมด: ช่องว่างช่องไหนก็ตอบสนองคำขอไหนก็ได้ เลยไม่มีปัญหา "ช่องเล็กเกินไป" เกิดขึ้นเลย

11. เลือก Allocator ให้ถูกกับงาน

ไม่มีตัวไหนมาแทนที่ตัวไหนได้ — engine จริงใช้ทั้งหมดนี้ควบคู่กันไป เลือกตามสถานการณ์:

• Stack (ตัวแปร automatic) — ทางเลือกเริ่มต้นสำหรับอะไรก็ตามที่ไม่ต้องอยู่นานเกินฟังก์ชันปัจจุบัน เร็วที่สุดเท่าที่จะเป็นไปได้ และคุณไม่ต้องเขียนโค้ด allocator เลยแม้แต่บรรทัดเดียว
• Arena / bump allocator — การจองจำนวนมากที่ตายพร้อมกันหมด: scratch data ต่อเฟรม, buffer ชั่วคราวตอนโหลด level, working memory สำหรับ pathfinding search หนึ่งครั้ง O(1) ในการจอง, O(1) ในการคืนทั้งหมดพร้อมกัน
• Pool allocator — object จำนวนมากที่ขนาดเท่ากันแต่ lifetime แยกจากกัน: กระสุน, ศัตรู, particle ที่เก็บเป็น object แยกตัว, network packet O(1) ในการจองและคืนทีละตัว โดยไม่มี fragmentation เลย
• new/malloc แบบ general-purpose — การจองที่ไม่บ่อย ขนาดไม่แน่นอน อยู่นาน และอะไรก็ตามที่อยู่นอก hot path: สร้างข้อมูล level ครั้งเดียวตอนโหลด, สร้าง UI, manager object แบบใช้ครั้งเดียว ใช้ได้สบาย ๆ ตรงนั้น

แนวคิดที่วนซ้ำตลอดทั้งบทนี้คือ: รู้จัก รูปร่าง ของข้อมูลคุณ (padding, AoS กับ SoA) และรู้จัก lifetime ของข้อมูลคุณ (arena กับ pool กับ general-purpose) แล้วเลือกเครื่องมือที่เข้ากับทั้งสองอย่าง นี่คือความหมายของ "allocator แบบที่ engine ทำกัน" — ไม่ใช่ allocator สารพัดประโยชน์ตัวเดียว แต่เป็นกล่องเครื่องมือเล็ก ๆ ที่มีผู้เชี่ยวชาญหลายคน แต่ละคนเรียบง่ายเพราะมันแค่ต้องจัดการ pattern เฉพาะของตัวเองให้ดีเท่านั้น

12. คำศัพท์

• Allocator — โค้ดที่รับผิดชอบแจกจ่ายและเรียกคืนก้อน memory
• Alignment — ตัวเลขที่ address ของ type นั้นต้องหารลงตัว (เช่น double ต้องการ multiple ของ 8)
• Padding — ไบต์เติมที่ไม่ได้ใช้ ซึ่ง compiler แทรกเข้าไปเพื่อให้ member และ struct ทั้งก้อนตกที่ address ที่ align ถูกต้อง
• AoS (Array-of-Structs) — array เดียวที่เก็บ object ทั้งก้อนเรียงติดกัน ทุก field ของ object ถูกแปะติดกัน
• SoA (Struct-of-Arrays) — array แยกกันหนึ่งตัวต่อหนึ่ง field ทำให้ค่าของ field เดียวกันทุกตัวอยู่ติดกันใน memory
• Cache line — ก้อนขนาดคงที่ (ปกติ 64 ไบต์) ที่ CPU ดึงจาก RAM มาทีเดียว ตามที่พูดถึงในบท 3.1
• SIMD — single instruction, multiple data คำสั่งเดียวที่ประมวลผลค่าที่อยู่ติดกันหลายค่าพร้อมกัน
• Fragmentation — memory ว่างที่กระจัดกระจายเป็นช่องเล็ก ๆ ที่แต่ละช่องเล็กเกินกว่าจะตอบสนองคำขอใหม่ได้ ถึงแม้พื้นที่ว่างรวมจะพอก็ตาม
• Hot path — โค้ดที่รันบ่อยมาก (ทุกเฟรม หรือหลายครั้งต่อเฟรม) ที่ต้นทุนเล็ก ๆ สะสมเร็วมาก
• Arena / bump allocator — แจก memory โดยขยับ pointer ไปข้างหน้า คืนทุกอย่างพร้อมกันด้วยการรีเซ็ต pointer นั้น
• Per-frame scratch allocator — arena ที่ถูก reset ตอนเริ่มทุกเฟรม ใช้เก็บข้อมูลชั่วคราวอายุสั้นของเฟรมนั้น
• Pool allocator — ช่องขนาดคงที่ที่จองไว้ล่วงหน้า แจกและคืนทีละช่องผ่าน free list ไม่มี fragmentation, O(1) ในการจอง/คืน
• Free list — linked list ของ block หรือช่องที่ยังไม่ได้ใช้อยู่ตอนนี้ มักถูกเก็บไว้ข้างในหน่วยความจำที่ไม่ได้ใช้นั่นเอง
• Placement new — รูปแบบของ new ที่สร้าง object ที่ address ของ memory ที่คุณเป็นเจ้าของอยู่แล้ว แทนที่จะจอง memory ใหม่

13. แบบฝึกหัด

#include <cstdio>

struct Enemy {
    bool   isAlive;
    double health;
    char   team;
    int    id;
};

int main() {
    printf("sizeof(Enemy) = %zu\n", sizeof(Enemy));
}

#include <cstdio>

struct Enemy {
    double health;
    int    id;
    bool   isAlive;
    char   team;
};

int main() {
    printf("sizeof(Enemy) = %zu\n", sizeof(Enemy));
}

sizeof(Enemy) = 16

#include <vector>

struct Enemy {
    float x, y;
    float health;
    int   id;
};

// TODO: struct EnemySystem with parallel arrays instead of a vector<Enemy>
// TODO: void damageAll(EnemySystem& es, float amount);

#include <vector>
#include <cstdio>

struct EnemySystem {
    std::vector<float> x, y;
    std::vector<float> health;
    std::vector<int>   id;
};

void damageAll(EnemySystem& es, float amount) {
    for (size_t i = 0; i < es.health.size(); ++i) {
        es.health[i] -= amount;
    }
}

int main() {
    EnemySystem es;
    es.x      = {0.0f, 1.0f};
    es.y      = {0.0f, 1.0f};
    es.health = {100.0f, 50.0f};
    es.id     = {1, 2};

    damageAll(es, 10.0f);

    printf("health[0] = %.1f\n", es.health[0]);
    printf("health[1] = %.1f\n", es.health[1]);
}

health[0] = 90.0
health[1] = 40.0

// Starting point: same ArenaAllocator as section 8 (m_begin, m_current, m_end).
// TODO: add this method.
//   void* allocate(size_t bytes, size_t alignment);
// It must round m_current UP to the next multiple of "alignment"
// before returning it, and must still refuse to overrun m_end.

#include <cstdio>
#include <cstdint>
#include <cstdlib>

class ArenaAllocator {
public:
    explicit ArenaAllocator(size_t sizeBytes) {
        m_begin   = static_cast<uint8_t*>(std::malloc(sizeBytes));
        m_current = m_begin;
        m_end     = m_begin + sizeBytes;
    }

    ~ArenaAllocator() {
        std::free(m_begin);
    }

    void reset() {
        m_current = m_begin;
    }

    // alignment MUST be a power of two (1, 2, 4, 8, 16, ...) - every real
    // C++ alignment requirement is a power of two, so this is always safe.
    void* allocate(size_t bytes, size_t alignment) {
        uintptr_t rawAddr     = reinterpret_cast<uintptr_t>(m_current);
        uintptr_t alignedAddr = (rawAddr + (alignment - 1)) & ~(alignment - 1);
        size_t padding        = static_cast<size_t>(alignedAddr - rawAddr);

        if (m_current + padding + bytes > m_end) {
            return nullptr;             // not enough room, even counting padding
        }

        m_current += padding;           // skip the padding bytes
        void* result = m_current;       // this address is now aligned
        m_current += bytes;
        return result;
    }

private:
    uint8_t* m_begin;
    uint8_t* m_current;
    uint8_t* m_end;
};

int main() {
    ArenaAllocator arena(64);

    void* p1 = arena.allocate(1, 1);    // 1 byte, no alignment need
    void* p2 = arena.allocate(8, 8);    // 8 bytes, must land on a multiple of 8

    printf("p1 = %p\n", p1);
    printf("p2 = %p\n", p2);
    printf("p2 is 8-byte aligned: %s\n",
           (reinterpret_cast<uintptr_t>(p2) % 8 == 0) ? "yes" : "no");
}

p1 = 0x55f2a1b0b000
p2 = 0x55f2a1b0b008
p2 is 8-byte aligned: yes