{"id":4703,"date":"2026-07-31T16:56:20","date_gmt":"2026-07-31T16:56:20","guid":{"rendered":"https:\/\/rssfeedtelegrambot.bnaya.co.il\/index.php\/2026\/07\/31\/dont-stop-early-case-folding-source-code-at-memory-speed\/"},"modified":"2026-07-31T16:56:20","modified_gmt":"2026-07-31T16:56:20","slug":"dont-stop-early-case-folding-source-code-at-memory-speed","status":"publish","type":"post","link":"https:\/\/rssfeedtelegrambot.bnaya.co.il\/index.php\/2026\/07\/31\/dont-stop-early-case-folding-source-code-at-memory-speed\/","title":{"rendered":"Don\u2019t stop early: Case-folding source code at memory speed"},"content":{"rendered":"
Suppose a user searches for caf\u00e9 and your corpus contains CAF\u00c9, or they type stra\u00dfe and you\u2019ve 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.<\/p>\n
It\u2019s a basic operation, but at GitHub we run it a lot. Blackbird, GitHub\u2019s code search engine, indexes over 180 million repositories\u2014more 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.<\/p>\n
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.<\/p>\n
Folding is not lowercasing<\/h2>\n
It is tempting to reach for str::to_lowercase<\/code>, but lowercasing and folding are different operations with different goals:<\/p>\n
Lowercasing is for display, and it\u2019s locale- and context-sensitive: Greek final sigma lowercases to \u03c2 at the end of a word and \u03c3 elsewhere, and Turkish I lowercases differently than English I. Case folding is for comparison, and it\u2019s 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.<\/p>\n
The two operations diverge on real characters\u2014\u00df, \u0130, final sigma\u2014which is why lowercasing as a stand-in silently produces wrong matches. This crate implements only the simple (1-to-1) folds\u2014statuses C and S in CaseFolding.txt<\/code>\u2014and not the multi-character \u201cfull\u201d folds (\u00df \u2192 ss) or Turkic locale folds (the dotted \u0130). This isn\u2019t an unusual choice: common tools and regex engines like ripgrep make the same restriction, and being consistent across tools is important.<\/p>\n
The counterintuitive core: Don\u2019t stop early<\/h2>\n
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.<\/p>\n
The fold of an ASCII letter is trivial\u2014A..=Z<\/code> map to a..=z<\/code>, everything else is unchanged\u2014so the ASCII pass is really just \u201csweep the buffer, lowercase in place.\u201d Ask any LLM for it and you might get something like this:<\/p>\n
\n
let bytes = s.as_bytes_mut(); \nfor (i, b) in bytes.iter_mut().enumerate() { \n if *b >= 0x80 { \n break; \/\/ non-ASCII at index i: hand the rest to the Unicode path \n } \n if b.is_ascii_uppercase() { \n *b += 32; \/\/ 'A'..='Z' \u2192 'a'..='z' \n } \n}<\/code><\/pre>\n<\/div>\n
It looks ideal: do the cheap byte work, and the instant you hit a non-ASCII byte, break and let the \u201creal\u201d Unicode path take over: \u201conly do the cheap work until you have to.\u201d On an Apple M4 this runs at about 3 GiB\/s<\/strong>. That sounds fine in isolation, but it is more than 15\u00d7 short<\/strong> of \u201coptimal\u201d because of the if branches.<\/p>\n
Let\u2019s delete every branch, line by line:<\/p>\n
\n
if b >= 0x80 { break }<\/code> \u2192 don\u2019t stop at all. OR<\/code>every byte into an accumulator and test it once<\/em>, after the loop: high_bit_acc |= *b<\/code>. Same information (was there any non-ASCII byte?), zero branches in the body.<\/li>\n
The<\/strong> A..=Z<\/code> range test<\/strong> \u2192 make it arithmetic. b.wrapping_sub(b'A') < 26<\/code> is true exactly for A..=Z<\/code> (any other byte wraps to \u2265 26), yielding a 0\/1 mask with no branch.<\/li>\n
The conditional write<\/strong> \u2192 fold the mask into the store.| (is_upper << 5)<\/code>sets bit 5\u2014turning an upper-case letter lower-case and being a no-op on everything else\u2014the byte is always written, never branched on.<\/li>\n<\/ul>\n
What\u2019s left has no branch in its body and no early exit:<\/p>\n
\n
let mut high_bit_acc: u8 = 0; \nfor b in &mut bytes { \n high_bit_acc |= *b; \/\/ detect any non-ASCII byte \n let is_upper = b.wrapping_sub(b'A') < 26; \/\/ branchless A..=Z test \n *b |= u8::from(is_upper) << 5; \/\/ set bit 5 \u2192 lowercase, else no-op \n} \nif high_bit_acc & 0x80 == 0 { \n return bytes; \/\/ pure ASCII: already folded in place, no second buffer \n}<\/code><\/pre>\n<\/div>\n
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<\/strong>\u2014essentially memory bandwidth. And we come out of the pass already knowing, from high_bit_acc<\/code>, whether there\u2019s any non-ASCII work left to do.<\/p>\n
How much did each step matter? Measuring the cumulative ladder on pure ASCII (Apple M4, 5.7 KB buffer):<\/p>\n
The early-exit is what gates vectorization: keep the break but make the body perfectly branch-free and you still get zero<\/strong> vector instructions (~2.6 GiB\/s); a data-dependent loop exit is enough on its own to keep the loop scalar. Only once the break is gone can the compiler vectorize. The final step\u2014making the upper-case fold branchless\u2014then turns a partially<\/em> vectorized loop (which still compiles the conditional store to a compare-blend-masked-store, ~7.6 GiB\/s) into the straight-line arithmetic that hits memory bandwidth.<\/p>\n
\n
\n\n
\n
Note: Branchless is a<\/strong> pessimization<\/strong> in scalar code.<\/strong> Look again at the table: making the body branchless while keeping<\/em> the break (2.6 GiB\/s) is actually slower<\/strong> than the naive branchy loop (3.1 GiB\/s). The asm explains why. The branchy version only stores a byte when it actually changes one; its conditional strb<\/code>is skipped for every lowercase letter, digit and space (the vast majority of real text), and the well-predicted branch that guards it is nearly free. The branchless version replaces that rarely taken store with an unconditional<\/strong> strb<\/code>every iteration<\/strong>, writing back all ~5,700 bytes instead of just the handful of upper-case ones. Extra write traffic for no benefit. Branchless-write only wins<\/em> once the loop vectorizes, because then the store becomes a single 16-byte vector write regardless of content, and the per-byte cost disappears. The lesson: a branchless body is worth it only<\/strong> as the enabler for vectorization. On its own, in scalar code, it can cost you.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n
There\u2019s also a middle ground, and it\u2019s what standard libraries use. Instead of testing one byte at a time, [u8]::is_ascii<\/code> scans a machine word at a time<\/strong>\u2014on a 64-bit target it tests 16 bytes per iteration by OR-ing two u64 lanes and checking all their high bits with a single & 0x8080_8080_8080_8080<\/code> mask. You can build the ASCII fast path on top of that: chunk-scan to find the ASCII prefix, then run the branchless (vectorizable) convert over it. That keeps the early-exit ability\u2014it still bails on the first non-ASCII block\u2014while letting both halves go fast. The catch is that it reads the data twice<\/strong> (once to scan, once to convert), landing at about 23 GiB\/s<\/strong>\u2014roughly half of the single-pass branchless sweep, and ~7\u00d7 the naive break loop. A solid, general-purpose default; just not the absolute ceiling when you control the whole loop and can fold detection and conversion into one branch-free pass.<\/p>\n
Wouldn\u2019t<\/strong> fusing<\/em><\/strong> the two passes be faster?<\/strong> It\u2019s the obvious next thought: keep the chunked early-exit but convert each 16-byte block right after you\u2019ve confirmed it\u2019s ASCII, reading the data only once<\/em>. Measured, it\u2019s ~2.6\u00d7 slower<\/strong>\u20148.7 GiB\/s versus the two-pass 23. The inner block convert still vectorizes to a single 16-byte op, but now there\u2019s a data-dependent early-exit branch every 16 bytes<\/em>, and that branch pins the loop to one block at a time: the compiler doesn\u2019t unroll or software-pipeline across blocks, and each iteration pays the full load\u2192test\u2192branch\u2192convert\u2192store latency with nothing to hide it behind. Split into two passes, each one is clean: the scan is a branch-light, store-free<\/strong> word scan that races through memory, and the convert is the fully-vectorized branch-free sweep at >45 GiB\/s. Two fast, branch-free passes beat one branchy fused pass\u2014even though the fused version touches the data half as many times. It\u2019s the same lesson one more time: in the hot loop, the branch is the enemy.<\/p>\n
Avoiding the heap<\/h2>\n
Forty-Five GiB\/s also means doing zero unnecessary allocation. simple_fold<\/code> takes the input String by value<\/em>, owning the heap buffer it can mutate and return it. If the OR-accumulator\u2019s high bit was clear, the input was pure ASCII already folded in place. We hand the same allocation<\/strong> straight back, no second buffer and no copy. Otherwise, we memchr<\/code>to the first non-ASCII byte and scan the tail from there, leaving the output buffer unallocated<\/em> (a null write cursor) until we hit a character that folds to different bytes<\/strong>. Text whose multibyte content never folds\u2014CJK, Hangul, Kana, Arabic, Hebrew, symbols\u2014also returns the original allocation untouched, never copying a byte.<\/p>\n
Why a second<\/em> buffer rather than rewriting in place like the ASCII pass? Because folding can make the string longer<\/strong>: almost every fold preserves the UTF-8 length or shrinks it, but two outliers grow\u2014U+023A<\/code> (\u023a) and U+023E<\/code> (\u2c7f) are 2 bytes each yet fold to 3-byte characters (\u2c65, \u0240). Once one appears, the output no longer fits in the input\u2019s bytes, and we need somewhere new to write.<\/p>\n
We allocate that buffer once<\/strong>, sized for the worst case, rather than growing it as more folds appear. Incremental reserve calls would mean re-checking capacity, occasionally reallocating, copying everything written so far, and juggling extra length\/capacity bookkeeping; a single up-front allocation lets a raw write cursor run straight to the end with none of that. And since the cursor is null<\/code>until that first growing\/changing fold, it doubles as the \u201chave we allocated the extra buffer yet?\u201d flag.<\/p>\n
Sizing it needs a bound on growth, and those same two outliers give it: every 2 input bytes yield at most 3 output bytes, capping the output at 1.5\u00d7 the input<\/strong>\u2014exactly the capacity we reserve:<\/p>\n
\n
out = Vec::with_capacity(bytes.len() + bytes.len() \/ 2 + 4); <\/code><\/pre>\n<\/div>\n
After that the loop writes through a raw pointer with no capacity checks and calls set_len<\/code> once at the end. Two more details keep it branch-light. The run of unchanged bytes between two folds is moved with a single copy_nonoverlapping<\/code> rather than byte by byte. And each fold unconditionally writes all 4 bytes of a little-endian word before bumping the cursor by only the folded<\/em> length (1\u20134)\u2014dropping a branch on the output length from the hot path, with the + 4 in the reservation as the headroom that makes the final character\u2019s over-store safe.<\/p>\n
Making Unicode cheap too<\/h2>\n
When a character does<\/em> fold, we still don\u2019t want to fall off a cliff\u2014decode UTF-8, hash lookup, re-encode. Unicode 16.0 has 1484 simple-fold mappings, but they\u2019re a very<\/em> sparse and very<\/em> structured relation. Four observations shrink them to 1776 bytes<\/strong> and let the fold run without ever decoding a full character<\/strong>.<\/p>\n
Even on the non-ASCII path, the overwhelming majority of characters do not fold. The hot operation isn\u2019t really \u201cfold this character,\u201d it\u2019s \u201cdoes this character fold?\u201d Almost always no. The table has to make that negative test<\/strong> as cheap as possible; the actual folding is the rare case on an already-rare path. That priority is what shapes the layout below\u2014the page bitmap exists precisely so a non-folding character is rejected in a single bit test, straight from its leading UTF-8 bytes, without decoding or scanning anything.<\/p>\n
This is exactly why a HashMap<u32, u32><\/code> is the wrong<\/em> shape for the job, not just a bigger one. A hash map is optimized for the hit<\/strong>: it finds a present key in roughly one probe, and only spends extra work (more probes, full key comparison) when load factor or collisions bite. But our workload is dominated by misses<\/strong>\u2014characters that aren\u2019t in the table at all\u2014and a miss is a hash map\u2019s least<\/em> favorite query: it still has to hash the key, jump to a bucket, and walk the probe sequence far enough to prove absence<\/em>.<\/p>\n
Foldable code points cluster into 64-code-point \u201cpages\u201d<\/h2>\n
Foldable code points bunch together. Slice the code space into 64-code-point \u201cpages\u201d and the ~1484 folds touch just 59<\/strong> of ~1960 possible pages. A one-bit-per-page presence<\/strong> bitmap<\/strong> answers the negative test on its own: a clear bit is a definitive<\/em> \u201cno fold\u201d\u2014copy through, done\u2014which is what makes fold-free scripts cheap. Only on a set bit do we consult a second structure, a cumulative-popcount side table<\/strong> that ranks the page (how many populated pages precede it) to find its slice of entries, storing nothing for the ~1900 empty pages.<\/p>\n
\n
let (word_idx, bit_idx, c_len) = if lead < 0xE0 { \n (0usize, lead & 0x1F, 2usize) \/\/ 2-byte: word 0 \n} else if lead < 0xF0 { \n ((lead & 0x0F) as usize, bytes[read + 1] & 0x3F, 3) \/\/ 3-byte: word = nibble \n \n} else { \n ( \n (((lead & 0x07) as usize) << 6) | (bytes[read + 1] & 0x3F) as usize, \n bytes[read + 2] & 0x3F, \n 4usize, \n ) \/\/ 4-byte: merge 2 bytes \n}; \n\/\/ reject without decoding: clear bit \u21d2 no fold \nif word_idx >= PAGE_BITMAP.len() || (PAGE_BITMAP[word_idx] >> bit_idx) & 1 == 0 { \n read += c_len; \n continue; \n} <\/code><\/pre>\n<\/div>\n
Because word_idx<\/code>depends only on the lead byte (and, for four-byte sequences, the first continuation byte), the bitmap load can be issued early.<\/p>\n
Within a page, folds come in runs<\/h2>\n
A set page bit tells us something<\/em> on this page folds, but not which code points or to what. The obvious encoding is one entry per foldable code point\u2014but that is both bulky and slow to search: a page can hold dozens of folds, and we\u2019d have to scan them all to find the one matching the current code point. The structure of the data rescues us again. Adjacent code points overwhelmingly share the same delta to their fold: A\u2013Z all map +32<\/code>, and Latin Extended is full of alternating<\/em> runs like 0x0100<\/code>, 0x0102<\/code>, 0x0104<\/code>, \u2026 where every second code point folds. Instead of per-code-point entries we store runs<\/strong>\u2014start, end, stride, delta\u2014and a 1-bit stride flag covers both the contiguous and the every-other case. This interval compression collapses the ~1484 individual folds into just 238<\/strong> runs across the 59 pages (\u2248four per page), leaving the within-page search only a handful of entries to look at instead of dozens. This range-with-delta encoding (including the stride trick) is borrowed from Go\u2019s unicode package, whose CaseRange<\/code><\/a> records store a Lo\/Hi range plus per-case deltas, with an UpperLower<\/code> sentinel marking the alternating blocks. Runs are split at the page boundaries so a run never straddles two pages.<\/p>\n