3.1 หน่วยความจำและ CPU

คุณรู้อยู่แล้วว่า memory คือแถวยาว ๆ ของ byte ที่มีเลข address และ pointer ก็คือแค่หนึ่งในเลขพวกนั้น บทก่อน ๆ ก็เคยพูดผ่าน ๆ ว่าการอ่าน memory "ตามลำดับ" เร็วกว่าการกระโดดไปมา เพราะมีสิ่งที่เรียกว่า cache แต่บทพวกนั้นไม่ได้อธิบายว่า ทำไม หรือมันมีต้นทุนแค่ไหนจริง ๆ บทนี้จะเปิดเรื่องนั้น: สายพานของที่เก็บข้อมูลที่ CPU ต้องดึงข้อมูลผ่านก่อนจะใช้งานได้, ทำไม CPU ไม่เคยดึงข้อมูลทีละ byte เดียว และทำไมโค้ดสองชิ้นที่ทำงานปริมาณเท่ากันเป๊ะ — จำนวน operation เท่ากัน, Big-O เท่ากัน — ถึงรันเร็วช้าต่างกันได้มหาศาล แค่เพราะข้อมูลถูกจัดเรียงต่างกัน

เหมือนเดิม: โค้ด C++ สั้น ๆ ที่รันได้จริง, output จริง (หรือถ้าเป็นเรื่องภายใน CPU ที่ไม่มีอะไรให้ print ก็จะมี worked trace ให้ไล่ดูแทน) แล้วค่อยอธิบายแบบง่าย ๆ บทนี้มี benchmark เต็มรูปแบบสองอัน ลองพิมพ์ตามแล้วรันดูเอง ตัวเลข millisecond ที่คุณได้จะไม่เท่ากับตัวเลขตัวอย่างในนี้เป๊ะ — เครื่องคุณไม่ใช่เครื่องผม — แต่เวอร์ชันไหนชนะ และชนะประมาณเท่าไหร่ จะไม่เปลี่ยน

1. Memory hierarchy: register, cache, RAM

CPU ไม่ได้เก็บข้อมูลไว้ในระยะห่างเท่ากันหมด บางที่เก็บอยู่ในตัวชิป CPU เลย ตอบสนองแทบจะทันที บางที่อยู่ห่างออกไปนิดหน่อย และบางที่อยู่คนละชิปไปเลย ซึ่งกินเวลาเดินทางมากกว่ากันเยอะ วิศวกรออกแบบชิปเลยจัดเป็นหลายชั้น แต่ละชั้นเล็กกว่าและเร็วกว่าชั้นที่อยู่ล่างมัน กองชั้นแบบนี้เรียกว่า memory hierarchy

• register คือช่องเก็บข้อมูลเล็ก ๆ ที่ฝังอยู่ใน CPU เลย — บนเครื่อง 64-bit หนึ่ง register เก็บเลขได้ 8 byte มีอยู่แค่ไม่กี่สิบตัวเท่านั้น การอ่าน register ไม่ได้เป็นการ "fetch" จริง ๆ ด้วยซ้ำ มันเกิดขึ้นเป็นส่วนหนึ่งของการรัน instruction เลย
• L1, L2, L3 cache (cache คือพื้นที่เก็บข้อมูลเล็ก ๆ ที่เร็ว ไว้เก็บสำเนาข้อมูลที่ CPU น่าจะต้องใช้อีกในไม่ช้า) อยู่บนชิปเดียวกับ core ของ CPU แต่ไกลจาก core มากกว่า register L1 เล็กสุดและใกล้สุด ปกติเป็นของ core เดียว L2 ใหญ่กว่าและไกลขึ้นนิดหน่อย L3 เป็น cache ระดับที่ใหญ่สุด และปกติใช้ร่วมกันทุก core ในชิป
• RAM (main memory คือ memory หลักหน่วยกิกะไบต์ที่คุณเรียนไปในบท C นั่นแหละ ที่ที่ address กับ malloc ชี้ไปจริง ๆ) อยู่บนชิปของตัวเอง ต้องเดินทางผ่านสายไฟออกนอก CPU ไป มันใหญ่กว่า cache ทุกระดับมาก และช้ากว่า L1 ประมาณ 100 เท่า

ตัวเลขข้างบน (nanosecond, kilobyte, megabyte) เป็นตัวเลขคร่าว ๆ และจะต่างกันไปในแต่ละรุ่น CPU — อย่าไปท่องจำว่าเป๊ะขนาดนั้น สิ่งที่สำคัญ และเป็นจริงแทบทุกเครื่องที่คุณจะเอาไป profile เกม คือ รูปทรง: แต่ละชั้นที่ลงมาต่ำกว่านั้นใหญ่ขึ้นและช้าลงประมาณหนึ่งอันดับ (order of magnitude) จากชั้นที่อยู่เหนือมัน

