Zig Optimization #4: pointer chasing ช้ากว่า array 247 เท่า แต่ SoA ชนะแค่ 9%

เรื่องการจัดวางข้อมูลเป็นหัวข้อที่ชุมชน Zig พูดถึงบ่อยที่สุด ต้นทางคือทอล์กของ Andrew Kelley เรื่อง data-oriented design ที่เล่าว่าเขาลดขนาด token ของคอมไพเลอร์จาก 64 ไบต์เหลือ 5 ไบต์ และลด AST node จาก 120 ไบต์เหลือเฉลี่ย 15.6 ไบต์

ตัวเลขพวกนั้นน่าประทับใจ แต่มันมาจาก Zig ยุค 0.9 บนเครื่องที่ไม่ได้ระบุ ผมเลยวัดเองบนเครื่องนี้กับข้อมูลจริง แล้วผลออกมาน่าสนใจกว่าที่คาด — ทั้งในทางที่ดีและทางที่ทำให้ต้องระวัง

เงื่อนไขการวัด: Apple M5 Pro (cache line 128 ไบต์), macOS, Zig 0.16.0, -O ReleaseFast, N = 2,000,000 แถว median จาก 11 รอบ · โค้ดอยู่ที่ bench/layout.zig

---

ผลทั้งหมด

งาน                                median      เทียบ
AoS อ่านฟิลด์เดียว                 0.664 ms     1.10x
SoA อ่านฟิลด์เดียว                 0.605 ms     1.00x  ← เร็วกว่า 9%
AoS อ่านทุกฟิลด์                   1.604 ms
SoA อ่านทุกฟิลด์                   1.498 ms
เข้าถึงผ่าน index แบบ usize        0.483 ms
เข้าถึงผ่าน index แบบ u32          0.485 ms     ← ไม่ต่างกันเลย
เดิน linked list ที่ node กระจาย   111.911 ms   247x
เดิน array ต่อเนื่อง                0.453 ms     1.00x

หน่วยความจำ: AoS 32,000,000 ไบต์ / SoA 30,000,000 ไบต์ (ประหยัด 6%)
@sizeOf(Record) = 16 ไบต์ แต่ฟิลด์รวมกันจริง = 15 ไบต์

---

เรื่องที่หนึ่ง: SoA ชนะ แต่ชนะน้อยกว่าที่เล่ากัน

MultiArrayList เก็บข้อมูลแบบแยกคอลัมน์ ทฤษฎีคือเวลาอ่านแค่ฟิลด์เดียว CPU ไม่ต้องลากฟิลด์อื่นขึ้นมาด้วย

ผลจริง: เร็วขึ้น 9% ไม่ใช่หลายเท่า

เหตุผลอยู่ที่ตัวเลขบรรทัดล่างของตาราง — Record ที่ผมใช้มีขนาด 16 ไบต์ และฟิลด์ที่อ่านคือ u64 ขนาด 8 ไบต์ แปลว่าครึ่งหนึ่งของสิ่งที่ลากขึ้นมาถูกใช้จริงอยู่แล้ว การแยกคอลัมน์จึงประหยัดได้แค่อีกครึ่ง

ถ้า struct ใหญ่กว่านี้ ส่วนต่างจะมากกว่านี้ — ลองนึกถึง struct 128 ไบต์ที่อ่านแค่ฟิลด์ 2 ไบต์ นั่นคือกรณีที่ SoA ชนะขาด และเป็นกรณีที่คอมไพเลอร์ Zig เจอกับ token ของตัวเอง

const std = @import("std");

const Record = struct {
    status: u16,
    bytes: u64,
    ip: u32,
    cached: bool,
};

test "ขนาดที่หายไปกับการจัดตำแหน่ง" {
    // ฟิลด์รวมกันจริง = 8 + 4 + 2 + 1 = 15 ไบต์
    const raw = @sizeOf(u64) + @sizeOf(u32) + @sizeOf(u16) + @sizeOf(bool);
    try std.testing.expectEqual(@as(usize, 15), raw);

    // แต่ต้องปัดขึ้นให้ตรงกับ alignment ของฟิลด์ที่ใหญ่ที่สุด
    try std.testing.expectEqual(@as(usize, 16), @sizeOf(Record));

    // เก็บแยกคอลัมน์ไม่ต้องปัด จึงใช้ 15 ไบต์ต่อแถว
    const n = 2_000_000;
    try std.testing.expect(std.MultiArrayList(Record).capacityInBytes(n) < @sizeOf(Record) * n);
}

ที่ 2 ล้านแถวคือ 32 MB เทียบกับ 30 MB — ประหยัด 6%

และผลที่ไม่ได้คาดไว้: ตอนอ่าน ทุกฟิลด์ SoA ก็ยังเร็วกว่าเล็กน้อย (1.498 vs 1.604 ms) ทั้งที่ทฤษฎีบอกว่ากรณีนี้ SoA ควรแพ้เพราะต้องไปหยิบของจากสี่ที่มาประกอบกัน คำอธิบายที่น่าจะเป็นคือการอ่านสี่สายที่ต่อเนื่องกันเป็นรูปแบบที่ตัวอ่านล่วงหน้าของ CPU ทำได้ดี แต่ผมไม่ได้พิสูจน์ และจะไม่เดาแทนคุณ ถ้าโครงสร้างของคุณต่างจากนี้ ให้วัดเอง

