Цикл ускорился с 3,1 до 45 гигабайт в секунду после того, как из него убрали ранний выход

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

Привычный приём выглядит разумно: идти по байтам, а на первом не-ASCII прерваться и отдать остаток полноценному Unicode-пути. На Apple M4 это даёт 3,1 ГиБ/с. Оказалось, что тормозит именно ранний выход: пока условие выхода из цикла зависит от данных, компилятор не может его векторизовать.

🔘 если убрать break, но оставить ветвление в теле, LLVM векторизует наполовину: 7,6 ГиБ/с и 25 векторных инструкций;
🔘 полностью безветвевой проход даёт больше 45 ГиБ/с и 41 векторную инструкцию, это уже пропускная способность памяти;
🔘 безветвевое тело с сохранённым break медленнее наивного варианта, 2,6 против 3,1 ГиБ/с: безусловная запись каждого байта обходится дороже редкой хорошо предсказанной ветки;
🔘 компромисс из стандартных библиотек, когда сначала сканируют машинными словами по 16 байт, а потом сворачивают регистр, читает данные дважды и упирается в 23 ГиБ/с;
🔘 попытка слить эти два прохода в один даёт 8,7 ГиБ/с: ветка, зависящая от данных, возвращается каждые 16 байт, и цикл снова обрабатывает по одному блоку без разворачивания;
🔘 таблица для редкого пути ужата до 1776 байт: 1484 отображения Unicode 16.0 уложились в 238 диапазонов на 59 страницах из примерно 1960, и свёртка идёт арифметикой прямо над байтами UTF-8, без декодирования символа.

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

Полная статья: https://github.blog/engineering/architecture-optimization/dont-stop-early-case-folding-source-code-at-memory-speed/

@prog_stuff