Инженеры GitHub рассказали, как им удалось ускорить операцию case folding для поискового индекса кода до более чем 45 ГиБ/с на одно ядро. Речь идёт о преобразовании текста к канонической форме без учёта регистра, которое используют поисковые системы, регулярные выражения и системы с нечувствительными к регистру именами пользователей и хостов.
GitHub использует собственный поисковый движок Blackbird, который индексирует более 180 млн репозиториев (свыше 480 ТБ исходного кода). Каждый байт перед индексированием проходит через case folding, а при поиске операция повторяется для каждого кандидата в результаты. На таком объёме даже базовые операции становятся критичными по производительности.
Компания открыла результаты в виде Rust-библиотеки casefold. Её задача — выполнять простое (1-к-1) Unicode-case folding, опираясь на таблицу CaseFolding.txt из базы Unicode, без сложных многосимвольных и локалезависимых преобразований (ß → ss, турецкий I и т.п.), что совпадает с подходом распространённых инструментов вроде ripgrep.
Авторы подчёркивают различие между нижним регистром и case folding. Преобразование в нижний регистр служит для отображения и зависит от языка и контекста, а folding используется для сравнения строк и должен оставаться контекстно и локалезависимо нейтральным. Использование to_lowercase вместо folding даёт некорректные совпадения на реальных символах вроде ß, İ и финальной сигмы.
Основной трафик GitHub — это исходный код, где абсолютное большинство символов — ASCII. Поэтому ключевая цель — сделать ASCII-путь максимально быстрым и не позволить редким не-ASCII-символам замедлить общий проход.
Первая идея, от которой инженерам пришлось отказаться, выглядела естественной: останавливать ASCII-цикл при первом не-ASCII-байте и передавать управление полному Unicode-процессу. На Apple M4 такой код показывал около 3 ГиБ/с, что оказалось более чем в 15 раз медленнее теоретического предела из-за ветвлений внутри цикла и раннего выхода.
Решением стало написание цикла без ветвлений по данным и без раннего выхода: буфер проходится целиком, каждый байт проверяется и, при необходимости, переводится в нижний регистр, а параллельно накапливается флаг наличия не-ASCII. Такой цикл легко векторизуется LLVM, генерируя NEON-инструкции по 16 байт за раз и достигая скорости свыше 45 ГиБ/с — фактически ограниченной только пропускной способностью памяти.
Авторы сравнили разные подходы на чистом ASCII (буфер 5,7 КБ, Apple M4):
- цикл с проверкой каждого байта и выходом при первом не-ASCII — около 2,6–3 ГиБ/с;
- двухпроходный вариант стандартных библиотек: сначала поиск ASCII-префикса по словам с маской 0x8080_8080_8080_8080, затем векторизованный проход по этому префиксу — примерно 23 ГиБ/с за счёт повторного чтения данных;
- единый проход с блочным ранним выходом (проверка 16-байтных блоков и немедленное преобразование) — около 8,7 ГиБ/с из‑за ветвления каждые 16 байт;
- полностью безветвевой одинарный проход — более 45 ГиБ/с.
Из этих измерений инженеры делают вывод: ветвления в горячем цикле — главный противник производительности. Даже если алгоритм формально читает данные в два раза чаще, но делает это в двух чистых безветвевых прохода, он может работать заметно быстрее, чем одно ветвистое чтение.
Для не-ASCII-пути задача усложняется: case folding в Unicode иногда может удлинять строку. Почти все отображения сохраняют или уменьшают длину UTF-8-последовательности, однако есть редкие исключения, например U+023A (Ⱥ) и U+023E (Ɀ), которые занимают 2 байта и сворачиваются в 3-байтовые символы (ⱥ, ɀ). Это вынуждает использовать второй буфер, поскольку результат может не поместиться в исходный.
Функция simple_fold принимает строку по значению, с владением исходным буфером. Если накопитель старших битов показывает, что все байты ASCII, то строка уже преобразована на месте и возвращается без дополнительного выделения и копирования. При обнаружении не-ASCII-символов код через memchr находит их первое появление и начинает обработку хвоста, не выделяя дополнительный буфер, пока не встретится символ, который действительно меняет байтовое представление при folding.
Второй буфер выделяется один раз под худший случай — до 1,5× длины входа, исходя из оценки, что каждые 2 входных байта могут превратиться максимум в 3 выходных. Это позволяет избежать поэтапного увеличения буфера, многократных realloc и копирования уже записанных данных, а также убрать проверки вместимости из горячего пути: запись идёт через сырой указатель, а длина выставляется в конце одной операцией set_len.
Перенос непреобразованных байтов (ASCII и многобайтовых символов без folding) выполняется блоками через copy_nonoverlapping, а не по одному байту. При встрече символа, который действительно сворачивается, сначала копируется «хвост» непреобразованных байтов с прошлого места folding одним блоком, затем записывается результат преобразования текущего символа.
Для ускорения таблицы соответствий инженеры воспользовались структурой самих Unicode-мэппингов. В Unicode 16.0 1484 простых case-folding соответствия образуют разреженное и структурированное множество. Наблюдения позволили ужать данные до 1776 байт и выполнять folding без декодирования полного кодпоинта.
Во‑первых, большинство символов не имеют folding. Поэтому основная операция — быстрый отрицательный ответ «этот символ не меняется». Вместо хеш-таблицы (где промах дорог: нужно хешировать, проверять корзины, проходить цепочку коллизий) GitHub использует поразрядную схему «страниц» по 64 кодпоинта. Из примерно 1960 возможных страниц folding задействует лишь 59. Один бит на страницу говорит, есть ли вообще folding на этой странице. Если бит нулевой, символ сразу копируется как есть.
Для страниц с folding применяются дополнительные таблицы: накопительная таблица подсчёта единиц (rank) определяет смещение внутри общего массива интервалов. Вместо записи каждого кодпоинта отдельно используются интервалы (runs), описываемые началом, концом, шагом (поддерживаются непрерывные и «через один») и дельтой до целевого кода. Такой подход, вдохновлённый структурой CaseRange в unicode-пакете Go, сжимает 1484 сопоставления до 238 интервалов, в среднем около четырёх на страницу.
Внутри страницы поиск по интервалам реализован без ветвлений и в широком формате. Младшие 6 битов конца интервала хранятся в массиве RUN_END_LOW, и до восьми таких значений загружаются в один u64. Далее с помощью техники SWAR (одно машинное слово, имитирующее вектор) выполняется одновременное сравнение «ключей» с текущим кодом; первая подходящая позиция находится через сканирование бита. В худшем случае одна из страниц содержит до 30 интервалов, и тогда сравнение несколько раз повторяется в небольшом цикле, но это единичный и редкий сценарий.
Ключевой приём — работа в байтовом представлении UTF-8 без декодирования кода символа. На машинах с little-endian UTF-8-последовательность символа в виде u32 отличается от свернутой последовательности на постоянную дельту, зависящую от интервала. Таблица BYTE_DELTA даёт эту дельту, и folding сводится к маскированной загрузке u32, одной операции wrapping_add и четырёхбайтовой записи. Информация о длине входной и выходной последовательности берётся из компактной константы LEN_BITS, которая кодирует длину по старшим четырём битам ведущего байта.
Такой подход корректно обрабатывает изменения длины, например U+212A (символ Кельвина, 3 байта) → «k» (1 байт) или U+023A (2 байта) → U+2C65 (3 байта), просто записывая больше или меньше байтов, чем было прочитано. Авторы отмечают, что по их данным ни ICU, ни Go, ни Rust regex, ни CPython, ни glibc не реализуют folding через арифметику в байтовом пространстве — везде сначала декодируется кодпоинт, затем результат перекодируется.
Алгоритм предполагает корректный, канонический UTF-8 без избыточных (overlong) кодировок. При другом виде входа маска длины и дельта перестанут быть корректными, поэтому для произвольных байтов вход должен быть предварительно проверен и нормализован. В контексте Rust это не проблема, поскольку типы &str и String по определению содержат валидный UTF-8.
На не-ASCII-пути дополнительно используется оптимизация: ASCII-байты в хвостовой части не вызывают обращения к таблицам страниц, а просто пропускаются одним шагом, при этом сохраняется стратегия пакетного копирования непреобразованных диапазонов. Это особенно ускоряет смешанный текст, где кодовые символы сочетаются с CJK, диакритиками и пробелами.
Итоговый объём таблиц составляет примерно 9,6 бита на каждое folding-соответствие, больше половины из которых занимает BYTE_DELTA — плата за отказ от декодирования. Остальная структура (индексы и интервалы) укладывается примерно в 4,4 бита на запись, что заметно меньше, чем у альтернатив вроде ICU или самодельной хеш-таблицы.
В ASCII-кейсе case folding в реализации GitHub достигает скорости на уровне пропускной способности памяти, более чем в 10 раз опережая другие полноценные реализации и более чем на 50% — стандартную функцию to_lowercase, которая вообще не эквивалентна folding. Для оценки верхней границы скорости на не-ASCII-тексте инженеры измерили оптимизированный цикл «декодирование+кодирование UTF-8 без folding» на базе библиотеки simdutf и получили около 2 ГБ/с. В худшем случае для входа, где складывается каждый символ, их реализация folding показывает скорость лишь примерно в два раза ниже, при этом заметно опережая наивную хеш-таблицу на всех типах нагрузки.
Авторы подчёркивают два принципа, которые принесли основной выигрыш: отказ от раннего выхода и ветвлений в горячем цикле при работе с ASCII, а также выполнение folding как арифметики по байтам UTF-8 вместо декодирования кода символа. Это позволило вынести редкие случаи в отдельный лёгкий путь и держать таблицу соответствий достаточно компактной (1776 байт), чтобы она постоянно находилась в кэше процессора.
Полное описание алгоритма, включая подробное объяснение структуры таблиц и дополнительные бенчмарки, доступно в разделе про производительность в README библиотеки casefold, где также опубликованы сгенерированные таблицы и заметки по дизайну.
