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.