[Перевод] Ветвление оказалось дороже лишней работы: как GitHub разогнал обработку исходного кода до 45 ГиБ/с

Представим, что пользователь ищет café, а в вашем корпусе есть CAFÉ. Или вводит straße, а у вас хранится STRASSE. Чтобы считать такие строки совпадениями, нужна каноническая форма, которая устраняет различия в регистре: тогда строки, отличающиеся только регистром, будут считаться равными.

Для этого и нужна регистровая свёртка (case folding). Она используется везде, где текст нужно сопоставлять, а не отображать: в поисковых системах, флагах (?i) регулярных выражений, регистронезависимых именах пользователей и хостов.

Операция базовая, но в GitHub мы выполняем её очень часто. Blackbird, поисковый движок GitHub по коду, индексирует более 180 миллионов репозиториев — свыше 480 ТБ исходного кода. Перед извлечением n‑грамм и построением индекса регистровую свёртку проходит каждый байт.

А для каждого потенциального результата запроса нужна ещё одна, явная или неявная, операция регистровой свёртки, чтобы найти совпадения. В таких масштабах начинает иметь значение скорость даже самых простых операций.

Эта статья о том, как мы ускорили регистровую свёртку. И начинается всё с неожиданного наблюдения: самое большое ускорение на быстром пути для ASCII мы получили, не добавив оптимизацию, а убрав её. Оказалось, что быстрее пройти весь буфер циклом без ветвлений, чем досрочно завершать обработку на первом байте вне ASCII.

Получившуюся реализацию мы опубликовали в открытом доступе как Rust‑crate casefold.

Регистровая свёртка — не приведение к нижнему регистру

Первым делом хочется взять str::to_lowercase, но приведение к нижнему регистру и регистровая свёртка — разные операции с разными задачами.

Приведение к нижнему регистру предназначено для отображения текста и зависит от локали и контекста: например, заглавная греческая сигма в конце слова превращается в ς, а в остальных позициях — в σ; турецкая I тоже преобразуется не так, как английская. Регистровая свёртка нужна для сравнения и намеренно не зависит ни от контекста, ни от локали. Её цель — получить стабильное и симметричное отношение: если после свёртки A совпадает с B, то и B после свёртки должен совпадать с A в любой локали.

Именно для этого в Unicode Character Database предусмотрен отдельный файл CaseFolding.txt.

Эти две операции по‑разному обрабатывают реальные символы — ß, İ, конечную сигму, — поэтому попытка заменить регистровую свёртку простым приведением к нижнему регистру незаметно приводит к неверным совпадениям. Этот crate реализует только простую регистровую свёртку «один к одному» — статусы C и S из CaseFolding.txt — без многосимвольной полной свёртки (ß → ss) и специальных правил регистровой свёртки для тюркских языков (например, для İ с точкой).

Такой выбор вполне обычен: популярные инструменты и движки регулярных выражений вроде ripgrep придерживаются того же ограничения, а единообразное поведение разных инструментов здесь важно.

Парадоксальная идея: не останавливайтесь раньше времени

Мы работаем в основном с исходным кодом, поэтому подавляющая часть обрабатываемого текста — ASCII. Самое важное для нас — заставить этот случай работать на скорости памяти. Всё остальное должно лишь не дать редкому пути обработки Unicode испортить результат.

Регистровая свёртка ASCII‑буквы элементарна: A..=Z преобразуются в a..=z, всё остальное остаётся без изменений. Поэтому проход по ASCII фактически сводится к тому, чтобы «пройти по буферу и на месте перевести заглавные буквы в нижний регистр». Попросите любую LLM написать такой код, и она вполне может выдать что‑нибудь вроде этого:

let bytes = s.as_bytes_mut(); 
for (i, b) in bytes.iter_mut().enumerate() { 
    if *b >= 0x80 { 
        break; // non-ASCII at index i: hand the rest to the Unicode path 
    } 
    if b.is_ascii_uppercase() { 
        *b += 32; // 'A'..='Z' → 'a'..='z' 
    } 
}

