GitHub managed to run case folding at more than 45 gigabytes per second on a single core by redesigning the software loop so that it does not stop at the first non-ASCII byte, but scans the entire buffer without data-dependent control-flow branches. The company uses this operation in the Blackbird code search engine, which indexes more than 180 million repositories and over 480 terabytes of source code.
Alexander Neubeck and Greg Orzell presented the design’s details in a post published on the GitHub Blog on July 31, 2026. The post also announced that the result was available in an open-source Rust library called casefold.
Case Folding Is Not Simply Converting to Lowercase
Search engines and text-matching tools need a canonical representation that makes strings differing only in letter case equal during comparison. This appears in search, case-insensitive regular expressions, usernames, and hostnames.
However, converting text to lowercase does not serve the same purpose. Lowercasing may depend on language and context, such as the different forms of the Greek sigma character at the end of a word and within it, or the differing rules for the letter I in Turkish. Case folding, by contrast, is designed for comparison and is therefore independent of language and context. The result also differs in cases such as the German letter ß, the Turkish letter İ, and the Greek final sigma.
The library performs simple one-to-one folding according to the C and S statuses in the CaseFolding.txt file belonging to the Unicode Character Database. It does not perform multicharacter folding operations, such as converting ß to ss, nor Turkish-specific folding operations.
Removing the Optimization That Was Slowing the Loop
Because source code consists mostly of ASCII characters, the fastest path focuses on converting uppercase Latin letters from A to Z to lowercase letters. The obvious design stopped immediately upon finding a non-ASCII byte, then sent the remainder of the text to the Unicode path. But tests on an Apple M4 processor showed that this approach achieved only about 3 gigabytes per second.
The main reason was the control-flow branches inside the loop. Instead of testing every byte and stopping early, the algorithm collects the top bit of all bytes into a single variable, then tests the result after the scan is complete. The test for whether a byte falls within the uppercase-letter range is performed arithmetically by subtracting the letter A with wraparound and comparing the result with 26. An arithmetic mask is then used to set the fifth bit in the byte, converting the uppercase letter to lowercase without a branch or conditional write.
This structure allows the LLVM compiler to generate vector instructions that process 16 bytes at a time using NEON on the Apple M4. The result exceeds 45 gigabytes per second, approaching the memory-bandwidth limit. GitHub’s measurements indicate that removing the early exit was the factor that enabled vectorization; retaining the data-dependent exit prevents vector instructions from being generated even when the rest of the loop becomes branchless.
Why Is a Fused Scan Not Always Faster?
GitHub tested a compromise based on scanning ASCII in blocks and then converting the ASCII prefix. This approach reads the data twice, but achieved about 23 gigabytes per second—far faster than the naive loop—while retaining the ability to stop at the first non-ASCII block.
By contrast, combining scanning and conversion in a single loop operating on 16-byte blocks was slower, reaching about 8.7 gigabytes per second versus 23 gigabytes per second for the two-pass solution. According to the post, the early-exit branch after each block prevents the compiler from unrolling the loop or hiding the latency between reading, testing, converting, and writing. Thus, two clean, vectorizable loops outperformed a single loop that touched the data fewer times but contained a content-dependent branch.
Reducing Memory Allocations
The simple_fold function takes ownership of a String, allowing it to modify its buffer and return it directly. If the text is entirely ASCII, the same memory is returned after converting the characters in place, without a second buffer or additional copying.
When non-ASCII characters are present, the algorithm does not create a new buffer until it reaches a character whose length or content changes. The post explains that most folding operations preserve or reduce UTF-8 length, but the characters U+023A and U+023E can each increase from two bytes to three. For this reason, the algorithm reserves, in one operation, a maximum capacity approximately 1.5 times the input length, instead of expanding the buffer gradually and copying the data again.
It also moves groups of unchanged bytes using copy_nonoverlapping instead of copying them one byte at a time. Some non-Latin text, such as CJK, Hangul, Kana, Arabic, Hebrew, and symbols, remains in its original allocation when it contains no characters requiring folding.
Processing Unicode in Byte Space
Unicode 16.0 contains 1484 simple folding operations, but GitHub compressed its table to 1776 bytes by exploiting the clustering of foldable characters in pages of 64 code points. To test whether a character needs folding, the algorithm uses a bit map; if the corresponding bit is not enabled, the character is rejected immediately without decoding UTF-8 or searching a hash table.
Within pages containing folding operations, the algorithm stores contiguous ranges rather than a separate record for each code point. The ranges are described by a start, an end, a step, and a delta, reducing approximately 1484 operations to 238 ranges distributed across 59 pages. It also uses a parallel comparison of eight keys at a time to identify the appropriate range.
After finding the range, the folded characters are calculated by adding UTF-8 bytes at the byte level with a range-specific constant, instead of decoding the character into a code point and then re-encoding it. This makes it possible to handle length changes, such as converting U+212A, the kelvin sign, from three bytes to the one-byte letter k, or converting U+023A into a character that is three bytes long.
This approach assumes that the input is valid and compact UTF-8, an assumption guaranteed by Rust’s String and str types. Raw data from other sources must be validated or normalized before these calculations are used.
Results and Measurement Limitations
For the common ASCII case, the library exceeds 45 gigabytes per second, making it more than 50% faster than the not-entirely-equivalent str::to_lowercase function, according to the measurements reported in the post. In the worst-case inputs, where most characters require folding, the approaches based on byte-space arithmetic were approximately twice as fast as the optimized UTF-8 decode-and-re-encode path.
GitHub emphasizes that the figures and comparison percentages are indicative rather than literally transferable between processors, because they depend on automatic vectorization, SWAR, and little-endian byte arithmetic, as well as memory bandwidth and processor architecture. The post summarizes the idea in two principles: scan the entire common path without branches, and implement the rare Unicode-specific path in byte space instead of decoding and re-encoding characters.