Don’t stop early: Case-folding source code at memory speed
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.
Read original(opens in new tab)