На первый взгляд всё идеально: выполняем дешёвую побайтовую обработку, а как только встречаем байт вне ASCII, останавливаемся и передаём управление «настоящему» пути обработки Unicode. То есть «делаем дешёвую работу ровно до тех пор, пока без дорогой уже не обойтись». На Apple M4 такой код выдаёт около 3 ГиБ/с.

Само по себе это звучит неплохо, но до «оптимального» варианта ему не хватает больше чем 15 раз — из‑за ветвлений if.

Давайте уберём все ветвления, одно за другим:

• if b >= 0x80 { break } → вообще не останавливаемся. Каждый байт объединяем побитовым OR с аккумулятором, а проверку делаем всего один раз, после цикла: high_bit_acc |= *b. Информация та же — встретился ли хотя бы один байт вне ASCII, — а ветвлений в теле цикла нет.

• Проверку диапазона A..=Z → заменяем арифметикой. Выражение b.wrapping_sub(b'A') < 26 истинно только для A..=Z: для любого другого байта результат будет не меньше 26. Так мы получаем маску 0/1 без ветвления.

• Условную запись → включаем маску прямо в операцию записи. | (is_upper << 5) устанавливает бит 5, превращая заглавную букву в строчную, а для всех остальных байтов ничего не меняет. Запись выполняется всегда, без ветвления.

В итоге получаем цикл без ветвлений в теле и без досрочного выхода:

let mut high_bit_acc: u8 = 0;

for b in &mut bytes {
    high_bit_acc |= *b; // проверяем, встретился ли хотя бы один байт вне ASCII

    let is_upper = b.wrapping_sub(b'A') < 26; // проверка A..=Z без ветвлений

    *b |= u8::from(is_upper) << 5; // устанавливаем бит 5 → нижний регистр, иначе ничего не меняем
}

if high_bit_acc & 0x80 == 0 {
    return bytes; // только ASCII: свёртка уже выполнена на месте, второй буфер не нужен
}

Цикл без потока управления, зависящего от данных, тривиально векторизуется: LLVM генерирует NEON‑код, обрабатывающий по 16 байт за раз, и вся конструкция работает со скоростью более 45 ГиБ/с — фактически упираясь в пропускную способность памяти. А после прохода мы уже знаем по high_bit_acc, осталась ли вообще работа для пути обработки Unicode.

Насколько важен был каждый из этих шагов? Вот как менялась производительность по мере оптимизации на чистом ASCII (Apple M4, буфер 5,7 КБ):

Именно досрочный выход не даёт векторизовать цикл: можно оставить break и сделать тело полностью без ветвлений, но векторных инструкций всё равно не будет (~2,6 ГиБ/с). Одного выхода из цикла, зависящего от данных, достаточно, чтобы код остался скалярным. Только после удаления break компилятор получает возможность векторизовать цикл.

Последний шаг — регистровая свёртка заглавных букв без ветвлений — превращает частично векторизованный цикл, где условная запись всё ещё компилируется в последовательность compare‑blend‑masked‑store (~7,6 ГиБ/с), в прямолинейную арифметику, которая уже упирается в пропускную способность памяти.

Примечание

В скалярном коде отказ от ветвлений может, наоборот, ухудшить производительность. Ещё раз посмотрите на таблицу: если сделать тело цикла без ветвлений, но оставить break (2,6 ГиБ/с), результат окажется даже хуже, чем у наивного варианта с ветвлениями (3,1 ГиБ/с). Ассемблерный код хорошо показывает почему.

В варианте с ветвлениями байт записывается только тогда, когда действительно меняется: условная инструкция strb пропускается для каждой строчной буквы, цифры и пробела, то есть для подавляющего большинства реального текста, а хорошо предсказываемое ветвление, которое её охраняет, почти ничего не стоит. Вариант без ветвлений заменяет эту редко выполняемую запись безусловным strb на каждой итерации и в итоге перезаписывает все ~5700 байт вместо нескольких заглавных букв.

