Don’t Stop Early: Case-Folding Source Code at Memory Speed

Don’t Stop Early: Case-Folding Source Code at Memory Speed

Case-insensitive search is everywhere. Every time a developer presses Ctrl+Shift+F to find a variable named user_id or UserID, the underlying engine must decide: are those two strings equal? For that split second, a piece of code performs 'case-folding' — converting both strings to a normalized form. It sounds trivial. But in massive monorepos, this single operation can make or break search performance.

A recent engineering deep dive from GitHub explores exactly this problem. The article, titled “Don’t Stop Early: Case-Folding Source Code at Memory Speed” (Source), describes how the team implemented a case-folding routine that runs at memory bandwidth — the theoretical maximum speed at which data can be read from RAM. No clever caching. No exotic hardware. Just a smarter loop.

Why Case-Folding Is Harder Than It Sounds

Case-folding is not the same as toLowerCase() in every language. In Unicode, the rules are messy: İ caps to itself, German ß becomes SS in full case-folding, and Greek sigma has positional forms. But here’s the dirty secret of source code: the vast majority of identifiers, keywords, and strings are ASCII. Lowercase a is 0x61, uppercase A is 0x41. The only difference is one bit — the fifth bit (0x20). That simple fact makes ASCII case-folding an ideal candidate for bit-twiddling.

The naive approach is a loop:

for byte in input {
    if byte >= b'A' && byte <= b'Z' {
        byte += 0x20;
    }
}

This works, but it stops early when the string ends. It also branches — and branching is expensive. Each conditional 'if' is a branch that the CPU must predict. If the branch prediction is wrong, the pipeline stalls. For case-folding, uppercase letters are rare, but their positions are irregular. That makes prediction difficult.

The ‘Stop Early’ Trap

Why would anyone stop early? Because the most common implementation of a string comparison compares byte by byte until a mismatch is found. The first mismatch is a fast 'no'. However, the GitHub article explains that this 'don’t stop early' instinct — trying to shave off a tiny portion of work — creates a performance cliff. When a function call is invoked millions of times per second, the branch predictor becomes the bottleneck.

The deeper point is that CPUs love predictability. A branch that is always taken, or never taken, costs almost nothing. A branch that jumps in a random pattern costs dozens of cycles. When your input is a codebase with mixed naming conventions — snake_case, camelCase, PascalCase — uppercase letters appear in unpredictable positions. The CPU mispredicts, and the whole pipeline clears.

The Memory-Speed Strategy: Don’t Stop Early

The solution proposed in the article is counterintuitive: process the entire input, even if you know the result is going to be negative. Instead of stopping at a mismatched byte, transform every byte unconditionally.

The implementation is a classic example of SWAR — SIMD Within a Register. Modern 64-bit registers can hold 8 bytes at once. By loading 8 bytes, applying a bitmask, and adding a small constant, the CPU can case-fold 8 characters in the same time as 1. No branches. No early exits. The code just marches through memory like a memcpy.

Here’s the rough idea (not the exact GitHub code, but the same principle):

• Load 8 bytes into a 64-bit word.
• Compute a mask that identifies bytes in the range A–Z.
• Add 0x20 to only those bytes.
• Store the 8 folded bytes back.

Instead of 'stop and check', the routine simply processes a chunk. The last few remaining bytes are handled with a fallback, but the main loop is flat and branchless. The result: deterministic execution, zero branch mispredictions, and memory-level throughput.

Naive vs Optimized: A Performance Look

The table shows the core tradeoff. Early-exit logic might save work on average, but that work is cheap. The real cost is unpredictable control flow. By flattening the control flow, the optimized version reaches closer to the memory bandwidth limit.

How the GitHub Team Put It Into Practice

According to the article, the team integrated this case-folding technique into a source search code path. The material describes how they iterated from a simple scalar loop to a branchless block-based implementation. The developers didn’t stop at the first working version; they profiled and discovered that despite the simplicity of the function, it was taking meaningful per-call overhead.

One notable design choice: the team deliberately avoided early termination when scanning for candidate strings. Instead, they let the fold operation run over the full chunk, then compare folded data with another folded chunk. This makes the whole path linear and cache-friendly.

The article is also a lesson in benchmarking. The authors note that raw 'average time' is misleading; you have to measure tail latency, branch misprediction rate, and throughput at high call counts.

What This Means for Real-World Software

This isn’t just a niche compiler trick. Any tool that does case-insensitive matching — code search engines, linters, static analyzers, text editors, build systems — can benefit from the same technique. The broader principle is: measure your branches before you optimize your loops.

For developers, the takeaway is twofold. First, when you’re about to micro-optimize a string function, ask whether the CPU will spend more time deciding what to do than actually doing it. Second, 'stopping early' is often a premature exit from an optimization mindset. As the article suggests, the most efficient algorithm is not the one that does the least work, but the one that keeps the processor’s execution pipeline full.

Memory speed is the ultimate ceiling. Once you hit it, the only remaining optimization is to avoid touching memory at all. The GitHub team didn’t need to do that — they simply stopped stopping.

Conclusion

The phrase 'don’t stop early' has a double meaning. On the surface, it’s about a loop that doesn’t bail out early. But it’s also a reminder not to settle for the first obvious solution. The case-folding technique described in the source article is both elegant and practical — and it shows how a deep understanding of CPU pipelines can still yield massive wins.

Read the full engineering deep dive here: Don’t stop early: Case-folding source code at memory speed