GitHub’s case-folding trick: faster search with a counterintuitive twist
GitHub’s engineers just proved that sometimes the fastest way to make text search faster is to stop trying to be clever. In a new post, they reveal how their code search engine Blackbird—indexing over 180 million repositories—now folds case distinctions at memory speed, not by adding layers of logic, but by removing one. The secret? Ignoring an early-exit check that seemed like optimization and instead sweeping every byte in one pass.
The ASCII surprise
Most source code is ASCII, so folding letters to lowercase is mostly a matter of checking if a byte is between 0x41 and 0x5A and adding 32. A typical implementation would scan the buffer, lowercase on the fly, and bail the instant it hits a non-ASCII byte—handing off the rest to a Unicode path. On an M4 chip, that approach clocks in at about 3 GiB/s. The GitHub team found that removing the early exit and simply running the same loop over every byte, no matter what, pushed throughput past 6 GiB/s on the same hardware. The rare non-ASCII byte still triggers a slower Unicode fallback, but the massive speed gain on the 99% ASCII path more than makes up for it.
Why lowercasing isn’t folding
It’s tempting to reuse str::to_lowercase, but the two are different. Lowercasing is display-oriented, locale-aware, and context-sensitive—Greek final sigma and Turkish dotted I behave differently. Case folding, by contrast, is comparison-oriented, locale-independent, and stable: if A folds to B, B folds to A everywhere. That’s why GitHub’s new Rust crate, casefold, implements only the simple one-to-one folds from Unicode’s CaseFolding.txt, ignoring multi-character expansions like ß→ss or locale-specific rules. Popular tools such as ripgrep make the same choice to keep behavior consistent across systems.
The engineering takeaway
For teams running heavy text processing at scale, this result is a reminder that micro-optimizations can backfire. In a domain where every cycle counts—search engines, regex matchers, case-insensitive usernames—even a small branch can shave off hundreds of megabytes per second. The lesson is to profile first, then simplify, and resist the urge to add “clever” early exits until the data says otherwise.
Why it matters
For developers who rely on fast, accurate code search across millions of repos, this change isn’t just a benchmark bump—it’s a practical doubling of throughput that can shorten CI times and reduce query latency. For the Rust ecosystem, the open-source casefold crate offers a drop-in way to fold text without locale surprises. And for the broader industry, it’s proof that when performance is paramount, the best optimization may be the one you didn’t add.
Source: GitHub Blog. AI-assisted editorial synthesis — TechnoExpress.