ขยาย nanosecond ให้เป็นสเกลที่มนุษย์รู้สึกได้

nanosecond มันเล็กเกินกว่าจะรู้สึกได้ ลองขยายมันดู สมมติว่าอ่านจาก L1 cache ใช้เวลา 1 วินาที ในสเกลนี้ อ่านจาก L2 ใช้ประมาณ 4 วินาที อ่านจาก L3 ใช้ประมาณ 15 วินาที และอ่านจาก RAM ใช้เวลานานกว่าหนึ่งนาทีครึ่งไปอีก ถ้าโปรแกรมของคุณต้องเดินทางไป RAM แบบนี้เป็นล้าน ๆ ครั้ง เพราะข้อมูลกระจัดกระจายอยู่ทั่ว memory แทนที่จะเป็นแค่ไม่กี่ครั้งเพราะข้อมูลอยู่ติดกัน คุณจะเห็นเลยว่าทำไมความต่างนี้ถึงกลายเป็น frame time ที่วัดได้จริง

นี่คือจุดที่ register เข้ามาเกี่ยวในลูปเล็ก ๆ ที่คุ้นเคย ตัวอย่างนี้ไม่มีอะไรให้ print — ส่วนที่น่าสนใจคือข้อมูลแต่ละก้อนอยู่ตรงไหนจริง ๆ ระหว่างที่ลูปรัน ไม่ใช่มัน output อะไรออกมา

int sum = 0;
for (int i = 0; i < 4; i++) {
    sum += arr[i];
}

2. Cache line: CPU ไม่เคยอ่านทีละ byte เดียว

นี่คือรายละเอียดที่อธิบายเกือบทุกอย่างที่เหลือในบทนี้ เมื่อ CPU ต้องการ byte หนึ่งตัว, int หนึ่งตัว หรือข้อมูลชิ้นเล็ก ๆ จาก RAM ฮาร์ดแวร์จะไม่ไปดึงแค่ค่านั้นค่าเดียว แต่จะดึงก้อนขนาดคงที่ที่มีค่านั้นอยู่ในนั้น เรียกว่า cache line — ปกติคือ 64 byte บน CPU ของโน้ตบุ๊คกับเดสก์ท็อปยุคใหม่ ก้อน 64 byte ทั้งก้อนเคลื่อนย้ายไปด้วยกันเป็นหน่วยเดียว ระหว่าง RAM กับ cache

ลองนึกถึงโกดังที่ส่งของเป็นพาเลทเต็ม ๆ เท่านั้น ไม่เคยส่งทีละกล่อง สั่งกล่องเดียว แต่พาเลททั้งพาเลทมาส่งที่ท่าเรือคุณเลย กล่องอื่น ๆ บนพาเลทนั้นก็มานั่งรออยู่ตรงนั้นด้วย — ฟรี ถ้าคุณบังเอิญต้องใช้มันต่อ

int ธรรมดามีขนาด 4 byte ดังนั้น cache line 64 byte จะจุ int ได้พอดี 16 ตัว แตะ arr[0] เป็นครั้งแรก แล้ว — ตราบใดที่ array เริ่มต้นที่จุดเริ่มของ line พอดี ซึ่ง array ที่เพิ่ง allocate ใหม่มักจะเป็นแบบนั้น — arr[1] ถึง arr[15] จะมาถึงในทริปเดียวกัน โดยไม่มีต้นทุนเพิ่มเลย

std::vector<int> arr(16, 0);
for (int i = 0; i < 16; i++) arr[i] = i;

int total = 0;
for (int i = 0; i < 16; i++) total += arr[i];   // reads arr[0] .. arr[15]

Worked trace: ลูปที่สองอ่านค่า 16 ตัว แต่มันออกจากชิปแค่ครั้งเดียวเท่านั้น การอ่าน arr[0] ทำให้เกิดการดึง cache line หนึ่งครั้งซึ่งบังเอิญครอบคลุม array ทั้งก้อนพอดี ดังนั้นการอ่านอีก 15 ครั้งที่เหลือมีอยู่ใน L1 อยู่แล้ว — ไม่ต้องเดินทางไป RAM เลยสักครั้ง

3. Spatial locality: เดินไล่ array ตามลำดับถึงเร็ว

