Бенчмаркая поиск по строке: самописные циклы проигрывают от ×14 до ×154

Уважаемые читатели, в этой статье я хочу рассказать про поиск по строке и представить свои выводы. Началось с оптимизации: сравнил поиск символа циклом со string.IndexOf — и получил разницу в разы. Заодно выяснилось, что серверный Xeon с AVX-512 в этой задаче медленнее игрового десктопа с AVX2. Ниже разбор обоих фактов с дизасмом и замерами.

Будет четыре истории, и в каждой — вопрос, на который я искал ответ:

Насколько обычный for по строке медленнее string.IndexOf — и меняется ли разрыв с длиной строки?
Почему сервер с AVX-512 — самыми широкими векторными регистрами — оказался в два с лишним раза медленнее десктопа с AVX2?
Можно ли догнать BCL, если написать вектор самому через intrinsics? Я попробовал двумя способами — один дал замедление в 10 раз.
И что со всем этим делать на практике: какие методы брать и каких ошибок избегать.

Всё на BenchmarkDotNet v0.15.8, машинный код снят переменной DOTNET_JitDisasm, весь код на гите — можно повторить и проверить.

Методика замеров: тесты гонялись на реалистичном тексте (случайные буквы и пробелы, а не повтор одного символа — на строке из повторов цифры получаются заниженными), в двух сценариях (искомый символ есть в середине / его нет вообще) и на трёх длинах (32, 512, 65536).

Тест дополнительно сверяет, что все методы возвращают одинаковый результат.

Четыре машины:

Машина	CPU	ОС	Векторы
№1	AMD Ryzen 9 5950X, 16 ядер	Windows 10	AVX2 (ymm, 32 Б)
№2	Intel Core i9-10900KF, 10 ядер	Windows 10	AVX2 (ymm, 32 Б)
№3	2 x Intel Xeon Silver 4314, 32 ядра	Windows Server 2022	AVX-512 (zmm, 64 Б)
№4	2 x Intel Xeon Silver 4314, 32 ядра	Windows Server 2022	AVX-512 (zmm, 64 Б)

Немного теории: почему цикл — это скаляр

Процессор умеет обрабатывать не один символ за такт, а сразу вектор — 16, 32 или 64 байта одной инструкцией (SSE, AVX2, AVX-512). За счёт этого и достигается скорость строковых операций в BCL.

Важно понимать, чего JIT не делает. RyuJIT не векторизует произвольный цикл. Кое-что он умеет: развернуть простой цикл, свернуть операции над Vector<T>, в .NET 9 добавили оптимизацию индукционных переменных. Но взять обычный for со сравнением символов и превратить его в SIMD-поиск он не может — общий запрос на автовекторизацию в трекере dotnet/runtime #12466 открыт с 2019 года. Поэтому SIMD-скорость строк лежит не в компиляторе, а внутри методов BCL — вектора там написаны вручную.

История первая: цикл против BCL

Задача — найти символ в строке. Первый вариант — цикл, второй — string.IndexOf:

static int IndexOfCharManual(string s, char c){    for (int i = 0; i < s.Length; i++)    {        if (s[i] == c)        {            return i;        }    }    return -1;}s.IndexOf(c);

Снимаем машинный код цикла — чистый скаляр, один символ за проход, ни одного векторного регистра:

; IndexOfCharManual, .NET 10 — тело циклаmovzx    r10, word ptr [rcx+2*r8+0x0C]   ; берём ОДИН символcmp      r10d, edxje       SHORT FOUNDinc      r8dcmp      eax, r8djg       SHORT LOOP

А внутри IndexOf — вектор. На десктопе это ymm (16 символов за инструкцию), на Xeon — zmm (32 символа):

; IndexOf в BCL, десктопvpbroadcastw ymm0, ymm0     ; размножили искомый символ по регистру ; IndexOf в BCL, Xeonvpbroadcastw zmm0, eax      ; регистр вдвое шире

Замер на строке 64 КБ в сценарии Miss — искомого символа нет, оба варианта сканируют строку целиком:

*Рис. 1. Свой цикл против IndexOf на строке 64 КБ: разрыв в разы*

Разрыв — от 8 до 14 раз в зависимости от машины. К такому замеру есть два очевидных возражения, разберу оба.

А если символ находится быстро?

Первое возражение: в реальном коде символ обычно есть, и цикл выходит из поиска раньше. Проверяем — ставим символ ровно в середину (сценарий Hit):

*Рис. 2. Ранний выход не спасает: даже с символом в середине BCL быстрее в 13 раз*

Ранний выход не спасает: даже когда символ в середине, BCL быстрее в 13 раз. Вектор проходит те же полстроки, только пачками по 16-32 символа, а цикл — по одному.