Получаем лишний трафик записи без какой‑либо пользы. Безусловная запись начинает выигрывать только после векторизации цикла: тогда она превращается в одну 16-байтовую векторную запись независимо от содержимого, и стоимость на каждый отдельный байт исчезает.

Вывод простой: тело без ветвлений имеет смысл прежде всего как средство добиться векторизации. Само по себе, в скалярном коде, оно вполне может оказаться дороже.

Есть и промежуточный вариант — именно его используют стандартные библиотеки. Вместо проверки по одному байту [u8]::is_ascii сканирует по машинному слову за раз: на 64-битной платформе за одну итерацию проверяются 16 байт — две 64-битные lane объединяются через OR, после чего все старшие биты проверяются одной маской & 0x8080_8080_8080_8080. На этом можно построить быстрый путь для ASCII: сначала блоками найти ASCII‑префикс, а затем прогнать по нему преобразование без ветвлений, которое уже можно векторизовать.

Так сохраняется возможность досрочного выхода — обработка по‑прежнему прекращается на первом блоке с не‑ASCII‑байтом, — но обе части работают быстро.

Минус в том, что данные приходится читать дважды: один раз при сканировании и ещё раз при преобразовании. В результате получается около 23 ГиБ/с — примерно половина скорости однопроходного цикла без ветвлений и примерно в семь раз быстрее наивного варианта с break. Для универсального решения это отличный компромисс, но не абсолютный предел производительности, если вы контролируете весь цикл и можете совместить обнаружение не‑ASCII и преобразование в одном проходе без ветвлений.

А разве объединить два прохода не будет быстрее? Это кажется очевидным следующим шагом: сохранить блочный досрочный выход, но сразу преобразовывать каждый 16-байтовый блок, как только мы убедились, что он целиком состоит из ASCII, и таким образом читать данные только один раз. На практике такой вариант оказывается примерно в 2,6 раза медленнее: 8,7 ГиБ/с против 23 ГиБ/с у двухпроходного.

Внутреннее преобразование блока по‑прежнему векторизуется в одну 16-байтовую операцию, но теперь каждые 16 байт возникает ветвление с досрочным выходом, зависящее от данных. Из‑за него цикл обрабатывает строго по одному блоку за раз: компилятор не разворачивает цикл и не применяет программную конвейеризацию между блоками, поэтому на каждой итерации приходится полностью оплачивать цепочку загрузка → проверка → ветвление → преобразование → запись, и скрыть эту задержку нечем.

Если же разделить работу на два прохода, каждый получается очень простым: первый быстро сканирует память машинными словами почти без ветвлений и вообще без записей, а второй выполняет полностью векторизованный проход без ветвлений со скоростью более 45 ГиБ/с. Два быстрых прохода без ветвлений оказываются быстрее одного объединённого прохода с ветвлениями, хотя тот обращается к данным вдвое реже. Всё тот же вывод ещё раз: в горячем цикле главный враг — ветвление.

Обходимся без лишних выделений памяти в куче

45 ГиБ/с означают ещё и отсутствие любых ненужных выделений памяти. simple_fold принимает входную строку String по значению, то есть получает во владение буфер в куче и может изменить его, а затем вернуть. Если старший бит OR‑аккумулятора не установлен, значит, вход состоял только из ASCII и регистровая свёртка уже выполнена на месте. Мы просто возвращаем тот же самый буфер — без второй аллокации и без копирования.

В противном случае с помощью memchr находим первый байт вне ASCII и продолжаем сканирование с него. При этом выходной буфер пока вообще не выделяем: указатель текущей позиции записи остаётся нулевым до тех пор, пока не встретится символ, чья свёртка меняет байтовое представление. Поэтому текст, в котором многобайтовые символы при свёртке не меняются — CJK, хангыль, кана, арабское и еврейское письмо, различные символы, — тоже возвращает исходный буфер без изменений и без копирования единого байта.

