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

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. 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. 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.

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. ” 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. OR every byte into an accumulator and test it once , after the loop: high_bit_acc |= *b . ), zero branches in the body.

=Z range test → make it arithmetic. =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. 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 pass already knowing, from high_bit_acc , whether there’s any non-ASCII work left to do.

How much did each step matter? 7 KB buffer): Version   Throughput   Vectorized? 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. 6 GiB/s) into the straight-line arithmetic that hits memory bandwidth. Note: Branchless is a pessimization in scalar code.

1 GiB/s). The asm explains why. The branchy version only stores a byte when it actually changes one; its conditional strb 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 strb every iteration , 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 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 as the enabler for vectorization. On its own, in scalar code, it can cost you. There’s also a middle ground, and it’s what standard libraries use.

Instead of testing one byte at a time, [u8]::is_ascii scans a machine word at a time —on 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 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—it still bails on the first non-ASCII block—while letting both halves go fast.

The catch is that it reads the data twice (once to scan, once to convert), landing at about 23 GiB/s —roughly half of the single-pass branchless sweep, and ~7× 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. Wouldn’t fusing the two passes be faster?

It’s the obvious next thought: keep the chunked early-exit but convert each 16-byte block right after you’ve confirmed it’s ASCII, reading the data only once . 7 GiB/s versus the two-pass 23. The inner block convert still vectorizes to a single 16-byte op, but now there’s a data-dependent early-exit branch every 16 bytes , and that branch pins the loop to one block at a time: the compiler doesn’t unroll or software-pipeline across blocks, and each iteration pays the full load→test→branch→convert→store latency with nothing to hide it behind.

Split into two passes, each one is clean: the scan is a branch-light, store-free 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—even though the fused version touches the data half as many times. It’s the same lesson one more time: in the hot loop, the branch is the enemy.

Avoiding the heap Forty-Five GiB/s also means doing zero unnecessary allocation. simple_fold takes the input String by value , owning the heap buffer it can mutate and return it. If the OR-accumulator’s high bit was clear, the input was pure ASCII already folded in place.

We hand the same allocation straight back, no second buffer and no copy. Otherwise, we memchr to the first non-ASCII byte and scan the tail from there, leaving the output buffer unallocated (a null write cursor) until we hit a character that folds to different bytes . Text whose multibyte content never folds—CJK, Hangul, Kana, Arabic, Hebrew, symbols—also returns the original allocation untouched, never copying a byte.

Why a second buffer rather than rewriting in place like the ASCII pass? Because folding can make the string longer : almost every fold preserves the UTF-8 length or shrinks it, but two outliers grow— U+023A (Ⱥ) and U+023E (Ɀ) are 2 bytes each yet fold to 3-byte characters (ⱥ, ɀ). Once one appears, the output no longer fits in the input’s bytes, and we need somewhere new to write.

We allocate that buffer once , 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. ” flag.

len() / 2 + 4); After that the loop writes through a raw pointer with no capacity checks and calls set_len 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 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 length (1–4)—dropping a branch on the output length from the hot path, with the + 4 in the reservation as the headroom that makes the final character’s over-store safe. Making Unicode cheap too When a character does fold, we still don’t want to fall off a cliff—decode UTF-8, hash lookup, re-encode. 0 has 1484 simple-fold mappings, but they’re a very sparse and very structured relation.

Four observations shrink them to 1776 bytes and let the fold run without ever decoding a full character . Even on the non-ASCII path, the overwhelming majority of characters do not fold. ” Almost always no.

The table has to make that negative test as cheap as possible; the actual folding is the rare case on an already-rare path. That priority is what shapes the layout below—the 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. This is exactly why a HashMap is the wrong shape for the job, not just a bigger one.

A hash map is optimized for the hit : 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 —characters that aren’t in the table at all—and a miss is a hash map’s least favorite query: it still has to hash the key, jump to a bucket, and walk the probe sequence far enough to prove absence . Foldable code points cluster into 64-code-point “pages” Foldable code points bunch together.

Slice the code space into 64-code-point “pages” and the ~1484 folds touch just 59 of ~1960 possible pages. A one-bit-per-page presence bitmap answers the negative test on its own: a clear bit is a definitive “no fold”—copy through, done—which is what makes fold-free scripts cheap. Only on a set bit do we consult a second structure, a cumulative-popcount side table that ranks the page (how many populated pages precede it) to find its slice of entries, storing nothing for the ~1900 empty pages.

len() || (PAGE_BITMAP[word_idx] >> bit_idx) & 1 == 0 { read += c_len; continue; }" tabindex="0" role="button"> Because word_idx depends only on the lead byte (and, for four-byte sequences, the first continuation byte), the bitmap load can be issued early. Within a page, folds come in runs A set page bit tells us something on this page folds, but not which code points or to what. The obvious encoding is one entry per foldable code point—but that is both bulky and slow to search: a page can hold dozens of folds, and we’d 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–Z all map +32 , and Latin Extended is full of alternating runs like 0x0100 , 0x0102 , 0x0104 , … where every second code point folds. Instead of per-code-point entries we store runs —start, end, stride, delta—and 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 runs across the 59 pages (≈four 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’s unicode package, whose CaseRange records store a Lo/Hi range plus per-case deltas, with an UpperLower sentinel marking the alternating blocks. Runs are split at the page boundaries so a run never straddles two pages.

