Проверьте все байты __m128i на совпадение одного байта, используя SSE / AVX / AVX2

Question

Я ищу эффективные способы вычисления следующей функции:

Ввод: __m128i data, uint8_t in;

Вывод: логическое значение, показывающее, есть ли байты в data in.

Я, по сути, использую их для реализации стека с эффективным пространством / временем для байтов с емкостью 8. Мое наиболее эффективное решение - сначала вычислить __m128i tmp со всеми байтами как in.Затем проверьте, является ли какой-либо байт в tmp\xor data нулевым байтом.

Answer 1

Да, AVX2 имеет эффективную байтовую трансляцию.SSSE3 pshufb с маской со всеми нулями столь же дешев, но вы должны создать вектор управления перемешиванием.AVX512BW / F даже имеет одну инструкцию vpbroadcastb/w/d/q x/y/zmm, r32.(С необязательной маскировкой вы можете обнулить некоторые или объединить с существующим вектором, если хотите, например, вставить в позицию, используя однобитную маску.)

К счастью, компиляторы знают, как это сделать при реализации _mm_set1_epi8 так что мы можем оставить это компилятору.

Затем он просто сводится к обычному pcmpeqb / pmovmskb, чтобы получить целое число, которое будет иметь бит 1 для соответствующих элементов, которые выможет переходить на.

// 0 for not found, non-zero for found.  (Bit position tells you where).
unsigned contains(__m128i data, uint8_t needle) {
    __m128i k = _mm_set1_epi8(needle);
    __m128i cmp = _mm_cmpeq_epi8(data, k);  // vector mask
    return _mm_movemask_epi8(cmp);          // integer bitmask 
}

Как и следовало ожидать, все компиляторы используют это asm ( Godbolt )

contains(long long __vector(2), unsigned char):
    vmovd   xmm1, edi
    vpbroadcastb    xmm1, xmm1
    vpcmpeqb        xmm0, xmm0, xmm1
    vpmovmskb       eax, xmm0
    ret

За исключением MSVC, который тратит впустуюинструкция по movsx eax, dl первая.(Windows x64 передает 2-й аргумент в RDX, а x86-64 System V передает первый целое arg в RDI.)

---

Без AVX2 вы получите что-то вродеэто с SSSE3 или выше

# gcc8.3 -O3 -march=nehalem
contains(long long __vector(2), unsigned char):
    movd    xmm1, edi

    pxor    xmm2, xmm2
    pshufb  xmm1, xmm2         # _mm_shuffle_epi8(needle, _mm_setzero_si128())

    pcmpeqb xmm0, xmm1
    pmovmskb        eax, xmm0
    ret

или только с SSE2 (базовый уровень для x86-64):

contains(long long __vector(2), unsigned char):
    mov     DWORD PTR [rsp-12], edi
    movd    xmm1, DWORD PTR [rsp-12]    # gcc's tune=generic strategy is still store/reload  /facepalm
    punpcklbw       xmm1, xmm1          # duplicate to low 2 bytes
    punpcklwd       xmm1, xmm1          # duplciate to low 4 bytes
    pshufd  xmm1, xmm1, 0               # broadcast

    pcmpeqb xmm1, xmm0
    pmovmskb        eax, xmm1
    ret

---

Похожие:

• Как сравнить два вектора с использованием SIMD и получить один логический результат? и множество дубликатов

• Как подсчитать вхождение байта в массив с использованием SIMD?

• SIMD / SSE: Как проверить, что все векторные элементы отличны от нуля (pxor + ptest + jcc = 4 мопа против. pcmpeqb + pmovmskb + слитый макрос test/jcc = 3 моп.)

• Индексы ненулевых байтов регистра SSE / AVX (поиск позиций совпадения)

• Как подсчитывать вхождения символов, используя SIMD (как memchr, но подсчет совпадений вместо поиска первого, используя AVX2. С эффективным накоплениемиз подсчетови эффективные горизонтальные суммы.)