2026-09-07 — Debian Code Search 以純 Go SIMD 重寫 TurboPFor 甩掉最後一個 cgo 依賴

Debian Code Search 用純 Go SIMD 重寫 TurboPFor，甩掉最後一個 cgo 依賴

Michael Stapelberg 個人技術部落格 · 2026-09-06

原本的問題

Debian Code Search（Debian/dcs）的反向索引用 TurboPFor 格式壓縮文件 ID 列表，長期以來都靠 cgo 呼叫 C 函式庫 powturbo/TurboPFor-Integer-Compression 來編碼與解碼。cgo 邊界會拖慢建置、增加跨平台移植成本，也擋住 Go 編譯器的 escape analysis 與 inlining 等最佳化路徑。Stapelberg 想把這最後一個 cgo 依賴換成純 Go 實作，但直接照搬邏輯寫出的純量版本，一開始只有 C 版本 76% 的速度（commit e920dc7），效能落差大到不足以取代原本的函式庫。

採用的方法

Go 1.26 新增了實驗性的 simd/archsimd 套件（需開啟 GOEXPERIMENT=simd），在 amd64 上提供 128、256、512-bit 向量型別，讓開發者不必手寫組合語言就能直接在 Go 裡呼叫 SIMD 指令。Stapelberg 分階段導入：先用 AVX2 實作整段 bitpack/unpack 的 kernel（commit 6a9b173），再用 AVX512 處理例外值（exception）的 gather 操作（commit 5d58489），並用 Go generics 依照每種 bit width 產生特化版本的 bitpack 迴圈，例如 bitpack32Unrolled[T bitWidthT]（commit 2db8415）。

其中效益最大的改動是 positional popcount 的重寫：原本統計 32 個值的 bit histogram 需要逐 bit 掃描，Stapelberg 改用 VPERMB 搭配 GF2P8AFFINEQB（Galois Field affine transform）指令，把每個值的統計成本從 12 條指令壓到 1.5 條（commit d02ff36）。這個技巧參考自 2019 年 Klarqvist、Muła、Lemire 的 positional popcount 論文與 Harold Aptroot 2024 年的實作筆記。解碼器則另外設計了向量化（vertical）記憶體佈局 bitunpack256v32，一次攤平處理 256 個值而非逐筆解碼。

//go:build goexperiment.simd && amd64
var hasAVX2 = archsimd.X86.AVX2()

func fillConstant(output []uint32, val uint32) {
	if !hasAVX2 {
		fillConstantScalar(output, val)
		return
	}
	// SIMD implementation
}

實際效果

Stapelberg 用 benchstat -filter '/impl:go /vals:debian-mix .unit:(Mval/s)' baseline.txt bench.txt 逐步量測每個改動的效果：

• 編碼器：加上 SIMD 與 bit-width 特化後追平 C 版本；再加上 positional popcount 後整體再提升 2x；remainder block 改用 generics 後加速 49%–64%
• 解碼器：先靠減少記憶體配置把吞吐量從 773 Mval/s 拉到 858 Mval/s；SIMD vertical layout bitunpack256v32 又比純量版快約 3x
• 整體：純 Go 實作追平甚至超越舊有的 cgo 版本，僅比對應的 C TurboPFor 實作慢約 1.4x

這個結果讓 Debian Code Search 得以完全移除最後一個 cgo 依賴，改用純 Go 加上實驗性 SIMD 套件維持原有的查詢效能。Stapelberg 也同步維護了一份教學用的簡化解碼器 goturbopfor，方便理解 TurboPFor 格式本身。

原始來源：Debian Code Search: Fast TurboPFor with Go SIMD、Debian/dcs repo、powturbo/TurboPFor-Integer-Compression