15.6 SIMD และ Cache (สายลึก)

ในบท C memory เราเรียนไปแล้วว่า memory คืออาเรย์ยักษ์ของไบต์ที่มีเลขกำกับ และ pointer ก็คือตัวเลขที่ใช้เรียกชื่อไบต์ตัวใดตัวหนึ่งในนั้น array เก็บ element ของมันเรียงต่อกันในอาเรย์ของไบต์นั้น ไม่มีช่องว่างคั่นเลย เรื่องนั้นเป็นเรื่องของ ความถูกต้อง (correctness) — คือรู้ว่า memory ชิ้นหนึ่งคืออะไรจริง ๆ บทนี้เป็นเรื่องของ ความเร็ว (speed) — คือดูว่าเกิดอะไรขึ้นเวลาโค้ดของเราสั่งให้ CPU อ่านและเขียนไบต์พวกนั้นจริง ๆ เป็นล้าน ๆ ครั้งต่อหนึ่งเฟรม

1. ทำไมต้องมีบทนี้: จากไบต์สู่ความเร็ว

ส่วนที่น่าแปลกใจคือ โค้ดสองชิ้นที่ทำคณิตศาสตร์เหมือนกันเป๊ะ — จำนวนการบวกการคูณเท่ากันทุกอย่าง — ความเร็วอาจต่างกันได้ถึง 5 ถึง 30 เท่า แค่เพราะชิ้นหนึ่งขอ memory ตามลำดับที่ CPU ชอบ ส่วนอีกชิ้นไม่ทำแบบนั้น นี่ไม่ใช่รายละเอียดเล็ก ๆ เลย ใน game engine จริง รูปแบบการเข้าถึง memory มักเป็นตัวแปรที่ส่งผลต่อ performance มากกว่า algorithm ที่ฉลาดเสียอีก physics engine, particle system, หรือ skinning system ที่ "ทำงานเท่ากัน" แต่แตะ memory แบบไม่ดี อาจเสียเวลาทั้งเฟรมไปกับการรอเฉย ๆ ได้

บทนี้เน้นสองเทคนิคหลัก คือทำให้การเข้าถึง memory เป็นแบบ cache-friendly (ให้ CPU แทบไม่ต้องรอ RAM เลย) กับการใช้ SIMD (Single Instruction, Multiple Data — ให้หนึ่งคำสั่งของ CPU ทำคณิตศาสตร์ 4 หรือ 8 ค่าพร้อมกันในทีเดียว แทนที่จะทำทีละค่า) ทั้งสองอย่างถูกใช้ตลอดเวลาใน particle system, physics solver, skinning, และ culling และทั้งสองอย่างก็เป็นเหตุผลที่ pattern Entity-Component-System (ECS) มีอยู่ ซึ่งเราจะเจอแบบเต็ม ๆ ใน Phase 16 — บทนี้อธิบายเหตุผลระดับฮาร์ดแวร์ว่าทำไม ECS ถึงถูกออกแบบมาแบบนั้น

2. ลำดับชั้นของ Memory: Register, L1, L2, L3, RAM

CPU core อ่านค่าจาก RAM (main memory) ตรง ๆ ทุกคำสั่งไม่ได้ — RAM ช้าเกินไปมากเมื่อเทียบกับความเร็วที่ core สมัยใหม่รันคำสั่งได้ ดังนั้นระหว่าง core กับ RAM จึงมี memory หลายชั้นที่เล็กกว่าและเร็วกว่าคั่นอยู่ เรียกว่า cache แต่ละชั้นคือสำเนาของส่วนเล็ก ๆ ของ RAM ที่เก็บไว้ใกล้ ๆ core

ชั้นที่อยู่ใกล้ core ที่สุดจะเล็กมากและเร็วสุด ๆ ส่วนชั้นที่อยู่ไกลออกไปจะใหญ่กว่าและช้ากว่า L1, L2, และ L3 ย่อมาจาก "Level 1/2/3 cache" — L1 อยู่ใกล้ที่สุดและเล็กที่สุด L3 อยู่ไกลที่สุด (แต่ก็ยังเร็วกว่า RAM มาก) และใหญ่ที่สุด ปกติจะถูกแชร์กันใช้โดยทุก core บนชิป

ต้นทุนการเข้าถึงโดยประมาณ

ตัวเลขที่แน่นอนจะต่างกันไปตามรุ่นและเจนของ CPU แต่ อัตราส่วน ระหว่างแต่ละชั้นจะใกล้เคียงกันในเกือบทุก CPU สมัยใหม่ ไม่ว่าจะเป็นเดสก์ท็อป, console, หรือมือถือ ประมาณคร่าว ๆ (หน่วยเป็น CPU clock cycle):

คำสั่งบวกหรือคูณหนึ่งคำสั่งใช้เวลาประมาณ 1 cycle ของ throughput นั่นแปลว่า cache miss (ค่าที่ต้องการยังไม่มีอยู่ใน cache) ที่ต้องไปเอาถึง RAM จะกินเวลาพอ ๆ กับคำสั่งคณิตศาสตร์ธรรมดา ๆ 100 ถึง 200 กว่าคำสั่ง ถ้า inner loop ของเรา miss cache ทุกรอบ CPU จะใช้เวลาเกือบทั้งหมดนั่งรอเฉย ๆ รอให้ไบต์มาถึง ไม่ได้คำนวณอะไรเลย

3. Cache Line: Memory มาทีละ 64 ไบต์

cache ไม่ได้ดึง memory ทีละไบต์ หรือทีละ float การดึงแต่ละครั้งจะดึงมาเป็นก้อนขนาดคงที่ที่เรียกว่า cache line ใน CPU สมัยใหม่แทบทุกตัว ไม่ว่าจะเป็นเดสก์ท็อป, console, หรือมือถือ cache line มีขนาด 64 ไบต์

