GitHub's Casefold Rust Crate Hits 45 GiB/s by Dropping Early Exits

Case folding is the unglamorous string operation that lets a search for cafe match CAFÉ or Straße. It runs behind case-insensitive regex, hostname comparison, and full-text search. At GitHub's scale, it also runs a lot. A new engineering post from the Blackbird code search team lays out how they got the operation running at memory bandwidth on a single core, and open-sourced the result as a Rust crate called casefold.

Blackbird, GitHub's code search engine, indexes over 180 million repositories, more than 480TB of source code. Every byte is case-folded before ngrams are extracted and the index is built, and for every potential query result another case folding operation is needed to locate matches. At that scale, the speed of even a basic operation starts to matter.

Folding is not lowercasing

Before the performance work, the post draws a sharp line between two operations that look identical but aren't. Lowercasing is for display, and it is locale- and context-sensitive: Greek final sigma lowercases to ς at the end of a word and σ elsewhere, and Turkish I lowercases differently than English I. Case folding is for comparison, and it is deliberately context-free and locale-independent. Using to_lowercase as a stand-in silently produces wrong matches on characters like ß, İ, and final sigma.

The crate implements only the simple (1-to-1) folds, statuses C and S in CaseFolding.txt, and not the multi-character full folds (ß → ss) or Turkic locale folds, matching what tools like ripgrep already do.

The branch that was killing vectorization

Source code is overwhelmingly ASCII, so the ASCII fast path dominates. The naive loop looks reasonable: iterate byte by byte, break on the first non-ASCII byte, hand the rest to the Unicode path. On an Apple M4 this runs at about 3 GiB/s. That is more than 15x below what the hardware can do, and the culprit is the if branches.

The team rewrote the inner loop with no data-dependent control flow at all:

• No early exit. OR every byte into an accumulator and test it once, after the loop, so the presence of any non-ASCII byte is detected without a branch.
• Arithmetic range test. b.wrapping_sub(b'A') < 26 is true only for A through Z, yielding a 0/1 mask instead of a compare-and-jump.
• Unconditional store. The lowercase bit is folded into the write with | (is_upper << 5), so every iteration writes the byte back, changed or not.

The result is a loop LLVM can auto-vectorize into 16-byte NEON stores that hit memory bandwidth. The breakdown of what each change was worth:

Version	Throughput	Vectorized
Naive break + branch test	3.1 GiB/s	No
Branchless body, keep break	2.6 GiB/s	No
Drop the early-exit break	7.6 GiB/s	Partial
Fully branchless loop	>45 GiB/s	Yes

The key finding is counterintuitive. The early-exit is what gates vectorization: keep the break but make the body perfectly branch-free and you still get zero vector instructions; a data-dependent loop exit is enough on its own to keep the loop scalar. Removing what looks like a helpful optimization is what unlocks the 15x speedup.

There is a subtler warning in the numbers too. Branchless is a pessimization in scalar code. The branchless body alone, without vectorization, is actually slower than the naive version because it turns a rarely-taken store into an unconditional one. Branchless code only pays off when it enables the compiler to emit SIMD.

Unicode without decoding

The rare path, when a non-ASCII character shows up, is where the second unusual idea lives. Standard implementations decode UTF-8 into a code point, look up the fold, and re-encode. This crate skips both the decode and the encode.

Unicode 16.0 has 1484 simple-fold mappings, but they are a very sparse and very structured relation. The team exploits three properties:

1. Foldable code points cluster. Slice the code space into 64-code-point pages and the ~1484 folds touch just 59 of ~1960 possible pages. A one-bit-per-page bitmap answers the common negative question, does this character fold at all, from the leading UTF-8 bytes alone.
2. Folds come in runs. Adjacent code points share deltas: A-Z all map +32, Latin Extended alternates in stride-2 runs. This interval compression collapses the ~1484 individual folds into just 238 runs across the 59 pages.
3. Folding is byte addition. On a little-endian machine, reading the source UTF-8 bytes as a u32 and adding a per-run constant produces the folded bytes directly, no round-trip through a decoded code point.

That is the part they believe is genuinely new: every other folder they looked at, ICU, Go's unicode, Rust's regex, CPython, glibc, decodes UTF-8 to a code point, applies the fold there, and re-encodes. Doing the arithmetic in byte space skips both the decode and the encode, which is exactly why this path can outrun a hash map that already has the answer tabulated.

The whole lookup table weighs 1776 bytes, about 9.6 bits per fold entry. For comparison, a naive HashMap<u32, u32> would use roughly 17 KB and lose on every workload.

How it stacks up

Against two other real folders that produce identical output, the numbers are lopsided on the common cases and competitive on the pathological one:

Workload	casefold	simd_normalizer	HashMap
Pure ASCII	>45 GiB/s	1.21 GiB/s	213 MiB/s
CJK, no folds	2.95 GiB/s	1.97 GiB/s	558 MiB/s
Latin/Greek all-folding	869 MiB/s	922 MiB/s	334 MiB/s
Length-changing folds	1.26 GiB/s	716 MiB/s	233 MiB/s

The worst case, an adversarial buffer where every single character folds, is the one row where a dedicated SIMD normalizer edges ahead. Every realistic mix, source code, prose, CJK with ASCII punctuation, lands firmly in casefold's territory.

When it is worth reaching for

The crate is a drop-in fit if you are building search infrastructure, log indexing, or any pipeline that case-folds large volumes of mostly-ASCII text in Rust. It is available now on crates.io, with the generated table and design notes in the rust-gems repo. If your workload is dominated by short strings, or by Turkic locale rules, or by the multi-character full folds, the simple-fold-only design will not cover you.

The broader lesson generalizes past this crate. Two intuitions worth updating: an early-exit branch that looks like a free optimization can silently cost you an order of magnitude by killing auto-vectorization, and a hash map is the wrong default for lookups dominated by misses. Both ideas are portable to any hot loop that processes bytes at scale.