GitHub ускорил case folding для поиска по коду до 45+ GiB/s на ядро

Инженеры GitHub Александр Нойбек и Грег Орзелл опубликовали техническую статью, в которой рассказали, как ускорили операцию case folding — приведение текста к единому регистру для сравнения — до скорости более 45 GiB/s на одном ядре. Оптимизация применяется в поисковом движке Blackbird, который индексирует более 180 миллионов репозиториев и 480 ТБ исходного кода. Результат опубликован в виде Rust-крейта casefold.

Зачем нужен case folding

Case folding — это операция приведения текста к канонической форме, которая стирает различия в регистре. Она используется в поисковых системах, регулярных выражениях с флагом (?i), а также для регистронезависимых имён пользователей и хостов. В отличие от lowercasing, case folding не зависит от локали и контекста: например, греческая конечная сигма в нижнем регистре пишется как ς в конце слова и σ в остальных случаях, а турецкая I преобразуется иначе, чем английская. Case folding же всегда даёт одинаковый результат.

Ключевая идея: не останавливаться рано

Основной выигрыш в скорости для ASCII-текста дало удаление раннего выхода из цикла. Наивная реализация проверяет каждый байт и останавливается при первом не-ASCII символе, передавая управление Unicode-пути. Однако такая реализация работает со скоростью около 3 GiB/s на Apple M4, что более чем в 15 раз медленнее оптимальной.

Инженеры убрали все ветвления в цикле: вместо проверки каждого байта на не-ASCII они накапливают результат в аккумуляторе и проверяют его после цикла. Проверка диапазона A..=Z заменена арифметической операцией b.wrapping_sub(b'A') < 26, а условная запись — безусловной операцией *b |= u8::from(is_upper)