Почему здесь нужен второй буфер, а не перезапись на месте, как в случае с ASCII? Потому что регистровая свёртка может увеличить длину строки. Почти все преобразования либо сохраняют длину UTF-8, либо уменьшают её, но есть два исключения: U+023A (Ⱥ) и U+023E (Ɀ) занимают по 2 байта, а после свёртки превращаются в трёхбайтовые символы (ⱥ, ɀ).

Как только встречается один из них, результат уже не помещается в исходный набор байтов и писать его приходится в новый буфер.

Мы выделяем этот буфер один раз, сразу под худший случай, а не увеличиваем его по мере появления новых преобразований. Последовательные вызовы reserve означали бы постоянные проверки ёмкости, периодические перераспределения памяти, копирование уже записанных данных и дополнительный учёт длины и ёмкости. Если же выделить память заранее, сырой указатель записи может просто двигаться до самого конца без всех этих накладных расходов.

А поскольку до первого увеличивающего или изменяющего свёртку символа указатель остаётся нулевым, он заодно служит флагом «дополнительный буфер уже выделен или ещё нет».

Чтобы правильно выбрать размер буфера, нужна верхняя граница роста, и её дают те же два исключения: каждые 2 входных байта могут превратиться максимум в 3 выходных. Значит, итоговый размер не превысит 1,5× от входного — именно такую ёмкость мы и резервируем:

out = Vec::with_capacity(bytes.len() + bytes.len() / 2 + 4);

После этого цикл пишет через сырой указатель без проверок ёмкости, а set_len вызывается всего один раз, в самом конце. Ещё две детали помогают свести ветвления к минимуму. Диапазон неизменившихся байтов между двумя преобразованиями переносится одним вызовом copy_nonoverlapping, а не побайтово.

Кроме того, для каждого результата свёртки мы безусловно записываем все 4 байта little‑endian‑слова, а затем сдвигаем указатель только на фактическую длину результата — от 1 до 4 байт. Так из горячего пути исчезает ветвление по длине результата, а дополнительные + 4 байта при резервировании дают запас по размеру, благодаря которому запись лишних байтов за логический конец последнего значения остаётся безопасной.

Делаем Unicode тоже дешёвым

Даже когда символ нужно свернуть, мы всё равно не хотим резко проваливаться по производительности из‑за цепочки «декодировать UTF-8 → выполнить поиск в хеш‑таблице → снова закодировать». В Unicode 16.0 есть 1484 соответствия для простой регистровой свёртки, но это очень разреженная и при этом очень структурированная зависимость. Четыре наблюдения позволяют ужать таблицу до 1776 байт и выполнять свёртку, вообще не декодируя символ целиком.

Даже на пути обработки не‑ASCII подавляющее большинство символов не меняются при свёртке. Поэтому главная операция здесь на самом деле не «свернуть этот символ», а «нужно ли вообще его сворачивать?». Почти всегда ответ отрицательный.

Значит, таблица должна делать именно эту проверку как можно дешевле; сама свёртка — редкий случай внутри и без того редко используемого пути. Именно этот приоритет определяет структуру данных ниже. Битовая карта страниц нужна как раз для того, чтобы символ, не требующий свёртки, можно было отсеять одной проверкой бита прямо по начальным байтам UTF-8 — без декодирования и какого‑либо сканирования.

Именно поэтому HashMap<u32, u32> здесь не просто избыточна по размеру, а в принципе имеет неподходящую структуру. Хеш‑таблица оптимизирована под попадания: существующий ключ обычно находится примерно за одну пробу, а дополнительная работа — новые пробы и полное сравнение ключей — появляется уже при высоком коэффициенте заполнения или коллизиях. Но в нашей нагрузке преобладают промахи: символов, которых в таблице вообще нет.

