Go map使用Swiss Table重新實現，性能最高提升近50%
在2024月11月5日的Go compiler and runtime meeting notes[1]中，我們注意到了一段重要內容，如下圖紅框所示：
圖片
這表明，來自字節的一位工程師在兩年多前提出的“使用Swiss table重新實現Go map[2]”的建議即將落地，目前該issue已經被納入Go 1.24里程碑[3]。
Swiss Table是由Google工程師于2017年開發的一種高效哈希表實現，旨在優化內存使用和提升性能，解決Google內部代碼庫中廣泛使用的std::unordered_map所面臨的性能問題。Google工程師Matt Kulukundis在2017年CppCon大會上詳細介紹了他們在Swiss Table上的工作[4]：
圖片
目前，Swiss Table已被應用于多種編程語言，包括C++ Abseil庫的flat_hash_map(可替換std::unordered_map)[5]、Rust標準庫Hashmap的默認實現[6]等。
Swiss Table的出色表現是字節工程師提出這一問題的直接原因。字節跳動作為國內使用Go語言較為廣泛的大廠。據issue描述，Go map的CPU消耗約占服務總體開銷的4%。其中，map的插入（mapassign）和訪問（mapaccess）操作的CPU消耗幾乎是1:1。大家可千萬不能小看4%這個數字，以字節、Google這樣大廠的體量，減少1%也意味著真金白銀的大幅節省。
Swiss Table被視為解決這一問題的潛在方案。字節工程師初版實現的基準測試結果顯示，與原實現相比，Swiss Table在查詢、插入和刪除操作上均提升了20%至50%的性能，尤其是在處理大hashmap時表現尤為突出；迭代性能提升了10%；內存使用減少了0%至25%，并且不再消耗額外內存。
這些顯著的性能提升引起了Go編譯器和運行時團隊的關注，特別是當時負責該子團隊的Austin Clements。在經過兩年多的實驗和評估后，Go團隊成員Michael Pratt[7]基于Swiss Table實現的internal/runtime/maps最終成為Go map的底層默認實現。
在本文中，我們將簡單介紹Swiss Table這一高效的哈希表實現算法，并提前看一下Go map的Swiss Table實現。
在進入swiss table工作原理介紹之前，我們先來回顧一下當前Go map的實現(Go 1.23.x)。
1. Go map的當前實現
map，也稱為映射，或字典，或哈希表[8]，是和數組等一樣的最常見的數據結構。實現map有兩個關鍵的考量，一個是哈希函數(hash function)，另一個就是碰撞處理(collision handling)。hash函數是數學家的事情，這里不表。對于碰撞處理，在大學數據結構課程中，老師通常會介紹兩種常見的處理方案：
- 開放尋址法(Open Addressing)
在發生哈希碰撞時，嘗試在哈希表中尋找下一個可用的位置，如下圖所示k3與k1的哈希值發生碰撞后，算法會嘗試從k1的位置開始向后找到一個空閑的位置：
圖片
- 鏈式哈希法(拉鏈法, Chaining)
每個哈希桶(bucket)存儲一個鏈表（或其他數據結構），所有哈希值相同的元素(比如k1和k3)都被存儲在該鏈表中。
圖片
Go當前的map實現采用的就是鏈式哈希，當然是經過優化過的了。要了解Go map的實現，關鍵把握住下面幾點：
- 編譯器重寫
我們在用戶層代碼中使用的map操作都會被Go編譯器重寫為對應的runtime的map操作，就如下面Go團隊成員Keith Randall在GopherCon大會上講解map實現原理[9]的一個截圖所示：
圖片
- 鏈式哈希
前面提過，Go map當前采用的是鏈式哈希的實現，一個map在內存中的結構大致如下：
圖片
來自Keith Randall的ppt截圖
我們看到，一個map Header代表了一個map類型的實例，map header中存儲了有關map的元數據(圖中字段與當前實現可能有少許差異，畢竟那是幾年前的一個片子了)，如：
- len: 當前map中鍵值對的數量。
- bucket array: 存儲數據的bucket數組，可以對比前面的鏈式哈希的原理圖進行理解，不過不同的是，Go map中每個bucket本身就可以存儲多個鍵值對，而不是指向一個鍵值對的鏈表。
- hash seed: 用于哈希計算的種子，用于分散數據并提高安全性。通常一個bucket可以存儲8個鍵值對，這些鍵值對是根據鍵的哈希值分配到對應的bucket中。
- 溢出桶(overflow bucket)
每個bucket后面還會有Overflow Bucket。當一個bucket中的數據超出容量時，會創建overflow bucket來存儲多余的數據。這樣可以避免直接擴展bucket數組，節省內存空間。但如果出現過多的overflow bucket，性能就會下降。
- “螞蟻搬家”式的擴容
當map中出現過多overflow bucket而導致性能下降時，我們就要考慮map bucket擴容的事兒了，以始終保證map的操作性能在一個合理的范圍。是否擴容由一個名為load factor的參數所控制。load factor是元素數量與bucket數量的比值，比值越高，map的讀寫性能越差。目前Go map采用了一個經驗值來確定是否要擴容，即load factor = 6.5。當load factor超過這個值時，就會觸發擴容。所謂擴容就是增大bucket數量(當前實現為增大一倍數量)，減少碰撞，讓每個bucket中存放的element數量降下來。
擴容需要對存量element做rehash，在元素數量較多的情況下，“一次性”的完成桶的擴容會造成map操作延遲“突增”，無法滿足一些業務場景的要求，因此Go map采用“增量”擴容的方式，即在訪問和插入數據時，“螞蟻搬家”式的做點搬移元素的操作，直到所有元素完成搬移。
Go map的當前實現應該可以適合大多數的場合，但依然有一些性能和延遲敏感的業務場景覺得Go map不夠快，另外一個常被詬病的就是當前實現的桶擴容后就不再縮容(shrink)了[11]，這會給內存帶來壓力。
下面我們再來看看swiss table的結構和工作原理。
2. Swiss table的工作原理
就像前面提到的，Swiss table并非來自某個大學或研究機構的論文，而是來自Google工程師在工程領域的"最佳實踐"，因此關于Swiss table的主要資料都來自Google的開源C++ library Abseil[12]以及開發者的演講視頻[13]。在Abseil庫中，它是flat_hash_map、flat_hash_set、node_hash_map以及node_hash_set等數據結構的底層實現，并且Swiss table的實現在2018年9月正式開源[14]。
和Go map當前實現不同，Swiss table使用的不是拉鏈法，而是開放尋址，但并非傳統的方案。下面是根據公開資源畫出的一個Swiss table的邏輯結構圖(注意：并非真實內存布局)：
圖片
如果用一個式子來表示Swiss table，我們可以用：
A swiss table = N * (metdata array + slots array)我們看到：swiss table將所謂的桶（這里叫slot）分為多個group，每個group中有16個slot，這也是swiss table的創新，即將開放尋址方法中的probing(探測key碰撞后下一個可用的位置(slot))放到一個16個slot的group中進行，這樣的好處是可以通過一個SIMD指令[15]并行探測16個slot，這種方法也被稱為Group Probing。
在上圖中，我們看到一個Group由metadata和16個slot組成。metadata中存儲的是元數據，而slot中存儲的是元素(key和value)。Group probling主要是基于metadata實現的，Google工程師的演講有對group probing實現的細節描述。
當我們向swiss table插入一個元素或是查找一個元素時，swiss table會通過hash函數對key進行求值，結果是一個8字節(64bit)的數。和Go map的當前實現一樣，這個哈希值的不同bit功用不同，下圖是一個來自abseil官網的示例：
圖片
哈希值的高57bit被稱為H1，低7bit被稱為H2。前者用于標識該元素在Group內的索引，查找和插入時都需要它。后者將被用于該元素的元數據，放在metadata中存儲，用于快速的group probing之用，也被稱為哈希指紋。
每個Group的metadata也是一個16字節數組，每個字節對應一個slot，是該slot的控制字節。這個字節的8個bit位的組成如下：
圖來自abseil庫官網
metadata中的控制字節有三個狀態：
- 最高位為1，其余全零為**空閑狀態(Empty)**，即對應的slot尚未曾被任何element占據過；
- 最高位為0，后7位為哈希指紋(H2)，為對應的slot當前已經有element占據的已使用狀態；
- 最高位為1，其他位為1111110的，為對應的slot為已刪除狀態，后續可以被繼續使用。
下面是Abseil開發者演進slide中的一個針對swiss table的迭代邏輯：
圖片
通過這幅圖可以看出H1的作用。不過這里通過pos = pos + 1進行probing（探測）顯然是不高效的！metadata之所以設計為如此，并保存了插入元素的哈希指紋就是為了實現高效的probing，下圖演示了基于key的hash值的H2指紋通過SIMD指令從16個位置中快速得到匹配的pos的過程：
圖片
雖然有兩個匹配項，但這個過程就像“布隆過濾器”一樣，快速排除了不可能的匹配項，減少了不必要的內存訪問。
由于metadata僅有16個字節，它的內存局部性更好。16個控制字節正好填充一個64字節的緩存行(cache line)，使用SIMD指令一次性加載整組控制字節，預取效率高，幾乎沒有cache miss。
由此也可以看到：swiss table的16個條目的分組大小不是隨意選擇的，而是基于現代CPU的緩存行大小(64字節)優化的，保證了一個Group的控制字節能被單次SIMD指令處理。
此外swiss table也是通過load factor來判定是否需要對哈希表進行擴容，一旦擴容，swiss table通常是會將group數量增加一倍，然后重新計算當前所有元素在新groups中的新位置(rehash)，這個過程是有一定開銷的。如果不做優化，當表中元素數量較多時，這個過程會導致操作延遲增加。
最后，雖然多數情況是在group內做probing，但當元素插入時，如果當前Group已滿，就必須探測到下一個Group，并將元素插入到下一個Group。這樣，在該元素的查找操作中，probing也會跨group進行。
到這里，我們已經粗略了解了swiss table的工作原理，那么Go tip對swiss table當前的實現又是怎樣的呢？我們下面就來看看。
3. Go tip版本當前的實現
Go tip版本基于swiss table的實現在https://github.com/golang/go/blob/master/src/internal/runtime/maps下。
由于Go map是原生類型，且有了第一版實現，考慮到Go1兼容性，新版基于swiss table的實現也要繼承已有的語義約束。同時，也要盡量避免swiss table自身的短板，Go團隊在swiss table之上做了局部改進。比如為了將擴容帶來的開銷降到最低，Go引入了多table的設計，以支持漸進式擴容。也就是說一個map實際上是多個swiss table，而不是像上面說的一個map就是一個swiss table。每個table擁有自己的load factor，可以獨立擴容(table的擴容是一次性擴容)，這樣就可以將擴容的開銷從全部數據變為局部少量數據，減少擴容帶來的影響。
Go swiss-table based map的邏輯結構大致如下：
圖片
我們可以看出與C++ swisstable的最直觀不同之處除了有多個table外，每個group包含8個slot和一個control word，而不是16個slot。此外，Go使用了二次探測(quadratic probing), 探測序列必須以空slot結束。
為了實現漸進式擴容，數據分散在多個table中；單個table容量有上限(maxTableCapacity)，超過上限時分裂成兩個table；使用可擴展哈希(extendible hashing)根據hash高位選擇table，且每個table可以獨立增長。
Go使用Directory管理多個table，Directory是Table的數組，大小為2^globalDepth。如果globalDepth=2，那Directory最多有4個表，分為0x00、0x01、0x10、0x11。Go通過key的hash值的前globalDepth個bit來選擇table。這是一種“extendible hashing”，這是一種動態哈希技術，其核心特點是通過動態調整使用的哈希位數(比如上面提到的globalDepth)來實現漸進式擴容。比如：初始可能只用1位哈希值來區分，需要時可以擴展到用2位，再需要時可以擴展到用3位，以此類推。
舉個例子，假設我們用二進制表示哈希值的高位，來看一個漸進式擴容的過程：
- 初始狀態 (Global Depth = 1):
directory
hash前綴 指向的table
0*** --> table1 (Local Depth = 1)
1*** --> table2 (Local Depth = 1)- 當table1滿了需要分裂時，增加一位哈希值 (Global Depth = 2):
directory
hash前綴 指向的table
00** --> table3 (Local Depth = 2) // 由table1擴容而成
01** --> table4 (Local Depth = 2) // 由table1擴容而成
10** --> table2 (Local Depth = 1)
11** --> table2 (Local Depth = 1) // 復用table2因為它的Local Depth還是1- 如果table2也滿了，需要分裂：
directory
hash前綴 指向的table
00** --> table3 (Local Depth = 2)
01** --> table4 (Local Depth = 2)
10** --> table5 (Local Depth = 2) // 由table2擴容而成
11** --> table6 (Local Depth = 2) // 由table2擴容而成通過extendible hashing實現的漸進式擴容，每次只處理一部分數據，擴容過程對其他操作影響小，空間利用更靈活。
對于新版go map實現而言，單個Table達到負載因子閾值時觸發Table擴容。當需要分裂的Table的localDepth等于map的globalDepth時觸發Directory擴容，這就好理解了。
除此之外，Go版本對small map也有特定優化，比如少量元素(<=8)時直接使用單個group，避免或盡量降低swiss table天生在少量元素情況下的性能回退問題。
更多實現細節，大家可以自行閱讀https://github.com/golang/go/blob/master/src/internal/runtime/maps/下的Go源碼進行理解。
注：目前swiss table版的go map依然還未最終定型，并且后續還會有各種優化加入，這里只是對當前的實現(2024.11.10)做概略介紹，不代表以后的map實現與上述思路完全一致。
4. Benchmark
目前gotip版本中GOEXPERIMENT=swissmap默認已經打開[16]，我們直接用gotip版本即可體驗基于swiss table實現的map。
字節工程師zhangyunhao的gomapbench repo[17]提供了對map的性能基準測試代碼，不過這個基準測試太多，我大幅簡化了一下，只使用Int64，并只測試了元素個數分別為12、256和8192時的情況。
注：我基于Centos 7.9，使用Go 1.23.0和gotip(devel go1.24-84e58c8 linux/amd64)跑的benchmark。
// 在experiments/swiss-table-map/mapbenchmark目錄下
$go test -run='^$' -timeout=10h -bench=. -count=10 > origin-map.txt
$GOEXPERIMENT=swissmap gotip test -run='^$' -timeout=10h -bench=. -count=10 > swiss-table-map.txt
$benchstat origin-map.txt swiss-table-map.txt > result.txt下面是result.txt中的結果：
goos: linux
goarch: amd64
pkg: demo
cpu: Intel(R) Xeon(R) Platinum
│ origin-map.txt │ swiss-table-map.txt │
│ sec/op │ sec/op vs base │
MapIter/Int/12-8 179.7n ± 10% 190.6n ± 4% ~ (p=0.436 n=10)
MapIter/Int/256-8 4.328μ ± 5% 3.748μ ± 1% -13.40% (p=0.000 n=10)
MapIter/Int/8192-8 137.3μ ± 1% 123.6μ ± 1% -9.95% (p=0.000 n=10)
MapAccessHit/Int64/12-8 10.12n ± 2% 10.68n ± 14% +5.64% (p=0.000 n=10)
MapAccessHit/Int64/256-8 10.29n ± 3% 11.29n ± 1% +9.77% (p=0.000 n=10)
MapAccessHit/Int64/8192-8 25.99n ± 1% 14.93n ± 1% -42.57% (p=0.000 n=10)
MapAccessMiss/Int64/12-8 12.39n ± 88% 20.99n ± 50% ~ (p=0.669 n=10)
MapAccessMiss/Int64/256-8 13.12n ± 6% 11.34n ± 7% -13.56% (p=0.000 n=10)
MapAccessMiss/Int64/8192-8 15.71n ± 1% 14.03n ± 1% -10.66% (p=0.000 n=10)
MapAssignGrow/Int64/12-8 607.1n ± 2% 622.6n ± 2% +2.54% (p=0.000 n=10)
MapAssignGrow/Int64/256-8 25.98μ ± 3% 23.22μ ± 1% -10.64% (p=0.000 n=10)
MapAssignGrow/Int64/8192-8 792.3μ ± 1% 844.1μ ± 1% +6.54% (p=0.000 n=10)
MapAssignPreAllocate/Int64/12-8 450.2n ± 2% 409.2n ± 1% -9.11% (p=0.000 n=10)
MapAssignPreAllocate/Int64/256-8 10.412μ ± 1% 6.055μ ± 2% -41.84% (p=0.000 n=10)
MapAssignPreAllocate/Int64/8192-8 342.4μ ± 1% 232.6μ ± 2% -32.05% (p=0.000 n=10)
MapAssignReuse/Int64/12-8 374.2n ± 1% 235.4n ± 2% -37.07% (p=0.000 n=10)
MapAssignReuse/Int64/256-8 8.737μ ± 1% 4.716μ ± 4% -46.03% (p=0.000 n=10)
MapAssignReuse/Int64/8192-8 296.4μ ± 1% 181.0μ ± 1% -38.93% (p=0.000 n=10)
geomean 1.159μ 984.2n -15.11%我們看到了除了少數測試項有不足外(比如MapAssignGrow以及一些元素數量少的情況下)，大多數測試項中，新版基于swiss table的map的性能都有大幅提升，有些甚至接近50%！
5. 小結
本文探討了Go語言中的map實現的重塑，即引入Swiss Table這一高效哈希表結構的背景與優勢。Swiss Table由Google工程師開發，旨在優化內存使用和提升性能，解決了傳統哈希表在高負載情況下的性能瓶頸。通過對比現有的鏈式哈希實現，Swiss Table展示了在查詢、插入和刪除操作上顯著提高的性能，尤其是在處理大規模數據時。
經過兩年多的實驗與評估，Go團隊決定將Swiss Table作為Go map的底層實現，預計將在Go 1.24[19]中正式落地。新的實現不僅承繼了原有的語義約束，還通過引入多表和漸進式擴容的設計，進一步優化了擴容過程的性能。盡管當前實現仍在完善中，但Swiss Table的引入無疑為Go語言的性能提升提供了新的可能性，并為未來進一步優化奠定了基礎。
對于那些因Go引入自定義iterator[20]而批評Go團隊的Gopher來說，這個Go map的重塑無疑會很對他們的胃口。
本文涉及的源碼可以在這里[21]下載。
6. 參考資料
- runtime: use SwissTable[22] - https://github.com/golang/go/issues/54766
- swiss table benchmark result[23] - https://gist.github.com/aclements/9fb32ac0a287d2ff360f1bc166cdf4b8
- Swisstable, a Quick and Dirty Description[24] - https://faultlore.com/blah/hashbrown-tldr/
- Swiss Tables Design Notes[25] - https://abseil.io/about/design/swisstables
- Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step[26] - https://www.youtube.com/watch?v=ncHmEUmJZf4
- Abseil's Open Source Hashtables: 2 Years In[27] - https://www.youtube.com/watch?v=JZE3_0qvrMg
- Swiss Tables and absl::Hash[28] - https://abseil.io/blog/20180927-swisstables
- SwissMap: A smaller, faster Golang Hash Table[29] - https://www.dolthub.com/blog/2023-03-28-swiss-map/
- What is a Hash Map?[30] - https://www.freecodecamp.org/news/what-is-a-hash-map/
- Inside the Map Implementation[31] - https://www.youtube.com/watch?v=Tl7mi9QmLns
參考資料
[1] 2024月11月5日的Go compiler and runtime meeting notes: https://github.com/golang/go/issues/43930#issuecomment-2458068992
[2] 使用Swiss table重新實現Go map: https://github.com/golang/go/issues/54766
[3] Go 1.24里程碑: https://github.com/golang/go/milestone/322
[4] Google工程師Matt Kulukundis在2017年CppCon大會上詳細介紹了他們在Swiss Table上的工作: https://www.youtube.com/watch?v=ncHmEUmJZf4
[5] C++ Abseil庫的flat_hash_map(可替換std::unordered_map): https://abseil.io/about/design/swisstables
[6] Rust標準庫Hashmap的默認實現: https://github.com/rust-lang/hashbrown
[7] Michael Pratt: https://github.com/prattmic
[8] 哈希表: https://en.wikipedia.org/wiki/Hash_table
[9] map實現原理: https://www.youtube.com/watch?v=Tl7mi9QmLns
[10] 《Go語言第一課》: http://gk.link/a/10AVZ
[11] 不再縮容(shrink)了: https://github.com/golang/go/issues/20135
[12] Google的開源C++ library Abseil: https://abseil.io/
[13] 開發者的演講視頻: https://www.youtube.com/watch?v=ncHmEUmJZf4
[14] Swiss table的實現在2018年9月正式開源: https://abseil.io/blog/20180927-swisstables
[15] SIMD指令: https://tonybai.com/2024/07/21/simd-in-go
[16] GOEXPERIMENT=swissmap默認已經打開: https://github.com/golang/go/commit/99d60c24e23d4d97ce51b1ee5660b60a5651693a
[17] gomapbench repo: https://github.com/zhangyunhao116/gomapbench
[18] 《Go語言第一課》: http://gk.link/a/10AVZ
[19] Go 1.24: https://github.com/golang/go/milestone/322
[20] 自定義iterator: https://tonybai.com/2024/06/24/range-over-func-and-package-iter-in-go-1-23/
[21] 這里: https://github.com/bigwhite/experiments/tree/master/swiss-table-map
[22] runtime: use SwissTable: https://github.com/golang/go/issues/54766
[23] swiss table benchmark result: https://gist.github.com/aclements/9fb32ac0a287d2ff360f1bc166cdf4b8
[24] Swisstable, a Quick and Dirty Description: https://faultlore.com/blah/hashbrown-tldr/
[25] Swiss Tables Design Notes: https://abseil.io/about/design/swisstables
[26] Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step: https://www.youtube.com/watch?v=ncHmEUmJZf4
[27] Abseil's Open Source Hashtables: 2 Years In: https://www.youtube.com/watch?v=JZE3_0qvrMg
[28] Swiss Tables and absl::Hash: https://abseil.io/blog/20180927-swisstables
[29] SwissMap: A smaller, faster Golang Hash Table: https://www.dolthub.com/blog/2023-03-28-swiss-map/
[30] What is a Hash Map?: https://www.freecodecamp.org/news/what-is-a-hash-map/
[31] Inside the Map Implementation: https://www.youtube.com/watch?v=Tl7mi9QmLns
