GitHub’s Casefold Crate Turns Case-Insensitive Search Into a Byte-Arithmetic Problem

GitHub published an engineering post on July 31, 2026, describing how it rebuilt case folding, the operation that lets a search for “café” also match “CAFÉ”, for Blackbird, its code search engine. Blackbird indexes more than 180 million repositories and over 480 terabytes of source code, according to the post by engineers Alexander Neubeck and Greg Orzell, and every one of those bytes gets case-folded before GitHub extracts n-grams and builds a search index from them. The team packaged the result as a Rust crate called casefold, which GitHub published on crates.io on July 9, 2026, three weeks before the blog post explained how it works. The crate lives in GitHub’s public rust-gems repository under the MIT license.

Folding Is Not Lowercasing

The post opens by drawing a line between two operations that look interchangeable but are not. Lowercasing is meant for display and is locale- and context-sensitive: Greek capital sigma normally lowercases to sigma (σ) but takes a different final form (ς) at the end of a word, and Turkish text lowercases a dotted and a dotless I differently than English does. Case folding exists purely to support comparison, so it has to stay context-free and symmetric: if A folds to match B, B has to fold to match A the same way, no matter where either string appears. That symmetry is what a case-insensitive search index actually needs, and it is why GitHub built a dedicated fold function rather than reusing Rust’s standard lowercasing routines.

The Optimization That Made It Slower

The counterintuitive finding in GitHub’s post is that the biggest speedup on the all-ASCII fast path came from deleting an optimization instead of adding one. The team’s first instinct was to stop scanning as soon as the code hit a non-ASCII byte, since most source code is overwhelmingly ASCII. Removing that early exit and instead sweeping the entire buffer with a branch-free loop turned out to be faster: the branch created by the early-exit check was itself the bottleneck once the buffer was long enough for the compiler to auto-vectorize the sweep. Two separate branch-free passes, an initial scan plus a vectorized convert, beat one branch-heavy fused pass even though the fused version touched the data only half as many times. The crate also skips heap allocation on the common path. Its simple_fold function takes ownership of the input String and reuses the existing buffer in place for pure ASCII text, only allocating a second buffer the first time it meets a character that actually changes length or bytes under folding, such as the Kelvin sign (U+212A) folding down to a plain “k”.

A 1,776-Byte Table Beats a 17-Kilobyte Hash Map

Unicode 16.0 defines 1,484 simple case-fold mappings, and the obvious way to store them, a hash map keyed by code point, costs around 17 kilobytes and pays for a hash and a probe sequence on every character, including the vast majority of characters that never fold at all. GitHub’s structure answers “does this character fold?” with a single bit test before it looks anything up. Foldable code points cluster tightly: the crate’s lookup structure divides its addressable range into 64-code-point pages, roughly 1,960 of them, and only 59 contain a fold at all. A one-bit-per-page bitmap, backed by a cumulative-popcount side table, turns “no fold here” into one bitmap read for every character that does not need folding, which covers most CJK and Kana text in a code search index. Within those 59 populated pages, folds cluster further into runs, encoded with an approach GitHub’s post credits to the Go standard library’s unicode package. Go’s CaseRange type, confirmed on its current package documentation, stores a low and high boundary plus a per-range delta, with a special UpperLower constant (defined in Go’s source as one past the maximum valid code point) marking ranges that alternate between upper and lower case every other character. Go’s own package still ships Unicode 15.0 tables as of its current documentation, one version behind the 16.0 data GitHub’s crate draws from. GitHub packs each run’s boundaries into six bits apiece, so both boundary arrays fit one byte per run, and the fold itself is computed as a little-endian byte addition: the UTF-8 bytes of the character, read as a 32-bit integer, plus a per-run delta, written straight back with no Unicode decode or re-encode step in between. The complete table behind simple_fold, covering every simple fold in Unicode 16.0, comes to 1,776 bytes, or roughly 9.6 bits per fold entry.

Those figures come from the casefold crate’s own published README, alongside the crate’s second function, index_fold, which reuses the same fold table to collapse every character, ASCII or not, down to a single byte. That one-byte-per-character output is exactly what Blackbird needs to build fixed-width n-grams for its substring index: a fixed k-gram becomes k contiguous bytes that are already case-folded, so lookups are case-insensitive without any extra comparison step at query time.

The Benchmarks

GitHub’s blog post describes the ASCII fast path running above 45 gibibytes per second on a single core. The casefold crate’s own published benchmarks, run separately with the criterion framework on an Apple M-series machine, show 40.8 GiB/s on pure ASCII input, more than 30 times the 1.21 GiB/s that GitHub measured for simd-normalizer, an independent SIMD-accelerated Unicode normalization crate that the README’s benchmark table groups among the “true case-folders” producing the same output as simple_fold, and roughly 195 times the 213 mebibytes per second the same benchmark measured for a hash-map-based fold table doing the identical byte-level lookup. On mixed Basic Multilingual Plane text that folds throughout, casefold measured 869 MiB/s, marginally behind simd-normalizer’s 922 MiB/s, the one workload in the published results where GitHub’s approach trails. On text that never folds at all, such as CJK or Myanmar script, casefold’s page-bitmap check let it return the input essentially untouched at just under 3 GiB/s, still ahead of the other true case-folding implementations GitHub benchmarked. The README is explicit that separate standard-library routines benchmarked alongside casefold, including Rust’s own str::to_lowercase, perform Unicode lowercasing rather than case folding and are shown only as a throughput reference, not as interchangeable alternatives, since their output differs from a true fold on precisely the kind of accented, Greek, and Turkish text described above.

Part of a Broader Toolkit

Casefold is one of several crates in rust-gems, a small public collection of algorithm crates GitHub maintains for problems that recur across Blackbird’s indexing and retrieval pipeline. The same repository includes bpe and bpe-openai, byte-pair-encoding tokenizers used for chunking documents and for reproducing OpenAI’s own tokenizers; sparse-ngrams, for extracting the variable-length byte n-grams Blackbird uses in its substring index; geo_filters, for approximate distinct-count problems; and smaller utilities for hash-sorted maps and constant-time consistent hashing. Individually, each crate solves a narrow, unglamorous problem. Collectively, they describe what running search and retrieval over hundreds of millions of repositories actually takes: a willingness to replace idiomatic, general-purpose standard library calls with hand-built, byte-level routines wherever a basic operation runs often enough for its constant factor to matter, then publish the result as a reusable crate instead of keeping it as internal plumbing.

Why It Matters Beyond GitHub

Case folding is not unique to code search. Any system that needs case-insensitive comparison at scale, including log search, username and hostname lookups, and regex engines with an (?i) flag, faces the same tradeoff GitHub describes: a general-purpose Unicode routine that decodes every character is correct but slow, and a naive lookup table is fast but large enough to blow past a CPU’s cache on every miss. GitHub’s answer, a table under two kilobytes that fits comfortably in L1 cache and never decodes a code point on the common path, is a reminder that at sufficient scale, the operations least likely to get a second look, the ones assumed to be solved and shipped in a standard library, are often exactly where hand-tuned, byte-level engineering still pays for itself. The crate is on crates.io now, so any Rust project with the same case-insensitive matching problem can use GitHub’s table without rebuilding it from scratch.