Debian Code Search: Fast TurboPFor with Go SIMD

查看原文 / View Original 编辑 / Edit

Debian Code Search: Fast TurboPFor with Go SIMD

Debian Code Search: Fast TurboPFor with Go SIMD published 2026-09-06 in tags debian golang. Debian Code Search：利用 Go SIMD 实现快速 TurboPFor，发布于 2026 年 9 月 6 日，标签：debian, golang。

This August, I accomplished what I wanted for many years: I deleted the last cgo dependency in Debian Code Search! This was made possible by Go’s recently introduced SIMD support, because now we can implement the TurboPFor integer compression format as efficiently — more efficiently, in fact, by using the newer AVX512 instruction set! — as the reference implementation. 今年八月，我完成了多年来的夙愿：我删除了 Debian Code Search 中最后一个 cgo 依赖！这得益于 Go 最近引入的 SIMD 支持，因为现在我们可以利用更新的 AVX512 指令集，以与参考实现相同（甚至更高效）的性能来实现 TurboPFor 整数压缩格式！

Background: Why does DCS need a fast Integer Codec?

背景：为什么 DCS 需要快速的整数编解码器？

Debian Code Search (DCS) is a search engine that allows searching all the Open Source source code within Debian, with either literal search expressions or regular expression search queries. A search engine uses an inverted index: a map from term to documents containing the term. Each document is typically represented most efficiently by using an id, so the index consists of many lists of document ids. When searching, it is important to quickly decode these lists to answer the search query. Debian Code Search (DCS) 是一个搜索引擎，允许用户使用字面搜索表达式或正则表达式搜索 Debian 内的所有开源源代码。搜索引擎使用倒排索引：即从词项到包含该词项的文档的映射。每个文档通常通过 ID 来最高效地表示，因此索引由许多文档 ID 列表组成。在搜索时，快速解码这些列表以响应查询至关重要。

However, there is a point of diminishing returns where the decoding speed, even though it can still be measurably improved quite a bit, no longer influences the overall query duration. From 2012 (its inception) to 2019, Debian Code Search used to use a small index format, and queries were fast because the index was kept entirely in RAM. In 2019, I implemented the new index format, which adds an on-disk positional index. For literal queries (78.2% of DCS queries), querying the positional index on disk is faster than querying the non-positional index in RAM. 然而，解码速度存在边际效应递减点：尽管解码速度仍有显著提升空间，但它已不再影响整体查询耗时。从 2012 年（创立）到 2019 年，Debian Code Search 使用一种小型索引格式，由于索引完全保存在内存中，查询速度很快。2019 年，我实现了新的索引格式，增加了磁盘位置索引。对于字面查询（占 DCS 查询的 78.2%），查询磁盘上的位置索引比查询内存中的非位置索引更快。

The efficient encoding of the TurboPFor format makes it possible to fit such an index on a mid-sized Hetzner server, which I rent with two 1 TB SSD disks. The optimized decoder of the C TurboPFor library is what made decoding fast at query time. If you want to dive deeper into the algorithm, see this blog post from February 2019: TurboPFor: an analysis. TurboPFor 格式的高效编码使得将此类索引存放在中型 Hetzner 服务器（我租用了两块 1TB SSD）上成为可能。C 语言版 TurboPFor 库的优化解码器是实现查询时快速解码的关键。如果你想深入了解该算法，请参阅 2019 年 2 月的博文：TurboPFor: an analysis。

SIMD in Go

Go 中的 SIMD

For many years, you had the following options for using SIMD instructions in Go: 多年来，在 Go 中使用 SIMD 指令有以下几种选择：

  1. Hand-writing Go assembler code. This is only doable for small functions, for example bytes.IndexByte is implemented with hand-written Go assembly (including AVX2).

  2. 手写 Go 汇编代码。这仅适用于小型函数，例如 bytes.IndexByte 就是通过手写 Go 汇编（包括 AVX2）实现的。

  3. Generating Go assembler code with tools like Michael McLoughlin’s “Avo”. This is how crypto/internal/fips140/sha256 uses AVX2. While Avo generator code definitely is higher-level than hand-written assembly, it is still too close to assembly for my taste.

  4. 使用 Michael McLoughlin 的“Avo”等工具生成 Go 汇编代码。crypto/internal/fips140/sha256 就是这样使用 AVX2 的。虽然 Avo 生成的代码确实比手写汇编更高级，但在我看来它仍然太接近汇编了。

  5. Use a C library via cgo so gcc or clang compiles SIMD code. Debian Code Search used to use the powturbo/TurboPFor C library via cgo for the last 7 years. The C TurboPFor library has served us well, but Debian Code Search was always intended to be a project using Go, so I would prefer it if I did not have any C code in the project.

  6. 通过 cgo 使用 C 库，让 gcc 或 clang 编译 SIMD 代码。过去 7 年里，Debian Code Search 一直通过 cgo 使用 powturbo/TurboPFor C 库。C 版 TurboPFor 库表现良好，但 Debian Code Search 的初衷始终是一个纯 Go 项目，所以我更希望项目中不包含任何 C 代码。

