Debian Code Search: Fast TurboPFor with Go SIMD
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 (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. 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. 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: Motivation I have recently been looking into speeding up Debian Code Search. As a quick reminder, search engines answer queries by consulting an inverted index: a map from term to documents containing that term (called a “posting list”). See the Debian Code Search Bachelor Thesis (PDF) for a lot more details. Read more → If you want to learn more about the positional index, see this blog post from September 2019: Over the last few months, I have been developing a new index format for Debian Code Search. This required a lot of careful refactoring, re-implementation, debug tool creation and debugging. Read more → For many years, you had the following options for using SIMD instructions in Go: 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. Go 1.26 (released in February 2026) introduced the package: Go 1.26 introduces a new experimental package , which can be enabled by setting the environment variable at build time. This package provides access to architecture-specific SIMD operations. It is currently available on the architecture and supports 128-bit, 256-bit, and 512-bit vector types, such as and , with operations such as . The API is not yet considered stable. — Go 1.26 Release Notes For my 2019 TurboPFor analysis, I implemented , 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. The TurboPFor format/algorithm has a vector-optimized part: bitpacking comes in a scalar variant ( ) and a vector variant ( ) , where the vector variant is used for full blocks (256 values) and the scalar variant is used for remainder blocks (< 256 values). When Go 1.26 was released, I used Claude Code to explore whether my native Go decoder’s 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. 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. 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 . 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 its performance would match how DCS uses C TurboPFor (via cgo). Beating C TurboPFor was possible in 2-3 commits (SIMD and bit width specialization). To my surprise, Claude Fable 5 pointed out that the encoder’s block scanning could be done more efficiently using a technique called positional popcount, and that is another 2x speed-up ! 😲 To be clear: I am not saying the Go compiler beats C here. Certainly, the C compiler can also produce fast AVX512 code and can be used to implement positional popcount. When comparing apples to apples, i.e. backporting the AVX512 kernels and positional popcount technique to C TurboPFor, Go benchmarks a little slower at ≈1.4x C. This spectacular result (much faster than what DCS had before) got me curious how far I could push the decoder with SIMD after all. I ended up matching/exceeding the cgo version here, too! The rest of this article explains a few classes of optimizations I encountered along the way. When I wrote my teaching decoder , I named its functions to match the upstream C TurboPFor library, but now I want to get away from names like — they make sense from the TurboPFor perspective, but for Debian Code Search, we can use cleaner names. Before writing any code, I audited how DCS uses integer compression / decompression. In Debian Code Search, we have the following usage patterns: For reading the index, we do keep the decoded s fully in memory, so we only need , a function that reads values ( ) from and returns how many bytes it consumed. For writing the index (both in partial indexing, and when merging), keeping the entire index in memory is prohibitively expensive, so we need a streaming API, for decoding and for encoding. Ultimately, I converged on the following API: This API (the decoder works similarly) allows us to process data in TurboPFor format without any memory allocations. The types are not safe for concurrent use by multiple goroutines. The zero value is ready to be used. For the streaming API, the result only stays valid until the next call. Before we can optimize anything, we need a working decoder and encoder. The decoder already exists: my teaching decoder. Next up, I needed an encoder. Writing a TurboPFor encoder has a delightfully simple starting point: You can encode all values at bit width 32, in little endian, at which point you only need to add a one-byte TurboPFor block header every 256 values and you’re done: Of course, this is a terribly inefficient compressor, so after the first commit, the real work starts: implement each block type until the compression matches the original C TurboPFor implementation (same output file size), or in other words: do the reverse of the decoder. I found it interesting to realize that the main work of the encoder is to scan the input values and choose the optimal block type, whereas the actual encoding itself is cheap in comparison. At this point, we can look at performance and see that the Go encoder is at 76% of the C encoder. In all honesty, I could have probably stopped here, but now that the milestone of a viable replacement was reached, I got curious to see how far it would be possible to push the encoder (how much work to reach C speeds?) and afterwards, the decoder, too. The microarchitecture of a CPU determines which instructions it provides, and that includes not just SIMD instruction sets (like AVX2), but also other useful instructions like (Leading Zero Count), which can be used to implement more efficiently, which the TurboPFor encoder needs to call on every input value to determine the ideal bit width. Let’s walk through how to set the microarchitecture level when using Go on 64-bit x86 (x86-64). Go uses the environment variable to configure the target compilation architecture, and I am using the value to select 64-bit x86 (AVX2 and AVX512 are instruction sets found on x86-64 CPUs). With , the architecture-specific variable configures the microarchitecture level for which to compile and Go 1.18 introduced these 4 different levels : (default): The baseline. Exclusively generates instructions that all 64-bit x86 processors can execute. : all v1 instructions, plus CMPXCHG16B, LAHF, SAHF, POPCNT, SSE3, SSE4.1, SSE4.2, SSSE3. : all v2 instructions, plus AVX, AVX2 , BMI1, BMI2, F16C, FMA, LZCNT, MOVBE, OSXSAVE. : all v3 instructions, plus AVX512F , AVX512BW, AVX512CD, AVX512DQ, AVX512VL. In 2026, I generally recommend compiling with so that functions like are compiled into intrinsics ( ) instead of using a lookup table. For Intel CPUs, setting means your programs will only start on Haswell CPUs (2013) or newer; for AMD CPUs that means Zen 1 (2017) or newer. In this specific case (DCS), I am even compiling with . The microarchitecture level requires AVX512, which means AMD Zen 4, Zen 5 or newer (Intel’s story is… complicated). Luckily, both my main development PC (Zen 5) and the Debian Code Search server (Zen 4) are recent enough. Setting has little effect on Go 1.27 itself: the only change is that maps use one less instruction ( instead of ). But compiling with allows us to move one more feature check from runtime to compile time, see SIMD build tags . It makes sense to set the microarchitecture level in your benchmark setup so that you don’t measure the slow fallback implementations. I use in my . Go’s built-in package contains support for benchmarks which are written in functions of the form . The simplest way to run such benchmarks is , but I ended up configuring a few convenience targets, which write results to and compare against (the previous commit’s results, usually), using the very useful tool . The and units are custom metrics I am reporting from the various sub-benchmarks , which are arranged such that I can filter / report them with . The main encoder (and decoder) benchmarks compare 3 different implementations (cgo, Go, Go with the StreamEncoder API) with a number of benchmark cases that are designed to cover the different block types and contain a similar mix of values as what we see in Debian Code Search: Go has included excellent performance tooling for many years, see the “Profiling Go Programs” blog post (2011) for an example of how to use , a sampling profiler. This profiler can help track down which part of a program runs slow, or where memory allocations happen. Once you identified the slow part of a program, how do you know why it’s slow? To learn more about the specific bottlenecks your program encounters, you can consult your CPU’s hardware performance counters . For example, you could check the branch predictor counters to see if your program is slow due to a high number of branch mispredicts. On Linux, the tool is the best way to access the CPU hardware performance counters. A good starting point for working with is the documentation on “Top-down analysis with the perf tool” , which describes the optimization method that Intel established. In my , I set up two targets: The numbers are high level numbers that indicate how much work the implementation is doing. Reducing the number usually increases speed. To see the counters for each instruction (and source code lines), I use , followed by . A quick shortcut is , which directly shows the hottest function. Let’s first see how far we can get without reaching for SIMD instructions. (The examples are not necessarily in commit order, but cherry-picked for clarity.) PGO stands for Profile-Guided Optimization and is a feature that Go introduced as a preview in Go 1.20 (released in February 2023) and shipped as ready for general production use in Go 1.21 (released in August 2023). The idea is to capture a CPU profile that records where your program spends most of its CPU time, which you then provide to the Go compiler to give it more data to make better decisions. Most importantly, this way the Go compiler can inline functions much more aggressively than its usual heuristics allow, which does have a measurably positive effect in my series of optimization commits. Another optimization that a PGO profile allows the compiler to do is conditional devirtualization — but our TurboPFor code does not use any interfaces. My strategy is to enable PGO before doing any other optimizations, so that we have the full inlining budget available that PGO gives us, and can measure the effect of other commits clearly. Surprisingly, turning on PGO actually decreases our performance (-13% geomean), but a closer investigation reveals that we just got unlucky. Let me explain. Aside from inlining and conditional devirtualization, PGO also influences alignment: The Go compiler sets on the first block of a loop (the “loop body”) for all loops in hot functions (per the PGO profile), i.e. Go will insert up to 31 bytes of padding to make the block land on a 64-byte boundary. Documentation like AMD’s “Software Optimization Guide for the AMD Zen5 Microarchitecture” (2024, #58455) explicitly recommends aligning hot loops that way: […] for hot loops, some further knowledge of trade-offs can be helpful. Because the processor can read an aligned 64-byte fetch block every cycle, it is suggested to either align the start of the loop to the beginning of a 64-byte cache line […] Indeed, when compiling with to disable the alignment, performance remains as good as without PGO. How can the padding hurt more than help? The answer is: It’s not the padding itself! It’s a side-effect of the padding moving instructions to different addresses. In the unlucky arrangement, a macro-fused + instruction pair now ends up exactly on a 32-byte boundary . However, the Go compiler ensures fused branch sequences must never cross or end at a 32-byte boundary to fix Intel erratum SKX102 (discussion: Go issue #35881 ) by inserting s. This padding, unlike the loop alignment padding, is not free; these extra instructions slow down our otherwise dispatch-bound loops. Because the commits after the PGO enabling commit change the code, this unlucky situation is avoided for the rest of the optimization series (by chance). Memory allocations are quite expensive, at least in comparison to encoding/decoding integers, so I followed my usual strategy of first reducing memory allocations as much as possible. In my teaching decoder, whenever the code needed a scratch buffer, it would allocate it right then and there with : The Go compiler can turn calls into stack allocations, if is known at compile-time. But, in this case is not known at compile-time. We can verify that Go calls into the runtime ( ) by dumping the object code (assembly) with source annotated ( ): An easy speed-up was to avoid allocations through reuse (in ). In the DCS package (with the improved API design ), I ended up with a field in the type, which brings us from 773 Mval/s to 858 Mval/s on the debian-mix: Aside from the speed-up, avoiding memory allocations is generally nice in benchmarks because it removes the garbage collector from the equation and makes it less likely that your benchmarks get other processes OOM-killed on the same machine. In general, we want to make it easy for the compiler to understand as much as possible about our algorithm. Consider this implementation: Let’s think through what determines the iterations and control flow this function uses: With a bit of careful rearrangement, we can provide the compiler with both, a fixed number of input values (say, 32), and a bit width, both known at compile time. Why is this worthwhile? Because we can manually unroll the loop, let the compiler eliminate much of the repetition and get much faster compiled code as a result! Let’s first fix the number of input values to 32 and rewrite the loop to calculate the position offsets within instead of changing on each value (with ): Next, we want to specialize not just for 32 input values, but also for each of the 32 bit widths. Can we do better than hand-copying 32 times (= 8192 lines of Go code)? Yes, we can use Go generics to help us with the code generation! In Go, array types like (not slices like !) contain the length of the array as part of their type, meaning (an array of length 1) is a different type than . Instead of passing the bit width as a function parameter, we can declare 32 different types (one for each bit width) and recover the bit width (at compile time!) from the type system: When we instantiate with all 32 different types ( , , …, ), the compiler substitutes the type parameter and produces 32 copies of the function, which we can find in our compiled executable with names like . The “shape” of a generic type is based on its memory layout, so a shape for must be different than the shape for . Because the is now known at compile time, the Go compiler can generate close to the optimal machine code for each bit width, which we can confirm using . The code is branchless (after the one bounds check per 32 values) and aside from the loads and stores (from/to memory) consists only of shifts and bit operations, all with constant operands: Now we need to actually call from the general function: Encoding remainder blocks is quite a bit faster (full blocks use the vertical layout anyway): This performance win comes at the cost of binary size increase. In this case, the section (executable code) grows by about 20 KB and the section grows by another 26 KB. Definitely a price I am very willing to pay, but the case might not be as clear in all circumstances. Even without reaching for SIMD instructions, a TurboPFor implementation can be made faster by making it work bigger strides. Take this code from the teaching decoder which counts the number of exceptions by checking if each value’s bit is set in the exception bitmap: We can use the functions to count ones bits in the exception bitmap, 64 values at a time. For remainder blocks, the rest is processed 8 values (1 byte) at a time: uses a 64-bit register. For comparison, AVX2 SIMD instructions use 256-bit registers (= 8 ) and AVX512 SIMD instructions use 512-bit registers. In the following sections, we will first set up our build tags for conditional compilation to use a trivial SIMD instruction, then walk through an AVX2 and AVX512 SIMD kernel. Let’s assume we have the following scalar code: To increase throughput, we can use AVX2 instructions if they are available on the CPU on which the program runs, i.e. using runtime dispatch. We’ll first rename to (it’s now the fallback path): Next, we’ll supply two different implementations ( and ), the latter of which is selected when compiling for with (the latter will hopefully be dropped in a later version of Go). The variant just dispatches to the , which will likely be inlined: The variant assigns the global variable by doing a check and then jumps to the scalar fallback if , i.e. the CPU is too old: We can go one step further by conditionally compiling when is set to or higher (i.e. the build tag is set). As a practical example from Debian Code Search, we currently need the following checks / dispatches: In DCS, the effect is measurably positive, but small . First, here is the layout explanation from my 2019 TurboPFor analysis blog post : In regular (non-SIMD) bitpacking , integers are stored on disk one after the other, padded to a full byte, as a byte is the smallest addressable unit when reading data from disk. For example, if you bitpack only one 3 bit int, you will end up with 5 bits of padding. SIMD bitpacking works like regular bitpacking, but processes 8 little-endian values at the same time, leveraging the AVX instruction set . The following illustration shows the order in which 3-bit integers are decoded from disk: The scalar implementation uses an array of 8 to process 8 values at a time: The SIMD version also processes 8 values, but without a loop! One difference is that we no longer have the luxury of using for (holding rest and current bits); because AVX2 registers only fit 8 (not 8 ). Instead, we split into and . The SIMD version benchmarks about 3x as fast as the scalar version. Another significant speedup is to use generics for bit width specialization for this SIMD kernel so that becomes a compile-time constant and the compiler can generate better code. For my TurboPFor encoder, I implemented the same techniques as described above: Bitpack full blocks with SIMD (AVX2) Gather exceptions using SIMD (AVX512) Use generics to specialize per bit width These changes are sufficient to roughly match the cgo performance, but then Claude Fable 5 found another 2x speed-up on top of that ! The key observation is that once encoding blocks is fast, the preceding step of scanning the input values to decide which block type to use becomes the bottleneck. Here is the encoder’s main function, which first does one pass over the input values ( ) and then prices all different block types at all relevant bit widths (requires fast access to the histogram): I’ll show you a slightly shortened version of , the function which is the bottleneck: Let’s consider the following 3 example values to understand the resulting : The resulting exception count histogram would contain ( shortened to ): In words, this means that at bit width 10, we could encode all the values without any exceptions. But most values do not need 10 bits, so a bit width of 5 would be more efficient, but requires storing one exception. Encoding at bit width 4 requires 2 exceptions, and so on. The function above is intentionally kept simple for illustration. We can make it faster by moving the per-bit-width loop outside the per-element loop . The fast version still needs about 12 instructions per value. With SIMD, we can reduce this to by 8x to only 1.5 instructions per value! The trick is to turn each input value into its “smear mask” (imagine taking the first 1 bit and smearing it across the remaining positions). Here are the smear masks for our example: Turning a value into its smear mask is computationally cheap: Go implements (functions like ) by calculating . We can calculate the “smear mask” of a value with , i.e. starting with a 32-one-bits mask and shifting it by the number of leading zeros. Now, to obtain e.g. , we can count the 1 bits at bit position 4 of all input values. The instruction counts bits very efficiently, but it counts one bits within a register, so it counts rows, not columns. Counting columns is called Positional Population Count . I found the following papers that describe positional popcount with SIMD: To understand the AVX512 implementation of positional popcount, I found it most helpful to visualize an AVX512 register (512 bits, i.e. 64 bytes). The graphic below uses the layout, meaning it divides the register into 8 lanes of 64 bits (= 8 bytes) each. This illustration shows the whole process: how s are loaded into an AVX512 register (all 4 of its bytes, in sequence) and where we end up, i.e. the 32 positional popcounts: Let’s break down this process into its individual steps. First, we turn each loaded value into its smear mask as explained above. The vector instruction calculates (1 byte) of 64 bytes at once, but first we need to shuffle the bytes inside the register: in load order, we have a full (4 bytes), followed by another , per lane. First, we permute the bytes ( ) such that all the first bytes of each value end up in one lane (“transpose the bytes”): Next, we “transpose the bits” using the instruction, which sounds scary but turns out to be quite flexible for bit manipulation of all kinds. The instruction is also “the star of the show” in Go’s Green Tea Garbage Collector (2025). Here is the bit transpose, shown in the AVX512 register layout (see below for a different layout): I found it easier to understand the transpose step when arranging the 8 bytes of lane 0 from top-to-bottom (instead of left-to-right), because then it looks like a 90 degree clockwise rotation: Now we can use to count the bits in all 64 bytes at once: After all loop iterations (processing 16 values each) are done, we add the two groups (first 8 values, second 8 values) to obtain the 32 exception counts: Here is the Go code that implements what I described visually above: Have a look at the commit introducing positional popcount to DCS for the full code (including shuffle tables and ISA checks) as well as the detailed benchmark results. The SIMD optimizations I showed above beat the cgo TurboPFor library that Debian Code Search used before. When comparing apples to apples, i.e. backporting the AVX512 kernels and positional popcount technique to C TurboPFor, Go benchmarks a little slower at ≈1.4x C. Could we make my Go TurboPFor implementation even faster, to truly match the C speed? Yes! But also no. Let me explain: We could use more SIMD instructions to remove all code that still processes one value at a time. For example, in my encoder’s function. Or we could price all bit widths concurrently in . Or in the decoder’s exception apply code path. But all of these SIMD instructions make understanding (and changing) the code harder, so I am cautious regarding which ones I introduce. A big part of the performance gap is due to Go’s bounds checks . While it costs performance, bounds checking is great for safety, so I will not turn off bounds checking. The Go compiler eliminates a number of bounds checks when it understands it’s safe to do so. One optimization avenue could be to make the prove pass in the Go compiler smarter to eliminate more bounds checks. When doing mid-stack inlining (proposal #19348) (2017), Go sometimes needs to put instructions into the binary so that it can attach inlining markers. For dispatch-bound functions, these extra NOPs can measurable slow down execution. The Go compiler currently allows specifying the architecture ( ) and microarchitecture ( ), but not a specific CPU architecture (like AMD Zen 4). Therefore, CPU-specific workarounds for one vendor affect all the generated code. The specific one I encountered in my code is that the Go compiler emits before every to break a false-output-dependency from the Intel Sandy Bridge Skylake era, which is unnecessary on AMD Zen CPUs. I suspect that Go intentionally does not offer this level of customizability. After all of the above points are addressed, what remains is better code generation in specific cases. To illustrate what I mean, consider the example of incrementing a loop variable, where Go re-derives an index every time: Go: (3 instructions) clang: (2 instructions) Depending on the specific case, improving the compiler might be easy or prohibitively complex. Often, such improvements are hard to measure conclusively. Go’s SIMD support makes available — in Go code without having to resort to cgo or assembly — a powerful part of modern CPUs which allows speeding up the kind of computation that TurboPFor needs by an order of magnitude! 😲 I found it very valuable to use a coding agent (Claude Code, with Opus 5 and Fable 5 in this case) to help with the many tedious parts of such performance work (and still it took me weeks!). The LLM can read objdump output much faster than I can, can see patterns and correlations I might never identify, never becomes frustrated after a compiler error or runtime panic, and never runs out of patience to run one more experiment, as long as I give it measurable and reachable goals. The performance of the SIMD code which one can get from the Go compiler is pretty close to what a good C compiler like clang provides. The CPU performance counters show value decoding speeds of 7 instructions/cycle (IPC) on a machine where the maximum is 8 IPC. To me, SIMD support is a very welcome addition to Go. Hand-writing Go assembler code . This is only doable for small functions, for example is implemented with hand-written Go assembly (including AVX2). Generating Go assembler code with tools like Michael McLoughlin’s “Avo” . This is how uses AVX2 . While Avo generator code definitely is higher-level than hind-written assembly, it is still too close to assembly for my taste. 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. Partial Indexing: When a new package (or package version) enters Debian, all of its (text) files are indexed. If the package (hypothetically) contained only with , we would assign document ID to and store in the partial index that trigrams , , , , etc. are all found in doc ( ). Full Index Merging: The many thousands of partial index files (for each Debian package) are combined into a small handful of large index files: When searching, it would be expensive to consult thousands of indexes. To merge multiple partial index files into one larger index (which can then be efficiently queried), we need to re-encode the partial index files: what used to be document ID in the partial index might be document ID in the full index. Querying (searching): When users enter search queries, these queries need to be answered as quickly as possible. The relevant entries in the full indexes are decoded (in parallel). The TurboPFor bitpacking block type ( bitpacking implementation commit ) encodes a bit stream of variable bit width (where the bit width is in range ) in little endian byte order. By scanning all values and choosing the smallest bit width that allows representing all values, this technique saves disk space (compresses). The bitpacking with exceptions block type ( bitpacking with exceptions implementation commit ) determines two bit widths: one for values, the other bit width for encoding exceptions. This allows choosing a lower bit width (that does not cover all values) compared to the bitpacking block type. A bitmap encodes whether a value has an exception or not. The bitpacking with VB exceptions block type ( bitpacking with VB exceptions implementation commit ) is a variant which does not use an exception bitmap and encodes exceptions using a variable byte integer encoding. This is more efficient when there are few exceptions (less than 20) or the exceptions are very different in bit width compared to the other values. Lastly, the constant block type ( constant implementation commit ) stores just one value on disk. This is useful for all-zero or all-one blocks, for example. The number of input values ( ), but not their actual value. The bit width to pack into ( ). Bitpack full blocks with SIMD (AVX2) Gather exceptions using SIMD (AVX512) Use generics to specialize per bit width 2019: “Efficient Computation of Positional Population Counts Using SIMD Instructions” (Klarqvist, Muła, Lemire) introduces an AVX512 implementation using Carry-Save Adder (CSA) networks, but in my testing, that approach is slower for TurboPFor encoding. 2024: “Histogramming bytes with positional popcount (GF2P8AFFINEQB edition)” (Harold Aptroot) shared a C++ implementation illustrating the technique I am using. If you are not familiar with how C++ vector intrinsics look, take a look at this example. 2025: “Faster Positional-Population Counts for AVX2, AVX-512, and ASIMD” (Clausecker, Lemire, Schintke) improves performance over the 2019 paper, but cites the Aptroot blog post as “Future Work”, promising even faster processing for smaller inputs. We could use more SIMD instructions to remove all code that still processes one value at a time. For example, in my encoder’s function. Or we could price all bit widths concurrently in . Or in the decoder’s exception apply code path. But all of these SIMD instructions make understanding (and changing) the code harder, so I am cautious regarding which ones I introduce. A big part of the performance gap is due to Go’s bounds checks . While it costs performance, bounds checking is great for safety, so I will not turn off bounds checking. The Go compiler eliminates a number of bounds checks when it understands it’s safe to do so. One optimization avenue could be to make the prove pass in the Go compiler smarter to eliminate more bounds checks. When doing mid-stack inlining (proposal #19348) (2017), Go sometimes needs to put instructions into the binary so that it can attach inlining markers. For dispatch-bound functions, these extra NOPs can measurable slow down execution. The Go compiler currently allows specifying the architecture ( ) and microarchitecture ( ), but not a specific CPU architecture (like AMD Zen 4). Therefore, CPU-specific workarounds for one vendor affect all the generated code. The specific one I encountered in my code is that the Go compiler emits before every to break a false-output-dependency from the Intel Sandy Bridge Skylake era, which is unnecessary on AMD Zen CPUs. I suspect that Go intentionally does not offer this level of customizability. After all of the above points are addressed, what remains is better code generation in specific cases. To illustrate what I mean, consider the example of incrementing a loop variable, where Go re-derives an index every time: Go: (3 instructions) clang: (2 instructions) Depending on the specific case, improving the compiler might be easy or prohibitively complex. Often, such improvements are hard to measure conclusively.
Security
C
Open Source
Rust
Programming
AI
Gaming
Performance
HTML
Python
Go
C++
Database
Swift
DevOps
Java
Ruby
Shell
Mobile
CSS
JSON
JavaScript
Web Development