А промах — самый невыгодный запрос для хеш‑таблицы. Всё равно приходится вычислять хеш, переходить к нужному бакету и проходить последовательность проб достаточно далеко, чтобы доказать отсутствие ключа.

Кодовые точки со свёрткой группируются в «страницы» по 64 точки

Кодовые точки, для которых определена регистровая свёртка, расположены группами. Если разбить всё пространство кодовых точек на «страницы» по 64 точки, то ~1484 преобразования затрагивают всего 59 из примерно 1960 возможных страниц. Битовая карта наличия с одним битом на страницу сама по себе позволяет выполнить отрицательную проверку: сброшенный бит однозначно означает «здесь свёртки нет» — просто копируем символ дальше и заканчиваем.

Именно поэтому письменности, символы которых не требуют свёртки, обходятся так дёшево.

Только если бит установлен, мы обращаемся ко второй структуре — вспомогательной таблице накопленного popcount. Она определяет порядковый номер страницы по числу заполненных страниц перед ней и тем самым находит соответствующий ей диапазон записей. Для ~1900 пустых страниц при этом вообще ничего хранить не приходится.

let (word_idx, bit_idx, c_len) = if lead < 0xE0 {
    (0usize, lead & 0x1F, 2usize) // 2 байта: слово 0
} else if lead < 0xF0 {
    ((lead & 0x0F) as usize, bytes[read + 1] & 0x3F, 3) // 3 байта: слово = nibble

} else {
    (
        (((lead & 0x07) as usize) << 6) | (bytes[read + 1] & 0x3F) as usize,
        bytes[read + 2] & 0x3F,
        4usize,
    ) // 4 байта: объединяем 2 байта
};

// отсекаем без декодирования: сброшенный бит ⇒ свёртки нет
if word_idx >= PAGE_BITMAP.len() || (PAGE_BITMAP[word_idx] >> bit_idx) & 1 == 0 {
    read += c_len;
    continue;
}

Поскольку word_idx зависит только от начального байта, а для четырёхбайтовых последовательностей ещё и от первого байта продолжения, чтение из битовой карты можно запустить заранее.

Внутри страницы свёртки образуют диапазоны

Установленный бит страницы говорит нам, что какие‑то кодовые точки на этой странице требуют свёртки, но не уточняет, какие именно и во что они преобразуются. Очевидный вариант — хранить отдельную запись для каждой такой кодовой точки. Но это и громоздко, и медленно при поиске: на одной странице могут находиться десятки преобразований, и для поиска нужной кодовой точки пришлось бы просматривать их все.

И здесь нас снова выручает структура самих данных. У соседних кодовых точек в подавляющем большинстве случаев одинаковое смещение при свёртке: весь диапазон A‑Z сдвигается на +32, а в Latin Extended много чередующихся диапазонов вроде 0×0100, 0×0102, 0×0104, …, где сворачивается каждая вторая кодовая точка.

Поэтому вместо отдельных записей для каждой кодовой точки мы храним диапазоны: начало, конец, шаг и смещение. Одного бита для шага достаточно, чтобы описать как непрерывные диапазоны, так и варианты «через один». Такое интервальное сжатие превращает ~1484 отдельных преобразования всего в 238 диапазонов на 59 страницах — в среднем примерно четыре на страницу.

В результате внутри страницы приходится просматривать лишь несколько записей вместо десятков.

Такое представление «диапазон + смещение», включая трюк с шагом, позаимствовано из пакета unicode языка Go. Его записи CaseRange хранят диапазон Lo/Hi и смещения для разных регистров, а специальное значение UpperLower обозначает чередующиеся блоки. На границах страниц диапазоны разделяются, поэтому ни один из них не пересекает две страницы.

Одна запись диапазона помещается в два байта

