Bên trong Map của Go 1.24: Cơ chế Swiss Table thay đổi hiệu suất như thế nào?

Go 1.24 đã chính thức thay thế thuật toán map cũ bằng thiết kế Swiss Table, đánh dấu một bước ngoặt lớn trong cách runtime xử lý kiểu dữ liệu quan trọng này. Với khả năng tăng tốc các thao tác map lên đến 60% trong benchmark vi mô, bài viết này từ đội ngũ VictoriaMetrics sẽ giúp bạn hiểu rõ cấu trúc nhóm (group), bảng (table), thư mục (directory) mới, cùng cách Go tận dụng SIMD và chiến lược tăng trưởng thông minh để tối ưu hiệu năng.

Từ Map truyền thống đến Swiss Table

Khi bạn khai báo một map với make(map[string]int), runtime không chỉ đơn thuần tạo một vùng nhớ. Nó tạo ra một con trỏ trỏ tới cấu trúc internal/runtime/maps.Map. Cấu trúc này chứa hai trường quan trọng: used (đếm số lượng entry) và seed (một số ngẫu nhiên cho mỗi map).

Trường seed đóng vai trò then chốt trong việc phân bổ dữ liệu. Khi cần tìm một key, Go sẽ băm key đó cùng với seed của map. Vì mỗi map có một seed riêng, cùng một key khi được băm trong hai map khác nhau sẽ cho ra kết quả khác nhau, dẫn đến vị trí lưu trữ khác nhau. Điều này giúp giảm thiểu va chạm khi nhiều map hoạt động cùng lúc trong một chương trình lớn.

Giải mã cấu trúc Group

Đơn vị lưu trữ nhỏ nhất trong Swiss Table là một group với 8 slots. Mỗi group bao gồm hai phần chính: hàng trên cùng là 8 byte điều khiển (control bytes), và bên dưới là các cặp key-value.

8 byte điều khiển này tạo thành một "từ điều khiển" (control word) 64-bit. Mỗi byte điều khiển tương ứng với một slot bên dưới. Khi Go băm một key, nó chia hash thành hai phần: H1 (57 bit trên) dùng để xác định group bắt đầu, và H2 (7 bit dưới) được lưu trực tiếp vào byte điều khiển.

Điểm đặc biệt là bit cao nhất trong mỗi byte điều khiển có vai trò đánh dấu trạng thái: bit 0 nghĩa là slot đang chứa dữ liệu với H2, bit 1 nghĩa là slot trống hoặc đã bị xóa. Slot trống (10000000) sẽ dừng quá trình tìm kiếm, trong khi slot "tombstone" (11111110) cho phép tìm kiếm tiếp tục sang các group khác.

Sức mạnh của SIMD trong tìm kiếm

Một trong những cải tiến lớn nhất là việc sử dụng SIMD (Single Instruction, Multiple Data). Thay vì so sánh key với từng slot một, Go có thể so sánh một H2 value với tất cả 8 byte điều khiển cùng lúc. Kết quả là một bitmap với 8 bit, mỗi bit đại diện cho một slot khớp hoặc không khớp.

Trên kiến trúc AMD64, Go sử dụng SIMD để thực hiện phép so sánh này. Các kiến trúc khác cũng đạt được kết quả tương tự thông qua các phép toán bitwise trên control word 64-bit. Kỹ thuật này cho phép Go chỉ đọc key đầy đủ từ các slot ứng viên tiềm năng thay vì phải kiểm tra tuần tự cả 8 slot, từ đó giảm đáng kể số lần truy cập bộ nhớ.

Khi Map lớn lên: Sự xuất hiện của Table và Directory

Khi một group chứa quá 8 entries, Go sẽ nhân đôi số group từ 1 lên 2 và giới thiệu cấu trúc mới gọi là table. Lúc này, H1 bắt đầu phát huy vai trò của mình trong việc chọn group bắt đầu. Với 2 group, Go chỉ cần dùng 1 bit thấp nhất của H1 để quyết định key thuộc group 0 hay group 1.

Tuy nhiên, một table không thể phát triển vô hạn. Khi đạt 128 groups (tương đương 1024 slots), table buộc phải "tách" (split) thành 2 table nhỏ hơn. Lúc này, directory - một mảng con trỏ - trở nên quan trọng. Thay vì quản lý trực tiếp các groups, Map trỏ tới directory, và directory trỏ tới các tables.

