Don’t stop early: Case-folding source code at memory speed
GitHub open-sourced casefold, a Rust crate optimizing case-folding for code search by processing ASCII text in a single branch-free pass at over 45 GiB/s on a single core.
The useful question is what changes for users, developers or buyers, and whether the announcement stays industry context or becomes something people can actually use.
GitHub’s Blackbird code search engine indexes over 180 million repositories, requiring every byte of source code to be case-folded before indexing and during queries. Case-folding converts text to a canonical form to ensure case-insensitive matches, such as treating 'CAFÉ' and 'café' as equivalent. The operation is fundamental to search engines, regex flags, and case-insensitive identifiers, but its performance at GitHub’s scale demanded optimization.
The crate casefold achieves over 45 GiB/s on an Apple M4 by removing data-dependent branches in the ASCII fast path, enabling full vectorization. A naive early-exit loop that stops at the first non-ASCII byte runs at just 3 GiB/s due to branch penalties. By eliminating the branch and processing the entire buffer in a single pass, the compiler vectorizes the loop, hitting memory bandwidth limits. This approach contrasts with standard library methods that scan twice—once to detect ASCII blocks and again to convert—resulting in slower performance.
Case-folding differs from lowercasing, as it is locale-independent and context-free, relying on Unicode’s CaseFolding.txt for stable, symmetric mappings. The crate implements only simple 1-to-1 folds (statuses C and S), excluding multi-character or locale-specific folds like 'ß' to 'ss' or Turkish dotted 'İ'. This restriction aligns with tools like ripgrep and prioritizes speed for GitHub’s predominantly ASCII source code, where memory-speed processing is critical.
The implementation avoids unnecessary allocations by mutating the input buffer in place for ASCII text. For non-ASCII characters that fold to longer UTF-8 sequences, it allocates a single buffer sized to the worst-case 1.5x growth. The fold table is optimized to 1776 bytes using a page-based bitmap, allowing a single bit test to reject non-foldable characters without full UTF-8 decoding. This structure ensures the hot path remains branch-light, with folds handled as rare exceptions.