ดังนั้นถ้าเราอ่าน float ตัวเดียวขนาด 4 ไบต์ที่ address หนึ่ง ฮาร์ดแวร์จะดึงก้อน 64 ไบต์ที่ align มาทั้งก้อนที่มีค่านั้นอยู่ — คือ 16 float (หรือ 8 double) ไม่ว่าเราจะขอ 15 ตัวที่เหลือด้วยหรือไม่ก็ตาม

เรื่องนี้ส่งผลตรง ๆ ต่อวิธีที่เราควรเขียน loop ถ้าค่าตัวถัดไปที่เราจะอ่านคือ float ตัวถัดไปใน memory มันมีโอกาสสูงมากที่จะอยู่ใน cache line ที่เราเพิ่งจ่ายไปแล้ว — อ่านแบบนี้จะได้ L1 hit ใช้เวลาประมาณ 4 cycle แต่ถ้าค่าตัวถัดไปอยู่ไกลออกไป นั่นคือ cache line ใหม่เอี่ยม อาจต้องเดินทางไปถึง RAM เต็ม ๆ ใช้เวลาประมาณ 200 cycle

การเข้าถึงแบบเรียงลำดับ (sequential access) เร็ว เพราะมันใช้ cache line ที่ดึงมาแล้วซ้ำ ส่วน การเข้าถึงแบบสุ่มหรือกระจัดกระจาย (random/scattered access) ช้า เพราะเกือบทุกครั้งที่เข้าถึงต้องการ cache line ใหม่ และเมื่อ working set ของเราใหญ่เกินกว่าจะใส่ใน cache ได้ การดึงใหม่ ๆ พวกนั้นส่วนใหญ่ก็ต้องไปถึง RAM

4. Sequential Access ชนะ: Row-Major vs Column-Major

array 2 มิติจริง ๆ แล้วก็คือ array 1 มิติที่แอบซ่อนอยู่ ใน C กับ C++ matrix แบบ row-major จะเก็บ matrix[row][col] ไว้ที่ index แบบแบน row * width + col — ดังนั้น row 0 จะมาก่อนใน memory เรียงตามลำดับ ตามด้วย row 1, row 2, ไปเรื่อย ๆ

#include <cstdio>
#include <chrono>
#include <vector>

const int N = 4096;

int main() {
    std::vector<float> matrix(N * N, 1.0f);

    // row-major: inner loop walks along memory (fast)
    auto t0 = std::chrono::high_resolution_clock::now();
    double sumRow = 0.0;
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            sumRow += matrix[row * N + col];
        }
    }
    auto t1 = std::chrono::high_resolution_clock::now();

    // column-major: inner loop jumps N floats every step (slow)
    double sumCol = 0.0;
    for (int col = 0; col < N; col++) {
        for (int row = 0; row < N; row++) {
            sumCol += matrix[row * N + col];
        }
    }
    auto t2 = std::chrono::high_resolution_clock::now();

    double msRow = std::chrono::duration<double, std::milli>(t1 - t0).count();
    double msCol = std::chrono::duration<double, std::milli>(t2 - t1).count();

    printf("row-major:    %.2f ms  (sum = %.0f)\n", msRow, sumRow);
    printf("column-major: %.2f ms  (sum = %.0f)\n", msCol, sumCol);
}

อ่านโค้ด timing

loop ทั้งสองแบบทำสิ่งเดียวกันทางคณิตศาสตร์เป๊ะ ๆ คือบวก element ทุกตัวของ matrix เดียวกัน ตัวละครั้งเดียว ต่างกันแค่ลำดับที่ nested loop สองชั้นเดินผ่าน index เท่านั้น เวอร์ชัน row-major ที่ inner loop เป็น col จะเดินตรง ๆ ตาม memory ทีละ float — ใช้ cache line ที่ดึงมาทุกก้อนอย่างเต็มที่ ส่วนเวอร์ชัน column-major ที่ inner loop เป็น row จะกระโดดไปข้างหน้าทีละ N float ในทุกก้าว — สำหรับ N = 4096 นั่นคือ 16 KB ระหว่างการเข้าถึงแต่ละครั้ง ใหญ่กว่า cache line มาก และมักใหญ่กว่า L1 หรือ L2 ทั้งก้อนด้วยซ้ำ เกือบทุกการเข้าถึงใน loop แบบ column-major จึงเป็นการดึง cache line ใหม่

วัดผลบน CPU เดสก์ท็อปทั่วไป ด้วย N = 4096 (matrix ของ float ขนาด 4096 x 4096 รวม 64 MB — ใหญ่กว่า cache ตัวไหนเลยมาก):

row-major:    14.20 ms  (sum = 16777216)
column-major: 168.53 ms  (sum = 16777216)

คณิตศาสตร์เหมือนกัน จำนวนการบวกเท่ากัน ผลรวมสุดท้ายเท่ากัน — แต่ช้ากว่าเกือบ 12 เท่า แค่เพราะลำดับ loop เท่านั้น นี่เป็นเรื่องของ memory ล้วน ๆ ไม่ใช่เรื่องคณิตศาสตร์เลย

5. Array of Structs กับ Struct of Arrays

มือใหม่ส่วนใหญ่มักเขียนข้อมูลแบบเดียวกันหมด คือมี struct หรือ class ที่เก็บทุก field ที่ object ต้องใช้ไว้ด้วยกัน แล้วเก็บใน array วิธีนี้เรียกว่า Array of Structs หรือ AoS

