I shipped two hot loops in the last eighteen months that ran slower in production than they did in my unit tests. Both times, the optimization I was proud of turned out to be the problem. Both times, swapping the clever version for a dumb sweep was the fix. That is partly why the GitHub search team’s recent writeup on case folding for their Blackbird index hit me like a therapy session.
Their arc is the same arc I keep reliving. They open sourced a Rust crate to fold Unicode case across a corpus measured in hundreds of terabytes. The first cut included a tidy early-exit branch that bailed the moment the loop met a non-ASCII byte. Synthetic benchmarks called it fast. Real production traces called it slow. They ripped out the branch. The whole pipeline ran faster. That is the whole postmortem, compressed.
What I want to do here is pull apart the parts that travel beyond Rust, the parts where I would have made different calls, and the discipline that keeps a library from turning into a kitchen sink. The crate is useful. The lessons are more useful.
Why comparing strings is harder than it looks
When most code needs to decide whether two strings are equivalent, the first move is to call str::to_lowercase. That call looks innocent. It is also almost always the wrong primitive for the job, because lowercasing is meant for display, not for comparison.
Lowercasing is locale-aware and context-sensitive. The Greek final sigma becomes ς at the end of a word and σ everywhere else. Turkish dotted I follows rules that differ from English I. Lowercase what you intend to print, not what you intend to compare. The bug is quiet, the bug is widespread, and the bug ships to production every week in some new application.
Folding is the operation built for comparison. It is context-free and locale-independent. The goal is to make straße and STRASSE agree, regardless of who typed the query or which locale they typed it in. If your search engine uses lowercasing for comparison, you have a quiet bug affecting every non-English user, and you will probably never hear about it because they will just stop using your product.
The Unicode standard publishes a table called CaseFolding.txt that defines the canonical folds. Most search engines follow the table. Most applications reach for lowercasing and ship the bug. The GitHub team picked folding for Blackbird and wrote up the choice in their README. Most libraries skip the documentation, which is exactly why the bug keeps shipping.
The benchmark that lied
Here is the part of the postmortem that I found uncomfortable, because I have made the same mistake. The first version of the case folder had a branch that stopped scanning the moment it saw a non-ASCII byte, then handed off to a slower universal path. The branch felt cheap. The dispatch felt unavoidable. The benchmark on a synthetic ASCII string said the early-exit version was faster, which is exactly what the benchmark would say.
When the team ran the same code on real source code from GitHub, the picture flipped. The branchless sweep that walked every byte won. The reasons, in plain language:
- Real source code carries UTF-8 more often than you would guess. Comments contain non-ASCII quotes. String literals contain emoji. Identifiers in C and Rust code contain non-ASCII letters surprisingly often. The branch that bails on non-ASCII fires less often than your test fixture suggested.
- The dispatch into the slower universal path costs more than the cycles you saved by skipping the ASCII bytes. Function call. Switch on byte length. Return into a different loop. That overhead is not free, and it is not rare.
- Modern CPUs are tuned for predictable inner loops. A tight
forover the byte length with no branches and no calls pipelines almost perfectly. The limit becomes how fast you can move bytes in and out of cache, not how many instructions you execute. For a code-search workload, that limit is the right one. - Synthetic benchmarks tend to lie, in either direction. A clean string of pure ASCII in a unit test fires the early-exit branch every iteration, which can make the branched version look faster than it actually is on messier data. Real production text is rarely that clean.
Branch predictors are good at their job. They are not magic. When the dominant case is “the early exit never fires,” the check costs you without buying you anything. A loop that handles every byte the same way wins on real data.
The trap most engineers fall into, and how to climb out
The pattern the GitHub team fell into is one of the most common in systems code. You write a loop that needs to handle two kinds of input: the cheap case and the expensive case. You add a check at the top of the loop. If the input is the cheap case, you handle it directly. If the input is the expensive case, you dispatch to a slower path. This is the kind of code you write when you have read three blog posts about UTF-8 and you want to feel smart.
You wonder why the code is slow, and you do not look at the branch because the benchmark said it was fast.
Climbing out requires a kind of discomfort. You delete the check. You write a loop that handles every byte the same way. The slow path still exists, but it lives somewhere else, called only when the loop genuinely needs it. The hot path becomes predictable. The CPU pipelines it. Moving bytes in and out of cache becomes the limit. The whole thing runs faster.
That is the lesson, and it is one I keep relearning. Clever code is not free. Clever code that is not measured on real data is a tax you pay in production forever.
What I would have done differently
I want to push back on one specific decision the team made, because I think it is a defensible call but the wrong default for most crates. The casefold crate ships only the simple one-to-one folds. It skips the full fold where ß becomes ss. It skips Turkic locale folds. The team’s argument, which is correct, is that ripgrep and most regex engines make the same restriction, and that matching what other tools do is more valuable than handling every edge case.
For a search indexer specifically, I agree. Code search almost never needs ß to match ss, and an indexer that quietly folds ß to ss will produce surprising matches for German-language code. The discipline to say no to features you do not need is exactly what keeps the crate small and fast. Most open source crates fail this test by version 1.5.
For a general-purpose string-comparison library, I would have shipped the full folds as the default, with a flag to opt out. The cost is a slightly larger API surface. The benefit is that someone reaching for casefold to compare user-typed text gets the right answer by default, not after they read the README and noticed the gotcha. The crate is small enough that the extra case work would not have hurt performance meaningfully.
That is not a criticism of the GitHub team. They were optimizing for a specific workload and they optimized for it honestly. The critique is for anyone thinking about copying their choices into a different context. Defaults are sticky, and a crate that says no to a feature is a crate that someone else has to add back later.
How this changes what you should write in your own code
If you take one thing away, let it be this. Profile your hot path on real data, not on the synthetic string you used to convince yourself the optimization was clever. The “stop at first non-ASCII” pattern shows up everywhere. It shows up in UTF-8 validators, in JSON parsers, in CSV readers and HTTP header parsers and template engines. It is almost always wrong on real text, because real text is not clean.
A loop that walks every byte the same way will usually beat the early exit, and the simpler code is easier to maintain. I have watched two engineers ship the early-exit pattern to production code in the last year. Both benchmarks said it was faster. Both production traces said otherwise. They reverted both changes within a week. The lesson is not new. The discipline to act on the lesson is rare.
If you maintain a Rust crate that needs to fold Unicode case for search or comparison, the casefold crate is worth a look. The source is small and it is a useful example of code that respects memory bandwidth instead of fighting it.
Trade-offs
This approach is not free. The branchless version reads like bitmask tricks to anyone who has never seen one, which is most code reviewers. The trade is explicit: hot-path speed in exchange for a slightly higher reading barrier for new contributors. For a foundational crate that runs on every search request, that trade is obviously worth it. For a one-shot script that runs once a week, the early-exit version is probably fine and easier to maintain.
Memory bandwidth is the new bottleneck for almost every hot loop in any language. If you find yourself optimizing a tight loop and the profiler is not telling you about cache misses, you are probably looking at the wrong loop. The right level to look at is L2 and L3 cache hit rate, not the instruction count. The GitHub team got that right. Most blog posts about hot-path optimization get it wrong.
In our own code, we have shipped two early-exit patches in the last year that we later deleted for the same reason the GitHub team deleted theirs. Both cases were JSON parsers. Both cases looked faster on synthetic input. Both cases were slower on real data. We now have a standing rule: no early-exit branches in hot loops without a benchmark that uses production data. Your rule might be different, but the principle is the same.
Your next step, if you want to copy this
If you maintain a hot loop in any language, take ten minutes this week and run it on production data with a profiler attached. Look for branches that fire less often than the comment says they will. Look for early-exit patterns that exist because someone was clever in 2018 and no one has revisited them since. Delete one. Ship the simpler version. See if anything breaks. If nothing breaks, you just got a free speedup.
Past me would have heard that the most expensive line of code I ever wrote was a branch I was proud of. The deletion cost nothing. The branch cost months of latency I never noticed. The lesson is not “never write clever code.” The lesson is “write clever code only after you have measured it on real data, and never trust a benchmark that uses only the inputs you happened to think of.”
Original Source: Case-folding source code at memory speed