А на коротких строках?

Второе возражение: на коротких строках накладные расходы векторного пути (проверки длины, обработка хвоста) могут съесть выигрыш. Разрыв по длинам:

*Рис. 3. Разрыв ×5 на коротких и ×14–15 на длинных — BCL быстрее на любой длине (лог-шкала)*

На 32 символах разрыв меньше — «всего» ×5, на 512 и дальше держится ×14–15. Но порога, где свой цикл выгоднее, нет — BCL быстрее на любой длине.

История вторая: AVX-512 медленнее AVX2

Теперь про сервер. По логике у Xeon регистры вдвое шире — значит, и поиск должен быть быстрее. Дизасм подтверждает: Xeon реально гоняет zmm, десктопы — ymm. А по пропускной способности вышло наоборот:

*Рис. 4. Пропускная способность IndexOf: десктопы на AVX2 против серверов на AVX-512*

Десктопы — 103 и 119 ГБ/с, серверные Xeon — 44. Вдвое шире регистр — в два с лишним раза медленнее работа. Причин две, и обе не про ширину:

Частота. Игровой Ryzen крутится под 5 ГГц, Xeon — 2.4 ГГц базовых и до 3.4 в турбо. Поиск в кэше упирается в частоту ядра, а не в ширину вектора.
Задержки масочных сравнений. AVX-512-сравнение кладёт результат в масочный регистр (k1 в листинге ниже), и эта связка медленнее AVX2-пары «сравнение + снятие маски» — на ряде процессоров AVX2-код из-за этого обгоняет.