แนวคิดจากหัวข้อที่แล้วมีชื่อเรียกว่า spatial locality ("spatial" แปลว่าเกี่ยวกับตำแหน่ง) มันบอกว่าถ้าโปรแกรมแตะ address หนึ่ง มันมักจะแตะ address ที่อยู่ใกล้ ๆ ในไม่ช้า การเดินไล่ array จาก index 0 ขึ้นไปคือตัวอย่างที่ชัดที่สุดของ spatial locality เพราะสมาชิกตัวถัดไปการันตีว่าอยู่ห่างจากตัวก่อนหน้าแค่ 4 byte เสมอ

ยังมีผลพลอยได้อีกชั้นซ้อนอยู่ด้านบนนี้ CPU หลายตัวมี hardware prefetcher — ฮาร์ดแวร์ที่คอยดู pattern การเข้าถึง memory ของคุณ สังเกตว่า "โค้ดนี้กำลังอ่าน address ถัด ๆ กันเป็นเส้นตรง" แล้วเริ่มดึง cache line ถัดไปเข้ามาล่วงหน้า ก่อนที่โค้ดคุณจะขอด้วยซ้ำ การเข้าถึงแบบเรียงลำดับ (sequential) เลยได้ประโยชน์สองต่อ: สมาชิกที่อยู่ใน line เดียวกับที่คุณกำลังใช้ก็ฟรีอยู่แล้ว แถม prefetcher ก็แอบโหลด line ถัดไปในพื้นหลังไปพร้อม ๆ กับที่คุณยังใช้ line นี้ไม่เสร็จ

cache miss คือสิ่งที่เพิ่งเกิดขึ้น 4 ครั้งข้างบน: CPU ขอข้อมูลที่ยังไม่มีอยู่ใน cache เลยต้องรอเดินทางไป RAM แบบช้า ๆ ส่วน cache hit คือการอ่านอีก 60 ครั้งที่เหลือ: ข้อมูลอยู่ตรงนั้นอยู่แล้ว เลยแทบไม่มีต้นทุนอะไรเลย การเข้าถึงแบบ sequential ทำให้จำนวน miss น้อยมากเมื่อเทียบกับจำนวนสมาชิกที่คุณแตะจริง ๆ

4. Cache miss: กระโดดไปมาถึงช้า

ทีนี้ลองทำตรงข้ามดูบ้าง แทนที่จะเดินไล่ array ให้ไล่ตามสาย pointer ที่แต่ละ node ถูก allocate แยกกันและบังเอิญไปตกอยู่ที่ address ที่ไม่เกี่ยวข้องกันเลยบน heap — นี่คือหน้าตาของ linked list ใน memory จริง ๆ พอคุณ insert node ทีละตัว ไม่มี stride (ระยะห่างคงที่) ระหว่าง node หนึ่งกับตัวถัดไป ดังนั้นทั้ง spatial locality และ prefetcher ช่วยอะไรไม่ได้เลย แต่ละก้าวเหมือนโยนเหรียญไปตกที่ RAM คนละส่วนกันโดยสิ้นเชิง

pattern แบบนี้ — ไล่ตาม pointer เพื่อหาสิ่งถัดไปที่จะอ่าน ซ้ำไปซ้ำมา โดยไม่มี stride ของ address ที่คาดเดาได้ — เรียกว่า pointer chasing ทุกก้าวอาจมีต้นทุนเต็ม ๆ ~100 ns ไป RAM ตามหัวข้อ 1 แทนที่จะเป็น ~1 ns ของ L1 hit array ในหัวข้อ 3 แตะ 64 สมาชิกแล้วเดินทางไป RAM แค่ 4 ครั้ง ส่วนอันนี้แตะ 64 สมาชิกแต่เดินทางไป RAM ประมาณ 64 ครั้ง ทราฟฟิกไป RAM มากกว่ากันถึง 16 เท่า เพื่อบวกเลขชุดเดียวกันเป๊ะ ๆ

5. Benchmark จริง: contiguous array เทียบกับ pointer chasing

ถึงเวลาดูของจริง ไม่ใช่แค่คิดตาม โปรแกรมนี้สร้างจำนวนเต็มสองล้านตัวชุดเดียวกันด้วยสองวิธี: วิธีแรกเป็น array แบบ contiguous ธรรมดา วิธีที่สองเป็น linked list ที่ node ถูกสร้างเรียงลำดับ แต่แล้วเอามาโยงต่อกันแบบสลับลำดับ (shuffle) — ดังนั้นการไล่ list จึงเท่ากับกระโดดไป address แบบสุ่มแทบทุกก้าว เหมือนใน diagram ของหัวข้อ 4 เป๊ะ ทั้งสองแบบบวกค่าทุกตัวครั้งเดียวเท่ากัน ดังนั้นทั้งคู่ทำงานแบบ O(n) เหมือนกัน

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>
#include <numeric>