AoS ตรงกับวิธีที่เราคิดถึง object ตามธรรมชาติ — "particle หนึ่งตัวมีตำแหน่ง, ความเร็ว, สี" — และมันก็ใช้ได้ดีกับโค้ดที่แตะ field ส่วนใหญ่หรือทุก field ของ object พร้อมกัน ปัญหาจะเกิดขึ้นเมื่อเราต้องการแค่ field เดียว จาก object จำนวนมาก เพราะทุก field ของ particle หนึ่งตัวอยู่ติดกันใน memory การอ่านแค่ life ของ particle ตัวที่ 0 ก็ยังลาก x, y, z, vx, vy, vz, สีทั้งหมด, rotation, และ scale เข้ามาใน cache ด้วย — ไบต์ที่เราจ่ายไปแต่ไม่เคยใช้เลย

Struct of Arrays หรือ SoA จะกลับ layout ไปอีกแบบ คือมี array แยกหนึ่งอันต่อหนึ่ง field ครอบคลุมทุก object นี่คือตัวอย่างที่ใกล้เคียงกับ particle จริง ๆ มากขึ้น: 14 float ต่อ particle (56 ไบต์) โดยที่ฟังก์ชันนี้ต้องการแค่ life เท่านั้น

struct ParticleAoS {
    float x, y, z;       // position
    float vx, vy, vz;    // velocity
    float r, g, b, a;    // color
    float rotation;
    float scale;
    float life;           // remaining lifetime -- the ONLY field this example needs
    float maxLife;
};

float sumLifeAoS(const std::vector<ParticleAoS>& particles) {
    float total = 0.0f;
    for (const auto& p : particles) {
        total += p.life;
    }
    return total;
}

struct ParticleSystemSoA {
    std::vector<float> x, y, z;
    std::vector<float> vx, vy, vz;
    std::vector<float> r, g, b, a;
    std::vector<float> rotation;
    std::vector<float> scale;
    std::vector<float> life;      // the only array this example touches
    std::vector<float> maxLife;
};

float sumLifeSoA(const ParticleSystemSoA& particles) {
    float total = 0.0f;
    for (float l : particles.life) {
        total += l;
    }
    return total;
}

วัดผลกับ particle 2,000,000 ตัว ทุกตัวมี life = 1.0:

int main() {
    const int N = 2000000;
    std::vector<ParticleAoS> aos(N);
    for (auto& p : aos) p.life = 1.0f;

    ParticleSystemSoA soa;
    soa.life.assign(N, 1.0f);

    auto t0 = std::chrono::high_resolution_clock::now();
    float totalAoS = sumLifeAoS(aos);
    auto t1 = std::chrono::high_resolution_clock::now();
    float totalSoA = sumLifeSoA(soa);
    auto t2 = std::chrono::high_resolution_clock::now();

    printf("AoS sumLife: %.2f ms (total = %.0f)\n",
           std::chrono::duration<double, std::milli>(t1 - t0).count(), totalAoS);
    printf("SoA sumLife: %.2f ms (total = %.0f)\n",
           std::chrono::duration<double, std::milli>(t2 - t1).count(), totalSoA);
}

AoS sumLife: 5.10 ms (total = 2000000)
SoA sumLife: 0.62 ms (total = 2000000)

เวอร์ชัน AoS อ่าน 56 ไบต์ต่อ particle เพื่อเอาแค่ 4 ไบต์ที่ใช้ได้จริง — ข้อมูลที่ไหลผ่านระบบ memory มากกว่าที่จำเป็นถึง 14 เท่า ส่วนเวอร์ชัน SoA อ่านแค่ 4 ไบต์ที่ต้องการเป๊ะ ๆ อัดแน่นอยู่กับค่า life ของ particle อีก 15 ตัวใน cache line เดียวกัน เร็วกว่าประมาณ 8 เท่าในกรณีนี้ สำหรับการอ่าน field เดียวจาก struct ขนาดกลาง ๆ — และช่องว่างจะยิ่งกว้างขึ้นถ้า struct ใหญ่ขึ้นหรือมี field ที่ไม่ได้ใช้เยอะขึ้น

6. SoA กับเหตุผลที่ ECS มีอยู่

ทางเลือกระหว่าง AoS กับ SoA ไม่ได้หยุดอยู่แค่ particle เท่านั้น ถ้าซูมออกไปดูทั้งเกม เราจะเจอปัญหาเดียวกันในสเกลที่ใหญ่ขึ้น: GameObject แบบดั้งเดิมเก็บตำแหน่ง, ความเร็ว, health, reference ไปยัง mesh, สถานะ AI, และอื่น ๆ ไว้ใน object ก้อนเดียวที่ allocate บน heap ระบบที่สนใจแค่ตำแหน่งกับความเร็ว — อย่างเช่นระบบเคลื่อนที่ — ก็ยังต้องกระโดดไปทุกที่ที่ GameObject แต่ละตัวบังเอิญไปอยู่บน heap

pattern Entity-Component-System (ECS) ที่เราจะเจอแบบเต็ม ๆ ใน Phase 16 ก็คือ SoA ที่เอามาใช้กับทั้งเกมเวิลด์นั่นเอง แทนที่จะมี object หนึ่งตัวต่อหนึ่ง entity ที่เก็บทุก field ไว้ด้วยกัน ECS จะเก็บ array ที่อัดแน่นหนึ่งชุดต่อหนึ่ง component type ครอบคลุมทุก entity ที่มี component นั้น ระบบเคลื่อนที่ที่ต้องการแค่ Position กับ Velocity จะไหลผ่าน array สองชุดนี้ตรง ๆ และไม่แตะ health, สถานะ AI, หรืออะไรอื่นเลย — ได้ประโยชน์จาก cache line แบบเดียวกับตัวอย่าง particle เป๊ะ ๆ แค่ขยายสเกลไปเป็นหลักพัน entity แทนที่จะเป็น particle system เดียว

นี่คือเหตุผลระดับฮาร์ดแวร์ว่าทำไม ECS ถึงมีอยู่ มันไม่ใช่แค่วิธีจัดโค้ดให้ "สะอาดกว่า" เฉย ๆ — array แบบ component ที่จัดเป็น SoA นั้น cache-friendly กว่า object ที่กระจัดกระจายอย่างมาก ด้วยเหตุผลเป๊ะ ๆ ตามที่บทนี้อธิบายมา

