Case folding в GitHub ускорили до пропускной способности памяти. Разбор, как branchless-подход меняет latency и throughput в поиске кода.
Когда система индексирует сотни терабайт кода, даже базовые операции начинают влиять на общую производительность. В GitHub это проявилось в движке поиска, где каждый байт проходит через case folding перед построением n-gram индекса и при проверке совпадений. На масштабе сотен миллионов репозиториев деградация начинается не из-за алгоритмической сложности, а из-за микродеталей: ветвления (branching), кэш-поведения и невозможности векторизации. Наивный ASCII fast path с ранним выходом при первом non-ASCII байте выглядит логично, но упирается в ~3 GiB/s на одном ядре. Причина — data-dependent ветвления, которые ломают предсказание и блокируют SIMD.
Выбор оказался контринтуитивным: убрать оптимизацию раннего выхода и сделать один проход без ветвлений. Такой branchless loop не имеет data-dependent control flow и легко векторизуется компилятором. В результате LLVM генерирует SIMD-инструкции (например, NEON), и throughput достигает >45 GiB/s — фактически предел пропускной способности памяти. Trade-off здесь прямой: мы всегда проходим весь буфер, даже если встречаем non-ASCII рано. Но выигрыш от векторизации перекрывает лишнюю работу. Это типичный компромисс между «делать меньше операций» и «делать их максимально предсказуемо и параллельно».
Реализация опирается на несколько принципов. Первый — объединение детекции и преобразования. В процессе прохода аккумулируется флаг наличия non-ASCII байтов через OR по старшим битам. Это убирает необходимость второго прохода для проверки. Второй — отказ от ветвлений даже внутри преобразования: перевод A..Z в a..z делается через арифметику над байтами без if. Это позволяет компилятору полностью векторизовать цикл. Третий — управление памятью. Функция принимает String по значению и переиспользует буфер. Если строка — чистый ASCII, результат возвращается без аллокаций и копирования.
Для non-ASCII пути используется отложенная аллокация. Пока символы не требуют изменения длины, запись идёт в исходный буфер. Как только встречается случай, где fold меняет байты, выделяется новый буфер с верхней оценкой 1.5× от входа. Это связано с редкими Unicode-исключениями, где 2 байта превращаются в 3. Такой подход убирает частые realloc и копирование. Дополнительно, копирование неизменённых участков выполняется блоками (copy_nonoverlapping), а не побайтно. Даже запись результата оптимизирована: всегда пишется 4 байта, а длина корректируется отдельно, что убирает ещё одно ветвление.
Интересный альтернативный путь — двухпроходная схема: сначала определить ASCII-префикс через word-level сканирование (по 16 байт), затем применить branchless преобразование. Это даёт около 23 GiB/s. Лучше, чем наивный подход, но хуже однопроходного branchless варианта. Попытка «слить» два прохода в один с обработкой блоков и ранним выходом снова возвращает ветвления и снижает производительность до ~8.7 GiB/s. Причина та же: даже редкое ветвление внутри горячего цикла мешает развёртке (unrolling) и конвейеризации.
С точки зрения корректности важно различать lowercasing и case folding. Lowercasing зависит от локали и контекста, тогда как case folding должен быть детерминированным и симметричным. Поэтому используется Unicode CaseFolding.txt и только simple folding (1-to-1 соответствия). Это исключает multi-character преобразования и локалезависимые случаи. Такой выбор — компромисс между полнотой и предсказуемостью. Он совпадает с практикой многих инструментов, что снижает риск расхождений в поиске.
Результат — не изменение алгоритма, а изменение формы исполнения. Убрали ветвления, упростили цикл, дали компилятору возможность векторизации и получили рост throughput на порядок. Метрики показывают достижение скорости, близкой к памяти, но точные показатели зависят от архитектуры CPU и не универсальны. Тем не менее, причинно-следственная связь ясна: в hot loop ветвления дороже лишних операций.
Этот кейс хорошо иллюстрирует общий индустриальный паттерн. В highload системах оптимизация часто сводится к снижению вариативности исполнения, а не к уменьшению количества шагов. Предсказуемый, линейный код выигрывает у «умного», но ветвящегося. Особенно там, где важны latency и стабильный throughput.