Don't Stop Early: Case-Folding Source Code at Memory Speed
How GitHub's code search team removed an early-exit branch from a hot loop and gained a 15× throughput improvement — because the branch, not the work, was the bottleneck.
The loop that stops as soon as it hits a non-ASCII byte looks more efficient than one that sweeps the entire buffer. On an Apple M4, the first version runs at 3 GiB/s. The second runs at over 45 GiB/s. The “optimization” was the bottleneck the whole time.
Source
Don’t stop early: Case-folding source code at memory speed
By: Alexander Neubeck & Greg Orzell, GitHub
Published: Jul 31 2026
Type: Engineering article
Worth saving because this is one of the clearest available demonstrations of the SIMD vectorization contract — the specific conditions under which a compiler can transform a scalar loop into parallel vector instructions. The counterintuitive result (branchless body code can be slower in scalar mode) is exactly the kind of thing that gets cargo-culted in the wrong direction without the underlying model.
The branch that blocked 15× throughput
GitHub’s Blackbird code search engine indexes over 180 million repositories — more than 480 terabytes of source code. Before extracting n-grams and building the search index, every byte gets case-folded. That operation runs twice: once during index construction, once per potential query result. At 480 TB, even a per-byte operation with negligible per-byte cost starts mattering enormously at scale.
Case folding and lowercasing look identical for ASCII text but solve fundamentally different problems. Lowercasing is for display, and it’s locale-sensitive: Turkish I lowercases differently than English I; Greek final sigma (ς) lowercases differently at the end of a word versus the middle. Case folding is for comparison — it’s deliberately context-free and symmetric, so if A folds to match B, then B folds to match A in every locale. The Unicode Character Database ships CaseFolding.txt precisely for this. Using str::to_lowercase as a stand-in silently produces wrong matches on characters like ß or İ. At GitHub’s scale, “wrong on a small class of characters” means millions of incorrect search results.
For source code, the corpus is overwhelmingly ASCII. The fast path is simple: if a byte falls in A..=Z, add 32 to lowercase it; everything else passes through unchanged. The natural instinct for this loop is to bail out the moment you see a non-ASCII byte — “do cheap work until you must do expensive work” — and hand the remainder to a full Unicode path. A loop written this way, with if *b >= 0x80 { break } in the body, runs at roughly 3 GiB/s on an M4. That sounds adequate until you know the machine’s memory bandwidth ceiling is around 100 GiB/s.
The issue is what the early-exit branch means to the compiler. LLVM (the backend Rust compiles through) can vectorize a loop — emit NEON or AVX instructions that process 16 bytes simultaneously — only when the loop body has no data-dependent control flow. The break condition on non-ASCII bytes is a promise to the CPU: the number of iterations depends on what the data contains. The CPU cannot speculatively pipeline past that boundary, and LLVM cannot reformulate the loop as a fixed-width vector operation. The result is fully scalar execution: one byte at a time, every iteration, even on hardware built to process 16 bytes at once.
The fix is to break the promise. Instead of exiting on the first non-ASCII byte, sweep the entire buffer and accumulate all bytes into a side variable with bitwise OR: high_bit_acc |= *b. Test the accumulator once, after the loop, to see whether any non-ASCII bytes appeared. The information content is identical; the branches inside the loop body are gone. With that exit branch removed, LLVM emits 16-byte-at-a-time NEON instructions, and throughput jumps to over 45 GiB/s — essentially the memory bandwidth limit.
The step-by-step measurement table is worth sitting with. The authors tracked throughput at each incremental change on a fixed pure-ASCII buffer. Removing only the early-exit break (while keeping a conditional write for uppercase letters) reaches 7.6 GiB/s with partial vectorization — 25 vector instructions, up from zero. Making the write branchless as well — replacing if b.is_ascii_uppercase() { *b += 32 } with *b |= u8::from(is_upper) << 5 — reaches full vectorization and >45 GiB/s. But there’s a counterintuitive row in that table: making the body perfectly branchless while keeping the early exit is actually slower than the original naive branchy loop — 2.6 GiB/s versus 3.1 GiB/s. The branchless body unconditionally writes back every byte in the buffer, even bytes that haven’t changed. Source code is mostly lowercase letters, digits, and punctuation; the original branchy version stores only the handful of uppercase bytes that actually change, and a well-predicted branch on predominantly-unchanged data is nearly free. Branchless arithmetic creates write pressure for no benefit in scalar code. It only pays off once vectorization turns each write into a 16-byte SIMD store that costs the same per byte as a 1-byte scalar store.
A second insight comes from the two-pass versus one-pass comparison. The obvious improvement would be to scan 16 bytes at a time for non-ASCII content and convert each block immediately after confirming it’s safe — read the data once, fold and detect in a single pass. Measured, this fused version runs at 8.7 GiB/s, about 2.6× slower than the two-pass approach. The reason is that the fused loop re-introduces a data-dependent exit every 16 bytes. That branch prevents the compiler from unrolling or software-pipelining across blocks, and each iteration pays full load-test-branch-convert-store latency with nothing to hide behind. Two clean passes — one word-level scan that races through memory detecting non-ASCII, one fully vectorized branch-free sweep that converts — beat one fused pass even though the fused version reads the data half as many times. The branch in the hot loop costs more than the extra memory read.
For non-ASCII characters, the authors built a 1,776-byte lookup structure. Of roughly 1,960 possible 64-code-point “pages” in Unicode, only 59 contain foldable characters. A one-bit-per-page presence bitmap answers the negative case — most characters do not fold — in a single bit test without decoding the code point at all. A set bit leads to a packed run-length table of 238 runs covering all 1,484 simple fold mappings; eight runs are compared simultaneously per step using SWAR arithmetic on a single 64-bit integer. When a fold is found, it applies as a little-endian byte addition: the UTF-8 bytes of the folded character equal the UTF-8 source bytes plus a per-run constant, with no decode and no re-encode. The authors believe this byte-space fold arithmetic is genuinely novel — every other folder they surveyed, including ICU, Go’s unicode package, Rust’s regex crate, CPython, and glibc, decodes to a code point first. The result: common non-ASCII text without foldable characters (CJK, Hangul, Arabic) runs at 2.95 GiB/s; only Latin/Greek/Cyrillic text where every character folds drops below 1 GiB/s. The whole structure fits in 1,776 bytes, small enough to stay resident in L1 cache. The crate is open-sourced as casefold on GitHub.
My take
What this post makes concrete is that compiler vectorization is an explicit contract, not a best-effort heuristic. The terms are: no data-dependent control flow in the loop body, no data-dependent exit from the loop. Violate either condition anywhere — even while making every other instruction in the body perfectly branch-free — and the compiler cannot vectorize. The regression from 3.1 GiB/s to 2.6 GiB/s when adding branchless writes while keeping the break is the proof. Branchless code has a real cost in scalar mode: unconditional writes, potential false dependencies, increased write traffic. It only pays when vectorization collects the return. The lesson generalises: profile the assembly before concluding that “branchless is faster.”
Where this is useful
- When writing a hot scan loop in Rust or C where early exit feels natural: measure with and without the break before shipping it.
- When a performance-sensitive loop with a predictable branch runs faster than the “branchless” version — check whether vectorization is being blocked; that’s almost always the explanation.
- When designing Unicode-aware text utilities: the paged bitmap plus run-length approach is a reusable pattern for any sparse character-property lookup where the negative case dominates.
- Not applicable when the loop genuinely must stop early for correctness, or when the input is consistently small enough that latency dominates over throughput.
Apply this: In your next hot loop with an early-exit on a data condition, try accumulating the condition into a side register with OR and testing once after the loop. Then compare the generated assembly with and without the change.
What I want to remember
Remember: A data-dependent exit branch in a loop body is a promise to the compiler that the iteration count depends on input. That promise blocks SIMD vectorization. Accumulate the condition, test outside the loop, and let the body run straight.