Điều thú vị là khi một table tách, Go không cần phải di dời toàn bộ dữ liệu của map. Nó chỉ di chuyển các entry trong chính table đó sang 2 table con. Các table khác vẫn nguyên vẹn. Đây chính là điểm khác biệt lớn so với cách làm cũ, nơi mà việc tăng trưởng đòi hỏi phải rebuild toàn bộ bucket array.

Chiến lược tìm kiếm theo "Dãy tam giác"

Khi H1 chọn một group bắt đầu, nếu group đó đã đầy, Go không tìm kiếm tuần tự sang group liền kề. Thay vào đó, nó sử dụng triangular probe sequence: bước nhảy +1, sau đó +2, rồi +3 và tiếp tục. Vì số group luôn là lũy thừa của 2, Go sẽ duyệt qua mọi group đúng một lần trước khi chuỗi lặp lại.

Điều này giải quyết vấn đề "overflow bucket" kinh điển của phiên bản map cũ. Trước đây, một bucket đầy phải tạo ra một bucket liên kết ngoài, tạo thành chuỗi các pointer dereference - mỗi lần phải đọc thêm một con trỏ mới. Với Swiss Table, tất cả groups nằm liền kề trong một mảng duy nhất, giúp tối ưu bộ nhớ cache CPU.

Vì sao lại dừng ở mức 7/8?

Go giới hạn load factor của một table ở mức 7/8 (87.5%). Điều này có nghĩa là trước khi fill đầy tất cả slots, Go sẽ kích hoạt quá trình tăng trưởng. Lý do nằm ở chi phí tìm kiếm: nếu table đầy 100%, một lần tìm kiếm key không tồn tại sẽ buộc Go phải quét toàn bộ các groups theo probe sequence. Việc giữ lại tối thiểu 12.5% số slots trống giúp dừng sớm quá trình tìm kiếm khi gặp slot trống, giảm đáng kể số lần đọc bộ nhớ không cần thiết.

GOEXPERIMENT=mapsplitgroup: Tương lai của layout

Ngoài ổn định hiện tại, Go 1.27 đang thử nghiệm một thiết kế mới gọi là split group layout. Với cài đặt GOEXPERIMENT=mapsplitgroup, các keys và values được tách thành 2 mảng riêng biệt thay vì xếp xen kẽ. Điều này mang lại hai lợi ích:

• Cải thiện locality: Khi tìm kiếm, Go chỉ cần đọc liên tục các keys để so sánh. Values chỉ được đọc khi tìm thấy key khớp.
• Tiết kiệm bộ nhớ: Với các map kiểu map[int64]struct{} (thường dùng làm set), layout cũ phải thêm padding 8 byte cho mỗi slot do value rỗng. Layout mới giúp tiết kiệm đến 56 byte cho một group 8 slots.

Go đã kích hoạt tính năng này mặc định trên nhánh phát triển, cho thấy đây gần như chắc chắn sẽ là mặc định trong các phiên bản tương lai.

So sánh hiệu suất và kết luận

Theo microbenchmarks của đội ngũ Go, các thao tác map trong Go 1.24 nhanh hơn tối đa 60% so với Go 1.23. Với các ứng dụng thực tế, mức cải thiện trung bình là khoảng 1.5% CPU time - một con số không nhỏ cho một sự thay đổi ở tầng runtime.

Mặc dù vẫn tồn tại một số trường hợp đặc biệt chậm hơn, nhưng tổng thể, việc chuyển sang Swiss Table là một nâng cấp đáng giá. Nó không chỉ giúp code của bạn chạy nhanh hơn mà còn đặt nền móng vững chắc cho việc tối ưu hóa trong tương lai, đặc biệt là với sự phát triển của các kiến trúc CPU hiện đại hỗ trợ SIMD mạnh mẽ.

Đối với cộng đồng lập trình viên Việt Nam đang theo dõi sự phát triển của Go, đây là một thay đổi quan trọng cần nắm bắt, đặc biệt khi các ứng dụng sử dụng map với quy mô lớn sẽ được hưởng lợi trực tiếp. Hãy thử nghiệm ứng dụng của bạn trên Go 1.24+ để cảm nhận sự khác biệt và theo dõi các thí nghiệm như mapsplitgroup để đón đầu xu hướng tối ưu bộ nhớ trong tương lai gần.