Go 1.26 (released in February 2026) introduced the simd/archsimd package: Go 1.26（于 2026 年 2 月发布）引入了 simd/archsimd 包：

Go 1.26 introduces a new experimental simd/archsimd package, which can be enabled by setting the environment variable GOEXPERIMENT=simd at build time. This package provides access to architecture-specific SIMD operations. It is currently available on the amd64 architecture and supports 128-bit, 256-bit, and 512-bit vector types, such as Int8x16 and Float64x8, with operations such as Int8x16.Add. The API is not yet considered stable. — Go 1.26 Release Notes Go 1.26 引入了一个新的实验性 simd/archsimd 包，可以通过在构建时设置环境变量 GOEXPERIMENT=simd 来启用。该包提供了对特定架构 SIMD 操作的访问。目前它在 amd64 架构上可用，支持 128 位、256 位和 512 位向量类型（如 Int8x16 和 Float64x8），并提供诸如 Int8x16.Add 之类的操作。该 API 尚不稳定。—— Go 1.26 发行说明

For my 2019 TurboPFor analysis, I implemented goturbopfor, a native Go teaching decoder (without any SIMD), because I find Go code easier to follow than C code, especially optimized C code. My implementation was intentionally not optimized so that the code was easier to study. 在 2019 年进行 TurboPFor 分析时，我实现了 goturbopfor，这是一个原生 Go 教学解码器（不含任何 SIMD），因为我觉得 Go 代码比 C 代码（尤其是经过优化的 C 代码）更容易理解。我的实现特意没有进行优化，以便于学习代码。

The TurboPFor format/algorithm has a vector-optimized part: bitpacking comes in a scalar variant (bitunpack32) and a vector variant (bitunpack256v32), where the vector variant is used for full blocks (256 values) and the scalar variant is used for remainder blocks (< 256 values). TurboPFor 格式/算法包含一个向量优化部分：位打包（bitpacking）分为标量变体（bitunpack32）和向量变体（bitunpack256v32），其中向量变体用于完整块（256 个值），标量变体用于剩余块（< 256 个值）。

When Go 1.26 was released, I used Claude Code to explore whether my native Go decoder’s bitunpack256v32 function (for the vertical vector layout) could be implemented using Go SIMD, and the answer was yes, it was possible and it was faster than without SIMD, but not quite at the level of C TurboPFor. If you let Claude Code try for long enough, it eventually finds enough optimizations (about 10) to match C performance. 当 Go 1.26 发布时，我使用 Claude Code 探索了我的原生 Go 解码器的 bitunpack256v32 函数（用于垂直向量布局）是否可以使用 Go SIMD 实现。答案是肯定的，这不仅可行，而且比不使用 SIMD 时更快，但尚未达到 C 版 TurboPFor 的水平。如果你让 Claude Code 尝试足够长的时间，它最终会找到足够的优化（约 10 处），从而达到 C 语言的性能水平。

I don’t want to vibe-code Debian Code Search, though, so I figured I would find some time to review the SIMD code at some point and see if I could implement something similar myself. Before I found enough time and motivation to complete said review, I discovered that to not regress real-life query performance by more than 10 to 100 milliseconds (which seems acceptable), I don’t actually need to add SIMD code to my teaching decoder at all; it would be sufficient to reduce allocations in my teaching decoder and specialize it per bit width. 不过，我不想通过“凭感觉编码”（vibe-coding）来维护 Debian Code Search，所以我打算找时间审查这些 SIMD 代码，看看自己能否实现类似的东西。在找到足够的时间和动力完成审查之前，我发现为了不让实际查询性能下降超过 10 到 100 毫秒（这似乎是可以接受的），我其实根本不需要在教学解码器中添加 SIMD 代码；只需减少教学解码器中的内存分配并针对每个位宽进行特化就足够了。

Encouraged by the possibility of using the optimized native Go decoder in Debian Code Search, I explored whether I could also implement a native Go encoder so that I could get rid of the C TurboPFor dependency entirely. The answer is yes, it is doable in a few days, and it isn’t even that much slower: Go is at 76% of C, see Debian/dcs commit e920dc7. The goal I set myself at that point was to see if I could learn enough SIMD to optimize the native Go encoder such that… 受到在 Debian Code Search 中使用优化后的原生 Go 解码器的可能性的鼓舞，我探索了是否也能实现一个原生 Go 编码器，从而彻底摆脱对 C 版 TurboPFor 的依赖。答案是肯定的，这在几天内就能完成，而且速度并没有慢多少：Go 的性能达到了 C 的 76%，详见 Debian/dcs 提交 e920dc7。当时我为自己设定的目标是，看看能否学习足够的 SIMD 知识来优化原生 Go 编码器，使其……

← 返回新闻列表 / Back to news list