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

GitHub刚刚开源了一个叫casefold的Rust工具库，专为代码搜索中的“大小写折叠”提速。所谓大小写折叠，就是把CAFÉ和café、STRASSE和straße这些仅因大小写或变音符号不同的文本，统一成一种便于比较的形式，这样搜索时才能准确匹配。过去很多程序用简单的转小写代替，但遇到德语ß、土耳其字母İ这类特殊字符就会出错。GitHub的团队发现了一个反直觉的窍门：与其在遇到非英文时提前停下，不如干脆不管，用无分支的方式扫完整个数据块，反而更快。这个库已经用在GitHub的代码搜索引擎里，它索引了超过1.8亿个仓库、480TB的代码，速度提升带来的收益非常可观。对普通开发者来说，这意味着以后在GitHub上搜代码时，大小写混淆、特殊字符拼写不同也能更快速、更准确地找到结果，而且这个工具是开源的，其他软件和搜索引擎也能借鉴使用，让日常的文本匹配体验更顺畅。

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. 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. 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 &sigmaf; 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. The Unicode Character Database ships an explicit CaseFolding.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. This crate implements only the simple (1-to-1) folds—statuses C and S in CaseFolding.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. The fold of an ASCII letter is trivial—A..=Z map to a..=z, everything else is unchanged—so the ASCII pass is really just “sweep the buffer, lowercase in place.” Ask any LLM for it and you might get something like this: let bytes = s.as_bytes_mut(); for (i, b) in bytes.iter_mut().enumerate() { if *b >= 0x80 { break; // non-ASCII at index i: hand the rest to the Unicode path } if b.is_ascii_uppercase() { *b += 32; // 'A'..='Z' → 'a'..='z' } } It looks ideal: do the cheap byte work, and the instant you hit a non-ASCII byte, break and let the “real” Unicode path take over: “only do the cheap work until you have to.” 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. ORevery byte into an accumulator and test it once, after the loop: high_bit_acc |= *b. Same information (was there any non-ASCII byte?), zero branches in the body. The A..=Z range test → make it arithmetic. b.wrapping_sub(b'A') < 26 is true exactly

Don&#8217;t stop early: Case-folding source code at memory speed

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