Suppose a person searches for café and your corpus accommodates CAFÉ, or they sort straße and also you’ve saved STRASSE. To make these rely as matches, you want a canonical kind that erases case distinctions, in order that two strings which differ solely in case evaluate equal. That kind is case folding, and it reveals up wherever textual content is matched quite than displayed: engines like google, regex (?i) flags, case-insensitive usernames and hostnames.
It’s a primary operation, however at GitHub we run it so much. Blackbird, GitHub’s code search engine, indexes over 180 million repositories—greater than 480TB of supply code. Each byte is case-folded earlier than we extract ngrams and construct the index, and for each potential question end result, one other (implicit or specific) case folding operation is required to find matches. At that scale, the pace of even a primary operation begins to matter.
This put up is about how we made it quick, and it begins someplace counterintuitive: the largest win within the ASCII quick path got here from eradicating an optimization, not including one. It seems to be quicker to comb the entire buffer with no branches than to cease early on the first non-ASCII byte. We open-sourced the end result as a Rust crate referred to as casefold.
Folding shouldn’t be lowercasing
It’s tempting to achieve for str::to_lowercase, however lowercasing and folding are completely different operations with completely different targets:
Lowercasing is for show, and it’s locale- and context-sensitive: Greek closing sigma lowercases to ς on the finish of a phrase and σ elsewhere, and Turkish I lowercases in another way than English I. Case folding is for comparability, and it’s intentionally context-free and locale-independent. The purpose is a relation that stays steady and symmetric, in order that if A folds to match B, B folds to match A in any locale. The Unicode Character Database ships an specific CaseFolding.txt for precisely that.
The 2 operations diverge on actual characters—ß, İ, closing sigma—which is why lowercasing as a stand-in silently produces flawed matches. This crate implements solely the easy (1-to-1) folds—statuses C and S in CaseFolding.txt—and never the multi-character “full” folds (ß → ss) or Turkic locale folds (the dotted İ). This isn’t an uncommon selection: frequent instruments and regex engines like ripgrep make the identical restriction, and being constant throughout instruments is essential.
The counterintuitive core: Don’t cease early
We deal largely with supply code, so the textual content we fold is overwhelmingly ASCII and making it run at reminiscence pace is the only most essential factor we will do. Every little thing else simply has to maintain the uncommon non-ASCII path from spoiling it.
The fold of an ASCII letter is trivial—A..=Z map to a..=z, every little thing else is unchanged—so the ASCII go is actually simply “sweep the buffer, lowercase in place.” Ask any LLM for it and also you may get one thing like this:
for (i, b) in bytes.iter_mut().enumerate() {
if *b >= 0x80 {
break; // non-ASCII at index i: hand the remaining to the Unicode path
}
if b.is_ascii_uppercase() {
*b += 32; // ‘A’..=’Z’ → ‘a’..=’z’
}
}
It appears to be like excellent: do a budget byte work, and the moment you hit a non-ASCII byte, break and let the “actual” Unicode path take over: “solely do a budget work till you need to.” On an Apple M4 this runs at about 3 GiB/s. That sounds high-quality in isolation, however it’s greater than 15× in need of “optimum” due to the if branches.
Let’s delete each department, line by line:
if b >= 0x80 { break } → don’t cease in any respect. ORevery byte into an accumulator and check it as soon as, after the loop: high_bit_acc |= *b. Similar info (was there any non-ASCII byte?), zero branches within the physique.
The A..=Z vary check → make it arithmetic. b.wrapping_sub(b’A’) < 26 is true precisely for A..=Z (some other byte wraps to ≥ 26), yielding a 0/1 masks with no department.
The conditional write → fold the masks into the shop.| (is_upper << 5)units bit 5—turning an upper-case letter lower-case and being a no-op on every little thing else—the byte is all the time written, by no means branched on.
What’s left has no department in its physique and no early exit:
for b in &mut bytes = u8::from(is_upper) << 5; // set bit 5 → lowercase, else no-op
if high_bit_acc & 0x80 == 0 {
return bytes; // pure ASCII: already folded in place, no second buffer
}
A loop with no data-dependent management movement is trivially vectorizable: LLVM emits 16-byte-at-a-time NEON and the entire thing runs at > 45 GiB/s—basically reminiscence bandwidth. And we come out of the go already realizing, from high_bit_acc, whether or not there’s any non-ASCII work left to do.
How a lot did every step matter? Measuring the cumulative ladder on pure ASCII (Apple M4, 5.7 KB buffer):
The early-exit is what gates vectorization: preserve the break however make the physique completely branch-free and you continue to get zero vector directions (~2.6 GiB/s); a data-dependent loop exit is sufficient by itself to maintain the loop scalar. Solely as soon as the break is gone can the compiler vectorize. The ultimate step—making the upper-case fold branchless—then turns {a partially} vectorized loop (which nonetheless compiles the conditional retailer to a compare-blend-masked-store, ~7.6 GiB/s) into the straight-line arithmetic that hits reminiscence bandwidth.
There’s additionally a center floor, and it’s what normal libraries use. As a substitute of testing one byte at a time, [u8]::is_ascii scans a machine phrase at a time—on a 64-bit goal it exams 16 bytes per iteration by OR-ing two u64 lanes and checking all their excessive bits with a single & 0x8080_8080_8080_8080 masks. You’ll be able to construct the ASCII quick path on high of that: chunk-scan to search out the ASCII prefix, then run the branchless (vectorizable) convert over it. That retains the early-exit capability—it nonetheless bails on the primary non-ASCII block—whereas letting each halves go quick. The catch is that it reads the info twice (as soon as to scan, as soon as to transform), touchdown at about 23 GiB/s—roughly half of the single-pass branchless sweep, and ~7× the naive break loop. A strong, general-purpose default; simply not absolutely the ceiling if you management the entire loop and might fold detection and conversion into one branch-free go.
Wouldn’t fusing the 2 passes be quicker? It’s the plain subsequent thought: preserve the chunked early-exit however convert every 16-byte block proper after you’ve confirmed it’s ASCII, studying the info solely as soon as. Measured, it’s ~2.6× slower—8.7 GiB/s versus the two-pass 23. The internal block convert nonetheless vectorizes to a single 16-byte op, however now there’s a data-dependent early-exit department each 16 bytes, and that department pins the loop to 1 block at a time: the compiler doesn’t unroll or software-pipeline throughout blocks, and every iteration pays the complete load→check→department→convert→retailer latency with nothing to cover it behind. Cut up into two passes, each is clear: the scan is a branch-light, store-free phrase scan that races via reminiscence, and the convert is the fully-vectorized branch-free sweep at >45 GiB/s. Two quick, branch-free passes beat one branchy fused go—regardless that the fused model touches the info half as many occasions. It’s the identical lesson yet another time: within the sizzling loop, the department is the enemy.
Avoiding the heap
Forty-5 GiB/s additionally means doing zero pointless allocation. simple_fold takes the enter String by worth, proudly owning the heap buffer it could possibly mutate and return it. If the OR-accumulator’s excessive bit was clear, the enter was pure ASCII already folded in place. We hand the identical allocation straight again, no second buffer and no copy. In any other case, we memchrto the primary non-ASCII byte and scan the tail from there, leaving the output buffer unallocated (a null write cursor) till we hit a personality that folds to completely different bytes. Textual content whose multibyte content material by no means folds—CJK, Hangul, Kana, Arabic, Hebrew, symbols—additionally returns the unique allocation untouched, by no means copying a byte.
Why a second buffer quite than rewriting in place just like the ASCII go? As a result of folding could make the string longer: virtually each fold preserves the UTF-8 size or shrinks it, however two outliers develop—U+023A (Ⱥ) and U+023E (Ɀ) are 2 bytes every but fold to 3-byte characters (ⱥ, ɀ). As soon as one seems, the output now not matches within the enter’s bytes, and we want someplace new to jot down.
We allocate that buffer as soon as, sized for the worst case, quite than rising it as extra folds seem. Incremental reserve calls would imply re-checking capability, sometimes reallocating, copying every little thing written to date, and juggling additional size/capability bookkeeping; a single up-front allocation lets a uncooked write cursor run straight to the top with none of that. And because the cursor is nulluntil that first rising/altering fold, it doubles because the “have we allotted the additional buffer but?” flag.
Sizing it wants a sure on development, and those self same two outliers give it: each 2 enter bytes yield at most 3 output bytes, capping the output at 1.5× the enter—precisely the capability we reserve:
After that the loop writes via a uncooked pointer with no capability checks and calls set_len as soon as on the finish. Two extra particulars preserve it branch-light. The run of unchanged bytes between two folds is moved with a single copy_nonoverlapping quite than byte by byte. And every fold unconditionally writes all 4 bytes of a little-endian phrase earlier than bumping the cursor by solely the folded size (1–4)—dropping a department on the output size from the recent path, with the + 4 within the reservation because the headroom that makes the ultimate character’s over-store protected.
Making Unicode low-cost too
When a personality does fold, we nonetheless don’t wish to fall off a cliff—decode UTF-8, hash lookup, re-encode. Unicode 16.0 has 1484 simple-fold mappings, however they’re a really sparse and really structured relation. 4 observations shrink them to 1776 bytes and let the fold run with out ever decoding a full character.
Even on the non-ASCII path, the overwhelming majority of characters don’t fold. The recent operation isn’t actually “fold this character,” it’s “does this character fold?” Nearly all the time no. The desk has to make that damaging check as low-cost as potential; the precise folding is the uncommon case on an already-rare path. That precedence is what shapes the structure under—the web page bitmap exists exactly so a non-folding character is rejected in a single bit check, straight from its main UTF-8 bytes, with out decoding or scanning something.
That is precisely why a HashMap is the flawed form for the job, not only a larger one. A hash map is optimized for the hit: it finds a gift key in roughly one probe, and solely spends additional work (extra probes, full key comparability) when load issue or collisions chunk. However our workload is dominated by misses—characters that aren’t within the desk in any respect—and a miss is a hash map’s least favourite question: it nonetheless has to hash the important thing, bounce to a bucket, and stroll the probe sequence far sufficient to show absence.
Foldable code factors cluster into 64-code-point “pages”
Foldable code factors bunch collectively. Slice the code area into 64-code-point “pages” and the ~1484 folds contact simply 59 of ~1960 potential pages. A one-bit-per-page presence bitmap solutions the damaging check by itself: a transparent bit is a definitive “no fold”—copy via, performed—which is what makes fold-free scripts low-cost. Solely on a set bit will we seek the advice of a second construction, a cumulative-popcount aspect desk that ranks the web page (what number of populated pages precede it) to search out its slice of entries, storing nothing for the ~1900 empty pages.
(0usize, lead & 0x1F, 2usize) // 2-byte: phrase 0
} else if lead < 0xF0 {
((lead & 0x0F) as usize, bytes[read + 1] & 0x3F, 3) // 3-byte: phrase = nibble
} else (bytes[read + 1] & 0x3F) as usize,
bytes[read + 2] & 0x3F,
4usize,
) // 4-byte: merge 2 bytes
;
// reject with out decoding: clear bit ⇒ no fold
if word_idx >= PAGE_BITMAP.len() || (PAGE_BITMAP[word_idx] >> bit_idx) & 1 == 0 {
learn += c_len;
proceed;
}
As a result of word_idxdepends solely on the lead byte (and, for four-byte sequences, the primary continuation byte), the bitmap load might be issued early.
Inside a web page, folds are available in runs
A set web page bit tells us one thing on this web page folds, however not which code factors or to what. The plain encoding is one entry per foldable code level—however that’s each cumbersome and sluggish to look: a web page can maintain dozens of folds, and we’d should scan all of them to search out the one matching the present code level. The construction of the info rescues us once more. Adjoining code factors overwhelmingly share the identical delta to their fold: A–Z all map +32, and Latin Prolonged is filled with alternating runs like 0x0100, 0x0102, 0x0104, … the place each second code level folds. As a substitute of per-code-point entries we retailer runs—begin, finish, stride, delta—and a 1-bit stride flag covers each the contiguous and the every-other case. This interval compression collapses the ~1484 particular person folds into simply 238 runs throughout the 59 pages (≈4 per web page), leaving the within-page search solely a handful of entries to have a look at as a substitute of dozens. This range-with-delta encoding (together with the stride trick) is borrowed from Go’s unicode package deal, whose CaseRange data retailer a Lo/Hello vary plus per-case deltas, with an UpperLower sentinel marking the alternating blocks. Runs are cut up on the web page boundaries so a run by no means straddles two pages.
A run file is 2 clear bytes
With each endpoints inside one web page they slot in 6 bits, cut up throughout two arrays: RUN_END_LOW[“i“] = finish & 0x3F (the scan key) and RUN_START_STRIDE[“i“] = (begin & 0x3F) | ((stride − 1) << 6) (learn solely on a success). As a result of every secret’s one clear byte, the within-page search can go large: quite than evaluating cp & 0x3F in opposition to the runs one by one, we load 8 end_low bytes right into a single u64 and check all of them without delay with one branchless SWAR step—(chunk | 0x80…80) − broadcast(low) & 0x80…80 units the highest bit of each lane whose secret’s ≥ cp & 0x3F. A single bit-scan of that masks (the keys are sorted, so the primary set lane is the run we wish) finds the slot. A web page holds ~4 runs on common; that one 8-wide evaluate virtually all the time resolves all the search in a single step. One unfortunate web page does maintain 30 runs, which places the evaluate inside a brief loop that strides eight keys at a time—however that loop journeys at most a handful of occasions on precisely one web page in all of Unicode, and by no means on the frequent ones. Both means: no per-run department, and no code-point reconstruction wherever.
/// or `n` if none. Scans 8 `end_low` bytes at a time through SWAR.
#[inline]
fn scan_end_low(lo: usize, n: usize, low_v: u8) -> usize {
const HIGH: u64 = 0x8080_8080_8080_8080;
const ONES: u64 = 0x0101_0101_0101_0101;
let bcast = (low_v as u64).wrapping_mul(ONES);
let mut base = 0;
whereas base < n {
// RUN_END_LOW is padded by 8 bytes so this learn is all the time in bounds.
let chunk = u64::from_le_bytes(
RUN_END_LOW[lo + base..lo + base + 8]
.try_into()
.anticipate(“8-byte slice”),
);
// `(b | 0x80) – low_v` retains its excessive bit iff `b >= low_v` (no
// cross-lane borrow). The primary set lane is the primary run `>= low_v`.
let ge = (chunk | HIGH).wrapping_sub(bcast) & HIGH;
if ge != 0 {
let j = base + (ge.trailing_zeros() / 8) as usize;
return if j < n { j } else { n };
}
base += 8;
}
n
}
= low_v` (no
// cross-lane borrow). The primary set lane is the primary run `>= low_v`.
let ge = (chunk | HIGH).wrapping_sub(bcast) & HIGH;
if ge != 0 {
let j = base + (ge.trailing_zeros() / 8) as usize;
return if j < n { j } else { n };
}
base += 8;
}
n
}” tabindex=”0″ function=”button”>
Folding is a little-endian byte addition
On a little-endian machine the folded character’s UTF-8 bytes, learn as a u32, equal the supply bytes (as a u32) plus a per-run fixed. A parallel BYTE_DELTA[i] desk then turns the entire fold right into a masked load, one wrapping_add, and a 4-byte retailer:
let folded = phrase.wrapping_add(BYTE_DELTA[i]); // the fold, as one byte add
write_u32_le(dst, folded); // retailer all 4 bytes…
dst += utf8_len(folded); // …advance by the folded size
Each lengths in that snippet—the length_mask for the supply character and the advance by the folded size for the vacation spot—come from yet another tiny trick. A UTF-8 sequence’s size is fastened by the highest 4 bits of its lead byte, letting the 16 potential lengths pack one nibble every right into a single 64-bit fixed (0x4322_1111_1111_1111); the size is then a shift and a masks, (LEN_BITS >> (4 * (lead >> 4))) & 0xF—no if chain, no desk reminiscence, nothing for the predictor to get flawed. (A rely main ones—(!lead).leading_zeros()—would additionally work, since a lead byte carries one main 1-bit per byte of the sequence.)
#[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
}
As a result of we advance by the folded size, this even handles length-changing folds—U+212A KELVIN SIGN (3 bytes) → ok (1 byte), or U+023A Ⱥ (2 bytes) → U+2C65 ⱥ (3 bytes)—by writing fewer or extra bytes than have been learn. That’s the half we imagine is genuinely new: each different folder we checked out—ICU, Go’s unicode, Rust’s regex, CPython, glibc—decodes UTF-8 to a code level, applies the fold there, and re-encodes (even SIMD folders decode first). Doing the arithmetic in byte area skips each the decode and the encode, which is precisely why this path can outrun a hash map that already has the reply tabulated—the hash map nonetheless has to decode its key and encode its end result. The byte-space arithmetic assumes the enter is well-formed, shortest-form UTF-8—each code level encoded with the minimal variety of bytes. Studying the supply bytes as a u32and including a per-run delta solely lands on the proper folded encoding when the supply is in canonical kind; an overlong encoding (a code level padded into extra bytes than mandatory, e.g. / as 0xC0 0xAF) has a special byte sample and would break thelength_mask and the delta arithmetic. This isn’t an actual restriction in Rust—&str/String are assured to carry legitimate UTF-8, which by definition rejects overlong sequences—however a caller feeding uncooked bytes from elsewhere should validate (or in any other case normalize) them first.
The ASCII shortcut within the tail loop
Another shortcut rounds out the tail loop. Keep in mind the primary go already lowercased each ASCII byte, so when the scan meets an ASCII byte within the tail it advances a single byte and strikes on—no web page probe, no desk contact in any respect. And it doesn’t copy that byte both: unmodified bytes (ASCII and non-folding multibyte alike) aren’t moved one by one. The scan simply retains strolling till it reaches a personality that really folds, then flushes the entire unchanged run between the final fold and this one with a single copy_nonoverlapping. Combined textual content—CJK with ASCII areas and punctuation, or code with the occasional accented identifier—subsequently races via the ASCII filler and solely consults the bitmap for real multibyte characters, copying in bulk quite than byte by byte.
Placing it collectively: the entire desk
That’s 9.6 bits per fold entry, over half of it the BYTE_DELTA aspect desk we commerce for the decode-free path; the index + run data alone are ~4.4 bits/entry.
Subsequent to the plain options, that 1776 bytes is an order of magnitude or extra smaller—and in contrast to most of them, it by no means decodes a personality:
The place it lands in opposition to the options
On the frequent case, ASCII, folding runs at reminiscence bandwidth (>45 GiB/s), greater than an order of magnitude forward of different actual folders and greater than 50% quicker than the (non-equivalent) str::to_lowercase operate. To get a tough “higher sure” for the non-ASCII case, we measured the optimized Utf8 decoding + encoding spherical journey with out performing any precise case folding utilizing the simdutf crate. This experiment achieves persistently about 2GB/sec and is simply about twice as quick than our resolution for the worst case all-folding enter. A naive hash map trails every little thing on all workloads.
The three columns are actual case folders that produce similar output: simple_fold (this crate), simd_normalizer (the simd-normalizer crate), and HashMap (naive CaseFolding.txt lookup). The workload rows are chosen to simulate completely different eventualities from typical to worst case:
Deal with absolutely the figures as illustrative, not moveable: the entire design leans on auto-vectorization, SWAR, and little-endian byte arithmetic, so the numbers—and even the ratios between rows—can shift considerably on a special microarchitecture (a wider or narrower vector unit, completely different reminiscence bandwidth, a big-endian goal, x86 vs ARM).
Extra particulars might be discovered within the efficiency part of the README.
Take this with you
Case folding is about as primary as textual content operations get, which is precisely why it was definitely worth the effort: we run it throughout each byte we index. The wins got here from two concepts that each minimize in opposition to intuition—sweep the entire buffer branch-free as a substitute of stopping early, and do the fold as byte-space arithmetic as a substitute of decoding to a code level. Collectively they let the frequent case run at reminiscence bandwidth and the uncommon fold run and not using a decode, in a desk sufficiently small (1776 bytes) to remain resident. The decode-free byte-space fold is the piece we imagine is genuinely new; it’s why this path can beat a hash map that already has the reply.
There’s absolutely extra to search out right here, and we’d wish to see it. The crate is casefold; the generated desk and full design notes dwell alongside the supply.
Written by
