Поиск по коду в GitHub — движок Blackbird — индексирует больше 180 млн репозиториев, это свыше 480 ТБ исходников. Каждый байт перед построением индекса проходит case folding, и ещё раз для каждого потенциального результата. Поэтому даже такая базовая операция должна работать быстро. GitHub выложил решение как Rust-крейт casefold.
Важно: case folding — это не lowercasing. Lowercasing нужен для отображения и зависит от контекста и локали. Folding сделан специально для сравнения: он контекстно-свободный и стабильный. Крейт реализует только простые folds 1-к-1 из CaseFolding.txt, без ß→ss и турецких исключений, — как и ripgrep.
Главный неочевидный вывод: нельзя останавливаться на первом не-ASCII байте. Наивный цикл на Apple M4 даёт около 3 GiB/s. Если убрать ветки из тела, но оставить ранний выход, будет хуже — 2.6 GiB/s. Скалярный код начинает безусловно писать каждый байт. А ранний выход не даёт компилятору векторизовать цикл. Убираешь break — LLVM собирает NEON-код по 16 байт, и скорость прыгает до >45 GiB/s, то есть до пропускной способности памяти. Даже разумная идея слить скан и конвертацию в один проход проигрывает: два прохода дают 23 GiB/s, а один цикл с проверкой каждые 16 байт — только 8.7 GiB/s.
Память тоже экономили. simple_fold принимает String по значению, и если текст чистый ASCII, возвращает тот же буфер без копирования. Для хвоста с не-ASCII выделяется один буфер с запасом 1.5×. Почти все folds не удлиняют строку, но U+023A и U+023E — 2 байта, а сворачиваются в 3-байтовые символы.
Unicode-таблица упакована в 1776 байт. 1484 mapping’а, 59 страниц по 64 code point’а, битовая карта присутствия, run’ы с дельтой. Вместо декодирования UTF-8 до code point’а fold делается как little-endian сложение байтовых слов. На чистом ASCII casefold даёт >45 GiB/s, на CJK без folds — 2.95 GiB/s, на worst-case folding — 869 MiB/s. Для сравнения: simd_normalizer на ASCII — 1.21 GiB/s, HashMap — 213 MiB/s. На worst-case simd_normalizer чуть быстрее: 922 против 869 MiB/s. Крейт называется casefold, таблица и полные заметки лежат рядом с исходниками.