GitHub удалось выполнять свёртку регистра, или Case Folding, со скоростью более 45 гигабайт в секунду на одном ядре, переработав программный цикл так, чтобы он не останавливался при первом байте, отличном от ASCII, а просматривал весь буфер без ветвлений управления, зависящих от данных. Компания использует этот процесс в поисковой системе исходного кода Blackbird, которая индексирует более 180 миллионов репозиториев и свыше 480 терабайт исходного кода.
Alexander Neubeck и Greg Orzell представили подробности этой конструкции в записи, опубликованной в блоге GitHub 31 июля 2026 года. В записи также сообщалось о выпуске результата в виде библиотеки Rust с открытым исходным кодом под названием casefold.
Свёртка регистра — это не просто преобразование в нижний регистр
Поисковым системам и инструментам сопоставления текста требуется стандартное представление, при котором строки, различающиеся регистром, считаются равными при сравнении. Это используется в поиске, регистронезависимых регулярных выражениях, именах пользователей и именах хостов.
Однако преобразование текста в нижний регистр не даёт того же результата. Такое преобразование может зависеть от языка и контекста, например от различий в начертании греческой сигмы в конце слова и внутри него или от особенностей буквы I в турецком языке. Свёртка регистра предназначена для сравнения и поэтому не зависит от языка и контекста. Результат также различается в таких случаях, как немецкая буква ß, турецкая буква İ и конечная греческая сигма.
Библиотека выполняет простую свёртку «один к одному» в соответствии с состояниями C и S из файла CaseFolding.txt базы данных символов Unicode. Она не выполняет многосимвольную свёртку, например преобразование ß в ss, и не выполняет специальную свёртку для турецкого языка.
Удаление оптимизации, замедлявшей цикл
Поскольку исходный код в основном состоит из символов ASCII, быстрый путь сосредоточен на преобразовании заглавных латинских букв от A до Z в строчные. Очевидная конструкция немедленно останавливалась при обнаружении байта, отличного от ASCII, а затем передавала оставшийся текст в путь Unicode. Однако тесты на процессоре Apple M4 показали, что такой подход обеспечивает скорость лишь около 3 гигабайт в секунду.
Главная причина — ветвления управления внутри цикла. Вместо проверки каждого байта и ранней остановки алгоритм собирает старшие биты всех байтов в одну переменную, а затем проверяет результат после завершения сканирования. Проверка того, находится ли байт в диапазоне заглавных букв, выполняется арифметически: из символа вычитается A с переполнением, а результат сравнивается с числом 26. Затем арифметическая маска используется для установки пятого бита байта, что преобразует заглавную букву в строчную без ветвления или условной записи.
Такая структура позволяет компилятору LLVM создавать векторные инструкции, обрабатывающие по 16 байт за раз с использованием NEON на Apple M4. Результат превышает 45 гигабайт в секунду, то есть приближается к пределу пропускной способности памяти. Измерения GitHub показывают, что удаление раннего выхода стало фактором, позволившим применить векторизацию: сохранение выхода, зависящего от данных, препятствует созданию векторных инструкций, даже если остальная часть цикла не содержит ветвлений.
Почему объединённое сканирование не всегда быстрее?
GitHub протестировала компромиссный вариант, основанный на проверке ASCII блоками с последующим преобразованием ASCII-префикса. Этот подход читает данные дважды, но достиг скорости около 23 гигабайт в секунду — намного быстрее наивного цикла — сохраняя возможность остановки на первом блоке, отличном от ASCII.
Объединение проверки и преобразования в одном цикле, работающем с блоками по 16 байт, оказалось медленнее: около 8,7 гигабайта в секунду против 23 гигабайт в секунду у двухпроходного решения. Согласно записи, ветвление для раннего выхода после каждого блока не позволяет компилятору развернуть цикл или скрыть задержки между чтением, проверкой, преобразованием и записью. Поэтому два чистых цикла, пригодных для векторизации, превзошли один цикл, который реже обращается к данным, но содержит ветвление, зависящее от содержимого.
Сокращение выделений памяти
Функция simple_fold принимает строку String по владению, что позволяет ей изменять собственный буфер и непосредственно возвращать его. Если текст полностью состоит из ASCII, возвращается та же память после преобразования символов на месте — без второго буфера и дополнительного копирования.
При наличии символов, отличных от ASCII, алгоритм создаёт новый буфер только при достижении символа, длина или содержимое которого изменяется. В записи поясняется, что большинство операций свёртки сохраняет длину UTF-8 или уменьшает её, однако символы U+023A и U+023E могут увеличиться с двух до трёх байт каждый. Поэтому алгоритм один раз резервирует максимальную ёмкость, приблизительно равную 1,5 длины входных данных, вместо постепенного расширения буфера и повторного копирования данных.
Кроме того, неизменившиеся группы байтов переносятся с помощью copy_nonoverlapping, а не копируются по одному байту. Некоторые нелатинские тексты, такие как CJK, Hangul, Kana, арабские и еврейские символы, а также знаки, сохраняются в исходном выделении памяти, если не содержат символов, требующих свёртки.
Обработка Unicode в байтовом пространстве
В Unicode 16.0 содержится 1484 простых операции свёртки, но GitHub сжала таблицу до 1776 байт, используя тот факт, что сворачиваемые символы сосредоточены в страницах по 64 кодовые точки. Чтобы проверить, требует ли символ свёртки, алгоритм использует битовую карту: если соответствующий бит не установлен, символ немедленно отклоняется без декодирования UTF-8 или поиска в хеш-таблице.
Внутри страниц, содержащих операции свёртки, алгоритм хранит соседние диапазоны вместо отдельной записи для каждой кодовой точки. Диапазоны описываются началом, концом, шагом и смещением, что сокращает примерно 1484 операции до 238 диапазонов, распределённых по 59 страницам. Для определения подходящего диапазона также используется параллельное сравнение восьми ключей одновременно.
После обнаружения диапазона свёрнутые символы вычисляются сложением байтов на уровне UTF-8 со специальной константой диапазона, а не декодированием символа в кодовую точку и последующим кодированием. Это позволяет обрабатывать изменения длины, например преобразовывать U+212A, символ кельвина, из трёх байт в однобайтовую букву k или преобразовывать U+023A в символ длиной три байта.
Этот подход предполагает корректный и кратчайший UTF-8 во входных данных — это гарантируется типами String и str в Rust. Сырые данные, поступающие из других источников, необходимо проверить или нормализовать перед использованием этих вычислений.
Результат и ограничения измерений
В распространённом случае ASCII скорость библиотеки превышает 45 гигабайт в секунду — согласно приведённым в записи измерениям, это более чем на 50% быстрее не полностью эквивалентной функции str::to_lowercase. В худших случаях входных данных, когда свёртки требует большинство символов, решения, основанные на вычислениях в байтовом пространстве, были примерно вдвое быстрее оптимизированного пути декодирования и повторного кодирования UTF-8.
GitHub подчёркивает, что эти числа и сравнительные показатели являются ориентировочными и не могут буквально переноситься между процессорами, поскольку зависят от автоматической векторизации, SWAR, вычислений над байтами в порядке little-endian, а также от пропускной способности памяти и архитектуры процессора. Запись сводит идею к двум принципам: полностью сканировать распространённый путь без ветвлений и выполнять редкий путь Unicode в байтовом пространстве, вместо декодирования символов и их повторного кодирования.