Don't Exit Early: Case Folding Source Code at Memory Speed

GitHub's code search engine Blackbird handles more than 180 million repositories and over 480TB of source code. Since every byte is case-folded before ngram extraction and indexing, and the same operation is repeated while finding search results, the speed of this basic operation matters.

Case folding is different from lowercasing for display. It is a normalization method for reliably comparing strings without depending on locale or context, and is defined in Unicode's CaseFolding.txt. Characters where the two operations produce different results—such as ß, Turkish İ, and the Greek final sigma—mean that simply using lowercasing can cause incorrect matches.

The public Rust crate casefold implements only the simple 1:1 folding corresponding to the C and S statuses in CaseFolding.txt. As a result, it does not support multi-character conversions like ß → ss or Turkic locale-specific folding, choosing consistency with tools like ripgrep instead.

Leveraging the fact that most source code is ASCII, the key optimization came—somewhat surprisingly—from eliminating early exit. The existing approach, which stopped immediately upon encountering a non-ASCII byte, achieved only about 3GiB/s on an Apple M4, more than 15 times slower than optimal due to branch cost.

The improved loop eliminates data-dependent branching as follows:

• Iterate through all bytes to the end and check for non-ASCII only once by OR-ing into high_bit_acc.
• Replace the A..=Z check with the arithmetic operation wrapping_sub(b'A') < 26.
• Convert the uppercase check into a mask, then set bit 5 to convert to lowercase without conditional writes.

This branchless loop folds ASCII input in place without a separate buffer, and once the full traversal is complete, it returns the result immediately if no non-ASCII bytes were found. Only the rare non-ASCII input is passed on to the subsequent Unicode path, keeping ASCII processing performance close to memory bandwidth levels.