2026-08-27 — Go sync.Map 雜湊樹重寫、CPU 記憶體排序模型與 mold 連結器平行化設計

並行系統再進化:Go sync.Map 雜湊樹重寫、CPU 記憶體排序機制與 mold 連結器平行化設計

VictoriaMetrics · 2026-08-26

VictoriaMetrics 工程團隊於 2026-08-26 發布文章,拆解 Go 標準函式庫 sync.Map 從公開 API 到內部雜湊樹(hash trie)實作的轉變。同一時間,晶片架構學者 Fabian Giesen 在部落格 fgiesen.wordpress.com(2026-08-25)發表 CPU 記憶體排序模型解析;連結器 mold 的作者 Rui Ueyama 則在 arXiv 公開論文 arxiv:2608.23228,說明這套大規模平行連結器已獲 ASPLOS 2027 錄取。三篇文章分別從語言執行期、硬體排序模型與建置工具鏈的角度,呈現系統軟體處理「平行化」的不同層次。

背景:sync.Map 為何要換內部結構

sync.Map 是 Go 標準庫中提供並行安全存取的 map,讓多個 goroutine 不必額外加鎖即可讀寫。它在 Go 尚未支援泛型前就已存在,因此 API 至今仍使用 any 型別。公開方法包含:

Load(key) / Store(key, value) / Delete(key)
LoadOrStore(key, value) / LoadAndDelete(key) / Swap(key, value)
CompareAndSwap(key, old, new) / CompareAndDelete(key, old)
Range(func(key, value any) bool) / Clear()

文章特別指出 sync.Map 沒有 Len 方法,要計數只能透過 Range 走訪整個 map。Go 1.24 曾把雜湊樹列為實驗性預設實作,Go 1.26 則移除實驗旗標,正式定為唯一實作。

核心改動:雜湊樹的節點設計

公開的 Map 內部封裝一個 isync.HashTrieMap[any, any],樹狀結構每個節點有 16 個子節點槽位,由雜湊值切出的 4 位元一組決定路徑,樹的最大深度因此固定為 16 層。節點分為兩種:

type indirect[K comparable, V any] struct {
    dead     atomic.Bool
    mu       Mutex
    parent   *indirect[K, V]
    children [16]atomic.Pointer[node[K, V]]
}

type entry[K comparable, V any] struct {
    overflow atomic.Pointer[entry[K, V]]
    key      K
    value    V
}

當多個鍵的雜湊值在所有分組都相同時,會透過 entry 節點的 overflow 欄位串成鏈結串列。寫入分四步:先無鎖搜尋、鎖住直接父節點、重新確認槽位有效,最後以原子指標寫入發布,Load 全程不需取得節點鎖,可與寫入並行執行。

規格細節:效能與記憶體代價

作者以 Apple M4 Pro 量測 200ms 執行結果,單鍵競爭寫入時雜湊樹反而較慢,但多鍵、多核心情境下優勢明顯:

情境	並行度	map+RWMutex	sync.Map
單鍵重複更新	1 CPU	19.43 ns/op	28.99 ns/op
單鍵重複更新	8 CPU	101.5 ns/op	124.4 ns/op
多鍵、命中率高	1 CPU	35.35 ns/op	58.90 ns/op
多鍵、命中率高	8 CPU	195.1 ns/op	32.87 ns/op

在 100 萬筆資料規模下,sync.Map 記憶體用量約為原生 map 的 3 到 5 倍(115.9 MiB 對 36.1 MiB),屬於用空間換取多核心寫入吞吐量的設計取捨。

CPU 記憶體排序:強弱模型與投機重排

Fabian Giesen 的文章把處理器分成兩類記憶體模型:x86、SPARC 採用較嚴格的 TSO(total store order),ARM、RISC-V 則屬於弱排序模型,允許更自由的載入/儲存重排。他指出 CPU 實際上採「先做、後驗證」(trust, but verify)的樂觀策略:多數 load 假設資料未被其他核心改動,因此可以提前重排執行,只有偵測到跨核心競爭時才回滾重試。經典的重排現象可用兩個執行緒示意:

// Thread 1         // Thread 2
x = 1;               y = 1;
r1 = load(y);        r2 = load(x);
// 弱排序模型下,r1==0 且 r2==0 可能同時成立

文章也提到 Apple Silicon 提供硬體級 TSO 相容模式,供 Rosetta 模擬 x86 程式使用,代價是約 7% 的效能損耗,顯示排序模型的選擇本質是相容性與效能之間的取捨。

mold 連結器:用資料平行化取代任務佇列

Rui Ueyama 在論文 arxiv:2608.23228 中指出,傳統連結器(如 gold)採任務平行化,把工作丟進佇列讓執行緒搶著做,但符號解析與封存檔(archive)處理彼此糾纏,難以真正平行。mold 的做法是先平行解析所有輸入檔案,再把符號解析拆成獨立的平行階段,關鍵步驟包括:

符號解析:對共用符號物件的 owner 欄位做原子 compare-and-swap
字串合併:用 HyperLogLog 預估基數的並行雜湊表,避免重新配置
重定位掃描與區段垃圾回收:parallel-for 搭配 feeder pattern 的標記清除
Identical Code Folding:以雜湊為基礎的 color refinement,逐輪平行細化
輸出產生:每個 input section 各自平行拷貝資料並套用 relocation

影響範圍:效能數字與瓶頸

論文測得連結 TensorFlow 除錯版二進位檔時,mold 僅需 3.23 秒,lld 需要 52.16 秒,達 16.1 倍差距;Firefox 除錯版為 0.89 秒對 4.44 秒(5.0 倍),整體對 lld 平均快 2.4 至 16.1 倍,對 GNU ld 最高快 112 倍。Firefox 連結在 1 執行緒時 mold 為 12.2 秒,32 執行緒降到 0.9 秒(13.5 倍),64 執行緒時因記憶體頻寬飽和而不再提升。消融實驗顯示,若把輸出拷貝與重定位這一階段改回序列執行,總時間會暴增 542%,但論文強調沒有單一優化能主導結果,加速是所有階段平行化的累積效果。

原始來源:VictoriaMetrics、Fabian Giesen's blog、arXiv:2608.23228

End of article