Don’t stop early: Case-folding source code at memory speed

The Case-Folding Bottleneck No One Thinks About

Case folding is the quiet workhorse behind search and matching: it turns CAFÉ into café and STRASSE into strasse, so queries and stored text can be compared without case noise. It’s omnipresent in regex flags, case-insensitive usernames, and just about any code that matches rather than displays text.

At GitHub’s scale the volume is staggering—Blackbird code search indexes 180 million repositories, over 480TB of source. Every byte must be case-folded before indexing and again while matching queries, so even minor per-byte costs multiply into real latency. The team’s answer is an open-source Rust crate, casefold, and the path there is not what you’d expect.

Why Normal Lowercasing Won’t Cut It

The instinct to reuse str::to_lowercase hides a core mismatch. Lowercasing is locale- and context-sensitive, meant for display; case folding is deliberately context-free and locale-independent, meant for comparison. Greek final sigma and Turkish I prove the divergence—the Unicode Character Database’s explicit CaseFolding.txt is the stable, symmetric relation that lowercasing can’t substitute for. The crate implements only the simple (1-to-1) statuses C and S, skipping full folds like ß → ss and Turkic, a restriction consistent with mainstream tools like ripgrep.

ASCII Fast Path: Branchless Wins

Source code is overwhelmingly ASCII, so making that path run at memory speed dominates. The direct approach—loop, test each byte for the high bit, bail on first non-ASCII—is intuitive but slow: on an Apple M4 it’s roughly 3 GiB/s, over 15× off the practical ceiling. The fix is strange: remove the early exit entirely.

Instead of branching per byte, OR every byte into an accumulator (high_bit_acc |= *b) and test once after the loop. The range test becomes arithmetic (b.wrapping_sub(b'A') < 26) yielding a 0/1 mask. The conditional write becomes unconditional: | (is_upper << 5) flips bit 5 on upper-case letters, a no-op on everything else. The result is a branch-free body with no early exit:

The compiler vectorizes this trivially—NEON handles 16 bytes per pass—pushing throughput past 45 GiB/s, right at memory bandwidth. The accumulated high-bit flag still tells you whether any non-ASCII work exists. But stripping the early exit alone gates vectorization: keeping it, even with a branch-free body, yields zero vector instructions. Only removing the branch lets the compiler generate straight-line arithmetic that hits the memory-speed ceiling. The cumulative effect: branchless detection plus branchless conversion hits bandwidth, whereas any data-dependent control flow stalls vectorization—whether the branch sits inside the loop or gates the exit.

A standard-library compromise exists too: scan by machine word (16 bytes at a time on 64-bit) checking a single & 0x8080_8080_8080_8080 mask, then convert the ASCII prefix. That’s ~23 GiB/s—solid, but half of the single-pass sweep because data is read twice. Fusing scan and convert into one pass actually does worse: ~8.7 GiB/s, because a data-dependent branch every 16 bytes prevents unrolling and software pipelining. Two clean branch-light passes beat one branchy fused pass, even though the fused version touches memory half as often.

Zero-Heap Folding in Practice

At 45 GiB/s, allocation would kill the win. The simple_fold API takes the input String by value, mutates it in place, and returns the same buffer when pure ASCII passes through. If a high-bit appears, it finds the first non-ASCII byte with memchr and scans the tail—leaving output unallocated until a character folds to different bytes. Multibyte text that never folds (CJK, Hangul, Kana, symbols) round-trips untouched.

Why a second buffer for the tail? A few folds grow the string: U+023A and U+023E are 2-byte characters that fold to 3-byte ones. With input 2 bytes at a time yielding at most 3 output bytes, capacity is bounded at 1.5× the input—allocated once up front. The write cursor stays null until the first growing fold, doubling as a dirty flag, and each fold writes a full little-endian 4-byte word before bumping by the actual folded length. Unchanged runs move with a single copy_nonoverlapping.

Unicode Folding on the Cheap

The rare non-ASCII path is dominated by misses—most multibyte characters don’t fold. Unicode 16.0 lists 1484 simple folds, but these cluster into just 59 occupied “pages” of 64 code points each across the ~1960 possible. A one-bit-per-page presence bitmap gives a definitive negative in a single bit test from the leading UTF-8 bytes, before decoding ever happens. A HashMap is wrong here: optimized for hits, it truly fails on proves-absence queries, which is exactly what dominates. On a set bit, a cumulative-popcount side table ranks the page and indexes its slice of fold entries.