Поскольку обе границы диапазона находятся внутри одной страницы, для каждой хватает 6 бит. Мы разнесли их по двум массивам: RUN_END_LOW[i] = end & 0x3F хранит конец диапазона и служит ключом поиска, а RUN_START_STRIDE[i] = (start & 0x3F) | ((stride − 1) << 6) хранит начало и шаг и читается только при совпадении.

Поскольку каждый ключ занимает ровно один байт, поиск внутри страницы можно распараллелить. Вместо того чтобы по очереди сравнивать cp & 0x3F с каждым диапазоном, мы загружаем сразу 8 байтов end_low в один u64 и проверяем их одной операцией SWAR без ветвлений: (chunk | 0x80…80) − broadcast(low) & 0x80…80 устанавливает старший бит в каждом lane, где ключ ≥ cp & 0x3F.

Затем одного поиска установленного бита в полученной маске достаточно, чтобы найти нужную позицию: ключи отсортированы, поэтому первый установленный lane и соответствует искомому диапазону.

В среднем на страницу приходится около четырёх диапазонов, так что одно сравнение сразу по восьми значениям почти всегда полностью закрывает поиск. Есть одна неудачная страница с 30 диапазонами: там сравнение выполняется в коротком цикле, который проходит по восемь ключей за раз. Но даже он делает всего несколько итераций, причём ровно на одной странице во всём Unicode и никогда на наиболее частых.

В любом случае мы получаем поиск без ветвления на каждый диапазон и без восстановления кодовой точки.

/// Смещение первого диапазона с `end_low >= low_v` на странице из `n` диапазонов,
/// либо `n`, если такого диапазона нет. Сканирует по 8 байтов `end_low` за раз через SWAR.
#[inline]
fn scan_end_low(lo: usize, n: usize, low_v: u8) -> usize {
    const HIGH: u64 = 0x8080_8080_8080_8080;
    const ONES: u64 = 0x0101_0101_0101_0101;
    let bcast = (low_v as u64).wrapping_mul(ONES);
    let mut base = 0;
    while base < n {
        // RUN_END_LOW дополнен 8 байтами, поэтому это чтение всегда остаётся в границах массива.
        let chunk = u64::from_le_bytes(
            RUN_END_LOW[lo + base..lo + base + 8]
                .try_into()
                .expect("8-byte slice"),
        );
        // `(b | 0x80) - low_v` сохраняет старший бит тогда и только тогда, когда
        // `b >= low_v` (без заимствования между lane). Первый установленный lane —
        // первый диапазон с `end_low >= low_v`.
        let ge = (chunk | HIGH).wrapping_sub(bcast) & HIGH;
        if ge != 0 {
            let j = base + (ge.trailing_zeros() / 8) as usize;
            return if j < n { j } else { n };
        }
        base += 8;
    }
    n
}

Регистровая свёртка как сложение байтов little‑endian

На машине с little‑endian байты UTF-8 свёрнутого символа, прочитанные как u32, равны байтам исходного символа, тоже прочитанным как u32, плюс константа, заданная для соответствующего диапазона. Параллельная таблица BYTE_DELTA[i] сводит всю регистровую свёртку к загрузке с маской, одному wrapping_add и записи четырёх байтов:

let word = u32::from_le_bytes(next_four_bytes) & length_mask; // оставляем байты только этого символа
let folded = word.wrapping_add(BYTE_DELTA[i]); // свёртка одним сложением байтов
write_u32_le(dst, folded); // записываем все 4 байта...

dst += utf8_len(folded); // ...сдвигаемся на длину результата свёртки

Обе длины в этом фрагменте — length_mask для исходного символа и сдвиг на длину результата свёртки для выходного — вычисляются ещё одним небольшим трюком. Длина UTF-8-последовательности однозначно определяется четырьмя старшими битами начального байта, поэтому все 16 возможных вариантов можно упаковать по одному полубайту в единственную 64-битную константу 0x4322_1111_1111_1111. После этого длина вычисляется одним сдвигом и маской:

