Zig Optimization #3: เลิก copy ข้อความ และใช้ hash map ให้ถูกวิธี

ในภาษาที่มี GC ข้อความเป็นของที่ copy กันได้ตามใจ Java กับ C# ทำให้ข้อความแก้ไม่ได้และ intern ให้บางส่วนอัตโนมัติ Go copy ตอนแปลง []byte เป็น string โดยที่คุณแทบไม่รู้ตัว

พอมาเขียน Zig นิสัยนั้นตามมาด้วย และมันแพงกว่าที่คิดมาก

เงื่อนไขการวัด: Apple M5 Pro, macOS, Zig 0.16.0, -O ReleaseFast, init.gpa งานคือ นับความถี่ 200,000 ครั้ง จาก key ที่ต่างกัน 64 แบบ (สัดส่วนแบบเดียวกับ log จริงที่ path ซ้ำ ๆ) median จาก 11 รอบ · โค้ดอยู่ที่ bench/maps.zig

---

ผลทั้งหมด แยกตามความยาว key

วิธี                          key 16 B    key 64 B   key 256 B
สร้างข้อความใหม่ทุกรอบ         5.445 ms    4.686 ms    6.567 ms
intern ครั้งเดียว (arena)      1.378 ms    1.488 ms    3.129 ms
contains + get + put          2.770 ms    3.612 ms    8.245 ms
getOrPut + จองตารางล่วงหน้า    1.005 ms    1.089 ms    2.734 ms
u32 handle + array            0.135 ms    0.132 ms    0.132 ms

จำนวนครั้งที่ขอหน่วยความจำ: สร้างใหม่ทุกรอบ = 200,069 / intern ครั้งเดียว = 9-11

อ่านตารางนี้แล้วเห็นสามเรื่องทันที

1. การสร้างข้อความใหม่ทุกรอบแพงที่สุด — ช้ากว่า interning ราว 4 เท่าที่ key สั้น
2. contains + get + put ช้ากว่า getOrPut 2.7-3.3 เท่า และยิ่ง key ยาวยิ่งแย่
3. การแปลง key เป็นตัวเลขแล้วนับด้วย array เร็วกว่าทุกวิธีราว 8-20 เท่า และเวลาไม่ขึ้นกับความยาว key เลย

---

เรื่องที่หนึ่ง: อย่าสร้างข้อความใหม่ทุกครั้งที่ค้น

รูปแบบที่คนเขียนโดยไม่ทันคิด คือประกอบ key ขึ้นมาใหม่ทุกรอบ เช่น map.get(prefix + name) ในภาษาอื่น พอแปลงมาเป็น Zig ก็กลายเป็นการขอหน่วยความจำหนึ่งครั้งต่อการค้นหาหนึ่งครั้ง

200,069 ครั้งเทียบกับ 9 ครั้ง คือความต่างของจำนวนการขอหน่วยความจำระหว่างสองวิธี

วิธีที่ถูกคือ copy เฉพาะตอนเห็น key นั้นครั้งแรก แล้วหลังจากนั้นใช้ของเดิม — เทคนิคเดียวกับที่ workshop บทที่ 4 ใช้

const std = @import("std");

const Counter = struct {
    arena: std.heap.ArenaAllocator,
    map: std.StringHashMapUnmanaged(u64) = .empty,

    fn init(child: std.mem.Allocator) Counter {
        return .{ .arena = .init(child) };
    }

    fn deinit(self: *Counter, gpa: std.mem.Allocator) void {
        self.map.deinit(gpa);
        self.arena.deinit();
    }

    fn add(self: *Counter, gpa: std.mem.Allocator, key: []const u8) !void {
        const gop = try self.map.getOrPut(gpa, key);
        if (!gop.found_existing) {
            gop.key_ptr.* = try self.arena.allocator().dupe(u8, key); // copy ครั้งเดียว
            gop.value_ptr.* = 0;
        }
        gop.value_ptr.* += 1;
    }
};

test "copy ครั้งเดียวต่อ key ไม่ใช่ต่อการค้นหา" {
    const gpa = std.testing.allocator;
    var c: Counter = .init(gpa);
    defer c.deinit(gpa);

    // ค้น 1,000 ครั้ง แต่มี key แค่ 4 แบบ
    const keys = [_][]const u8{ "/a", "/b", "/c", "/d" };
    for (0..1000) |i| try c.add(gpa, keys[i % keys.len]);

    try std.testing.expectEqual(@as(usize, 4), c.map.count());
    try std.testing.expectEqual(@as(u64, 250), c.map.get("/a").?);
}

