GitHub Case-Folds 480TB of Code at >45 GiB/s: The Branchless Casefold Crate

GitHub published an engineering deep-dive on July 31 that reads like a masterclass in why hot loops are slow. Blackbird, GitHub's code search engine, indexes over 180 million repositories and more than 480TB of source code, and it case-folds every byte before building its ngram index. That basic operation ran 15x slower than it needed to. The fix, open-sourced as the casefold crate in the github/rust-gems repository, now folds pure ASCII at over 45 GiB/s on a single Apple M4 core, which is essentially memory bandwidth.

The lesson is not "SIMD wins." It is that branchless code is a pessimization unless vectorization is allowed to happen, and the single thing that blocks vectorization in a loop is a data-dependent early exit.

Folding is not lowercasing#

The first trap is reaching for str::to_lowercase. Lowercasing is for display and is locale- and context-sensitive: Greek final sigma lowercases differently at word end, Turkish dotted I lowercases differently than English I. Case folding is for comparison: context-free, locale-independent, stable and symmetric, straight from the Unicode CaseFolding.txt table.

The crate implements only simple 1-to-1 folds (statuses C and S), not full folds like ß to ss, and not Turkic. That matches the restriction ripgrep and most regex engines make, so search results stay consistent across tools.

The counterintuitive core: don't stop early#

The naive ASCII fast path scans for a non-ASCII byte and breaks to a "real" Unicode path on the first hit. It runs at about 3.1 GiB/s. The GitHub team deleted the early exit entirely: OR every byte into an accumulator and test once after the loop, replace the A..=Z range test with the arithmetic wrapping_sub(b'A') < 26, and fold the conditional write into an unconditional *b |= is_upper << 5. Their measured ladder on the Apple M4:

The middle rung is the one that surprises: making the body branchless while keeping the break is slower than the naive loop, because the unconditional store writes all 5.7KB instead of only the uppercase bytes. The branchless store only pays off once the loop vectorizes and the store becomes one 16-byte vector op. A data-dependent loop exit, even a perfectly predicted one, is enough to keep the whole loop scalar. In the hot loop, the branch is the enemy.

There is a standard-library middle ground: scan machine words at a time (8 bytes per iteration via 0x8080_8080_8080_8080 masks) and convert only the ASCII prefix, which lands at about 23 GiB/s but reads the data twice. Fusing the scan and the convert into one pass is 2.6x slower (8.7 GiB/s): the exit branch every 8 bytes pins the loop, so the compiler never pipelines across blocks.

Unicode folding as byte arithmetic, no decode#

The genuinely new piece is the non-ASCII path. Unicode 16.0 has 1484 simple-fold mappings, but they are a sparse, structured relation. Foldable code points cluster into 64-code-point pages: only 59 of roughly 1960 pages are populated. A 1-bit-per-page presence bitmap (248 bytes) rejects a non-folding character in a single bit test from its lead byte, with no UTF-8 decode at all.

Within a page, folds come in runs: A..Z all map +32, and Latin Extended alternates every second code point. Storing runs (start, end, stride, delta), a shape borrowed from Go's unicode package, collapses 1484 folds into 238 runs. A run record is two clean bytes, and the within-page search is one SWAR step: 8 end-of-run bytes loaded into a u64 and compared branchlessly in a single arithmetic pass.

The fold itself is a little-endian addition. The folded character's UTF-8 bytes, read as a u32, equal the source bytes plus a per-run constant delta. The whole table is 1776 bytes (9.6 bits per fold entry), versus roughly 11.6KB for a naive array, 70KB for regex-syntax's table, 7.3KB for Go's SimpleFold, and ~17KB for a runtime HashMap. The crate never decodes a character: ICU, Go, Rust's regex crate, CPython and glibc all decode to a code point, fold, and re-encode. The byte-space arithmetic requires well-formed shortest-form UTF-8, which is a free guarantee inside Rust's &str but a caveat for anyone feeding raw bytes.

Measured against real folders: >45 GiB/s on pure ASCII, 2.95 GiB/s on fold-free CJK, and 869 MiB/s on the worst case of all-folding Latin/Greek/Cyrillic, where simd-normalizer edges ahead at 922 MiB/s. A HashMap trails everything at 213 MiB/s on ASCII. GitHub is honest that the numbers are illustrative, not portable: the design leans on auto-vectorization, SWAR and little-endian arithmetic.

What developers should take from this#

Three takeaways transfer beyond case folding. First, profiling at the "stop early" assumption is worth it: the instinct to bail on the rare case is what was quietly preventing the compiler from doing 16 bytes of work per instruction. Second, a branchless body is only worth it as the enabler for vectorization, never on its own, which is a rare and valuable nuance in SIMD advice. Third, structure beats tables: reorganizing 1484 mappings into pages and runs cut the memory footprint an order of magnitude while getting faster, because the miss path got a single bit test.

This is the same engineering culture as the 535K-line Zig-to-Rust rewrite of Bun and the pgrust Postgres rewrite: mature systems teams spending real effort on the basics, not headline features, because at 480TB of index, every byte is expensive. It is also a reminder that the Rust toolchain keeps compounding - casefold is the kind of crate that quietly becomes the right default for search, indexes and anything matching text, the way Rust-based build tools became the default for JS tooling.

Continue Reading#

• Bun Rewrites 535K Lines of Zig to Rust in 11 Days Using Claude
• pgrust Passes 100% of Postgres Regression Tests: What the Rust Rewrite Actually Means
• Astro 7 and Vite 8: The Rust-Powered Build Revolution
• GitHub Stacked PRs Are Now in Public Preview
• Build Log: Tool Directory, Search, Compare, RSS

Sources#

• Don't stop early: Case-folding source code at memory speed - GitHub Blog
• casefold - crates.io
• github/rust-gems - GitHub
• Unicode CaseFolding.txt - Unicode Character Database
• Go unicode tables (CaseRange) - golang/go