(LEN_BITS >> (4 * (lead >> 4))) & 0xF

Никакой цепочки if, никаких обращений к таблице в памяти и ничего, на чём мог бы ошибиться предсказатель ветвлений. Подошёл бы и подсчёт начальных единичных битов — (!lead).leading_zeros(), — поскольку в начальном байте UTF-8 на каждый байт последовательности приходится одна ведущая единица.

/// Число байтов в UTF-8-последовательности с начальным байтом `lead`.
#[inline]
pub fn utf8_len(lead: u8) -> usize {
    const UTF8_LEN_BY_LEAD: u64 = 0x4322_1111_1111_1111;
    ((UTF8_LEN_BY_LEAD >> (4 * (lead >> 4))) & 0xF) as usize
}

Поскольку указатель сдвигается на длину результата свёртки, этот подход без проблем обрабатывает даже преобразования с изменением длины: например, U+212A KELVIN SIGN (3 байта) → k (1 байт) или U+023A Ⱥ (2 байта) → U+2C65 ⱥ (3 байта). Мы просто записываем меньше или больше байтов, чем прочитали.

Именно эту часть мы считаем по‑настоящему новой. Все остальные реализации регистровой свёртки, которые мы изучали — ICU, пакет unicode в Go, regex в Rust, CPython, glibc, — сначала декодируют UTF-8 в кодовую точку, затем выполняют свёртку над ней и снова кодируют результат в UTF-8. Даже SIMD‑реализации сначала декодируют символы.

Арифметика непосредственно над байтовым представлением позволяет пропустить и декодирование, и повторное кодирование. Именно поэтому этот путь способен обогнать даже хеш‑таблицу, где ответ уже заранее хранится: хеш‑таблице всё равно приходится сначала декодировать ключ, а затем закодировать результат.

Такая байтовая арифметика предполагает, что на входе находится корректный UTF-8 в минимальной форме: каждая кодовая точка закодирована минимально возможным числом байтов. Чтение исходных байтов как u32 и прибавление смещения для диапазона дают правильную кодировку результата только при таком каноническом представлении.

Избыточная UTF-8-кодировка — когда кодовая точка занимает больше байтов, чем необходимо, например / представлена как 0xC0 0xAF, — имеет другую байтовую структуру и ломает как length_mask, так и арифметику со смещением.

Для Rust это не настоящее ограничение: &str и String гарантированно содержат корректный UTF-8, а избыточные последовательности по определению считаются некорректными. Но если вызывающая сторона передаёт сырые байты из другого источника, их сначала нужно проверить или иным образом привести к корректному представлению.

Быстрый путь для ASCII в хвостовом цикле

Есть ещё один приём, который завершает оптимизацию хвостового цикла. Напомним: первый проход уже перевёл все ASCII‑байты в нижний регистр. Поэтому, когда при сканировании хвоста встречается ASCII‑байт, мы просто сдвигаемся на один байт дальше — никаких проверок страницы и вообще никаких обращений к таблицам.

И этот байт тоже не копируется отдельно. Неизменившиеся байты — как ASCII, так и многобайтовые символы, для которых свёртка ничего не меняет, — не переносятся по одному. Сканирование просто продолжается до следующего символа, который действительно нужно свернуть.

После этого весь неизменившийся диапазон между предыдущим преобразованием и текущим копируется одним вызовом copy_nonoverlapping.

Поэтому смешанный текст — например, CJK с ASCII‑пробелами и пунктуацией или код с редкими идентификаторами с диакритикой — быстро проскакивает ASCII‑вставки, обращается к битовой карте только для настоящих многобайтовых символов и копирует данные целыми блоками, а не побайтово.

Собираем всё вместе: таблица целиком

Получается 9,6 бита на одну запись свёртки, причём больше половины приходится на вспомогательную таблицу BYTE_DELTA, которой мы платим за путь без декодирования. Сам индекс вместе с записями диапазонов занимает около 4,4 бита на запись.