7. Prefetching กับรูปแบบการเข้าถึงที่คาดเดาได้

การใช้ cache line ซ้ำไม่ใช่เหตุผลเดียวที่ทำให้ sequential access เร็ว CPU สมัยใหม่ยังมี hardware prefetcher — วงจรที่คอยจับตาดู pattern ของ address ที่โค้ดเราเข้าถึง ถ้ามันสังเกตเห็น stride ที่คงที่ (เช่น +64 ไบต์ทุกครั้งที่เข้าถึง) มันจะเริ่มดึง cache line อีกไม่กี่ก้อนถัดไปเข้ามาใน cache ก่อนที่โค้ดเราจะขอด้วยซ้ำ ซ่อน latency ของ RAM ไว้เบื้องหลังงานที่ core กำลังทำอยู่แล้ว

นี่คืออีกเหตุผลที่ loop ธรรมดา ๆ บน array วิ่งเร็ว: มันไม่ได้แค่ใช้ cache line ซ้ำ prefetcher ยังทายได้แม่นด้วยว่า address ถัดไปคืออะไร แล้วเริ่มดึงล่วงหน้าได้เลย ส่วน random access — เช่นการไล่ตาม linked list หรือ index ผ่าน array ของ index ที่ถูกสับ — จะทำให้ prefetcher ใช้งานไม่ได้เลย เพราะมันไม่มี stride คงที่ให้เรียนรู้ ทุกการเข้าถึงจึงต้องจ่ายค่า miss เต็ม ๆ โดยไม่มีการดึงล่วงหน้าช่วยเลย

compiler กับ hardware prefetcher จัดการ loop ธรรมดาได้ดีอยู่แล้วโดยไม่ต้องช่วยอะไรเพิ่ม hint สำหรับ prefetch แบบเขียนเองก็มีอยู่ (__builtin_prefetch ใน GCC/Clang หรือ intrinsic อย่าง _mm_prefetch ที่อื่น) ไว้ใช้กับกรณีที่ฮาร์ดแวร์ทายเองไม่ได้ — เช่นการไล่ tree หรือ linked list ที่เรารู้อยู่แล้วว่าอีกไม่กี่ก้าวข้างหน้าจะต้องใช้ node ไหน:

// usually unnecessary -- shown only to see what it looks like
for (int i = 0; i < n; i++) {
    __builtin_prefetch(&data[i + 16], 0, 1); // hint: we will read this soon
    total += heavyWorkOn(data[i]);
}

สำหรับ loop ธรรมดาบน array อย่างที่พูดมาตลอดบทนี้ เราแทบไม่ต้องใช้เทคนิคนี้เลย เพราะ hardware prefetcher ทำให้เราอยู่แล้ว ให้หยิบ manual prefetching มาใช้ก็ต่อเมื่อ profile แล้วเจอว่า loop ตัวใดตัวหนึ่งติดขัดเรื่อง memory จริง ๆ และ pattern การเข้าถึงไม่ใช่การเดิน array แบบธรรมดา

8. False Sharing: เมื่อ Thread แย่ง Cache Line กัน

การใช้ cache line ซ้ำเป็นเรื่องดีสำหรับ core เดียว แต่พอมีหลาย core เข้ามาเกี่ยวข้อง มันจะเกิดปัญหาใหม่ Cache coherency (การรักษาให้สำเนา cache ของทุก core ตรงกัน) ถูกติดตามในระดับของ cache line ทั้งก้อน ไม่ใช่ทีละไบต์ ถ้า thread สองตัวบนสอง core ต่างกันเขียนไปยังตัวแปรสองตัวที่ต่างกัน แต่บังเอิญไปอยู่ใน cache line 64 ไบต์เดียวกัน ฮาร์ดแวร์จะมองว่ามันแย่งกันใช้ — ทั้งที่ตัวแปรสองตัวนั้นไม่เคยทับซ้อนกันจริง ๆ เลย เรื่องนี้เรียกว่า false sharing

ทุกครั้งที่ core A เขียน counterA มันจะทำให้สำเนา cache ทั้งเส้นของ core B เป็นโมฆะ (invalidate) บังคับให้ core B ต้องดึงใหม่ ทุกครั้งที่ core B เขียน counterB ก็เกิดเรื่องเดียวกันย้อนกลับ cache line จะเด้งไปเด้งมาระหว่าง cache ของสอง core — แต่ละครั้งที่เด้งมีต้นทุนพอ ๆ กับ cache miss ไป shared cache หรือ RAM ทั้งที่ไม่มี thread ไหนแตะตัวแปรของอีกฝั่งเลยด้วยซ้ำ

#include <atomic>
#include <thread>
#include <chrono>
#include <cstdio>

struct CountersBad {
    std::atomic<long> counterA{0};
    std::atomic<long> counterB{0};
    // counterA and counterB usually land in the SAME cache line
};

struct CountersGood {
    alignas(64) std::atomic<long> counterA{0};
    alignas(64) std::atomic<long> counterB{0};
    // 64-byte alignment forces each counter onto its OWN cache line
};

const long ITERS = 100000000;

template <typename T>
double runTest(T& counters) {
    auto t0 = std::chrono::high_resolution_clock::now();
    std::thread ta([&] {
        for (long i = 0; i < ITERS; i++) counters.counterA++;
    });
    std::thread tb([&] {
        for (long i = 0; i < ITERS; i++) counters.counterB++;
    });
    ta.join();
    tb.join();
    auto t1 = std::chrono::high_resolution_clock::now();
    return std::chrono::duration<double, std::milli>(t1 - t0).count();
}

