Go map使用Swiss Table重新實(shí)現(xiàn)，性能最高提升近50%
在2024月11月5日的Go compiler and runtime meeting notes[1]中，我們注意到了一段重要內(nèi)容，如下圖紅框所示：
圖片
這表明，來(lái)自字節(jié)的一位工程師在兩年多前提出的“使用Swiss table重新實(shí)現(xiàn)Go map[2]”的建議即將落地，目前該issue已經(jīng)被納入Go 1.24里程碑[3]。
Swiss Table是由Google工程師于2017年開發(fā)的一種高效哈希表實(shí)現(xiàn)，旨在優(yōu)化內(nèi)存使用和提升性能，解決Google內(nèi)部代碼庫(kù)中廣泛使用的std::unordered_map所面臨的性能問(wèn)題。Google工程師Matt Kulukundis在2017年CppCon大會(huì)上詳細(xì)介紹了他們?cè)赟wiss Table上的工作[4]：
圖片
目前，Swiss Table已被應(yīng)用于多種編程語(yǔ)言，包括C++ Abseil庫(kù)的flat_hash_map(可替換std::unordered_map)[5]、Rust標(biāo)準(zhǔn)庫(kù)Hashmap的默認(rèn)實(shí)現(xiàn)[6]等。
Swiss Table的出色表現(xiàn)是字節(jié)工程師提出這一問(wèn)題的直接原因。字節(jié)跳動(dòng)作為國(guó)內(nèi)使用Go語(yǔ)言較為廣泛的大廠。據(jù)issue描述，Go map的CPU消耗約占服務(wù)總體開銷的4%。其中，map的插入（mapassign）和訪問(wèn)（mapaccess）操作的CPU消耗幾乎是1:1。大家可千萬(wàn)不能小看4%這個(gè)數(shù)字，以字節(jié)、Google這樣大廠的體量，減少1%也意味著真金白銀的大幅節(jié)省。
Swiss Table被視為解決這一問(wèn)題的潛在方案。字節(jié)工程師初版實(shí)現(xiàn)的基準(zhǔn)測(cè)試結(jié)果顯示，與原實(shí)現(xiàn)相比，Swiss Table在查詢、插入和刪除操作上均提升了20%至50%的性能，尤其是在處理大hashmap時(shí)表現(xiàn)尤為突出；迭代性能提升了10%；內(nèi)存使用減少了0%至25%，并且不再消耗額外內(nèi)存。
這些顯著的性能提升引起了Go編譯器和運(yùn)行時(shí)團(tuán)隊(duì)的關(guān)注，特別是當(dāng)時(shí)負(fù)責(zé)該子團(tuán)隊(duì)的Austin Clements。在經(jīng)過(guò)兩年多的實(shí)驗(yàn)和評(píng)估后，Go團(tuán)隊(duì)成員Michael Pratt[7]基于Swiss Table實(shí)現(xiàn)的internal/runtime/maps最終成為Go map的底層默認(rèn)實(shí)現(xiàn)。
在本文中，我們將簡(jiǎn)單介紹Swiss Table這一高效的哈希表實(shí)現(xiàn)算法，并提前看一下Go map的Swiss Table實(shí)現(xiàn)。
在進(jìn)入swiss table工作原理介紹之前，我們先來(lái)回顧一下當(dāng)前Go map的實(shí)現(xiàn)(Go 1.23.x)。
1. Go map的當(dāng)前實(shí)現(xiàn)
map，也稱為映射，或字典，或哈希表[8]，是和數(shù)組等一樣的最常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)。實(shí)現(xiàn)map有兩個(gè)關(guān)鍵的考量，一個(gè)是哈希函數(shù)(hash function)，另一個(gè)就是碰撞處理(collision handling)。hash函數(shù)是數(shù)學(xué)家的事情，這里不表。對(duì)于碰撞處理，在大學(xué)數(shù)據(jù)結(jié)構(gòu)課程中，老師通常會(huì)介紹兩種常見(jiàn)的處理方案：
- 開放尋址法(Open Addressing)
在發(fā)生哈希碰撞時(shí)，嘗試在哈希表中尋找下一個(gè)可用的位置，如下圖所示k3與k1的哈希值發(fā)生碰撞后，算法會(huì)嘗試從k1的位置開始向后找到一個(gè)空閑的位置：
圖片
- 鏈?zhǔn)焦７?拉鏈法, Chaining)
每個(gè)哈希桶(bucket)存儲(chǔ)一個(gè)鏈表（或其他數(shù)據(jù)結(jié)構(gòu)），所有哈希值相同的元素(比如k1和k3)都被存儲(chǔ)在該鏈表中。
圖片
Go當(dāng)前的map實(shí)現(xiàn)采用的就是鏈?zhǔn)焦?，?dāng)然是經(jīng)過(guò)優(yōu)化過(guò)的了。要了解Go map的實(shí)現(xiàn)，關(guān)鍵把握住下面幾點(diǎn)：
- 編譯器重寫
我們?cè)谟脩魧哟a中使用的map操作都會(huì)被Go編譯器重寫為對(duì)應(yīng)的runtime的map操作，就如下面Go團(tuán)隊(duì)成員Keith Randall在GopherCon大會(huì)上講解map實(shí)現(xiàn)原理[9]的一個(gè)截圖所示：
圖片
- 鏈?zhǔn)焦?/li>
前面提過(guò)，Go map當(dāng)前采用的是鏈?zhǔn)焦５膶?shí)現(xiàn)，一個(gè)map在內(nèi)存中的結(jié)構(gòu)大致如下：
圖片
來(lái)自Keith Randall的ppt截圖
我們看到，一個(gè)map Header代表了一個(gè)map類型的實(shí)例，map header中存儲(chǔ)了有關(guān)map的元數(shù)據(jù)(圖中字段與當(dāng)前實(shí)現(xiàn)可能有少許差異，畢竟那是幾年前的一個(gè)片子了)，如：
- len: 當(dāng)前map中鍵值對(duì)的數(shù)量。
- bucket array: 存儲(chǔ)數(shù)據(jù)的bucket數(shù)組，可以對(duì)比前面的鏈?zhǔn)焦５脑韴D進(jìn)行理解，不過(guò)不同的是，Go map中每個(gè)bucket本身就可以存儲(chǔ)多個(gè)鍵值對(duì)，而不是指向一個(gè)鍵值對(duì)的鏈表。
- hash seed: 用于哈希計(jì)算的種子，用于分散數(shù)據(jù)并提高安全性。通常一個(gè)bucket可以存儲(chǔ)8個(gè)鍵值對(duì)，這些鍵值對(duì)是根據(jù)鍵的哈希值分配到對(duì)應(yīng)的bucket中。
- 溢出桶(overflow bucket)
每個(gè)bucket后面還會(huì)有Overflow Bucket。當(dāng)一個(gè)bucket中的數(shù)據(jù)超出容量時(shí)，會(huì)創(chuàng)建overflow bucket來(lái)存儲(chǔ)多余的數(shù)據(jù)。這樣可以避免直接擴(kuò)展bucket數(shù)組，節(jié)省內(nèi)存空間。但如果出現(xiàn)過(guò)多的overflow bucket，性能就會(huì)下降。
- “螞蟻搬家”式的擴(kuò)容
當(dāng)map中出現(xiàn)過(guò)多overflow bucket而導(dǎo)致性能下降時(shí)，我們就要考慮map bucket擴(kuò)容的事兒了，以始終保證map的操作性能在一個(gè)合理的范圍。是否擴(kuò)容由一個(gè)名為load factor的參數(shù)所控制。load factor是元素?cái)?shù)量與bucket數(shù)量的比值，比值越高，map的讀寫性能越差。目前Go map采用了一個(gè)經(jīng)驗(yàn)值來(lái)確定是否要擴(kuò)容，即load factor = 6.5。當(dāng)load factor超過(guò)這個(gè)值時(shí)，就會(huì)觸發(fā)擴(kuò)容。所謂擴(kuò)容就是增大bucket數(shù)量(當(dāng)前實(shí)現(xiàn)為增大一倍數(shù)量)，減少碰撞，讓每個(gè)bucket中存放的element數(shù)量降下來(lái)。
擴(kuò)容需要對(duì)存量element做rehash，在元素?cái)?shù)量較多的情況下，“一次性”的完成桶的擴(kuò)容會(huì)造成map操作延遲“突增”，無(wú)法滿足一些業(yè)務(wù)場(chǎng)景的要求，因此Go map采用“增量”擴(kuò)容的方式，即在訪問(wèn)和插入數(shù)據(jù)時(shí)，“螞蟻搬家”式的做點(diǎn)搬移元素的操作，直到所有元素完成搬移。
Go map的當(dāng)前實(shí)現(xiàn)應(yīng)該可以適合大多數(shù)的場(chǎng)合，但依然有一些性能和延遲敏感的業(yè)務(wù)場(chǎng)景覺(jué)得Go map不夠快，另外一個(gè)常被詬病的就是當(dāng)前實(shí)現(xiàn)的桶擴(kuò)容后就不再縮容(shrink)了[11]，這會(huì)給內(nèi)存帶來(lái)壓力。
下面我們?cè)賮?lái)看看swiss table的結(jié)構(gòu)和工作原理。
2. Swiss table的工作原理
就像前面提到的，Swiss table并非來(lái)自某個(gè)大學(xué)或研究機(jī)構(gòu)的論文，而是來(lái)自Google工程師在工程領(lǐng)域的"最佳實(shí)踐"，因此關(guān)于Swiss table的主要資料都來(lái)自Google的開源C++ library Abseil[12]以及開發(fā)者的演講視頻[13]。在Abseil庫(kù)中，它是flat_hash_map、flat_hash_set、node_hash_map以及node_hash_set等數(shù)據(jù)結(jié)構(gòu)的底層實(shí)現(xiàn)，并且Swiss table的實(shí)現(xiàn)在2018年9月正式開源[14]。
和Go map當(dāng)前實(shí)現(xiàn)不同，Swiss table使用的不是拉鏈法，而是開放尋址，但并非傳統(tǒng)的方案。下面是根據(jù)公開資源畫出的一個(gè)Swiss table的邏輯結(jié)構(gòu)圖(注意：并非真實(shí)內(nèi)存布局)：
圖片
如果用一個(gè)式子來(lái)表示Swiss table，我們可以用：
A swiss table = N * (metdata array + slots array)我們看到：swiss table將所謂的桶（這里叫slot）分為多個(gè)group，每個(gè)group中有16個(gè)slot，這也是swiss table的創(chuàng)新，即將開放尋址方法中的probing(探測(cè)key碰撞后下一個(gè)可用的位置(slot))放到一個(gè)16個(gè)slot的group中進(jìn)行，這樣的好處是可以通過(guò)一個(gè)SIMD指令[15]并行探測(cè)16個(gè)slot，這種方法也被稱為Group Probing。
在上圖中，我們看到一個(gè)Group由metadata和16個(gè)slot組成。metadata中存儲(chǔ)的是元數(shù)據(jù)，而slot中存儲(chǔ)的是元素(key和value)。Group probling主要是基于metadata實(shí)現(xiàn)的，Google工程師的演講有對(duì)group probing實(shí)現(xiàn)的細(xì)節(jié)描述。
當(dāng)我們向swiss table插入一個(gè)元素或是查找一個(gè)元素時(shí)，swiss table會(huì)通過(guò)hash函數(shù)對(duì)key進(jìn)行求值，結(jié)果是一個(gè)8字節(jié)(64bit)的數(shù)。和Go map的當(dāng)前實(shí)現(xiàn)一樣，這個(gè)哈希值的不同bit功用不同，下圖是一個(gè)來(lái)自abseil官網(wǎng)的示例：
圖片
哈希值的高57bit被稱為H1，低7bit被稱為H2。前者用于標(biāo)識(shí)該元素在Group內(nèi)的索引，查找和插入時(shí)都需要它。后者將被用于該元素的元數(shù)據(jù)，放在metadata中存儲(chǔ)，用于快速的group probing之用，也被稱為哈希指紋。
每個(gè)Group的metadata也是一個(gè)16字節(jié)數(shù)組，每個(gè)字節(jié)對(duì)應(yīng)一個(gè)slot，是該slot的控制字節(jié)。這個(gè)字節(jié)的8個(gè)bit位的組成如下：
圖來(lái)自abseil庫(kù)官網(wǎng)
metadata中的控制字節(jié)有三個(gè)狀態(tài)：
- 最高位為1，其余全零為**空閑狀態(tài)(Empty)**，即對(duì)應(yīng)的slot尚未曾被任何element占據(jù)過(guò)；
- 最高位為0，后7位為哈希指紋(H2)，為對(duì)應(yīng)的slot當(dāng)前已經(jīng)有element占據(jù)的已使用狀態(tài)；
- 最高位為1，其他位為1111110的，為對(duì)應(yīng)的slot為已刪除狀態(tài)，后續(xù)可以被繼續(xù)使用。
下面是Abseil開發(fā)者演進(jìn)slide中的一個(gè)針對(duì)swiss table的迭代邏輯：
圖片
通過(guò)這幅圖可以看出H1的作用。不過(guò)這里通過(guò)pos = pos + 1進(jìn)行probing（探測(cè)）顯然是不高效的！metadata之所以設(shè)計(jì)為如此，并保存了插入元素的哈希指紋就是為了實(shí)現(xiàn)高效的probing，下圖演示了基于key的hash值的H2指紋通過(guò)SIMD指令從16個(gè)位置中快速得到匹配的pos的過(guò)程：
圖片
雖然有兩個(gè)匹配項(xiàng)，但這個(gè)過(guò)程就像“布隆過(guò)濾器”一樣，快速排除了不可能的匹配項(xiàng)，減少了不必要的內(nèi)存訪問(wèn)。
由于metadata僅有16個(gè)字節(jié)，它的內(nèi)存局部性更好。16個(gè)控制字節(jié)正好填充一個(gè)64字節(jié)的緩存行(cache line)，使用SIMD指令一次性加載整組控制字節(jié)，預(yù)取效率高，幾乎沒(méi)有cache miss。
由此也可以看到：swiss table的16個(gè)條目的分組大小不是隨意選擇的，而是基于現(xiàn)代CPU的緩存行大小(64字節(jié))優(yōu)化的，保證了一個(gè)Group的控制字節(jié)能被單次SIMD指令處理。
此外swiss table也是通過(guò)load factor來(lái)判定是否需要對(duì)哈希表進(jìn)行擴(kuò)容，一旦擴(kuò)容，swiss table通常是會(huì)將group數(shù)量增加一倍，然后重新計(jì)算當(dāng)前所有元素在新groups中的新位置(rehash)，這個(gè)過(guò)程是有一定開銷的。如果不做優(yōu)化，當(dāng)表中元素?cái)?shù)量較多時(shí)，這個(gè)過(guò)程會(huì)導(dǎo)致操作延遲增加。
最后，雖然多數(shù)情況是在group內(nèi)做probing，但當(dāng)元素插入時(shí)，如果當(dāng)前Group已滿，就必須探測(cè)到下一個(gè)Group，并將元素插入到下一個(gè)Group。這樣，在該元素的查找操作中，probing也會(huì)跨group進(jìn)行。
到這里，我們已經(jīng)粗略了解了swiss table的工作原理，那么Go tip對(duì)swiss table當(dāng)前的實(shí)現(xiàn)又是怎樣的呢？我們下面就來(lái)看看。
3. Go tip版本當(dāng)前的實(shí)現(xiàn)
Go tip版本基于swiss table的實(shí)現(xiàn)在https://github.com/golang/go/blob/master/src/internal/runtime/maps下。
由于Go map是原生類型，且有了第一版實(shí)現(xiàn)，考慮到Go1兼容性，新版基于swiss table的實(shí)現(xiàn)也要繼承已有的語(yǔ)義約束。同時(shí)，也要盡量避免swiss table自身的短板，Go團(tuán)隊(duì)在swiss table之上做了局部改進(jìn)。比如為了將擴(kuò)容帶來(lái)的開銷降到最低，Go引入了多table的設(shè)計(jì)，以支持漸進(jìn)式擴(kuò)容。也就是說(shuō)一個(gè)map實(shí)際上是多個(gè)swiss table，而不是像上面說(shuō)的一個(gè)map就是一個(gè)swiss table。每個(gè)table擁有自己的load factor，可以獨(dú)立擴(kuò)容(table的擴(kuò)容是一次性擴(kuò)容)，這樣就可以將擴(kuò)容的開銷從全部數(shù)據(jù)變?yōu)榫植可倭繑?shù)據(jù)，減少擴(kuò)容帶來(lái)的影響。
Go swiss-table based map的邏輯結(jié)構(gòu)大致如下：
圖片
我們可以看出與C++ swisstable的最直觀不同之處除了有多個(gè)table外，每個(gè)group包含8個(gè)slot和一個(gè)control word，而不是16個(gè)slot。此外，Go使用了二次探測(cè)(quadratic probing), 探測(cè)序列必須以空slot結(jié)束。
為了實(shí)現(xiàn)漸進(jìn)式擴(kuò)容，數(shù)據(jù)分散在多個(gè)table中；單個(gè)table容量有上限(maxTableCapacity)，超過(guò)上限時(shí)分裂成兩個(gè)table；使用可擴(kuò)展哈希(extendible hashing)根據(jù)hash高位選擇table，且每個(gè)table可以獨(dú)立增長(zhǎng)。
Go使用Directory管理多個(gè)table，Directory是Table的數(shù)組，大小為2^globalDepth。如果globalDepth=2，那Directory最多有4個(gè)表，分為0x00、0x01、0x10、0x11。Go通過(guò)key的hash值的前globalDepth個(gè)bit來(lái)選擇table。這是一種“extendible hashing”，這是一種動(dòng)態(tài)哈希技術(shù)，其核心特點(diǎn)是通過(guò)動(dòng)態(tài)調(diào)整使用的哈希位數(shù)(比如上面提到的globalDepth)來(lái)實(shí)現(xiàn)漸進(jìn)式擴(kuò)容。比如：初始可能只用1位哈希值來(lái)區(qū)分，需要時(shí)可以擴(kuò)展到用2位，再需要時(shí)可以擴(kuò)展到用3位，以此類推。
舉個(gè)例子，假設(shè)我們用二進(jìn)制表示哈希值的高位，來(lái)看一個(gè)漸進(jìn)式擴(kuò)容的過(guò)程：
- 初始狀態(tài) (Global Depth = 1):
directory
hash前綴 指向的table
0*** --> table1 (Local Depth = 1)
1*** --> table2 (Local Depth = 1)- 當(dāng)table1滿了需要分裂時(shí)，增加一位哈希值 (Global Depth = 2):
directory
hash前綴 指向的table
00** --> table3 (Local Depth = 2) // 由table1擴(kuò)容而成
01** --> table4 (Local Depth = 2) // 由table1擴(kuò)容而成
10** --> table2 (Local Depth = 1)
11** --> table2 (Local Depth = 1) // 復(fù)用table2因?yàn)樗腖ocal Depth還是1- 如果table2也滿了，需要分裂：
directory
hash前綴 指向的table
00** --> table3 (Local Depth = 2)
01** --> table4 (Local Depth = 2)
10** --> table5 (Local Depth = 2) // 由table2擴(kuò)容而成
11** --> table6 (Local Depth = 2) // 由table2擴(kuò)容而成通過(guò)extendible hashing實(shí)現(xiàn)的漸進(jìn)式擴(kuò)容，每次只處理一部分?jǐn)?shù)據(jù)，擴(kuò)容過(guò)程對(duì)其他操作影響小，空間利用更靈活。
對(duì)于新版go map實(shí)現(xiàn)而言，單個(gè)Table達(dá)到負(fù)載因子閾值時(shí)觸發(fā)Table擴(kuò)容。當(dāng)需要分裂的Table的localDepth等于map的globalDepth時(shí)觸發(fā)Directory擴(kuò)容，這就好理解了。
除此之外，Go版本對(duì)small map也有特定優(yōu)化，比如少量元素(<=8)時(shí)直接使用單個(gè)group，避免或盡量降低swiss table天生在少量元素情況下的性能回退問(wèn)題。
更多實(shí)現(xiàn)細(xì)節(jié)，大家可以自行閱讀https://github.com/golang/go/blob/master/src/internal/runtime/maps/下的Go源碼進(jìn)行理解。
注：目前swiss table版的go map依然還未最終定型，并且后續(xù)還會(huì)有各種優(yōu)化加入，這里只是對(duì)當(dāng)前的實(shí)現(xiàn)(2024.11.10)做概略介紹，不代表以后的map實(shí)現(xiàn)與上述思路完全一致。
4. Benchmark
目前gotip版本中GOEXPERIMENT=swissmap默認(rèn)已經(jīng)打開[16]，我們直接用gotip版本即可體驗(yàn)基于swiss table實(shí)現(xiàn)的map。
字節(jié)工程師zhangyunhao的gomapbench repo[17]提供了對(duì)map的性能基準(zhǔn)測(cè)試代碼，不過(guò)這個(gè)基準(zhǔn)測(cè)試太多，我大幅簡(jiǎn)化了一下，只使用Int64，并只測(cè)試了元素個(gè)數(shù)分別為12、256和8192時(shí)的情況。
注：我基于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中的結(jié)果：
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%我們看到了除了少數(shù)測(cè)試項(xiàng)有不足外(比如MapAssignGrow以及一些元素?cái)?shù)量少的情況下)，大多數(shù)測(cè)試項(xiàng)中，新版基于swiss table的map的性能都有大幅提升，有些甚至接近50%！
5. 小結(jié)
本文探討了Go語(yǔ)言中的map實(shí)現(xiàn)的重塑，即引入Swiss Table這一高效哈希表結(jié)構(gòu)的背景與優(yōu)勢(shì)。Swiss Table由Google工程師開發(fā)，旨在優(yōu)化內(nèi)存使用和提升性能，解決了傳統(tǒng)哈希表在高負(fù)載情況下的性能瓶頸。通過(guò)對(duì)比現(xiàn)有的鏈?zhǔn)焦?shí)現(xiàn)，Swiss Table展示了在查詢、插入和刪除操作上顯著提高的性能，尤其是在處理大規(guī)模數(shù)據(jù)時(shí)。
經(jīng)過(guò)兩年多的實(shí)驗(yàn)與評(píng)估，Go團(tuán)隊(duì)決定將Swiss Table作為Go map的底層實(shí)現(xiàn)，預(yù)計(jì)將在Go 1.24[19]中正式落地。新的實(shí)現(xiàn)不僅承繼了原有的語(yǔ)義約束，還通過(guò)引入多表和漸進(jìn)式擴(kuò)容的設(shè)計(jì)，進(jìn)一步優(yōu)化了擴(kuò)容過(guò)程的性能。盡管當(dāng)前實(shí)現(xiàn)仍在完善中，但Swiss Table的引入無(wú)疑為Go語(yǔ)言的性能提升提供了新的可能性，并為未來(lái)進(jìn)一步優(yōu)化奠定了基礎(chǔ)。
對(duì)于那些因Go引入自定義iterator[20]而批評(píng)Go團(tuán)隊(duì)的Gopher來(lái)說(shuō)，這個(gè)Go map的重塑無(wú)疑會(huì)很對(duì)他們的胃口。
本文涉及的源碼可以在這里[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重新實(shí)現(xiàn)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大會(huì)上詳細(xì)介紹了他們?cè)赟wiss Table上的工作: https://www.youtube.com/watch?v=ncHmEUmJZf4
[5] C++ Abseil庫(kù)的flat_hash_map(可替換std::unordered_map): https://abseil.io/about/design/swisstables
[6] Rust標(biāo)準(zhǔn)庫(kù)Hashmap的默認(rèn)實(shí)現(xiàn): https://github.com/rust-lang/hashbrown
[7] Michael Pratt: https://github.com/prattmic
[8] 哈希表: https://en.wikipedia.org/wiki/Hash_table
[9] map實(shí)現(xiàn)原理: https://www.youtube.com/watch?v=Tl7mi9QmLns
[10] 《Go語(yǔ)言第一課》: http://gk.link/a/10AVZ
[11] 不再縮容(shrink)了: https://github.com/golang/go/issues/20135
[12] Google的開源C++ library Abseil: https://abseil.io/
[13] 開發(fā)者的演講視頻: https://www.youtube.com/watch?v=ncHmEUmJZf4
[14] Swiss table的實(shí)現(xiàn)在2018年9月正式開源: https://abseil.io/blog/20180927-swisstables
[15] SIMD指令: https://tonybai.com/2024/07/21/simd-in-go
[16] GOEXPERIMENT=swissmap默認(rèn)已經(jīng)打開: https://github.com/golang/go/commit/99d60c24e23d4d97ce51b1ee5660b60a5651693a
[17] gomapbench repo: https://github.com/zhangyunhao116/gomapbench
[18] 《Go語(yǔ)言第一課》: 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