На фоне очевидных альтернатив эти 1776 байт меньше на порядок и более. И, в отличие от большинства из них, эта реализация вообще не декодирует символы:

Как это выглядит на фоне альтернатив

В самом частом случае — на ASCII — регистровая свёртка работает на уровне пропускной способности памяти (>45 ГиБ/с), более чем на порядок опережая другие реальные реализации и более чем на 50% — неэквивалентную функцию str::to_lowercase.

Чтобы получить грубую «верхнюю границу» для случая с не‑ASCII, мы отдельно измерили оптимизированный цикл декодирования и повторного кодирования UTF-8 без самой регистровой свёртки, используя crate simdutf. Такой тест стабильно показывает около 2 ГБ/с и всего примерно вдвое быстрее нашего решения на худшем сценарии, где сворачивать приходится каждый символ. Наивная реализация через хеш‑таблицу отстаёт от всех остальных на всех типах нагрузки.

Три столбца — это реальные реализации регистровой свёртки, которые дают одинаковый результат: simple_fold из этого crate, simd_normalizer из crate simd‑normalizer и HashMap с наивным поиском по CaseFolding.txt. Строки с нагрузками подобраны так, чтобы покрыть сценарии от типичных до худшего случая:

Абсолютные значения здесь стоит воспринимать как ориентир, а не как универсальные цифры. Вся конструкция сильно зависит от автовекторизации, SWAR и арифметики непосредственно над байтовым представлением в little‑endian, поэтому на другой микроархитектуре — с более широкими или узкими векторными блоками, другой пропускной способностью памяти, big‑endian или x86 вместо ARM — могут заметно измениться и сами результаты, и даже соотношения между ними.

Подробнее — в разделе о производительности в README.

Что стоит запомнить

Регистровая свёртка — одна из самых базовых текстовых операций, и именно поэтому её стоило так тщательно оптимизировать: мы прогоняем её по каждому байту, который индексируем.

Основной выигрыш дали две идеи, обе довольно неочевидные. Во‑первых, вместо досрочного выхода нужно пройти весь буфер циклом без ветвлений. Во‑вторых, саму свёртку можно выполнять арифметикой непосредственно над байтовым представлением, не декодируя UTF-8 в кодовую точку.

Вместе эти приёмы позволяют самому частому случаю работать на уровне пропускной способности памяти, а редким преобразованиям — обходиться без декодирования. И всё это помещается в таблицу размером всего 1776 байт. Именно свёртку без декодирования, через байтовую арифметику, мы считаем по‑настоящему новой частью этой работы.

Благодаря ей этот путь может обогнать даже хеш‑таблицу, где ответ уже заранее сохранён.

Наверняка здесь ещё есть что оптимизировать, и нам было бы интересно это увидеть. Crate называется casefold; сгенерированная таблица и подробное описание реализации находятся рядом с исходным кодом.

Когда производительность упирается в «мелочи» вроде лишнего ветвления, копирования или аллокации, интуитивные оптимизации могут дать обратный эффект. Чтобы находить такие узкие места, мало просто переписывать горячий код — важно уметь измерять его поведение, понимать работу памяти и проверять решения профилированием.

Именно так локальная оптимизация превращается в системный навык: вы начинаете видеть, где приложение действительно теряет производительность и почему более простой код иногда оказывается быстрее.

Если хотите глубже разобраться в низкоуровневой оптимизации и производительности, приходите на бесплатные открытые уроки:

• 7 сентября в 20:00. «Работа с памятью на языке C». Записаться

• 9 сентября в 20:00. «Go‑профилирование: как найти и исправить „тормоза“ в продакшене». Записаться

• 9 сентября в 20:00. «Владение, заимствование и ссылки в Rust: как компилятор делает ваш код безопасным». Записаться

Полный список бесплатных уроков августа можно найти в дайджесте.