เจาะลึก Swiss Tables เบื้องหลัง map ของ Go ที่ทำให้เร็วขึ้นสูงสุด 60%

บทความจากบล็อกของ VictoriaMetrics เมื่อวันที่ 3 กันยายน 2026 อธิบายกลไกภายในของ map ใน Go หลังจากที่ทีม Go เปลี่ยนมาใช้โครงสร้าง Swiss Tables ซึ่งเป็นเนื้อหาที่ขึ้นหน้าแรก Hacker News ในสุดสัปดาห์นี้ และเป็นความรู้ที่มีประโยชน์จริงกับใครก็ตามที่ต้องปรับจูนประสิทธิภาพระบบที่เขียนด้วย Go

โครงสร้างการจัดเก็บแบ่งเป็นลำดับชั้น หน่วยพื้นฐานคือ group ที่บรรจุช่อง key-value 8 ช่องพร้อม control byte ประกบ แต่ละ control byte เก็บเศษของแฮช 7 บิต (เรียกว่า H2) หรือเครื่องหมายพิเศษสำหรับสถานะว่าง/ถูกลบ เมื่อคำนวณแฮชจะแยกเป็น H1 (บิตสูง ใช้เลือก group) กับ H2 (บิตต่ำ 7 บิต ใช้กรองช่อง) การออกแบบแบบนี้เปิดทางให้ใช้ SIMD คือ Go เปรียบเทียบ H2 กับ control byte ทั้ง 8 ตัวพร้อมกันในคำสั่งเดียว

เมื่อ group เต็ม หลาย group จะรวมกันเป็น table ได้สูงสุด 128 group หรือ 1,024 ช่อง โดยใช้ลำดับการ probe แบบสามเหลี่ยม (ตรวจ group ที่ระยะ +1, +2, +3) เพื่อหาช่องว่างเมื่อ group เริ่มต้นเต็ม เหนือขึ้นไปคือ directory ซึ่งเป็นอาร์เรย์ของพอยน์เตอร์ที่จัดการหลาย table โดยใช้บิตซ้ายสุดของ H1 เลือก entry ทำให้แต่ละ table โตได้อิสระโดยไม่ต้องสร้างทั้ง map ใหม่ ตัว table รักษา load factor ที่ 7/8 คือรายการที่ยังใช้อยู่บวกช่องที่ถูกลบรวมกันไม่เกิน 87.5% ของความจุ เพื่อ "คงช่องว่างไว้บ้างก่อนที่ต้นทุนการสแกนจะสูงเกินไป"

ความต่างจากของเดิมชัดเจน โครงสร้างก่อนหน้านี้ใช้โซ่ overflow bucket ซึ่งหมายความว่า "การ lookup ต้องโหลด overflow pointer ก่อนจึงจะหาและตรวจ 8 ช่องถัดไปได้" ทุก bucket ที่เพิ่มขึ้นจึงสร้าง dependent pointer load Swiss Tables กำจัดปัญหานี้ด้วยการจัดสรร group ต่อเนื่องกันและใช้ triangular probing และเมื่อต้องขยาย ระบบจะ "สร้างเฉพาะ table ที่ต้องการพื้นที่เพิ่มขึ้นใหม่" แทนที่จะกระจายทั้ง map ใหม่

ผลด้านประสิทธิภาพ เบนช์มาร์กชี้ว่าการทำงานของ map เร็วขึ้นสูงสุด 60% เทียบกับ Go 1.23 แม้จะมีบางเคสที่ถดถอย ส่วนแอปพลิเคชันจริงเห็นการปรับปรุงเวลา CPU แบบ geometric mean ราว 1.5% นอกจากนี้ยังมีการปรับปรุงเชิงทดลองใน Go 1.27 คือ split group layout ที่แยก key ออกจาก value เพื่อเพิ่ม cache locality ตอน lookup และช่วยประหยัดหน่วยความจำใน map แบบ map[int64]struct{} ที่ไม่ต้องมี padding ระหว่าง key กับ value