A run record is two clean bytes With both endpoints inside one page they fit in 6 bits, split across two arrays: RUN_END_LOW[``i``] = end & 0x3F (the scan key) and RUN_START_STRIDE[``i``] = (start & 0x3F) | ((stride − 1) (read only on a hit). Because each key is one clean byte, the within-page search can go wide : rather than comparing cp & 0x3F against the runs one at a time, we load 8 end_low bytes into a single u64 and test all of them at once with one branchless SWAR step— (chunk | 0x80…80) − broadcast(low) & 0x80…80 sets the top bit of every lane whose key is ≥ cp & 0x3F . A single bit-scan of that mask (the keys are sorted, so the first set lane is the run we want) finds the slot.

A page holds ~4 runs on average; that one 8-wide compare almost always resolves the entire search in a single step. One unlucky page does hold 30 runs, which puts 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, and never on the common ones. Either way: no per-run branch, and no code-point reconstruction anywhere.

/// 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. wrapping_mul(ONES); let mut base = 0; while base = low_v` (no // cross-lane borrow).

The first set lane is the first run `>= low_v`. trailing_zeros() / 8) as usize; return if j = low_v` in a page of `n` runs, /// or `n` if none. Scans 8 `end_low` bytes at a time via SWAR.

wrapping_mul(ONES); let mut base = 0; while base = low_v` (no // cross-lane borrow). The first set lane is the first run `>= low_v`. trailing_zeros() / 8) as usize; return if j Folding is a little-endian byte addition On a little-endian machine the folded character’s UTF-8 bytes, read as a u32 , equal the source bytes (as a u32 ) plus a per-run constant .

wrapping_add(BYTE_DELTA[i]); // the fold, as one byte add write_u32_le(dst, folded); // store all 4 bytes... 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 tiny trick. A UTF-8 sequence’s length is fixed by the top four bits of its lead byte, letting the 16 possible lengths pack one nibble each into a single 64-bit constant ( 0x4322_1111_1111_1111 ); the length is then a shift and a mask, (LEN_BITS >> (4 * (lead >> 4))) & 0xF —no if chain, no table memory, nothing for the predictor to get wrong.

) /// 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 } usize { const UTF8_LEN_BY_LEAD: u64 = 0x4322_1111_1111_1111; ((UTF8_LEN_BY_LEAD >> (4 * (lead >> 4))) & 0xF) as usize }" tabindex="0" role="button"> Because we advance by the folded length, this even handles length-changing folds— U+212A KELVIN SIGN (3 bytes) → k (1 byte), or U+023A Ⱥ (2 bytes) → U+2C65 ⱥ (3 bytes)—by writing fewer or more bytes than were read. That’s the part we believe is genuinely new: every other folder we looked at—ICU, Go’s unicode, Rust’s regex, CPython, glibc—decodes UTF-8 to a code point, applies the fold there, and re-encodes (even SIMD folders decode first).

Doing the arithmetic in byte space skips both the decode and the encode, which is exactly why this path can outrun a hash map that already has the answer tabulated—the hash map still has to decode its key and encode its result. The byte-space arithmetic assumes the input is well-formed, shortest-form UTF-8 —every code point encoded with the minimal number of bytes. g.

/ as 0xC0 0xAF ) has a different byte pattern and would break the length_mask and the delta arithmetic. This is not a real restriction in Rust— &str / String are guaranteed to hold valid UTF-8, which by definition rejects overlong sequences—but a caller feeding raw bytes from elsewhere must validate (or otherwise normalize) them first. The ASCII shortcut in the tail loop One more shortcut rounds out the tail loop.

Remember the first pass already lowercased every ASCII byte, so when the scan meets an ASCII byte in the tail it advances a single byte and moves on—no page probe, no table touch at all. And it doesn’t copy that byte either: unmodified bytes (ASCII and non-folding multibyte alike) aren’t moved one at a time. The scan just keeps walking until it reaches a character that actually folds, then flushes the whole unchanged run between the last fold and this one with a single copy_nonoverlapping .

Mixed text—CJK with ASCII spaces and punctuation, or code with the occasional accented identifier—therefore races through the ASCII filler and only consults the bitmap for genuine multibyte characters, copying in bulk rather than byte by byte. 4 bits/entry. 3 KB  A runtime HashMap   ~17 KB  This crate (paged bitmap + packed runs)   1776 B   Where it lands against the alternatives On the common case, ASCII, folding runs at memory bandwidth (>45 GiB/s), more than an order of magnitude ahead of other real folders and more than 50% faster than the (non-equivalent) str::to_lowercase function.

To get a rough “upper bound” for the non-ASCII case, we measured the optimized Utf8 decoding + encoding round trip without performing any actual case folding using the simdutf crate. This experiment achieves consistently about 2GB/sec and is only about twice as fast than our solution for the worst case all-folding input. A naive hash map trails everything on all workloads.

txt lookup). 26 GiB/s   716 MiB/s  233 MiB/s  Treat the absolute figures as illustrative, not portable: the whole design leans on auto-vectorization, SWAR, and little-endian byte arithmetic, so the numbers—and even the ratios between rows—can shift substantially on a different microarchitecture (a wider or narrower vector unit, different memory bandwidth, a big-endian target, x86 vs ARM). More details can be found in the performance section of the README .

Take this with you Case folding is about as basic as text operations get, which is exactly why it was worth the effort: we run it across every byte we index. The wins came from two ideas that both cut against instinct—sweep the whole buffer branch-free instead of stopping early, and do the fold as byte-space arithmetic instead of decoding to a code point. Together they let the common case run at memory bandwidth and the rare fold run without a decode, in a table small enough (1776 bytes) to stay resident.

The decode-free byte-space fold is the piece we believe is genuinely new; it’s why this path can beat a hash map that already has the answer. There’s surely more to find here, and we’d like to see it. The crate is casefold ; the generated table and full design notes live alongside the source.

The post Don’t stop early: Case-folding source code at memory speed appeared first on The GitHub Blog .