int main() {
    CountersBad bad;
    CountersGood good;
    printf("false sharing: %.2f ms\n", runTest(bad));
    printf("padded:        %.2f ms\n", runTest(good));
}

false sharing: 612.40 ms
padded:        78.90 ms

alignas(64) บังคับให้ counter แต่ละตัวเริ่มที่ boundary 64 ไบต์ของตัวเอง ทำให้ counterA กับ counterB ไปอยู่คนละ cache line thread ทั้งสองก็เลยเลิกแย่ง cache line เดียวกัน และเวอร์ชันที่ padding แล้ววิ่งเร็วกว่าประมาณ 7.8 เท่า — ทั้งที่ increment เหมือนกันเป๊ะทุกอย่าง

9. SIMD: หนึ่งคำสั่ง หลายตัวเลข

ทุกอย่างที่ผ่านมาเป็นเรื่องของการไม่เสียเวลารอ memory SIMD จะเข้ามาแก้อีกครึ่งหนึ่งของปัญหา คือทำให้คำนวณได้มากขึ้นต่อหนึ่งคำสั่ง

SIMD ย่อมาจาก Single Instruction, Multiple Data คำสั่งแบบปกติ ("scalar") ทำงานกับค่าทีละตัว — คำสั่งบวกหนึ่งคำสั่งบวก float สองตัวได้ float ผลลัพธ์หนึ่งตัว ส่วนคำสั่ง SIMD จะอัดหลายค่าเข้าไปใน register กว้าง ๆ ตัวเดียว แล้วทำ operation เดียวกัน กับทุกค่าพร้อมกันด้วยคำสั่งเดียว

แต่ละช่องใน register กว้าง ๆ นั้นเรียกว่า lane ความกว้างของ register จะเป็นตัวกำหนดว่าเราจะได้กี่ lane:

SSE (128-bit) มีอยู่ใน CPU x86 แทบทุกตัวที่ผลิตในศตวรรษนี้ AVX กับ AVX2 (256-bit) พบได้ทั่วไปใน CPU เดสก์ท็อปและ console สมัยใหม่ AVX-512 (512-bit) จะเจอในชิปเซิร์ฟเวอร์และเดสก์ท็อประดับสูงบางตัว ฝั่ง ARM ก็มี NEON (128-bit, 4 float) ที่ใช้ในมือถือ, Apple Silicon, และ Nintendo Switch

SIMD เป็น parallelism คนละแบบกับ multithreading multithreading รัน instruction stream แยกกันบน core แยกกัน ส่วน SIMD รัน instruction stream เดียว แต่แต่ละคำสั่งทำงานได้ 4 หรือ 8 (หรือ 16) เท่า ทั้งสองอย่างซ้อนกันได้: loop ที่ทั้ง multithreaded และ vectorize ด้วย SIMD จะได้ speedup ทั้งสองแบบพร้อมกัน ซึ่งนั่นคือสิ่งที่ตัวอย่าง Burst ใน section 13 ทำเป๊ะ ๆ

10. Scalar vs SIMD: บวก Float Array สองตัว

ตัวอย่าง SIMD ที่ง่ายที่สุดคือการบวก array ของ float สองตัว ทีละ element

void addArrays(const float* a, const float* b, float* result, int n) {
    for (int i = 0; i < n; i++) {
        result[i] = a[i] + b[i];
    }
}

#include <immintrin.h>   // SSE / AVX intrinsics

void addArraysSIMD(const float* a, const float* b, float* result, int n) {
    int i = 0;
    for (; i + 4 <= n; i += 4) {
        __m128 va = _mm_loadu_ps(&a[i]);
        __m128 vb = _mm_loadu_ps(&b[i]);
        __m128 vr = _mm_add_ps(va, vb);
        _mm_storeu_ps(&result[i], vr);
    }
    for (; i < n; i++) {           // leftover elements, n not divisible by 4
        result[i] = a[i] + b[i];
    }
}

แต่ละ intrinsic call ทำอะไรบ้าง

• _mm_loadu_ps(&a[i]) — โหลด float 4 ตัวเริ่มจาก a[i] เข้า register SIMD ขนาด 128-bit (ตัว u หมายความว่า address ไม่จำเป็นต้อง align แบบพิเศษ)
• _mm_add_ps(va, vb) — บวกทั้ง 4 lane ของ va กับ vb พร้อมกันในคำสั่งเดียว
• _mm_storeu_ps(&result[i], vr) — เขียนผลลัพธ์ float 4 ตัวกลับไปยัง memory
• loop ที่สองต่อจาก loop หลักจัดการกับ element ที่ "เหลือ" ตอน n ไม่ใช่จำนวนที่หาร 4 ลงตัว

วัดผลบน CPU เดสก์ท็อปทั่วไป บวก array ของ float 20,000,000 ตัวสองอัน:

scalar: 21.85 ms
simd:    7.42 ms

เร็วขึ้นประมาณ 2.9 เท่า ไม่ถึง 4 เท่าเต็ม ๆ ตามที่อาจคาดหวังจาก 4 lane เหตุผลคือ loop นี้เป็น memory-bandwidth bound คือทุกครั้งที่บวก CPU ต้องดึง float สองตัวจาก RAM เข้ามาแล้วเขียนกลับออกไปหนึ่งตัว การทำให้เลขคณิตเร็วขึ้น 4 เท่าไม่ช่วยอะไร ถ้า bottleneck คือความเร็วที่ RAM ป้อนข้อมูลเข้ามาและรับผลลัพธ์ออกไปได้ — CPU ก็ยังเสียเวลาส่วนใหญ่ไปกับการรออยู่ดี ส่วนโค้ด SIMD ที่เน้นการคำนวณหนัก ๆ — คูณและบวกหลายรอบต่อค่าหนึ่งค่าที่อยู่ใน register อยู่แล้ว เช่น matrix transform หรือ inner loop ของ physics — จะได้ speedup ใกล้เคียง 4-8 เท่าเต็ม ๆ มากกว่า เพราะ bottleneck ตรงนั้นคือ throughput ของเลขคณิตจริง ๆ ไม่ใช่ memory