Because page selection depends only on lead bytes (plus one continuation byte for four-byte sequences), the bitmap load issues early, overlapping with the text scan itself. The result is 1776 bytes of table that make even Unicode folding almost invisible against memory bandwidth.

Run-length encoding for page-local folds

A set page bit tells us something folds on that page, but not which code points or to what. Storing one entry per foldable code point would be bulky and slow: a page can hold dozens of folds, requiring a scan to find a match. The data’s structure rescues us: adjacent code points overwhelmingly share the same fold delta. A–Z all map +32, while Latin Extended contains alternating runs such as 0x0100, 0x0102, 0x0104, where every second code point folds.

So instead of per-code-point entries, we store runs—start, end, stride, delta—with a 1-bit stride flag distinguishing contiguous from every-other sequences. This interval compression shrinks ~1484 individual folds to just 238 runs across 59 pages (≈four per page), leaving only a handful of entries to check per page. The encoding is borrowed from Go’s unicode package, whose CaseRange records hold a Lo/Hi range plus per-case deltas, with an UpperLower sentinel for alternating blocks. Runs never straddle page boundaries; they’re split so each is wholly contained in one page.

Two-byte run records, checked eight at a time

With both endpoints on one page, each fits in 6 bits, spread across two arrays: RUN_END_LOW[i] = end & 0x3F, the scan key, and RUN_START_STRIDE[i] = (start & 0x3F) | ((stride − 1) << 6), read only on a hit. Since each key is one clean byte, the within-page search goes wide: load 8 end_low bytes into a single u64 and test all of them with one branchless SWAR step—(chunk | 0x80…80) − broadcast(low) & 0x80…80 sets the top bit of every lane whose key is ≥ cp & 0x3F. Because the keys are sorted, a single bit-scan of the mask finds the first set lane: the run we want. The average page holds ~4 runs, so this one 8-wide compare usually resolves the entire search in one step. One outlier page has 30 runs, putting the compare inside a short loop that strides eight keys at a time—but that loop trips at most a handful of times on exactly one page in all of Unicode. Either way, there’s no per-run branch and no code-point reconstruction.

/// Offset of the first run with `end_low >= low_v` in a page of `n` runs, 
/// or `n` if none. Scans 8 `end_low` bytes at a time via SWAR. 
#[inline] 
fn scan_end_low(lo: usize, n: usize, low_v: u8) -> usize { 
    const HIGH: u64 = 0x8080_8080_8080_8080; 
    const ONES: u64 = 0x0101_0101_0101_0101; 
    let bcast = (low_v as u64).wrapping_mul(ONES); 
    let mut base = 0; 
    while base < n { 
        // RUN_END_LOW is padded by 8 bytes so this read is always in bounds. 
        let chunk = u64::from_le_bytes( 
            RUN_END_LOW[lo + base..lo + base + 8] 
                .try_into() 
                .expect("8-byte slice"), 
        ); 
        // `(b | 0x80) - low_v` keeps its high bit iff `b >= low_v` (no 
        // cross-lane borrow). The first set lane is the first run `>= low_v`. 
        let ge = (chunk | HIGH).wrapping_sub(bcast) & HIGH; 
        if ge != 0 { 
            let j = base + (ge.trailing_zeros() / 8) as usize; 
            return if j < n { j } else { n }; 
        } 
        base += 8; 
    } 
    n 
} 

Folding as little-endian byte addition

On little-endian hardware, a folded character’s UTF-8 bytes read as a u32 equal the source bytes plus a per-run constant. A parallel BYTE_DELTA[i] table turns the whole fold into a masked load, one wrapping_add, and a 4-byte store:

let word = u32::from_le_bytes(next_four_bytes) & length_mask; // keep this char's bytes 
let folded = word.wrapping_add(BYTE_DELTA[i]); // the fold, as one byte add 
write_u32_le(dst, folded); // store all 4 bytes... 
dst += utf8_len(folded); // ...advance by the folded length