struct Node {
    int value;
    Node* next;
};

int main() {
    const int N = 2000000;

    // ---- contiguous: a plain array ----
    std::vector<int> arr(N);
    std::iota(arr.begin(), arr.end(), 0);          // fill 0, 1, 2, 3, ...

    auto t0 = std::chrono::steady_clock::now();
    long long sum1 = 0;
    for (int i = 0; i < N; i++) sum1 += arr[i];
    auto t1 = std::chrono::steady_clock::now();

    // ---- scattered: the same N values, but as a linked list whose ----
    // ---- nodes are chained together in shuffled order             ----
    std::vector<Node*> nodes(N);
    for (int i = 0; i < N; i++) nodes[i] = new Node{i, nullptr};

    std::vector<int> order(N);
    std::iota(order.begin(), order.end(), 0);
    std::mt19937 rng(42);
    std::shuffle(order.begin(), order.end(), rng);
    for (int i = 0; i + 1 < N; i++)
        nodes[order[i]]->next = nodes[order[i + 1]];
    Node* head = nodes[order[0]];

    auto t2 = std::chrono::steady_clock::now();
    long long sum2 = 0;
    for (Node* p = head; p != nullptr; p = p->next) sum2 += p->value;
    auto t3 = std::chrono::steady_clock::now();

    double ms1 = std::chrono::duration<double, std::milli>(t1 - t0).count();
    double ms2 = std::chrono::duration<double, std::milli>(t3 - t2).count();

    std::cout << "contiguous sum = " << sum1 << "  time = " << ms1 << " ms\n";
    std::cout << "scattered  sum = " << sum2 << "  time = " << ms2 << " ms\n";

    for (Node* p : nodes) delete p;
}

ตัวอย่าง output (รันครั้งหนึ่งบนโน้ตบุ๊ค — ตัวเลข millisecond ของคุณจะไม่เท่ากันเป๊ะ แต่ช่องว่างระหว่างสองอันจะไม่เปลี่ยน):

contiguous sum = 1999999000000  time = 2.8 ms
scattered  sum = 1999999000000  time = 41.3 ms

ผลรวมทั้งสองเท่ากันเป๊ะ คือ 1999999000000 — ผลรวมของจำนวนเต็มทุกตัวตั้งแต่ 0 ถึง 1,999,999 เพราะโครงสร้างทั้งสองแบบเก็บค่าชุดเดียวกันเป๊ะ แค่เยี่ยมชมคนละลำดับ ทั้งสองลูปเป็น O(n): บวกหนึ่งครั้งต่อสมาชิก สองล้านสมาชิก แต่เวอร์ชันที่กระจัดกระจายใช้เวลานานกว่าประมาณ 15 เท่า ไม่มีอะไรเกี่ยวกับ algorithm เปลี่ยนไปเลย สิ่งที่เปลี่ยนคือสิ่งที่หัวข้อ 2 ถึง 4 อธิบายไว้เป๊ะ ๆ: เวอร์ชัน array ต้องเดินทางไป RAM แค่ทุก ๆ 16 สมาชิก ในขณะที่เวอร์ชัน list ต้องเดินทางแทบทุกก้าวเดียว

6. CPU ทำ pipeline กับ instruction ยังไง

แยกจากเรื่อง cache ไปเลย CPU ยุคใหม่ยังทำให้เร็วขึ้นด้วยการไม่รัน instruction หนึ่งตัวให้จบตั้งแต่ต้นจนจบก่อนเริ่มตัวถัดไป แต่จะแบ่งการรัน instruction ออกเป็นขั้น ๆ — เวอร์ชันย่อ ๆ มี 4 ขั้น: fetch (อ่าน instruction จาก memory), decode (แปลความหมายว่ามันคืออะไร), execute (ทำงานจริง), writeback (เก็บผลลัพธ์) CPU จริง ๆ มีขั้นเยอะกว่า 4 มาก แต่ 4 ขั้นก็พอให้เห็นภาพแล้ว

CPU ซ้อนขั้นเหล่านี้ข้าม instruction กันไปมา เหมือนสายพานประกอบสินค้า: ระหว่างที่ instruction 1 กำลัง execute instruction 2 ก็ decode ไปพร้อมกันได้แล้ว และ instruction 3 ก็ fetch ไปพร้อมกันได้แล้วเหมือนกัน การซ้อนกันแบบนี้เรียกว่า pipelining