11. Auto-Vectorization: เขียน Loop ที่ Compiler ทำให้เร็วขึ้นได้

เราแทบไม่ต้องเขียน intrinsic เองเลย compiler สมัยใหม่ — GCC, Clang, และ MSVC — สามารถแปลง loop แบบ scalar ธรรมดาให้กลายเป็นคำสั่ง SIMD ได้เองโดยอัตโนมัติ ที่ optimization level -O2 หรือ -O3 โดยไม่ต้องมี intrinsic อยู่ในซอร์สโค้ดของเราเลย

// compiled with -O3 -march=native -- no intrinsics written by hand
void addArrays(const float* a, const float* b, float* result, int n) {
    for (int i = 0; i < n; i++) {
        result[i] = a[i] + b[i];
    }
}

เมื่อ compile ด้วย -O3 -march=native loop ที่ดูธรรมดา ๆ นี้มักถูก compiler แปลงเป็นคำสั่ง SIMD ให้เองโดยอัตโนมัติ ได้ความเร็วใกล้เคียงกับเวอร์ชันที่เขียน intrinsic เองใน section ก่อนหน้า

สัญญาณที่บอกว่า loop จะไม่ auto-vectorize

• Pointer aliasing — ถ้า compiler พิสูจน์ไม่ได้ว่า result ไม่ทับซ้อนกับ a หรือ b ใน memory มันต้องสมมติกรณีที่แย่ที่สุดไว้ก่อน แล้วจะจัดลำดับหรือรวมกลุ่มการเขียนใหม่แบบปลอดภัยไม่ได้ การเติม __restrict เข้าไปคือคำสัญญาจากเราว่า pointer พวกนี้ไม่ทับซ้อนกัน ซึ่งมักจะปลดล็อกให้ vectorize ได้
• Loop-carried dependencies — ถ้ารอบที่ i ต้องใช้ผลลัพธ์เป๊ะ ๆ จากรอบที่ i - 1 (เช่น running total ที่ลำดับการปัดเศษของ floating-point มีผล) compiler มักจัดลำดับงานลง lane แบบปลอดภัยไม่ได้
• Branch ที่อยู่ใน loop ที่ต่างกันไปตาม element อาจขัดขวางหรือทำให้ vectorization ซับซ้อนขึ้น แม้บาง compiler จะยัง vectorize branch ง่าย ๆ ได้โดยใช้ mask
• การเรียกฟังก์ชัน ที่อยู่ใน loop ที่ไม่ได้ถูก inline หรือ compiler ไม่เข้าใจว่ามันทำอะไร

void addArraysFast(const float* __restrict a,
                    const float* __restrict b,
                    float* __restrict result, int n) {
    for (int i = 0; i < n; i++) {
        result[i] = a[i] + b[i];
    }
}

__restrict บอก compiler ว่า pointer ทั้งสามตัวนี้ไม่มีทางทับซ้อนกันเลย มันเลยโหลด บวก และเขียนเป็นชุด ๆ ละ 4 หรือ 8 ได้อย่างอิสระ โดยไม่ต้องกังวลว่าการเขียนไปที่ result[i] จะไปเปลี่ยน a[i] หรือ b[i] ที่จะอ่านทีหลัง loop ง่าย ๆ ที่ไม่มี branch, มี stride คงที่, และไม่มีความกำกวมเรื่อง aliasing คือ loop ที่ vectorize ได้ดีที่สุดพอดี — นี่ก็เป็นอีกเหตุผลที่การเก็บ hot loop ให้เรียบง่ายเป็นคำแนะนำที่ดีในตัวมันเอง แยกออกจากเรื่อง readability

12. เจอเรื่องนี้ตรงไหนบ้างในเกมจริง

layout แบบ cache-friendly กับ SIMD โผล่มาตลอดในระบบที่ต้องรันทุกเฟรมกับของจำนวนมากที่คล้าย ๆ กัน:

• Particle systems — particle เป็นพัน ๆ ตัว แต่ละตัวถูกอัปเดตด้วยคณิตศาสตร์ง่าย ๆ อย่าง position += velocity * dt ทุกเฟรม งานเล็ก ๆ ที่เหมือนกันทุก element บน array ขนาดใหญ่แบบนี้คือสิ่งที่ SoA กับ SIMD ถูกสร้างมาเพื่อรองรับพอดี
• Physics solvers — การ integrate ความเร็วกับตำแหน่งของ rigid body, การแก้ contact, และการเช็ก bounding box แบบ broad-phase ล้วนรันการคำนวณเล็ก ๆ แบบเดียวกันบน array ขนาดใหญ่ของ body ทั้งหมด
• Skinning — การผสมตำแหน่งของแต่ละ vertex จาก bone matrix สูงสุด 4 ตัวพร้อม weight ต่อ bone เป็นคณิตศาสตร์ที่เหมือนกันและเป็นอิสระต่อกัน ทำซ้ำสำหรับทุก vertex ของทุก mesh ทุกเฟรม
• Culling — frustum culling กับ occlusion culling ต้องเทส bounding box หรือ sphere เป็นพัน ๆ ตัวกับ plane ของกล้องทุกเฟรม SIMD ทำให้เทส object ได้ 4 หรือ 8 ตัวต่อคำสั่งเดียว และการเก็บข้อมูล bounding แบบ SoA (array แยกสำหรับ center X, center Y, center Z, radius) ทำให้การเทสนี้ไหลผ่าน memory ได้อย่างเรียบร้อย