---

เรื่องที่สอง: usize เป็น u32 ไม่ได้ช่วยอะไรเลย

คำแนะนำที่เจอบ่อยคือ “ใช้ u32 แทน usize สำหรับ index จะได้ประหยัดที่และเร็วขึ้น” — คอมไพเลอร์ Zig เองก็ใช้ enum(u32) เป็น index ของ AST จริง ๆ

ผลวัด: 0.483 ms เทียบกับ 0.485 ms — ต่างกันในระดับสัญญาณรบกวน

เหตุผลคือในงานนี้ ตัว index array ถูกอ่านแบบเรียงลำดับ (sequential) ซึ่ง CPU ทำนายล่วงหน้าได้หมด และตัวที่กำหนดความเร็วคือการเข้าถึง values ที่ปลายทาง ไม่ใช่ขนาดของ index

แต่ข้อได้เปรียบเรื่องหน่วยความจำเป็นเรื่องจริง — index array 2 ล้านตัวใช้ 16 MB เมื่อเป็น usize และ 8 MB เมื่อเป็น u32 ซึ่งสำคัญมากเมื่อ index ถูกฝังอยู่ในโครงสร้างที่มีเป็นล้านชิ้น

const std = @import("std");

/// รูปแบบที่คอมไพเลอร์ Zig ใช้กับ AST ของตัวเอง:
/// index เป็น enum(u32) และค่าพิเศษหนึ่งค่าทำหน้าที่เป็น "ไม่มี"
const NodeIndex = enum(u32) {
    none = std.math.maxInt(u32),
    _,

    fn toOptional(self: NodeIndex) ?u32 {
        return if (self == .none) null else @intFromEnum(self);
    }
};

test "index แบบ enum(u32) ที่ optional ไม่กินที่เพิ่ม" {
    try std.testing.expectEqual(@as(usize, 4), @sizeOf(NodeIndex));

    // ถ้าใช้ ?u32 ธรรมดาจะกินที่มากกว่า เพราะต้องมีธงแยก
    try std.testing.expect(@sizeOf(?u32) > @sizeOf(NodeIndex));

    const a: NodeIndex = @enumFromInt(7);
    try std.testing.expectEqual(@as(?u32, 7), a.toOptional());
    try std.testing.expectEqual(@as(?u32, null), NodeIndex.none.toOptional());
}

ท่านี้ให้ทั้งความประหยัดและความหมายที่ชัดเจน โดยไม่ต้องจ่ายไบต์เพิ่มให้ optional เลย

---

เรื่องที่สาม: ตัวเลขที่ควรทำให้คุณเปลี่ยนโครงสร้างข้อมูลจริง ๆ

เดิน linked list ที่ node กระจัดกระจาย   111.911 ms
เดิน array ต่อเนื่อง                       0.453 ms
                                          247 เท่า

247 เท่า นี่ไม่ใช่การปรับจูน นี่คือความต่างระหว่างโปรแกรมที่ใช้ได้กับโปรแกรมที่ใช้ไม่ได้

ทั้งสองแบบทำงานเหมือนกันเป๊ะ คือบวกเลข 2 ล้านตัว ต่างกันแค่ว่าตัวเลขถัดไปอยู่ที่ไหน — แบบแรกต้องอ่าน pointer ก่อนถึงจะรู้ว่าต้องไปที่ไหนต่อ และที่นั่นอยู่คนละที่กับที่เพิ่งอ่านมา ทำให้ CPU ทำนายล่วงหน้าไม่ได้เลยและต้องรอหน่วยความจำหลักทุกก้าว

สิ่งที่ทำให้ตัวเลขนี้ซื่อสัตย์: ผมสลับลำดับการวาง node ก่อนจะร้อยมันเข้าด้วยกัน ถ้าไม่ทำแบบนั้น node จะเรียงต่อกันในหน่วยความจำพอดี และคุณจะได้ตัวเลขที่สวยเกินจริงเพราะกำลังวัด array ที่ปลอมตัวเป็น linked list อยู่ — โค้ดบางส่วนที่ทำให้ benchmark ไม่โกหกคือสองบรรทัดนี้

// โค้ดบางส่วน — บรรทัดที่ทำให้ benchmark ไม่โกหก
const order = try arena.alloc(u32, N);
for (order, 0..) |*o, i| o.* = @intCast(i);
rand.shuffle(u32, order); // ถ้าลบบรรทัดนี้ ตัวเลขจะสวยเกินจริง

for (0..N - 1) |i| nodes[order[i]].next = &nodes[order[i + 1]];

โครงสร้างที่มีอาการเดียวกันในโค้ดจริง: linked list, tree ที่ node ถูกขอทีละชิ้น, HashMap ที่เก็บ pointer ไปยัง object, กราฟที่โยงกันด้วย pointer ทั้งหมดนี้ในภาษา GC ก็มีปัญหาเหมือนกัน แค่ถูกกลบด้วย compaction ของ GC บางตัว

