[Swiss Table] FlatHashSet 和 ConcurrentFlatHashSet 實作

在 C++ 開發中，標準庫的 std::unordered_set 因為採用鏈結串列（Separate Chaining）處理雜湊碰撞，每個節點都需要獨立配置記憶體。這導致指標跳躍頻繁，極易發生 Cache Miss，成為高效能程式的瓶頸。

現代高效能雜湊表（如 Google 的 absl::flat_hash_set 與 boost::unordered_flat_set）紛紛轉向 開放定址法（Open Addressing） 搭配 SIMD 硬體加速。今天要介紹的這份教學用實作 FlatHashSet.hpp，不僅重現了單執行緒的 SIMD 查詢，更透過四項精巧的並行控制機制，讓多執行緒下的寫入與刪除效能大幅超越 boost::concurrent_flat_set。

---

一、 為什麼它這麼快？記憶體佈局與 SIMD 加速

這份實作採用了與 boost::unordered_flat_set 相同的 Group 分組版面，將記憶體對齊與快取友好度發揮到極致：

1. 15 個 Slot + 16 Bytes 控制碼（Group 結構）

• 連續記憶體：所有的元素（slots）存放在一塊連續陣列中，走訪（for_each）時對 CPU 的硬體預取器（Hardware Prefetcher）極度友善。
• 控制位元組（ctrl）：每 15 個 Slot 分成一個 Group，並配置 16 bytes 的控制資訊：
  • ctrl[0..14]（Tag）：存放該元素 Hash 值的低 8 位元（0 代表空位，若算出 0 則轉為 1）。
  • ctrl[15]（Overflow Bitmask）：8 個位元的 Bloom Filter 概念。當某個 Group 滿了，新元素被迫往後探測（Probing）時，會在經過的 Group 設下對應的 Overflow 位元。

2. 一道 SSE2 指令同時比對 15 筆資料

查詢某個 Key 時，程式不需要逐一比對元素，而是利用 x86 的 SSE2 指令集（match 函式）：

1. _mm_loadu_si128：一次將整個 Group 的 16 bytes 控制碼載入 128-bit 暫存器。
2. _mm_cmpeq_epi8：將目標 Tag 複製 16 份，在單一 CPU 週期內同時與 15 個 Slot 的 Tag 進行平行比對。
3. _mm_movemask_epi8：將比對結果壓縮成一個 15-bit 的整數遮罩（Bitmask），再透過 C++20 的 std::countr_zero 精準定位相符的 Slot。

由於 Tag 有 8 位元，誤判率僅有 1/256，絕大多數的查詢只需要讀取 1 到 2 條 Cache Line 就能完成。而「查不到的 Key」只要檢查 ctrl[15] 的 Overflow 位元為 0，甚至連後續的 Group 都不用探測就能直接結束。

---

二、 單執行緒與多執行緒共用同一套演算法

這份程式碼在架構上非常乾淨，它將核心的 lookup、insertNew、forEach 抽離成模板函式，透過傳入不同的 lock 與 commit 策略（Policy）來切換行為：

• 單執行緒版（FlatHashSet）：傳入空的 noLock lambda，編譯器最佳化後會完全消除鎖的開銷（Zero-cost abstraction）。
• 多執行緒版（ConcurrentFlatHashSet）：傳入細粒度的讀寫鎖 lambda，重複利用完全相同的底層探測邏輯。

---

三、 超越 Boost 的四大並行優化機制

在多執行緒環境下，ConcurrentFlatHashSet 針對多核心 CPU 的快取一致性（Cache Coherence）痛點做了深度調校：

1. 分片容器鎖（64-Slot ContainerLock）與 128-Byte 對齊

一般操作（查詢、新增、刪除）只需要拿容器的「讀鎖」，只有全表擴容（grow）時才拿「寫鎖」。如果所有執行緒共用一把讀寫鎖，光是拿讀鎖的 Atomic 操作就會引發嚴重的 Cache Line 爭搶。

