Don’t stop early: Case-folding source code at memory speed (opens in new tab)

Case folding converts text into a canonical, case-insensitive form for comparisons, making it essential to GitHub’s large-scale code search. GitHub optimized this operation by removing an apparent optimization: instead of stopping at the first non-ASCII byte, it scans the entire buffer branchlessly, enabling SIMD vectorization. The resulting Rust casefold crate processes ASCII at over 45 GiB/s—close to memory-bandwidth limits.

Case Folding Is Not Lowercasing

• Lowercasing is intended for display and can depend on locale or context.
  • Greek sigma may become ς or σ.
  • Turkish I has locale-specific behavior.
• Case folding is intended for comparison and must be locale-independent and symmetric.
• Unicode provides explicit rules in CaseFolding.txt.
• The crate supports simple one-to-one folds (statuses C and S), but not:
  • Full folds such as ß → ss
  • Turkic-specific folds such as dotted İ
• This restriction matches tools such as ripgrep and helps maintain consistent matching behavior.

Why Case-Folding Performance Matters

• GitHub’s Blackbird search engine indexes more than:
  • 180 million repositories
  • 480 TB of source code
• Source bytes are case-folded before n-gram extraction and indexing.
• Folding is also needed when evaluating potential query matches.
• Since most source code is ASCII, optimizing the ASCII path provides the largest benefit.

Removing the Early Exit

• A conventional implementation scans until it finds a non-ASCII byte, then switches to Unicode processing.
• On an Apple M4, this branch-heavy approach reached only about 3.1 GiB/s.
• The optimized loop:
  • ORs every byte into an accumulator to detect non-ASCII data once.
  • Uses b.wrapping_sub(b'A') < 26 as a branchless uppercase test.
  • Sets bit 5 with | (is_upper << 5) to lowercase uppercase ASCII letters.
• The loop always processes and writes the entire buffer, then checks whether Unicode processing is necessary.

Vectorization Beats Early Termination

• Removing the data-dependent break allows LLVM to vectorize the loop with 16-byte NEON instructions.
• Performance progression on a 5.7 KB ASCII buffer:
  • Naive branchy loop: 3.1 GiB/s
  • Branchless body with early exit: 2.6 GiB/s
  • Early exit removed: 7.6 GiB/s
  • Fully branchless loop: over 45 GiB/s
• The early exit prevents vectorization even when the loop body is otherwise branch-free.
• Branchless arithmetic then eliminates compare-and-blend overhead and enables full memory-speed performance.

Why Branchless Code Can Be Slower

• In scalar code, the branchless version writes every byte, even when no change is needed.
• The branchy version skips stores for the majority of lowercase letters, digits, spaces, and other unchanged bytes.
• Its conditional branch is highly predictable, so it is inexpensive.
• Branchless writes become beneficial only after vectorization, where the processor handles a whole vector at once.

The practical lesson is to avoid data-dependent loop exits when they block vectorization. For predominantly ASCII workloads, a complete branchless scan can outperform “stop as soon as possible” logic by a wide margin, while an accumulated high-bit check efficiently identifies inputs requiring Unicode handling.