大家好，我是煎魚。

本次 Go1.24 新版本又帶來了一個(gè)比較不錯(cuò)的優(yōu)化點(diǎn)，Go map 做了一個(gè)比較大的改變，有了一定的性能優(yōu)化。

咱們又可以躺著升級(jí)個(gè)版本就得到一定的性能益處了。今天這篇文章將主要針對(duì)這部分進(jìn)行新版本特性分享。

該提案（go/issues/54766[1]）的發(fā)起方是來自字節(jié)的大佬們。主要目的建議在 Go map 使用 Swiss Table 來替換 Hashmap 的原始實(shí)現(xiàn)。

圖片

這里不得不提到 Swiss Table 是什么？好像比 Hashmap 牛逼許多。

Swiss Table 是什么

Swiss Table[2] 是一種用于解決哈希沖突的高效哈希表實(shí)現(xiàn)，最初由 Google 的工程師開發(fā)，在 2017 年首次在技術(shù)大會(huì)中提出。并應(yīng)用于其開源的 Abseil C++ 庫(kù)中。

圖片

Swiss Table 的名字來源于其獨(dú)特的查找方式，該方式結(jié)合了緊湊的存儲(chǔ)和高效的查找性能，類似瑞士軍刀般功能強(qiáng)大且多用途。

以下簡(jiǎn)單介紹 Swiss Table 的幾個(gè)核心概念。有想了解的同學(xué)可以淺嘗。不感興趣的可以跳過該章節(jié)。

緊湊的存儲(chǔ)布局

• Swiss Table 使用小塊連續(xù)內(nèi)存（稱為 bucket groups）存儲(chǔ)哈希表中的條目。每個(gè) bucket group 通常包含 16 個(gè)條目。
• 表的元數(shù)據(jù)（如哈希值的高位部分）存儲(chǔ)在一個(gè)緊湊的位圖結(jié)構(gòu)中，這使得查找操作可以快速跳過空的或不匹配的條目。

高效的查找

• 查找時(shí)，Swiss Table 通過元數(shù)據(jù)位圖快速定位可能的條目位置，避免遍歷所有條目。
• 使用 SIMD（單指令多數(shù)據(jù)）技術(shù)，在現(xiàn)代 CPU 上一次性檢查多個(gè)桶，大大提高了查找性能。

緩存友好

• 連續(xù)存儲(chǔ)布局和緊湊的元數(shù)據(jù)結(jié)構(gòu)減少了緩存未命中率，提高了性能。
• 查找和插入操作充分利用了 CPU 的緩存層次結(jié)構(gòu)。

減少內(nèi)存碎片

• Swiss Table 在設(shè)計(jì)上盡量減少內(nèi)存使用，同時(shí)保持高性能。
• 它通過有效的內(nèi)存管理策略減少了因沖突或增長(zhǎng)導(dǎo)致的內(nèi)存碎片。

漸進(jìn)式增長(zhǎng)

• 在需要擴(kuò)展哈希表時(shí)，Swiss Table 采用漸進(jìn)式增長(zhǎng)策略，避免了傳統(tǒng)哈希表一次性擴(kuò)展帶來的性能波動(dòng)。

對(duì) Go map 的用處和效益

在字節(jié)大佬們提供的測(cè)試報(bào)告中，Go map 使用 Swiss Table 而不是 Hashmap 時(shí)，能夠帶來以下的性能效益：

• 查詢：在查詢較大的 hashmap 或查詢 hashmap 中不存在的元素時(shí)，有顯著的提升（20%~50%）。在查詢?cè)剌^少的 hashmap 時(shí)，性能下降最多 20%。
• 插入和刪除：在幾乎所有情況下都有顯著提升（20%~50%）。
• 迭代（iterate）：性能提升了大約 10%。
• 內(nèi)存情況：在大多數(shù)情況下，內(nèi)存使用量減少了 0%~25%。重復(fù)使用固定大小的 hashmap 不再消耗任何額外的內(nèi)存。

使用 Swiss Table 的改造是對(duì)于 Go map 有較大的綜合性能提升的。針對(duì)這一變更評(píng)估了 2 年多（2022 年發(fā)起）后，將在 2025 年 2 月發(fā)布的 Go1.24 正式被應(yīng)用。

但由于該特性還處于實(shí)驗(yàn)性，希望關(guān)閉的同學(xué)也可以設(shè)置 GOEXPERIMENT=noswissmap 來進(jìn)行關(guān)閉。用于做簡(jiǎn)單的對(duì)照數(shù)據(jù)實(shí)驗(yàn)也是不錯(cuò)的。

總結(jié)

本次國(guó)內(nèi)的字節(jié)大佬們?yōu)?Go 運(yùn)行時(shí)貢獻(xiàn)了 Go map 的 Swiss Table 的改造，給 map 帶來了較大的性能提高。

參考資料

[1]go/issues/54766: https://github.com/golang/go/issues/54766

[2]Swiss Table: https://abseil.io/about/design/swisstables