• 分片設計：作者建立 64 個獨立的 Spinlock Slot，每個執行緒透過 thread_local 認領專屬的 Slot，平時讀取互不干擾。
• 對齊 128 Bytes：Intel CPU 的 L2 Spatial Prefetcher 會成對抓取相鄰兩條 64-byte 的 Cache Line。將 Slot 對齊 128 bytes，徹底避免了相鄰執行緒之間的 False Sharing（偽共享）。
• 無鎖化釋放（Plain Store）：釋放讀鎖時使用一般的 store(0, memory_order_release) 而非昂貴的 fetch_sub，避免觸發 CPU 記憶體依賴誤判（4K Aliasing），讓 8 執行緒下的查詢吞吐量從 28 Mops/s 翻倍提升至 54 Mops/s。

2. 樂觀讀（Optimistic Read）與 Prefetch 重疊延遲

在 Group 層級（每個 Group 配一把 tbb::spin_rw_mutex），查詢時會先不上鎖直接用 SIMD 掃描 Tag。只有當 Tag 真的相符時才去拿 Group 的讀鎖進行二次確認。
更巧妙的是，在執行昂貴的拿鎖（Atomic RMW）指令前，程式先呼叫 __builtin_prefetch 預取對應的 slots 記憶體，讓「等待鎖」與「Slot 的 Cache Miss 載入」重疊執行，大幅隱藏記憶體延遲。

3. 樂觀插入（Optimistic Insertion）防重複

兩個執行緒若同時插入相同的 Key，可能同時查到「不存在」。為了不在整個插入過程鎖住整張表，作者為每個 Group 設計了原子計數器 counters_：

1. 查詢前先讀取起始 Group 的計數 c0。
2. 找到空位並寫入 Tag 後，用 CAS（Compare-And-Swap）嘗試將計數器從 c0 推進到 c0 + 1。
3. 若 CAS 失敗，代表這段期間有其他執行緒也從這個 Group 完成了插入（可能是同一個 Key），此時只需把剛寫入的 Tag 清回 0 並重試即可。

4. 分片 Credit 計數器（解決 size 爭搶瓶頸）

boost::concurrent_flat_set 在多執行緒寫入與刪除時效能較慢，主因在於它使用單一原子變數維護元素總數，所有執行緒都在搶同一條 Cache Line。
本實作借鑒了分散式配額的概念：

• 每個執行緒的容器鎖 Slot 都附帶一個本地 credit（已預訂但尚未使用的空位配額）。
• 刪除時：直接將空位加回自己的 credit，完全不碰全域變數。
• 插入時：直接扣除自己的 credit；只有當 credit 用完時，才透過 CAS 向全域的 reserved_ 一次批發領取最多 64 個空位。

---

四、 效能實測數據對比

根據程式碼末尾提供的 Benchmark（測試環境為 400 萬筆隨機 uint64_t）：

單執行緒表現（ns/op，越低越好）

操作項目	本教學實作	boost::unordered_flat_set	std::unordered_set
查詢（Hit）	49.4 ns	50.3 ns	184 ns
查詢（Miss）	25.1 ns	24.0 ns	268 ns
走訪（For Each）	10.0 ns	17.3 ns	144 ns

單執行緒查詢速度與工業級的 Boost 並駕齊驅，比標準庫 std::unordered_set 快了 4 到 11 倍。

多執行緒吞吐量（36 執行緒，Mops/s，越高越好）

操作項目	本教學實作 (ConcurrentFlatHashSet)	boost::concurrent_flat_set	效能提升幅度
Find（查詢）	112.0 Mops/s	102.0 Mops/s	快約 10%
Insert（插入）	5.4 Mops/s	3.0 Mops/s	快 1.8 倍
Erase（刪除）	62.0 Mops/s	4.0 Mops/s	快 15.5 倍

---

五、 結語與設計取捨

這份程式碼是學習現代 C++ 系統程式設計的絕佳教材。它也坦誠地展示了高效能工程中的權衡（Trade-offs）：例如為了達成極致的樂觀讀，在不上鎖的情況下使用 SIMD 讀取 Tag，這在嚴格的 C++ 記憶體模型下屬於 Data Race（ThreadSanitizer 會發出警告），但在 x86 架構下單一 Byte 的讀寫具備原子性，實務上是安全且無害的。

透過這份實作，我們可以清楚看見：真正的效能突破，往往來自於對 CPU 快取架構、指令集平行化以及記憶體一致性模型的深刻理解，而不僅僅是演算法時間複雜度的紙上談兵。

---