ข้อควรระวังที่ตารางบอกแต่หัวข้อไม่ได้บอก: ที่ key ยาว 64 ไบต์ ความต่างระหว่างสองวิธีลดลงเหลือ 3 เท่า และตัวเลขของ “สร้างใหม่ทุกรอบ” ที่ 64 ไบต์ (4.686 ms) กลับ เร็วกว่า ที่ 16 ไบต์ (5.445 ms) ซึ่งฟังดูขัดกับสามัญสำนึก

คำอธิบายที่น่าจะเป็นคือขนาดก้อนที่ขอมีผลต่อเส้นทางที่ allocator เลือกใช้ ผมไม่ได้ไล่ดูลึกกว่านี้ และ จะไม่เดาแทนคุณ — สิ่งที่ยืนยันได้คือทิศทางรวม (สร้างใหม่ทุกรอบแพงกว่าเสมอ) ส่วนตัวคูณที่แน่นอนขึ้นกับขนาดข้อมูลของคุณเอง

---

เรื่องที่สอง: getOrPut แทนการค้นสามรอบ

รูปแบบที่ติดมาจาก Java (if (map.containsKey(k)) ... map.put(k, ...)) ทำให้ต้องคำนวณ hash และเดินตารางสามรอบ สำหรับการอัปเดตหนึ่งครั้ง

const std = @import("std");

test "getOrPut ทำงานรอบเดียว" {
    const gpa = std.testing.allocator;
    var map: std.StringHashMapUnmanaged(u64) = .empty;
    defer map.deinit(gpa);

    // จองตารางล่วงหน้าเมื่อรู้จำนวน key คร่าว ๆ
    try map.ensureTotalCapacity(gpa, 16);

    const keys = [_][]const u8{ "/a", "/b", "/a" };
    for (keys) |k| {
        const gop = map.getOrPutAssumeCapacity(k); // hash รอบเดียว
        if (!gop.found_existing) gop.value_ptr.* = 0;
        gop.value_ptr.* += 1;
    }

    try std.testing.expectEqual(@as(u64, 2), map.get("/a").?);
    try std.testing.expectEqual(@as(u64, 1), map.get("/b").?);
}

ผลวัด: 2.770 ms → 1.005 ms ที่ key 16 ไบต์ (2.8 เท่า) และ 8.245 ms → 2.734 ms ที่ key 256 ไบต์ (3.0 เท่า)

ยิ่ง key ยาวยิ่งได้กำไรมาก เพราะ StringHashMap คำนวณ hash จากเนื้อข้อความทั้งก้อน การค้นสามรอบจึงเท่ากับอ่านข้อความ 256 ไบต์สามเที่ยว

getOrPutAssumeCapacity ตัดการเช็คความจุออกไปอีกชั้น ใช้ได้เมื่อจองไว้พอแล้ว

---

เรื่องที่สาม: key ที่ดีที่สุดคือ key ที่ไม่ใช่ข้อความ

ผลที่สะดุดตาที่สุดในตารางคือแถวสุดท้าย — 0.132 ms ทุกความยาว key

วิธีคือ intern ข้อความให้กลายเป็น u32 เพียงครั้งเดียวตอนเห็นครั้งแรก แล้วหลังจากนั้นการนับทั้งหมดเป็นการบวกเลขใน array ธรรมดา ไม่มีการ hash ไม่มีการเทียบข้อความอีกเลย

const std = @import("std");

const Interner = struct {
    arena: std.heap.ArenaAllocator,
    ids: std.StringHashMapUnmanaged(u32) = .empty,
    counts: std.ArrayList(u64) = .empty,

    fn init(child: std.mem.Allocator) Interner {
        return .{ .arena = .init(child) };
    }

    fn deinit(self: *Interner, gpa: std.mem.Allocator) void {
        self.ids.deinit(gpa);
        self.counts.deinit(gpa);
        self.arena.deinit();
    }

    /// แปลงข้อความเป็นเลขประจำตัว ทำครั้งเดียวต่อ key
    fn intern(self: *Interner, gpa: std.mem.Allocator, key: []const u8) !u32 {
        const gop = try self.ids.getOrPut(gpa, key);
        if (!gop.found_existing) {
            gop.key_ptr.* = try self.arena.allocator().dupe(u8, key);
            gop.value_ptr.* = @intCast(self.counts.items.len);
            try self.counts.append(gpa, 0);
        }
        return gop.value_ptr.*;
    }

    /// หลังจากนี้การนับคือการบวกเลขล้วน ๆ
    fn bump(self: *Interner, id: u32) void {
        self.counts.items[id] += 1;
    }
};

