Why removing an optimization made GitHub's case-folding 15x faster

GitHub's Blackbird code search engine indexes over 180 million repositories and 480TB of source code, case-folding every byte before building its ngram index. At that scale, even a basic string operation's speed matters, prompting the team to open-source a Rust crate called casefold.

The key insight is counterintuitive: the biggest win came from removing an optimization, not adding one. A common ASCII fast-path pattern breaks out of its loop at the first non-ASCII byte, which seems efficient but actually prevents the compiler from vectorizing the loop. Removing that early exit and making the byte conversion fully branchless let LLVM emit 16-byte NEON vector instructions, pushing throughput from about 3 GiB/s to over 45 GiB/s on an Apple M4—essentially memory bandwidth.

The post also clarifies why case folding differs from lowercasing: lowercasing is locale-sensitive and meant for display (Turkish I, Greek final sigma), while folding must be context-free and symmetric for matching. The casefold crate implements only simple 1-to-1 folds, matching the behavior of tools like ripgrep rather than full Unicode folding (e.g., ß to ss).

The broader engineering lesson: branchless code can actually be slower in scalar execution, since it forces unconditional writes even when nothing changes. Its real payoff comes only when it unlocks compiler auto-vectorization—turning a branch-free loop into memory-bandwidth-bound machine code.