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

В сфере искусственного интеллекта произошло заметное событие. Geronom 10 минут назад Бенчмаркая поиск по строке: самописные циклы проигрывают от ×14 до ×154 Средний 10 мин 203 C# * . NET * Программирование * Аналитика Уважаемые читатели, в этой статье я хочу рассказать про поиск по строке и представить свои выводы. Началось с оптимизации: сравнил поиск символа циклом со string.

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

Технические детали

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

Можно ли догнать BCL, если написать вектор самому через intrinsics? Я попробовал двумя способами — один дал замедление в 10 раз. И что со всем этим делать на практике: какие методы брать и каких ошибок избегать.

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

Отраслевые последствия

Тест дополнительно сверяет, что все методы возвращают одинаковый результат. Четыре машины:МашинаCPUОСВекторы№1AMD Ryzen 9 5950X, 16 ядерWindows 10AVX2 (ymm, 32 Б)№2Intel Core i9-10900KF, 10 ядерWindows 10AVX2 (ymm, 32 Б)№32 x Intel Xeon Silver 4314, 32 ядраWindows Server 2022AVX-512 (zmm, 64 Б)№42 x Intel Xeon Silver 4314, 32 ядраWindows Server 2022AVX-512 (zmm, 64 Б)Немного теории: почему цикл — это скалярПроцессор умеет обрабатывать не один символ за такт, а сразу вектор — 16, 32 или 64 байта одной инструкцией (SSE, AVX2, AVX-512). За счёт этого и достигается скорость строковых операций в BCL.

Важно понимать, чего JIT не делает. RyuJIT не векторизует произвольный цикл. Кое-что он умеет: развернуть простой цикл, свернуть операции над Vector, в .

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

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