Это известная проблема — она зафиксирована в трекерах компиляторов. В LLVM (llvm-project #91302) покомандно разбирают, что AVX-512-сравнение через маски имеет бОльшую задержку, чем AVX2, и на ряде процессоров AVX2-код в разы быстрее. Похожее ловили в OpenVINO (issue #11710): Xeon с AVX-512 медленнее десктопа с AVX2. Вывод простой: шире регистр — не значит быстрее. Смотреть надо не на инструкцию в листинге, а на замер на конкретном железе.

Сразу закрою вопрос про ReadyToRun — «может, на сервере библиотека собрана заранее под общее железо?». Прогнал с DOTNET_ReadyToRun=0 (пере-JIT под своё железо на месте): разница ноль, 2.96 против 2.95 µs. Дело в частоте, а не в прекомпиляции.

История третья: пишем свой SIMD — и делаем хуже

JIT циклы не векторизует, но в .NET есть System.Runtime.Intrinsics — SIMD-поиск можно написать самому. Я попробовал двумя способами.

Способ 1: AVX2 на Vector256

Загружаем по 16 символов, сравниваем, ищем совпадение по маске:

Vector256<ushort> target = Vector256.Create((ushort)c);for (; i <= length - 16; i += 16){    Vector256<ushort> block = Avx.LoadVector256((ushort*)(p + i));    Vector256<ushort> eq = Avx2.CompareEqual(block, target);    int mask = Avx2.MoveMask(eq.AsByte());    if (mask != 0)    {        return i + BitOperations.TrailingZeroCount(mask) / 2;    }}// + ещё десяток строк на хвост (символы, не влезшие в вектор)

Дизасм подтверждает — AVX2 целыми ymm:

vpbroadcastw ymm0, ymm0                    ; размножили искомый символvpcmpeqw ymm1, ymm0, ymmword ptr [rcx...]  ; сравнили 16 символов разомvpmovmskb r9d, ymm1                        ; собрали маску совпадений

Ускорил скаляр в разы — с 15.4 до 1.9 µs на Ryzen. Но BCL всё равно впереди (1.11). Уже неплохой результат, но не победа.

Способ 2: AVX-512 на Vector512

Логичный шаг: у Xeon есть AVX-512, возьму 512-битные регистры — 32 символа за шаг вместо 16. Тот же код, но на Vector512:

Vector512<ushort> target = Vector512.Create((ushort)c);for (; i <= length - 32; i += 32){    Vector512<ushort> block = Avx512F.LoadVector512((ushort*)(p + i));    ulong mask = Avx512BW.CompareEqual(block, target)                        .ExtractMostSignificantBits();    if (mask != 0)    {        return i + BitOperations.TrailingZeroCount(mask);    }}

Ожидание — ускорение в два раза. Реальность:

*Рис. 5. Самописный вектор: на десктопе AVX-512 медленнее AVX2 в 8–10 раз (красным)*

На десктопах AVX-512-вариант дал замедление в 8–10 раз против AVX2-версии: 15.5 µs на Ryzen против 1.9. На Xeon — да, чуть быстрее ymm-варианта (3.06 против 3.36), но всё равно медленнее IndexOf. Наглядно (лог-шкала, иначе десктопный zmm не влезает):

*Рис. 6. Самописный AVX-512 на десктопе — катастрофа (лог-шкала)*

Почему так. Ни у Ryzen 9 5950X (Zen 3), ни у i9-10900KF (Comet Lake) аппаратного AVX-512 нет (у 10900KF по спецификации Intel ARK из векторных расширений — только SSE4.1/4.2 и AVX2): Avx512BW.IsSupported возвращает false, векторная ветка не выполняется, и весь поиск делает скалярный хвост — отсюда цифры порядка обычного цикла. То есть «беру самое широкое» на десктопе оборачивается не ускорением, а провалом в 10 раз — и выяснится это в лучшем случае на проде.

Разница с IndexOf вот в чём: библиотека не берёт AVX-512 вслепую. Она проверяет, где широкий вектор реально быстрее, и переключается — zmm на серверном Xeon, ymm на десктопе, обычные инструкции на старом железе, отдельные ветки под ARM. Дизасм это показывает прямо — один и тот же .NET 10, два разных листинга:

; IndexOf в BCL — десктоп (Ryzen), путь AVX2vpbroadcastw ymm0, ymm0                    ; символ на весь ymm — 16 символовvpcmpeqw ymm1, ymm0, ymmword ptr [rcx]     ; сравнили блок разом ; IndexOf в BCL — тот же бинарь на Xeon, путь AVX-512vpbroadcastw zmm0, eax                     ; символ на весь zmm — 32 символаvmovups  zmm1, zmmword ptr [rcx]           ; грузим 64 байтаvpcmpeqw k1, zmm1, zmm0                    ; сравнение сразу в масочный регистрkortestd k1, k1                            ; есть ли совпадение

Чтобы повторить это, придётся написать по ветке под каждую архитектуру и обработку хвостов для каждой — то есть переписать то, что уже лежит в IndexOf.

Мораль: свой SIMD писать можно и это полезный навык — но соревноваться с BCL в базовых операциях смысла нет. Там уже написано лучше, под все платформы, и с правильным выбором ширины вектора. «Оптимальный» Vector512 на десктопе — это ×10 замедление и unsafe в придачу.

История четвёртая: что делать на практике

Поиск одного из набора — SearchValues

Ищете любой символ из набора — гласную, разделитель, запрещённый символ? Не пишите цепочку || ch == …. С .NET 8 есть SearchValues — создаёте один раз в статическое поле:

private static readonly SearchValues<char> Vowels = SearchValues.Create("aeiou"); int i = text.AsSpan().IndexOfAny(Vowels);

Цифры на 64 КБ текста без гласных: перебор в цикле — 231 µs, IndexOfAny — 2.9, SearchValues — 1.5. Со старым IndexOfAny(«aeiou») разрыв в 1.8–1.9 раза: SearchValues строит структуру поиска один раз при создании, а IndexOfAny со строкой — на каждом вызове (внутренности разобраны у Стивена Тоуба в Performance Improvements in .NET 8).

*Рис. 7. Поиск гласной: перебор в цикле против IndexOfAny и SearchValues (лог-шкала)*

×154 с перебором — это уже не про SIMD

Откуда ×154, если это всего пять сравнений на символ? Снимаем дизасм перебора на .NET 10:

; IndexOfVowelManual, .NET 10 — на каждый символmovzx    r8, word ptr [rcx+2*rax+0x0C]  ; берём символcmp      r8d, 101                       ; ветвление №1: не больше 'e'?jle      SHORT CHECK_A_Esub      r8d, 105                       ; сдвигаем к 'i'cmp      r8d, 12ja       SHORT NEXT                     ; ветвление №2: вне i..u?mov      r10d, 0x1041                   ; биты 0, 6, 12 = i, o, ubt       r10d, r8d                      ; проверка битовой маской

JIT здесь не тупит, наоборот: с .NET 9 цепочку ch == ‘i’ || ch == ‘o’ || ch == ‘u’ он сворачивает в одну проверку битовой маской (bt). Инструкций мало. Проблема в другом: оба ветвления зависят от значения символа, а символы случайные — предсказатель переходов ошибается примерно на каждом втором, и каждая ошибка стоит порядка 13–20 тактов в зависимости от микроархитектуры (справочники Агнера Фога). Итог — 3.5 нс на символ.

В цикле с одним символом единственное сравнение на Miss всегда false и предсказывается идеально — 0.23 нс на символ. Вот и ×15 между перебором одного символа и пяти, остальное до ×154 добирает вектор.

Отсюда же и странность на графике: на .NET 8 перебор быстрее, чем на .NET 9/10 (154 µs против 231–236). Кодген другой — линейная цепочка сравнений без диапазонного ветвления:

; IndexOfVowelManual, .NET 8 — линейная цепочкаcmp      r8d, 101ja       SHORT CHECK_IOU    ; больше 'e' — проверяем i, o, ucmp      r8d, 97            ; 'a'?je       SHORT FOUNDcmp      r8d, 101           ; 'e'?je       SHORT FOUND

Новый кодген формально компактнее, но добавил ещё одно ветвление по данным — и на случайном тексте стал на треть медленнее. Мораль та же, что во всей статье: решают не инструкции, а ветвления по случайным данным. У векторного пути BCL ветвлений по данным нет вообще — он сравнивает блок целиком и смотрит маску совпадений.

Регистронезависимый поиск — не ToLower в цикле

Классическая ошибка — искать без учёта регистра:

for (int i = 0; i < s.Length; i++){    if (char.ToLowerInvariant(s[i]) == lower)   // вызов на КАЖДЫЙ символ    {        return i;    }}

Дизасм показывает: ToLowerInvariant на каждой итерации — это вызов в ICU, библиотеку локализации:

call     [TextInfo:IcuChangeCase(...)]   ; смена регистра каждую итерацию

А IndexOf(needle, StringComparison.OrdinalIgnoreCase) делает то же самое вектором. Разница — в 16–26 раз, а на .NET 8 доходит до ×39. Правильно так:

int i = s.IndexOf(needle, StringComparison.OrdinalIgnoreCase);

Дефолты IndexOf: char и string ищут по-разному

Перегрузки IndexOf ведут себя по-разному. s.IndexOf(‘a’) с char идёт напрямую в SpanHelpers.IndexOfChar — это всегда ordinal. А перегрузка s.IndexOf(«a») со строкой по дефолту использует StringComparison.CurrentCulture — это код из dotnet/runtime, String.Searching.cs:

// dotnet/runtime, String.Searching.cs (main)public int IndexOf(char value) => SpanHelpers.IndexOfChar(ref _firstChar, value, Length); public int IndexOf(string value){    return IndexOf(value, StringComparison.CurrentCulture);}

CurrentCulture означает поход в ICU с правилами сопоставления текущей культуры — в разы медленнее ordinal-поиска, плюс результат зависит от локали (в dotnet/docs #21249 таблица дефолтов по всем строковым методам, на это же есть правило анализатора CA1310). Поэтому StringComparison указывайте явно:

s.IndexOf("x", StringComparison.Ordinal);   // ordinal: сравнение по кодам символовs.IndexOf("x");                             // CurrentCulture по дефолту — медленно

Выводы

RyuJIT не векторизует ваши циклы (issue с 2019). Простой for по строке — всегда скаляр, на длинных данных в 8–14 раз медленнее BCL, и ранний выход не спасает. Не пишите строковый поиск своим циклом — IndexOf, IndexOfAny и SearchValues в BCL уже векторные. Count и SequenceEqual тоже: в замере они быстрее цикла в 5–7 раз на всех четырёх машинах.
Шире вектор — не быстрее код. Серверный AVX-512 в этой задаче в два с лишним раза медленнее десктопного AVX2 (частота + задержки масочных сравнений), и это подтверждают трекеры LLVM и OpenVINO. Меряйте на целевом железе, не переносите цифры десктоп ↔ сервер.
Самописный Vector512 на десктопе даёт ×10 замедление: ни у Zen 3, ни у Comet Lake аппаратного AVX-512 нет, и метод скатывается в скалярный хвост. IndexOf выбирает ширину вектора под железо сам — самому это не повторить, не переписав пол-рантайма. Не соревнуйтесь с BCL в базовых операциях.
Для набора символов — SearchValues в статическое поле: перебор в цикле проигрывает ему до ×154, и виноваты миспредикты ветвлений, а не число сравнений. Для регистронезависимого — OrdinalIgnoreCase, а не ToLower в цикле. И всегда указывайте StringComparison.Ordinal явно — иначе получите медленное культурное сравнение.

Код из статьи

SimdProof — бенчмарк (поиск символа, подсчёт, сравнение строк, поиск гласной, регистронезависимый поиск, самописные AVX2 и AVX-512, два сценария, три длины, net8/9/10) и снятие дизасма

Ссылки

Всем удачи и до новых встреч!

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

NativeAOT я не гонял — там векторизация статическая, картина может отличаться; прогоните — поделитесь.

ссылка на оригинал статьи https://habr.com/ru/articles/1059624/