สังเกตรูปแบบที่เหมือนกันไหม: array ขนาดใหญ่ของ element ที่แทบจะเป็นอิสระต่อกัน ทำคณิตศาสตร์ปริมาณเท่า ๆ กันทุกเฟรม รูปแบบนี้คือสิ่งที่บทนี้ทั้งบทพยายาม optimize มาตลอด — ไม่ใช่เรื่องบังเอิญเลยที่ engine จัด hot data แบบนี้โดยตั้งใจ

13. เอา SIMD มาใช้ใน C# โดยไม่ต้องเขียน Intrinsic: Burst กับ Job System

ทุกอย่างในบทนี้ที่ผ่านมาเป็น C++ ทั้งหมด ส่วน C# เฉย ๆ นั้น auto-vectorize ได้ไม่แน่นอน และ C# ธรรมดาก็ไม่ได้ให้เราเขียน intrinsic เองได้ง่าย ๆ แบบ C++ Unity แก้ปัญหานี้ด้วยสองส่วนที่ทำงานร่วมกัน คือ Burst compiler กับ Job System

Burst เอา subset ของ C# ที่ถูกจำกัดไว้เพื่อ performance สูง ๆ — value type, NativeArray, ไม่มี managed class หรือ garbage collection อยู่ในส่วนที่ compile — แล้ว compile ตรงไปเป็น native machine code ที่ optimize แล้ว โดยใช้ LLVM backend ตัวเดียวกับที่ขับเคลื่อน -O3 ของ Clang รวมถึง auto-vectorization ด้วย method ที่ติด [BurstCompile] จะไม่ถูก interpret หรือ JIT-compile แบบ C# ปกติ — มันถูก compile ล่วงหน้าเป็น machine code ที่ทำ SIMD ได้จริง

Job System จะ schedule งานให้กระจายไปยัง worker thread บนหลาย core อย่างปลอดภัย — ระบบเช็คความปลอดภัยของ Unity จะจับการเข้าถึง memory แบบทับซ้อนที่ไม่ได้ sync กันได้ตั้งแต่ใน editor ก่อนที่มันจะกลายเป็นบั๊กที่ reproduce ยาก IJobParallelFor จะแบ่ง loop บน NativeArray ออกเป็น batch แล้วรัน batch พวกนั้นกระจายไปตาม worker thread ที่มีอยู่

using Unity.Burst;
using Unity.Collections;
using Unity.Jobs;
using Unity.Mathematics;

[BurstCompile]
public struct UpdatePositionsJob : IJobParallelFor
{
    [ReadOnly] public NativeArray<float3> velocities;
    public NativeArray<float3> positions;
    public float deltaTime;

    public void Execute(int index)
    {
        positions[index] = positions[index] + velocities[index] * deltaTime;
    }
}

NativeArray<float3> positions = new NativeArray<float3>(1000000, Allocator.Persistent);
NativeArray<float3> velocities = new NativeArray<float3>(1000000, Allocator.Persistent);
// ... fill both with starting data ...

var job = new UpdatePositionsJob {
    positions = positions,
    velocities = velocities,
    deltaTime = Time.deltaTime
};

JobHandle handle = job.Schedule(positions.Length, 64); // batch size 64
handle.Complete();

อ่านโค้ด job

• [BurstCompile] — compile method Execute ของ job นี้ด้วย Burst แทนที่จะรันมันแบบ managed C# ธรรมดา
• NativeArray<float3> — buffer แบบแบน, unmanaged, ต่อเนื่องกัน วาง layout เหมือน C array เป๊ะ ๆ นี่คือสิ่งที่ทำให้ auto-vectorizer ของ Burst ทำงานได้ — List<float3> แบบ managed อาจถูก garbage collector ย้ายที่เมื่อไหร่ก็ได้ เลย compile แบบนี้กับมันไม่ได้
• [ReadOnly] — hint ว่า job นี้แค่อ่าน velocities เท่านั้น ทำให้ระบบความปลอดภัยยอมให้ทับซ้อนกับ job อื่นได้มากขึ้น
• Execute(int index) — เนื้อโค้ดที่รันต่อหนึ่ง element Job System จะเรียกฟังก์ชันนี้ครั้งละหนึ่ง index แบ่งเป็น batch ละ 64 (argument ตัวที่สองของ Schedule) กระจายไปตาม worker thread

วัดผลตอนอัปเดตตำแหน่งของ particle 1,000,000 ตัวจากความเร็วของมัน หนึ่งครั้งต่อเฟรม:

plain C# foreach, List<ParticleAoS>, no Burst:   38.70 ms
Burst IJobParallelFor, NativeArray<float3>:        1.15 ms

ช่องว่าง 33 เท่านี้ใหญ่กว่า 2.9 เท่าจากตัวอย่าง SIMD ล้วน ๆ ใน C++ ของ section 10 เพราะมีสามผลรวมกันอยู่: auto-vectorization ของ SIMD ในแต่ละ thread, worker thread หลายตัวรันขนานกันข้าม core, และการข้าม overhead ของ managed object กับ garbage collector ที่ loop foreach บน List<ParticleAoS> ธรรมดาต้องแบกไว้ แต่ทั้งหมดนี้จะไม่เกิดขึ้นเลยถ้าข้อมูลไม่ได้ถูกจัดเป็น NativeArray แบบแบนไว้ตั้งแต่แรก — คือ storage ทรง SoA จาก section 5 กับ 6 ที่ตอนนี้ให้ผลตอบแทนตรง ๆ ใน C# แล้ว

14. Glossary