pipelining จะคุ้มก็ต่อเมื่อ CPU ป้อนงานให้สายพานได้ต่อเนื่อง — มันต้องรู้ล่วงหน้าหลาย instruction ว่าตัวถัดไปคืออะไร เพื่อจะ fetch กับ decode ล่วงหน้าได้ สำหรับโค้ดตรง ๆ ธรรมดาเรื่องนี้ง่าย: instruction ต่อ instruction เรียงกันไป แต่ branch — เช่น if, เงื่อนไขของลูป, switch — ทำลายสมมติฐานนั้น เพราะ instruction ถัดไปขึ้นอยู่กับค่าที่ CPU ยังคำนวณไม่เสร็จ

7. Branch prediction: การเดาว่า if จะไปทางไหน

ถ้า CPU หยุดรอเฉย ๆ ทุกครั้งที่เจอ branch จนกว่าเงื่อนไขจะคำนวณเสร็จ pipeline จากหัวข้อที่แล้วจะว่างเปล่าแล้วต้องเติมใหม่ทุก if เลย — ช้ามาก แทนที่จะทำแบบนั้น CPU จะ เดา ว่า branch จะไปทางไหน โดยใช้ฮาร์ดแวร์เล็ก ๆ ชิ้นหนึ่งเรียกว่า branch predictor แล้วรีบ fetch, decode และแม้แต่ execute instruction ตามเส้นทางที่เดาไว้ทันที ก่อนที่จะรู้คำตอบจริง ๆ ด้วยซ้ำ การรัน instruction ตามการเดาแบบนี้เรียกว่า speculative execution

การเดาของ predictor มักอิงจากประวัติล่าสุดของ branch ตัวนั้น: ถ้า if ตัวนี้ถูก take (เข้าเงื่อนไข) มาหลายครั้งติดกันล่าสุด มันก็จะพนันว่าจะถูก take อีก วิธีนี้ได้ผลดีมากกับ branch ที่แทบจะไปทางเดียวตลอด หรือมี pattern ซ้ำ ๆ สม่ำเสมอ — เช่นเงื่อนไขจบลูป ที่เป็น "ยังไม่จบ" ติดกันหลายพันครั้งแล้วค่อยเป็น "จบ" แค่ครั้งเดียว แต่มันได้ผลแย่มากเมื่อผลลัพธ์เหมือนโยนเหรียญที่ไม่มี pattern ให้เรียนรู้เลย ซึ่งตรงกับ if บนข้อมูลสุ่มที่ไม่เรียงลำดับพอดี

ถ้าเดาถูก ต้นทุนแทบจะเป็นศูนย์ — pipeline ก็ทำงานต่อไปตามที่เริ่มไว้แล้ว แต่ถ้าเดาผิด นั่นเรียกว่า misprediction: instruction ทุกตัวที่ CPU รันแบบเก็งไปตามเส้นทางที่ผิดต้องถูกทิ้งไปหมด แล้วต้อง fetch ใหม่จาก instruction ที่ถูกต้อง เรียกว่า pipeline flush และมันมีต้นทุนประมาณเท่ากับ cycle ที่เสียเปล่าไปทั้ง pipeline — มักจะสิบถึงยี่สิบ cycle หรือมากกว่านั้น ทุกครั้งที่เกิดขึ้น

8. Benchmark จริง: ข้อมูลที่เรียงแล้วเทียบกับยังไม่เรียง

นี่คือวิธีคลาสสิกที่จะเห็นต้นทุนของ branch misprediction ด้วยตาตัวเอง โค้ดข้างล่างเติม array ด้วยค่า byte สุ่ม (ค่า 0-255) แล้วบวกเฉพาะตัวที่มีค่า 128 ขึ้นไป มันรันลูปบวกแบบเดียวกันเป๊ะสองรอบ: รอบแรกตอนข้อมูลยังเรียงแบบสุ่มอยู่ และรอบสองหลังจาก sort array ก่อน ผลรวมทั้งหมดเปลี่ยนไม่ได้จากการ sort — ค่าทุกตัวยังอยู่ครบ แค่เรียงลำดับต่างกัน — แต่ branch ข้างในลูปกลับเดาง่ายขึ้นเยอะทันที

#include <algorithm>
#include <vector>
#include <chrono>
#include <random>
#include <iostream>

