如何用SSE2/AVX/AVX2/AVX-512快速查找定长字节数组首匹配索引

安全阿岳

2026-8-16

基于SIMD指令集快速查找数组中首个匹配字节的实现

问题描述

给定长度为16、32或64字节且按64字节内存边界对齐的数组，如何利用SSE2/AVX/AVX2/AVX-512 SIMD指令集快速定位首个与指定字节值相等的元素索引？若不存在匹配元素，直接返回数组长度即可。

常规实现

常规方法通过简单循环即可完成，但在每秒需处理数百万个数组的场景下，性能无法满足需求（且查询操作无法并行，多线程优化无效）：

template <size_t Size>
size_t FindByte(uint8_t const (&arr)[Size], uint8_t b) {
    for (size_t i = 0; i < Size; ++i)
        if (arr[i] == b)
            return i;
    return Size;
}

现有尝试与优化需求

曾尝试基于SSE2结合预计算表的实现，但64KB的预计算表无法放入L1缓存，只能存放在L2缓存中，容易引发缓存缺失，并非最优方案。
期望实现无需预计算表，仅通过SIMD指令完成，同时适配32/64字节数组的AVX/AVX2/AVX-512版本。

已实现的高效SSE2方案

借助@PeterCordes的建议，已完成高效的SSE2实现：

#include <cstdint>
#include <iostream>
#include <bit>

#include <emmintrin.h>

size_t FindByte(uint8_t const * arr16, uint8_t b) {
    return std::countr_zero(uint16_t(
        _mm_movemask_epi8(_mm_cmpeq_epi8(
            _mm_loadu_si128((__m128i*)arr16), _mm_set1_epi8(b)))
    ));
}

int main() {
    uint8_t arr[16] = {3, 5, 7, 11, 13, 17, 19};
    std::cout << FindByte(arr, 17) << " "
        << FindByte(arr, 23) << std::endl;
}