# Swissmap


<img src="https://iili.io/2zob7dN.png" alt="SwissMap" width=100%>

[Go 1.24 mặc định sẽ dùng SwissMap](https://go-review.googlesource.com/c/go/+/594597), vậy SwissMap là gì? Tại sao nó lại quan trọng?

<!-- ## English Version -->

<!-- SwissMap and SwissTable offer an improved solution for high-performance, memory-efficient hash tables in Golang. -->

SwissMap và SwissTable cung cấp giải pháp cải tiến cho bảng băm hiệu năng cao, tiết kiệm bộ nhớ trong Golang.


<!-- ## Original Problem -->
<!-- In many applications, hash tables play a critical role, especially where rapid data access and minimal memory usage are essential. However, Golang’s built-in map, while convenient for general use, consumes more memory and may not provide the speed required in performance-critical scenarios. -->
## Vấn đề ban đầu
Trong nhiều ứng dụng, bảng băm (hash table) đóng vai trò quan trọng, đặc biệt khi cần truy cập dữ liệu với tốc độ cao sử dụng bộ nhớ tối thiểu. Tuy nhiên, bảng băm tích hợp sẵn (built-in map) của Golang, mặc dù thuận tiện cho các trường hợp phổ thông, nó lại tiêu tốn nhiều bộ nhớ hơn và có thể không đủ nhanh cho các tình huống yêu cầu hiệu suất cao (ví dụ DoltDB).


<!-- ## The Idea/Intuition Behind SwissMap (SwissTable Design) -->

## Ý tưởng đằng sau SwissMap

<!-- SwissMap provides a faster, more memory-efficient hash table than Golang’s built-in map, making it valuable for applications requiring quick lookups and memory optimization. This enhanced performance and efficiency help improve latency and reduce memory overhead. -->
<!-- SwissMap is based on SwissTable, a hash table design from Google’s Abseil library, known for its efficient, cache-friendly layout. Instead of the "open-hashing" approach in Golang’s map, SwissTable uses "closed-hashing," which enables faster lookups. The design optimizes cache usage and supports SIMD (Single Instruction, Multiple Data) instructions for faster comparisons, achieving a higher load factor (14/16) compared to Golang's 6.5/8, allowing it to store more data in the same space. -->
Giải thuật SwissMap tạo ra bảng băm cho tốc độ truy cập nhanh hơn, đồng thời tiết kiệm bộ nhớ hơn so với `map` trong Golang. SwissMap dựa trên [SwissTable](https://abseil.io/about/design/swisstables), thiết kế bảng băm trong thư viện Abseil của Google, nổi tiếng với bố cục hiệu quả, thân thiện với cache. Thay vì dùng **băm mở** (open-hashing) như trong map của Golang, SwissTable sử dụng **băm đóng** (closed-hashing), cho phép tìm kiếm nhanh hơn. Thiết kế này tối ưu hóa việc sử dụng cache và hỗ trợ các lệnh SIMD (Single Instruction, Multiple Data) cho phép so sánh nhanh hơn, đạt được hệ số tải (load factor) cao hơn (14/16 so với 6.5/8 của Golang), cho phép lưu trữ nhiều dữ liệu hơn trong cùng một không gian bộ nhớ.

<!-- ## Detailed Mechanism Compared with Golang’s Built-in Map -->

## Cơ Chế

<!-- - **Golang’s Built-in Map:** Uses open-hashing, where key-value pairs are stored in "buckets," grouping elements that collide into a single bucket. Searching involves scanning through possible matches in the bucket, optimized by “extra hash bits” for fast comparisons within each bucket, but with limited cache locality and density. -->
`map` Sử dụng giải thuật **băm mở** (open-hashing) trong đó, một khi xảy ra hiện tượng xung đột (collision - tức là các cặp khoá - giá trị (key-value) khác nhau có cùng 1 giá trị băm), thì các cặp khóa - giá trị đó được lưu trong cùng một "bucket". Khi cần tìm kiếm dữ liệu, giải thuật sẽ nhanh chóng chạy đến đúng bucket, nhưng sau đó phải duyệt qua từng cặp khóa - giá trị trong bucket để tìm ra khóa phù hợp. 

![](https://www.dolthub.com/blog/5dca1a3117941d58fef45067c12c9809/golang-map-bucket.svg)

Để tối ưu hóa việc so sánh trong từng bucket, `map` sử dụng thêm **các bit băm bổ sung** (extra hash bits).Trước khi so sánh trực tiếp khóa truy vấn (query key) với một khóa tiềm năng, đầu tiên thuật toán sẽ so sánh băm 8-bit của mỗi khóa (không phụ thuộc vào băm của bucket) để xem liệu có khả năng khớp hay không. Bước tiền kiểm tra (pre-check) này có tỷ lệ dương tính giả (false-positive) là 1/256 và giúp tăng tốc đáng kể các tìm kiếm trong bucket trong toàn bộ bảng băm. Để tìm hiểu thêm về thiết kế của map tích hợp trong Golang, hãy tham khảo [bài nói chuyện của Keith Randall tại GopherCon 2016: "Inside the Map Implementation."](https://www.youtube.com/watch?v=Tl7mi9QmLns&t=596s)


**SwissTable** sử dụng một cấu trúc (scheme) băm khác được gọi là **băm đóng** (closed-hashing). Thay vì gom nhóm các phần tử xung đột vào chung bucket, mỗi cặp khóa - giá trị trong bảng băm được gán một **slot** riêng. Vị trí của slot này được xác định bởi một **thuật toán thăm dò** (probing algorithm), với điểm bắt đầu được xác định bằng giá trị băm của khóa. Ví dụ đơn giản nhất là thăm dò tuyến tính, bắt đầu từ vị trí hash(key) mod size và dừng lại khi tìm thấy khóa mong muốn hoặc khi gặp một slot trống. Phương pháp thăm dò này được sử dụng để tìm cả các khóa hiện có và cả vị trí thích hợp để thêm các khóa mới (insert point). Giống như `map` trong Golang, SwissTable sử dụng các "băm ngắn" (short hashes) để tăng tốc quá trình kiểm tra trong khi thăm dò. Tuy nhiên, không giống như `map`, metadata băm của cặp khoá - giá trị được lưu trữ riêng biệt với dữ liệu khóa - giá trị.

<div style="text-align: center; margin-top: 50px; margin-bottom: 50px;">
    <img src="https://www.dolthub.com/blog/static/d9511dc9898dd5e4bb54c8082c274e1e/a1792/swiss-table-layout.png" alt="SwissTable" width=100%>
</div>

Bố cục bộ nhớ phân đoạn của SwissTable là yếu tố chính giúp tăng hiệu suất của nó. Các chuỗi thao tác thăm dò trên bảng băm chỉ truy cập mảng metadata cho đến khi tìm thấy một băm ngắn khớp. Kiểu truy cập này tối ưu hóa tính cục bộ của bộ nhớ cache trong quá trình thăm dò. Một khi khớp giá trị băm trong metadata, các khóa tương ứng gần như chắc chắn cũng sẽ khớp. 

Việc tách ra một một mảng metadata riêng biệt cũng cho phép sử dụng các lệnh SSE để so sánh đồng thời 16 băm ngắn! Sử dụng lệnh SSE không chỉ nhanh hơn mà còn là lí do SwissTable cho phép hệ số tải tối đa lên đến 14/16. 

Quan sát thấy: các **thăm dò âm** (negative probes - tìm kiếm một khóa không có trong bảng) chỉ kết thúc khi gặp một slot trống. Càng ít slot trống trong bảng, chuỗi thao tác thăm dò trung bình sẽ càng dài (vì sẽ khó bắt gặp slot trống hơn). Để duy trì thời gian truy cập O(1) cho bảng băm, ta cần giơi shanj chuỗi thăm dò trung bình bằng một hệ số nhỏ và không đổi. Để đạt hiệu quả với việc sử dụng lệnh SSE, ta sẽ chia độ dài chuỗi thăm dò trung bình cho 16. Các phép đo thực nghiệm cho thấy ngay cả ở tải tối đa, số bước thăm dò trung bình ít hơn hai lần so sánh theo cụm 16! Nếu bạn muốn tìm hiểu sâu hơn về thiết kế của SwissTable, hãy xem [bài nói chuyện của Matt Kulukundis tại CppCon 2017: “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”](https://www.youtube.com/watch?v=ncHmEUmJZf4&t=1449s).


## Tham khảo

- [https://abseil.io/about/design/swisstables](https://abseil.io/about/design/swisstables)
- [https://www.dolthub.com/blog/2023-03-28-swiss-map](https://www.dolthub.com/blog/2023-03-28-swiss-map)
- [https://www.youtube.com/watch?v=Tl7mi9QmLns&t=596s](https://www.youtube.com/watch?v=Tl7mi9QmLns&t=596s)
- [https://www.youtube.com/watch?v=ncHmEUmJZf4&t=1449s](https://www.youtube.com/watch?v=ncHmEUmJZf4&t=1449s)