Don’t stop early: Case-folding source code at memory speed

GitHub’s code search engine Blackbird indexes over 180 million repositories, requiring case-folding for every byte of source code to ensure case-insensitive matches. Case folding converts text to a canonical form for comparison, distinct from locale-sensitive lowercasing, and is essential for operations like search engines and case-insensitive usernames. The challenge was optimizing this basic operation at scale, where even small speed improvements significantly impact performance.

The crate casefold achieves over 45 GiB/s on a single core by using a branch-free loop that processes ASCII bytes without early exits. Traditional approaches, which stop at the first non-ASCII byte, run at just 3 GiB/s due to branch penalties. Removing data-dependent control flow allows vectorization, enabling the loop to process 16 bytes at a time. Benchmarks show that branch-free loops outperform even optimized two-pass methods, demonstrating that branches are the primary bottleneck in hot loops.

Case folding preserves UTF-8 length for most characters, but two outliers—U+023A (Ⱥ) and U+023E (Ɀ)—expand to three bytes when folded. To handle this, casefold allocates a secondary buffer sized for worst-case growth (1.5× input size) upfront, avoiding incremental reallocations. The design minimizes branches by moving unchanged byte runs in bulk and writing folded characters unconditionally, deferring length adjustments until the end.

The non-ASCII path leverages a sparse 1776-byte lookup table derived from Unicode 16.0’s 1484 simple-fold mappings. A one-bit-per-page bitmap quickly rejects non-foldable characters, while a cumulative-popcount side table locates foldable entries only when necessary. This structure prioritizes the common case—no fold—by enabling a single bit test from leading UTF-8 bytes, ensuring the hot path remains branch-light and efficient.