ทางแก้: เก็บของทั้งหมดใน array ต่อเนื่องกัน แล้วอ้างถึงกันด้วย index แทน pointer

const std = @import("std");

/// ต้นไม้ที่ทุก node อยู่ใน array เดียวกัน และอ้างถึงกันด้วย index
const Tree = struct {
    const Index = u32;
    const none: Index = std.math.maxInt(Index);

    const Node = struct {
        value: u64,
        left: Index = none,
        right: Index = none,
    };

    nodes: std.ArrayList(Node) = .empty,

    fn deinit(self: *Tree, gpa: std.mem.Allocator) void {
        self.nodes.deinit(gpa);
    }

    fn add(self: *Tree, gpa: std.mem.Allocator, value: u64) !Index {
        const idx: Index = @intCast(self.nodes.items.len);
        try self.nodes.append(gpa, .{ .value = value });
        return idx;
    }

    fn sum(self: Tree) u64 {
        var total: u64 = 0;
        for (self.nodes.items) |n| total += n.value; // วนแบบต่อเนื่อง
        return total;
    }
};

test "โครงสร้างต้นไม้ที่ไม่มี pointer เลย" {
    const gpa = std.testing.allocator;
    var t: Tree = .{};
    defer t.deinit(gpa);

    const root = try t.add(gpa, 10);
    const left = try t.add(gpa, 20);
    t.nodes.items[root].left = left;

    try std.testing.expectEqual(@as(u64, 30), t.sum());
    try std.testing.expectEqual(@as(u64, 20), t.nodes.items[t.nodes.items[root].left].value);
    try std.testing.expectEqual(Tree.none, t.nodes.items[root].right);
}

ได้กำไรสามอย่างพร้อมกัน: วนอ่านเร็วขึ้นมาก, ขอหน่วยความจำครั้งเดียวแทนที่จะขอต่อ node, และ index ยังใช้ได้แม้ array ถูกย้ายที่ตอนขยาย (ต่างจาก pointer ที่จะพัง)

---

สรุปว่าอะไรคุ้มทำจริง

เรียงตามผลที่วัดได้ ไม่ใช่ตามที่คนเล่ากัน

ทำอะไร	ผลที่วัดได้	คุ้มไหม
เลิก pointer chasing ใช้ array + index	247 เท่า	คุ้มที่สุด ทำก่อนเพื่อน
AoS → SoA	9% (struct 16 ไบต์)	คุ้มเมื่อ struct ใหญ่และอ่านไม่ครบทุกฟิลด์
AoS → SoA (หน่วยความจำ)	ประหยัด 6%	คุ้มเมื่อข้อมูลเยอะ
usize → u32 (ความเร็ว)	ไม่ต่าง	ไม่ต้องทำเพื่อความเร็ว
usize → u32 (หน่วยความจำ)	ครึ่งหนึ่ง	คุ้มเมื่อ index ฝังในโครงสร้างจำนวนมาก

ข้อสรุปที่ผมอยากให้จำที่สุด: ตัวเลขที่มีค่าจริง ๆ ในตารางนี้คือ 247 เท่า ไม่ใช่ 9% ถ้าเวลาของคุณมีจำกัด ให้ไปดูว่าโครงสร้างข้อมูลของคุณบังคับให้ CPU กระโดดไปมาหรือเปล่าก่อน แล้วค่อยมาคิดเรื่องแยกคอลัมน์ทีหลัง

---

สรุปบทนี้

• SoA เร็วกว่า AoS แค่ 9% ที่ struct 16 ไบต์ ไม่ใช่หลายเท่าอย่างที่เล่ากัน — ส่วนต่างขึ้นกับว่าคุณอ่านกี่ส่วนของ struct
• SoA ประหยัดหน่วยความจำ 6% ที่ struct นี้ เพราะไม่ต้องเสียที่ให้การจัดตำแหน่ง
• usize → u32 ไม่ทำให้เร็วขึ้นเลย ในการเข้าถึงแบบเรียงลำดับ แต่ประหยัดที่ครึ่งหนึ่ง
• enum(u32) ที่มีค่าพิเศษเป็น “ไม่มี” ให้ optional ที่ไม่กินที่เพิ่ม
• pointer chasing ช้ากว่า array ต่อเนื่อง 247 เท่า และนี่คือตัวเลขเดียวในบทนี้ที่ควรทำให้คุณลุกไปแก้โค้ด
• benchmark linked list ที่ไม่สลับลำดับ node ก่อน คือ benchmark ที่โกหก

บทสุดท้าย — buffer เดียวที่เปลี่ยนทุกอย่าง และรวมเคสที่ผมวัดแล้วพบว่า แก้ไปก็ไม่ต่าง

---

Navigation

• ก่อนหน้า: Optimization #3: ข้อความและ hash map
• ถัดไป: Optimization #5: I/O และผลลบที่ควรรู้
• โค้ด benchmark: bench/layout.zig
• ดูทั้งชุด: บทความแท็ก zig