int main() {
    const int N = 10000000;
    std::vector<int> data(N);

    std::mt19937 rng(7);
    std::uniform_int_distribution<int> dist(0, 255);
    for (int i = 0; i < N; i++) data[i] = dist(rng);

    // ---- unsorted: roughly 50/50, the branch is hard to guess ----
    auto t0 = std::chrono::steady_clock::now();
    long long sum1 = 0;
    for (int i = 0; i < N; i++)
        if (data[i] >= 128) sum1 += data[i];
    auto t1 = std::chrono::steady_clock::now();

    // ---- sorted: long runs of "no", then long runs of "yes" ----
    std::sort(data.begin(), data.end());

    auto t2 = std::chrono::steady_clock::now();
    long long sum2 = 0;
    for (int i = 0; i < N; i++)
        if (data[i] >= 128) sum2 += data[i];
    auto t3 = std::chrono::steady_clock::now();

    double ms1 = std::chrono::duration<double, std::milli>(t1 - t0).count();
    double ms2 = std::chrono::duration<double, std::milli>(t3 - t2).count();

    std::cout << "unsorted: sum = " << sum1 << "  time = " << ms1 << " ms\n";
    std::cout << "sorted:   sum = " << sum2 << "  time = " << ms2 << " ms\n";
}

ตัวอย่าง output (รันครั้งหนึ่งบนโน้ตบุ๊ค — ผลรวมที่แน่นอนขึ้นอยู่กับ random seed แต่ผลรวมทั้งสองจะเท่ากันเสมอ และเวอร์ชัน sorted จะชนะขาดทุกครั้ง):

unsorted: sum = 957530441  time = 54.1 ms
sorted:   sum = 957530441  time = 11.4 ms

ผลรวมเท่ากันทั้งสองรอบ — การ sort แค่จัดลำดับ array ใหม่ ไม่ได้เปลี่ยนว่าค่าไหนมีค่า 128 ขึ้นไปหรือไม่ ลูปเดียวกัน เงื่อนไขเปรียบเทียบเดียวกัน ปริมาณการคำนวณเท่ากัน แต่รอบที่ sorted แล้วเสร็จเร็วกว่าประมาณ 5 เท่า ก่อน sort เงื่อนไข data[i] >= 128 เป็นเหมือนการโยนเหรียญทุกก้าว ดังนั้น branch predictor จะเดาผิดเกือบครึ่งหนึ่ง — เกิด pipeline flush แทบทุกสมาชิกตัวเว้นตัว หลัง sort ค่า "ไม่เข้าเงื่อนไข" ทั้งหมดจะถูกจัดกลุ่มไว้ข้างหน้า และค่า "เข้าเงื่อนไข" ทั้งหมดถูกจัดกลุ่มไว้ข้างหลัง ดังนั้น branch จะตอบ "ไม่" ติดกันหลายพันครั้ง แล้วค่อยตอบ "ใช่" ติดกันหลายพันครั้ง predictor จะจับ pattern ของแต่ละช่วงยาว ๆ ได้เกือบจะทันที และเดาถูกแทบทุกครั้ง โดยมี misprediction แค่สองครั้งตลอดทั้งรอบ — ครั้งหนึ่งตอนเริ่ม อีกครั้งตรงจุดที่ช่วงเปลี่ยนจาก "ไม่" เป็น "ใช่"

9. บทสรุปสำหรับคนเขียนเกม: layout ชนะ algorithm ที่ฉลาด

เอาหัวข้อ 5 กับ 8 มาวางคู่กัน จะเห็น pattern ชัดเจนเลย ทั้งสอง benchmark ไม่ได้เปลี่ยน algorithm เลยแม้แต่นิดเดียว — ลูปเดิม เงื่อนไขเปรียบเทียบเดิม Big-O เดิม คำตอบสุดท้ายเดิม สิ่งเดียวที่เปลี่ยนคือข้อมูลอยู่ใน memory ยังไง หรือถูกเยี่ยมชมตามลำดับไหน แค่นั้นเองก็คุ้มค่าความต่างของเวลาจริง 5 ถึง 15 เท่าแล้ว นั่นใหญ่กว่าการปรับปรุง algorithm ส่วนใหญ่ที่มือใหม่มักจะหาเจอ และมันไม่มีต้นทุนเพิ่มเลยถ้าคุณคิดเรื่องนี้ไว้ตั้งแต่แรก

