Case folding at GitHub has been accelerated to memory bandwidth. An analysis of how the branchless approach changes latency and throughput in code search.
When a system indexes hundreds of terabytes of code, even basic operations begin to impact overall performance. At GitHub, this is evident in the search engine, where every byte goes through case folding before building the n-gram index and during match checking. At the scale of hundreds of millions of repositories, degradation begins not due to algorithmic complexity, but due to microdetails: branching, cache behavior, and the inability to vectorize. The naive ASCII fast path with early exit upon the first non-ASCII byte seems logical but hits ~3 GiB/s on a single core. The reason is data-dependent branching, which breaks prediction and blocks SIMD.
The choice turned out to be counterintuitive: remove the early exit optimization and make a single pass without branching. Such a branchless loop has no data-dependent control flow and is easily vectorized by the compiler. As a result, LLVM generates SIMD instructions (e.g., NEON), and throughput reaches >45 GiB/s — effectively the limit of memory bandwidth. The trade-off here is straightforward: we always traverse the entire buffer, even if we encounter non-ASCII early. But the gain from vectorization outweighs the extra work. This is a typical compromise between “doing fewer operations” and “doing them as predictably and in parallel as possible.”
The implementation relies on several principles. The first is combining detection and transformation. During the pass, a flag indicating the presence of non-ASCII bytes is accumulated through OR on the high bits. This eliminates the need for a second pass for verification. The second is the abandonment of branching even within the transformation: converting A..Z to a..z is done through arithmetic on bytes without if statements. This allows the compiler to fully vectorize the loop. The third is memory management. The function takes a String by value and reuses the buffer. If the string is pure ASCII, the result is returned without allocations and copying.
For the non-ASCII path, deferred allocation is used. As long as characters do not require a change in length, writing goes to the original buffer. Once a case is encountered where folding changes bytes, a new buffer is allocated with an upper estimate of 1.5× the input. This is due to rare Unicode exceptions where 2 bytes turn into 3. This approach eliminates frequent reallocations and copying. Additionally, copying unchanged sections is performed in blocks (copy_nonoverlapping), rather than byte-by-byte. Even the writing of the result is optimized: always writing 4 bytes, while the length is adjusted separately, which removes yet another branch.
An interesting alternative approach is a two-pass scheme: first, determine the ASCII prefix through word-level scanning (16 bytes at a time), then apply the branchless transformation. This yields about 23 GiB/s. Better than the naive approach, but worse than the single-pass branchless variant. Attempting to “merge” the two passes into one with block processing and early exit again introduces branching and reduces performance to ~8.7 GiB/s. The reason is the same: even rare branching within the hot loop hinders unrolling and pipelining.
From a correctness perspective, it is important to distinguish between lowercasing and case folding. Lowercasing depends on locale and context, while case folding must be deterministic and symmetric. Therefore, Unicode CaseFolding.txt is used, and only simple folding (1-to-1 mappings). This excludes multi-character transformations and locale-dependent cases. This choice is a compromise between completeness and predictability. It aligns with the practice of many tools, reducing the risk of discrepancies in search.
The result is not a change in the algorithm, but a change in execution form. Branching was removed, the loop was simplified, the compiler was given the opportunity for vectorization, and throughput increased by an order of magnitude. Metrics show speeds approaching memory limits, but exact figures depend on CPU architecture and are not universal. Nevertheless, the causal relationship is clear: in the hot loop, branching is more costly than extra operations.
This case well illustrates a general industry pattern. In high-load systems, optimization often comes down to reducing execution variability rather than minimizing the number of steps. Predictable, linear code outperforms “smart,” but branching code. Especially where latency and stable throughput are critical.