Both lengths in that snippet—the length_mask for the source character and the advance by the folded length for the destination—come from one more trick: a UTF-8 sequence’s length is fixed by the top four bits of its lead byte. The 16 possible lengths pack one nibble each into a single 64-bit constant (0x4322_1111_1111_1111), so the length is a shift and a mask, (LEN_BITS >> (4 * (lead >> 4))) & 0xF. No if chain, no table memory, nothing for the predictor to mispredict. A count of leading ones—(!lead).leading_zeros()—could also work, as a lead byte carries one leading 1-bit per sequence byte.

/// Number of bytes in the UTF-8 sequence whose lead byte is `lead`. 
#[inline] 
pub fn utf8_len(lead: u8) -> usize { 
    const UTF8_LEN_BY_LEAD: u64 = 0x4322_1111_1111_1111; 
    ((UTF8_LEN_BY_LEAD >> (4 * (lead >> 4))) & 0xF) as usize 
}

Advancing by the folded length handles length-changing folds—U+212A KELVIN SIGN (3 bytes) → k (1 byte), or U+023A Ⱥ (2 bytes) → U+2C65 ⱥ (3 bytes)—writing fewer or more bytes than were read. This is the aspect we believe is genuinely new: every other folder we inspected (ICU, Go’s unicode, Rust’s regex, CPython, glibc) decodes UTF-8 to a code point, folds there, and re-encodes, even in SIMD implementations. Byte-space arithmetic skips both decode and encode, which is exactly why this path can beat a hash map that already has the answer tabulated—that map must still decode its key and encode its result.

The byte-space approach assumes well-formed, shortest-form UTF-8, where every code point occupies the minimal byte count. An overlong encoding (e.g., / as 0xC0 0xAF) has a different byte pattern that breaks the length_mask and delta arithmetic. Rust callers are safe: &str and String guarantee valid UTF-8, which excludes overlong sequences. Callers feeding raw bytes from elsewhere must validate first.

The ASCII tail-loop shortcut

The tail loop gets one more shortcut. Since the first pass already lowercased every ASCII byte, meeting an ASCII byte in the tail advances a single byte without probing a page or touching the tables. It doesn’t copy that byte either: unchanged bytes (ASCII and non-folding multibyte alike) aren’t moved one at a time. The scan walks until it finds a character that folds, then flushes the whole unmodified run between the last fold and the current one with a single copy_nonoverlapping. Mixed text—CJK with ASCII spaces, code with accented identifiers—races through ASCII filler, consulting the bitmap only for multibyte characters and copying in bulk.

The complete table

That’s 9.6 bits per fold entry, over half of it the BYTE_DELTA side table we exchange for a decode-free path; the index and run records alone amount to ~4.4 bits/entry. At 1776 bytes, that’s an order of magnitude or more smaller than the obvious alternatives—and unlike most, it never decodes a character:

Measured against real folders

On common ASCII input, folding runs at memory bandwidth (>45 GiB/s), more than an order of magnitude faster than other real folders and over 50% faster than str::to_lowercase, which isn’t even equivalent. We also measured the most optimized UTF-8 decode+encode round trip that performs no folding at all—using the simdutf crate, consistently about 2 GB/s—to approximate an upper bound for the non-ASCII path. It’s only about twice as fast as our worst-case, all-folding input. A naive hash map trails everything.

Treat absolute figures as illustrative: the design relies on auto-vectorization, SWAR, and little-endian byte arithmetic, so numbers and ratios can shift substantially across microarchitectures—wider or narrower vectors, different memory bandwidth, big-endian targets, x86 vs. ARM. The performance section of the README has more detail.

Principles worth stealing

Case folding is as basic as text processing gets, which is why it earned the effort—we apply it to every indexed byte. The wins came from two counterintuitive ideas: sweeping the whole buffer branch-free instead of stopping at the first fold, and performing the fold as byte-space arithmetic instead of decoding to a code point. Together they let the common case run at memory bandwidth, the rare fold run without a decode, and the entire table—1776 bytes—stay cache-resident. The decode-free byte-space fold is the genuinely new piece, and it’s why this beats a pre-tabulated hash map. The crate is casefold; generated tables and full design notes ship with the source.