นี่คือเหตุผลเป๊ะ ๆ ว่าทำไมบท data structure ที่แล้วถึงพบว่า std::vector ชนะ std::list ทั้งที่ทั้งคู่เป็น O(n) เวลา iterate — ตอนนี้คุณรู้เหตุผลฝั่งฮาร์ดแวร์แล้ว: memory แบบ contiguous แปลว่า cache miss น้อย และมี stride ที่คาดเดาได้ให้ prefetcher เกาะไปด้วย ในขณะที่ node ที่กระจัดกระจายแปลว่า cache miss แทบทุกก้าว ตรรกะเดียวกันนี้ใช้ได้กับ branch ด้วย: ลูปที่วนบนข้อมูลที่ sort หรือแบ่งกลุ่มไว้แล้ว ซึ่ง branch เดิมไปทางเดิมยาว ๆ จะรัน pipeline เต็มสปีด ส่วนลูปที่มี branch แบบโยนเหรียญทุกสมาชิกจะโดน flush ซ้ำแล้วซ้ำเล่า

กฎที่ใช้ได้จริงสำหรับคนเขียนเกม: เมื่อสองวิธีมี Big-O ใกล้เคียงกัน ให้เลือกวิธีที่ hot loop (ลูปที่รันบ่อยที่สุด) เดินไล่ memory แบบ contiguous ตามลำดับที่คาดเดาได้ และมี branch ที่เรียบง่ายคาดเดาได้ สำหรับจำนวน entity, จำนวน particle และขนาดข้อมูลต่อเฟรมทั่วไปในเกม (หลักพันถึงหลักแสน ไม่ใช่หลักพันล้าน) ความต่างของ constant factor จาก cache miss กับ misprediction มักส่งผลต่อ frame time จริงมากกว่าการเปลี่ยนไปใช้ algorithm ที่ฉลาดกว่า

แอบดูล่วงหน้า: array of structures เทียบกับ structure of arrays

นี่คือจุดที่แนวคิดนี้จะไปต่อในบทหลัง ๆ สมมติคุณมี game entity พันตัว แต่ละตัวมี position, velocity และ health สัญชาตญาณแรกตามธรรมชาติคือทำ struct หนึ่งตัวต่อ entity หนึ่งตัว เก็บไว้ใน array เดียว — เรียกว่า array of structures (AoS) แต่ระบบที่ต้องการแค่ position อย่างเดียว (เช่นการเช็ค collision แบบ broad-phase) ก็ยังต้องลาก velocity กับ health ของทุก entity เข้า cache มาด้วยพร้อมกับ position เพราะทั้งหมดใช้ cache line ร่วมกัน

อีกทางเลือกคือ structure of arrays (SoA) ที่แยก array ต่างหากสำหรับแต่ละ field ลูปที่แตะแค่ position ตอนนี้จะยัด cache line แต่ละอันด้วย position ล้วน ๆ ไม่มีอย่างอื่นเจือปน ไม่เสีย bandwidth ไปกับข้อมูลที่ไม่ต้องใช้เลยแม้แต่นิดเดียว นี่คือแนวคิดหลักของ data-oriented design และเป็นเหตุผลเป๊ะ ๆ ว่าทำไม Unity DOTS/ECS กับ engine ประสิทธิภาพสูงส่วนใหญ่ถึงจัดเรียงข้อมูล entity แบบนี้ คุณไม่จำเป็นต้องสร้าง ECS เต็มรูปแบบเพื่อใช้แนวคิดนี้วันนี้ — แค่แยก array of struct หนึ่งตัวออกเป็น array คู่ขนานไม่กี่ตัว เวลาที่ hot loop แตะแค่บาง field ก็เป็นทริกเดียวกันแล้ว

10. Glossary