• Cache — memory ก้อนเล็ก ๆ ที่เร็ว เก็บสำเนาของข้อมูลที่เพิ่งใช้หรือคาดว่าจะถูกใช้ อยู่ระหว่าง CPU core กับ RAM
• Cache line — ก้อนขนาดคงที่ (64 ไบต์ในเกือบทุก CPU สมัยใหม่) ที่ cache ดึงเข้าหรือเอาออกทีละก้อน
• Cache hit / cache miss — hit คือข้อมูลอยู่ใน cache อยู่แล้ว (เร็ว) ส่วน miss คือ cache ต้องไปดึงจากชั้นที่ช้ากว่า ไล่ไปจนถึง RAM ได้ (ช้า)
• L1 / L2 / L3 cache — ชั้นของ cache ระหว่าง core กับ RAM เรียงจากเล็กสุด/เร็วสุด (L1) ไปใหญ่สุด/ช้าสุด (L3)
• Latency (in cycles) — จำนวน clock cycle ของ CPU ที่ operation หนึ่งใช้จนเสร็จ ใช้เปรียบเทียบความเร็วของ register, cache, และ RAM ในบทนี้
• Memory bandwidth — จำนวนไบต์ต่อวินาทีที่เคลื่อนย้ายระหว่าง RAM กับ CPU ได้จริง เป็น bottleneck ในโค้ดแบบ "memory-bound"
• Row-major / column-major — ลำดับที่ array 2 มิติถูกวางใน memory แบบแบน array ของ C กับ C++ เป็นแบบ row-major (แต่ละ row เก็บต่อเนื่องกัน)
• AoS (Array of Structs) — array ที่แต่ละ element เป็น struct ที่เก็บทุก field ของ object นั้นไว้ด้วยกัน
• SoA (Struct of Arrays) — layout ที่มี array แยกหนึ่งอันต่อหนึ่ง field ครอบคลุมทุก object แทนที่จะเป็น struct หนึ่งอันต่อหนึ่ง object
• ECS (Entity-Component-System) — architecture pattern (ครอบคลุมเต็ม ๆ ใน Phase 16) ที่เก็บแต่ละ component type เป็น array ที่อัดแน่นของตัวเองครอบคลุมทุก entity — คือ SoA ที่เอามาใช้กับทั้งเกมเวิลด์
• Prefetching — การที่ฮาร์ดแวร์ (หรือ hint ที่เขียนเอง) ดึง cache line เข้ามาก่อนที่จะถูกขอจริง ๆ โดยอิงจาก pattern การเข้าถึงที่คาดเดาได้
• False sharing — ความช้าที่เกิดจาก thread สองตัวเขียนไปยังตัวแปรคนละตัวที่บังเอิญอยู่ cache line เดียวกัน ทำให้ cache line เด้งไปมาระหว่าง cache ของแต่ละ core
• SIMD (Single Instruction, Multiple Data) — คำสั่ง CPU หนึ่งคำสั่งที่ทำ operation เดียวกันกับหลายค่า (lane) พร้อมกัน
• Lane — ช่องของค่าหนึ่งค่าภายใน register ของ SIMD register ขนาด 128-bit มี 4 lane สำหรับ float
• Vectorization / auto-vectorization — การแปลง loop แบบ scalar ให้เป็นคำสั่ง SIMD ไม่ว่าจะเขียนเอง (intrinsic) หรือให้ compiler ทำให้อัตโนมัติ
• Intrinsics — ฟังก์ชันที่ compiler เตรียมไว้ให้ (เช่น _mm_add_ps) ที่แม็ปตรงไปยังคำสั่ง machine ของ SIMD คำสั่งเดียว
• Burst — compiler แบบ ahead-of-time ของ Unity ที่แปลง C# subset ที่จำกัดไว้ ให้กลายเป็น native machine code ที่ optimize และ auto-vectorize แล้ว
• Job System — ระบบของ Unity สำหรับ schedule งานกระจายไปยัง worker thread หลายตัวอย่างปลอดภัย รวมถึง IJobParallelFor สำหรับ loop แบบ data-parallel
• NativeArray — array แบบแบน, unmanaged, ต่อเนื่องกันของ Unity ใช้งานได้จาก job ที่ compile ด้วย Burst (ต่างจาก type แบบ managed อย่าง List<T>)
• Blittable — type ที่มี memory layout เหมือนกันทั้งฝั่ง managed และ unmanaged (เช่น float, int, หรือ struct ง่าย ๆ ของสิ่งพวกนั้น) — จำเป็นสำหรับใช้ใน job ของ Burst

15. แบบฝึกหัด

double columnSum(const std::vector<float>& matrix, int N, int col) {
    double total = 0.0;
    for (int row = 0; row < N; row++) {
        total += matrix[row * N + col];
    }
    return total;
}

double sumAllColumns(const std::vector<float>& matrix, int N) {
    double grand = 0.0;
    for (int col = 0; col < N; col++) {
        grand += columnSum(matrix, N, col);
    }
    return grand;
}

double sumAllColumnsFast(const std::vector<float>& matrix, int N) {
    double grand = 0.0;
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            grand += matrix[row * N + col];
        }
    }
    return grand;
}

struct Enemy {
    float x, y;
    float health;
    float armor;
    char name[32];
    int aiState;
    float attackCooldown;
};

int countAlive(const std::vector<Enemy>& enemies) {
    int alive = 0;
    for (const auto& e : enemies) {
        if (e.health > 0.0f) alive++;
    }
    return alive;
}

struct EnemySoA {
    std::vector<float> x, y;
    std::vector<float> health;    // countAlive only needs this array
    std::vector<float> armor;
    std::vector<std::string> name;
    std::vector<int> aiState;
    std::vector<float> attackCooldown;
};

int countAliveSoA(const EnemySoA& enemies) {
    int alive = 0;
    for (float h : enemies.health) {
        if (h > 0.0f) alive++;
    }
    return alive;
}

[BurstCompile]
public struct ScaleJob : IJobParallelFor
{
    public NativeArray<float> values;
    public float factor;

    public void Execute(int index)
    {
        values[index] = values[index] * factor;
    }
}

var job = new ScaleJob { values = values, factor = 2.0f };
JobHandle handle = job.Schedule(values.Length, 64);
handle.Complete();