test "intern เป็น u32 แล้วนับด้วย array" {
    const gpa = std.testing.allocator;
    var it: Interner = .init(gpa);
    defer it.deinit(gpa);

    const a = try it.intern(gpa, "/very/long/path/that/would/be/slow/to/hash");
    const b = try it.intern(gpa, "/another/long/path");
    const a2 = try it.intern(gpa, "/very/long/path/that/would/be/slow/to/hash");

    try std.testing.expectEqual(a, a2); // ข้อความเดิมได้เลขเดิม
    try std.testing.expect(a != b);

    for (0..1000) |_| it.bump(a);
    it.bump(b);

    try std.testing.expectEqual(@as(u64, 1000), it.counts.items[a]);
    try std.testing.expectEqual(@as(u64, 1), it.counts.items[b]);
}

เมื่อไหร่ที่คุ้มทำ: เมื่อ key ตัวเดิมถูกใช้ซ้ำหลายครั้ง ในงานนับความถี่แบบนี้ key 64 แบบถูกใช้ 200,000 ครั้ง คือเฉลี่ยซ้ำ 3,125 ครั้งต่อ key — คุ้มมาก

เมื่อไหร่ที่ไม่คุ้ม: เมื่อ key แทบไม่ซ้ำเลย เพราะคุณจะจ่ายค่า hash เท่าเดิมแล้วยังต้องจ่ายค่าเก็บตารางแปลงเพิ่มอีก

นี่คือรูปแบบเดียวกับที่คอมไพเลอร์ Zig ใช้กับ identifier ในโค้ดที่มันคอมไพล์ — เก็บข้อความทั้งหมดไว้ในบัฟเฟอร์เดียว แล้วอ้างถึงด้วย u32 ตลอดทั้งระบบ

---

เลือก map ให้ตรงงาน

Zig มี hash map สองตระกูลที่ต่างกันจริง ๆ ไม่ใช่แค่ต่างชื่อ

	std.StringHashMap	std.array_hash_map.String
ค้นจุดเดียว	เร็วกว่า	ช้ากว่าเล็กน้อย
วนดูทั้งหมด	กระโดดไปมาในตาราง	ต่อเนื่องและเรียงตามลำดับที่ใส่
ลำดับตอนวน	ไม่แน่นอน	ตามลำดับที่เพิ่มเข้ามา
ตัวเลือกพิเศษ	—	store_hash แลกที่เก็บกับการลดการเทียบ key

ถ้าสุดท้ายต้องเอาทุกรายการมาเรียงอยู่แล้ว (แบบ zlog top) array_hash_map มีข้อดีตรงที่ข้อมูลต่อเนื่องกัน ส่วนถ้างานหลักคือค้นจุดเดียวถี่ ๆ ให้ใช้ StringHashMap

สิ่งที่ต้องรู้ก่อนใช้ AutoHashMap กับ key ที่เป็นข้อความ: มัน hash จาก “ตัวชี้กับความยาว” ไม่ใช่จากเนื้อข้อความ ข้อความเนื้อเดียวกันคนละที่อยู่จะกลายเป็นคนละ key — ต้องใช้ StringHashMap เท่านั้น

---

สรุปบทนี้

• สร้างข้อความใหม่ทุกครั้งที่ค้น = ขอหน่วยความจำ 200,069 ครั้ง เทียบกับ 9 ครั้งเมื่อ intern ครั้งเดียว (ช้ากว่าราว 4 เท่า)
• contains + get + put ช้ากว่า getOrPut 2.8-3.0 เท่า และยิ่ง key ยาวยิ่งต่าง
• แปลง key เป็น u32 แล้วนับด้วย array เร็วกว่าทุกวิธี 8-20 เท่า และเวลาไม่ขึ้นกับความยาว key
• ความยาว key มีผลชัดกับทุกวิธีที่ยังใช้ข้อความเป็น key
• ผลบางอย่างขัดสามัญสำนึก (key 64 ไบต์เร็วกว่า 16 ไบต์ในบางเคส) — รายงานตามจริงและไม่เดาสาเหตุ
• AutoHashMap ใช้กับ key ข้อความไม่ได้ ต้อง StringHashMap

บทหน้าเรื่องการจัดวางข้อมูล — และมีผลวัดที่จะทำให้หลายคนแปลกใจ ทั้งเรื่องที่ SoA ชนะน้อยกว่าที่คิด และเรื่องที่ pointer chasing แพงกว่าที่คิดมาก

---

Navigation

• ก่อนหน้า: Optimization #2: การขอหน่วยความจำ
• ถัดไป: Optimization #4: การจัดวางข้อมูล
• โค้ด benchmark: bench/maps.zig
• ดูทั้งชุด: บทความแท็ก zig