• Memory hierarchy — ลำดับชั้นของที่เก็บข้อมูลที่ CPU ต้องดึงข้อมูลผ่าน: register, L1/L2/L3 cache แล้วค่อยถึง RAM แต่ละชั้นใหญ่ขึ้นและช้าลงกว่าชั้นบนมัน
• Register — ช่องเก็บข้อมูลเล็ก ๆ ที่ฝังอยู่ใน CPU เอง เป็นที่ที่ค่าอยู่ได้เร็วที่สุด
• Cache (L1/L2/L3) — พื้นที่เก็บข้อมูลเล็ก ๆ ที่เร็ว อยู่บนชิป CPU เก็บสำเนาข้อมูลจาก RAM ที่เพิ่งใช้หรือกำลังจะใช้ L1 เล็กสุดเร็วสุด L3 ใหญ่สุดช้าสุดในสามระดับ
• RAM (main memory) — pool ของ memory ขนาดใหญ่ที่ address กับ pointer ชี้ไปถึง ใหญ่กว่า cache ทุกระดับมาก และช้ากว่า L1 ประมาณ 100 เท่า
• Cache line — ก้อนขนาดคงที่ (ปกติ 64 byte) ที่เคลื่อนย้ายเป็นหน่วยเดียวระหว่าง RAM กับ cache CPU ไม่เคยดึงข้อมูลน้อยกว่าหนึ่ง line เต็ม ๆ
• Cache hit / cache miss — hit คือข้อมูลที่อยู่ใน cache อยู่แล้ว (ถูก) miss คือข้อมูลที่ไม่มี ต้องเดินทางลงไปที่ชั้นล่างของ hierarchy
• Spatial locality — แนวโน้มที่โปรแกรมซึ่งแตะ address หนึ่งจะแตะ address ที่อยู่ใกล้ ๆ ในไม่ช้า การเข้าถึง array แบบเรียงลำดับคือตัวอย่างคลาสสิก
• Prefetching — ฮาร์ดแวร์สังเกตเห็น pattern การเข้าถึงที่คาดเดาได้ แล้วโหลดข้อมูลล่วงหน้าก่อนที่จะถูกขอจริง ๆ
• Pointer chasing — ไล่ตาม pointer ทีละตัว (เช่นใน linked list) เพื่อหาข้อมูลชิ้นถัดไป มักไม่มี address stride ที่คาดเดาได้ จึงทำให้ prefetch ไม่ได้ผล
• Pipeline (instruction pipeline) — สายพานของ CPU ที่แบ่งการรัน instruction เป็นขั้นซ้อนกัน (fetch, decode, execute, writeback) ทำให้มีหลาย instruction ทำงานพร้อมกันได้
• Latency vs. throughput — latency คือเวลาที่ instruction หนึ่งตัวใช้ตั้งแต่ต้นจนจบ throughput คือจำนวน instruction ที่เสร็จต่อ cycle โดยรวม pipelining เพิ่ม throughput โดยไม่เปลี่ยน latency
• Branch — จุดไหนก็ตามที่การทำงานไปได้สองทางขึ้นไปตามค่าตอน runtime เช่น if, เงื่อนไขลูป, switch
• Branch predictor / speculative execution — ฮาร์ดแวร์ที่เดาว่า branch จะไปทางไหน แล้วรัน instruction ตามเส้นทางที่เดาไว้ก่อนจะรู้คำตอบจริง
• Misprediction / pipeline flush — เมื่อเดาผิด instruction ที่รันแบบเก็งไว้จะถูกทิ้งทั้งหมด แล้วเริ่ม fetch ใหม่จากเส้นทางที่ถูกต้อง เสีย cycle ไปประมาณเท่ากับความลึกของ pipeline
• Data-oriented design — จัดข้อมูลเป็น layout แบบแบนและ contiguous ที่ออกแบบมาเฉพาะ เพื่อให้ hot loop แตะแค่ข้อมูลที่ต้องใช้จริง ลด cache miss ให้น้อยที่สุด
• Array of structures (AoS) / structure of arrays (SoA) — AoS เก็บหนึ่ง struct ต่อหนึ่งรายการใน array เดียว SoA เก็บแต่ละ field ไว้ใน array คู่ขนานของตัวเอง เพื่อให้ลูปที่วนแค่ field เดียวยังคงแน่นด้วยข้อมูลที่เป็นประโยชน์ใน cache

11. แบบฝึกหัด

struct Vec3 { float x, y, z; };   // each float is 4 bytes -> 12 bytes per Vec3

Vec3 positions[1000];

จบบทนี้แล้ว ใต้ algorithm ทุกตัวที่คุณเขียน CPU กำลังดึงข้อมูลของคุณผ่านลำดับชั้นของที่เก็บข้อมูลเป็นก้อน cache line ขนาดคงที่ และทำ pipeline กับ instruction ไปพร้อม ๆ กับเดาว่า branch ของคุณจะไปทางไหน การเข้าถึงแบบ contiguous และเรียงลำดับทำให้ pipeline กับ cache นั้นเต็มและทำงานลื่นไหล ส่วนการเข้าถึงแบบกระจัดกระจายกับ branch แบบโยนเหรียญจะทำให้มันขาดอาหาร หยุดชะงักไปทีละครั้ง จำนิสัยนี้ไว้ใช้ในทุกบทถัดไป: เลือก algorithm ที่สมเหตุสมผล เก็บข้อมูลที่ใช้บ่อยให้ contiguous และ branch ที่ใช้บ่อยให้คาดเดาได้ และวัดผลก่อนที่จะเชื่อการเดาว่าเวอร์ชันไหนเร็วกว่ากัน