Don't stop early: Case-folding source code at memory speed - The GitHub Blog<br>45 GiB/s on a single core." />
45 GiB/s on a single core." />
Try GitHub Copilot CLI
Attend GitHub Universe
Search
Alexander Neubeck & Greg Orzell
July 31, 2026
16 minutes
Share:
Suppose a user searches for café and your corpus contains CAFÉ, or they type straße and you’ve stored STRASSE. To make these count as matches, you need a canonical form that erases case distinctions, so that two strings which differ only in case compare equal. That form is case folding, and it shows up wherever text is matched rather than displayed: search engines, regex (?i) flags, case-insensitive usernames and hostnames.
It’s a basic operation, but at GitHub we run it a lot. Blackbird, GitHub’s code search engine, indexes over 180 million repositories—more than 480TB of source code. Every byte is case-folded before we extract ngrams and build the index, and for every potential query result, another (implicit or explicit) case folding operation is needed to locate matches. At that scale, the speed of even a basic operation starts to matter.
This post is about how we made it fast, and it starts somewhere counterintuitive: the biggest win in the ASCII fast path came from removing an optimization, not adding one. It turns out to be faster to sweep the whole buffer with no branches than to stop early at the first non-ASCII byte. We open-sourced the result as a Rust crate called casefold.
Folding is not lowercasing
It is tempting to reach for str::to_lowercase, but lowercasing and folding are different operations with different goals:
Lowercasing is for display, and it’s 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’s deliberately context-free and locale-independent. The point is a relation that stays stable and symmetric, so that if A folds to match B, B folds to match A in any locale. The Unicode Character Database ships an explicit CaseFolding.txt for exactly that.
The two operations diverge on real characters—ß, İ, final sigma—which is why lowercasing as a stand-in silently produces wrong matches. This 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 (the dotted İ). This isn’t an unusual choice: common tools and regex engines like ripgrep make the same restriction, and being consistent across tools is important.
The counterintuitive core: Don’t stop early
We deal mostly with source code, so the text we fold is overwhelmingly ASCII and making it run at memory speed is the single most important thing we can do. Everything else just has to keep the rare non-ASCII path from spoiling it.
The fold of an ASCII letter is trivial—A..=Z map to a..=z, everything else is unchanged—so the ASCII pass is really just “sweep the buffer, lowercase in place.” Ask any LLM for it and you might get something like this:
let bytes = s.as_bytes_mut();<br>for (i, b) in bytes.iter_mut().enumerate() {<br>if *b >= 0x80 {<br>break; // non-ASCII at index i: hand the rest to the Unicode path<br>if b.is_ascii_uppercase() {<br>*b += 32; // 'A'..='Z' → 'a'..='z'<br>= 0x80 {<br>break; // non-ASCII at index i: hand the rest to the Unicode path<br>if b.is_ascii_uppercase() {<br>*b += 32; // 'A'..='Z' → 'a'..='z'<br>}" tabindex="0" role="button">
It looks ideal: do the cheap byte work, and the instant you hit a non-ASCII byte, break and let the “real” Unicode path take over: “only do the cheap work until you have to.” On an Apple M4 this runs at about 3 GiB/s . That sounds fine in isolation, but it is more than 15× short of “optimal” because of the if branches.
Let’s delete every branch, line by line:
if b >= 0x80 { break } → don’t stop at all. ORevery byte into an accumulator and test it once, after the loop: high_bit_acc |= *b. Same information (was there any non-ASCII byte?), zero branches in the body.
The A..=Z range test → make it arithmetic. b.wrapping_sub(b'A') is true exactly for A..=Z (any other byte wraps to ≥ 26), yielding a 0/1 mask with no branch.
The conditional write → fold the mask into the store.| (is_upper sets bit 5—turning an upper-case letter lower-case and being a no-op on everything else—the byte is always written, never branched on.
What’s left has no branch in its body and no early exit:
let mut high_bit_acc: u8 = 0;<br>for b in &mut bytes {<br>high_bit_acc |= *b; // detect any non-ASCII byte<br>let is_upper = b.wrapping_sub(b'A')
A loop with no data-dependent control flow is trivially vectorizable: LLVM emits 16-byte-at-a-time NEON and the whole thing runs at > 45 GiB/s —essentially memory bandwidth. And we come out of the...