Hacker News Digest

SIMD-поиск подстроки в Zig

Автор реализовал алгоритм, который на 60 % быстрее std.mem.indexOf.
Идея: сравниваем 32-байтовые блоки текста с первым и последним символом искомого слова, используя AVX2.

1. Берём первый и последний байт needle (first, last).
2. Загружаем 32 байта haystack в вектор Block = @Vector(32, u8).
3. Создаём маски совпадений:

   const eq_first = first == block;
   const eq_last  = last  == block_shifted;
   const mask = @bitCast(eq_first & eq_last);
   

4. Для каждого установленного бита проверяем полное совпадение подстроки.
5. Хвост обрабатываем обычным indexOf.

Код (сокращённо):

const Block = @Vector(32, u8);
const first = @splat(needle[0]);
const last  = @splat(needle[k-1]);

while (i + k + 32 <= n) : (i += 32) {
    const f = haystack[i..][0..32].*;
    const l = haystack[i+k-1..][0..32].*;
    var mask: u32 = @bitCast((first == f) & (last == l));
    while (mask != 0) {
        const bit = @ctz(mask);
        if (mem.eql(u8, haystack[i+bit+1..][0..k-1], needle[1..]))
            return i + bit;
        mask &= mask - 1;
    }
}
return mem.indexOf(u8, haystack[i..], needle) orelse null;

Тест: поиск слова «newsletter» во всём «Моби Дике» (~1.2 МБ).
Сборка: zig build -Doptimize=ReleaseFast.

• Подход с SIMD-ускорением поиска подстроки популярен, но в худшем случае остаётся квадратичным O(m·n), поэтому нужен «откат» на линейный алгоритм (KMP/BM).
• Участники отмечают, что большинство реализаций опираются на 10-летние AVX/NEON, игнорируя AVX-512, SVE и RVV, которые дают больший выигрыш, но пока редки на десктопах и в облаках.
• Zig пока не предоставляет прямых intrinsics, хотя LLVM-бекенд позволяет вызывать нужные инструкции; это тормозит портирование низкоуровневых оптимизаций.
• Есть идея дальнейшего SIMD-фильтра: проверять не только первый/последний байт иглы, но и второй/предпоследний и т.д., накладывая маски.
• Вопросы Unicode: алгоритм работает на байтах, поэтому для UTF-8/16 потребуется дополнительная обработка переменной длины кодов.