Извлечь заданную позицию байтов из SIMD-вектора

Question

Я запускаю скамейку вычислений с использованием SIMD-инструкций. Эти инструкции возвращают вектор из 16 байт, как результат, названных compare, причем каждый байт является 0x00 или 0xff:

   0 1 2 3 4 5 6 7  15 16 
compare : 0x00 0x00 0x00 0x00 0xff 0x00 0x00 0x00 ... 0xff 0x00 

Bytes набором для 0xff значит мне нужно запустить функцию do_operation(i)с я быть положением байта.

Например, выше compare вектор средней, мне нужно запустить эту последовательность операций:

do_operation(4); 
do_operation(15); 

Вот быстрое решение я придумал до сих пор:

for(...) { 
     // 
     // SIMD computations 
     // 
     __m128i compare = ... // Result of SIMD computations 

     // Extract high and low quadwords for compare vector 
     std::uint64_t cmp_low = (_mm_cvtsi128_si64(compare)); 
     std::uint64_t cmp_high = (_mm_extract_epi64(compare, 1)); 

     // Process low quadword 
     if (cmp_low) { 
      const std::uint64_t low_possible_positions = 0x0706050403020100; 
      const std::uint64_t match_positions = _pext_u64(
        low_possible_positions, cmp_low); 
      const int match_count = _popcnt64(cmp_low)/8; 
      const std::uint8_t* match_pos_array = 
        reinterpret_cast<const std::uint8_t*>(&match_positions); 

      for (int i = 0; i < match_count; ++i) { 
       do_operation(i); 
      } 
     } 

     // Process high quadword (similarly) 
     if (cmp_high) { 

      const std::uint64_t high_possible_positions = 0x0f0e0d0c0b0a0908; 
      const std::uint64_t match_positions = _pext_u64(
        high_possible_positions, cmp_high); 
      const int match_count = _popcnt64(cmp_high)/8; 
      const std::uint8_t* match_pos_array = 
        reinterpret_cast<const std::uint8_t*>(&match_positions); 

      for(int i = 0; i < match_count; ++i) { 
       do_operation(i); 
      } 
     } 
} 

Я начинаю с извлечением первого и второго 64-битных целых чисел из 128-битного вектора (cmp_low и cmp_high). Затем я использую popcount для вычисления количества байтов, установленного на 0xff (количество бит, установленное в 1, деленное на 8). Наконец, я использую pext, чтобы получить позиции, без нулей, например:

0x0706050403020100 
0x000000ff00ff0000 
     | 
     PEXT 
     | 
0x0000000000000402 

Я хотел бы найти быстрое решение для извлечения позиций байт, установленных для 0xffcompare в векторе. Точнее, очень часто только 0, 1 или 2 байта установлены в 0xff в compare vector, и я хотел бы использовать эту информацию, чтобы избежать некоторых ветвей.

Answer 1

Вот краткий набросок того, как вы могли бы сократить количество тестов:

• Первое использование функции проецировать все LSB или MSB каждого байта вашего 128bit целое в значение 16bit (например, , есть инструкция по сборке SSE2 для X86 cpus: pmovmskb, которая поддерживается на компиляторах Intel и MS с внутренним кодом _mm_movemask_pi8, а gcc также имеет собственный: __builtin_ia32_ppmovmskb128;);

• Затем разделите это значение на 4 куска;

• определяет функции для обработки всех возможных значений полубайта (от 0 до 15) и помещает их в массив;

• Наконец, вызовите функцию, проиндексированную каждым полубайтом (с дополнительными параметрами, указывающими, какой кусок в 16 битах).

Answer 2

Поскольку в вашем случае очень часто только 0, 1 или 2 байта установлены в 0xFF в compare векторе, короткий в то время как петля на битовую может быть более эффективным, чем решение, основанное на pext инструкция. См. Также мой answer по аналогичному вопросу.

/* 
gcc -O3 -Wall -m64 -mavx2 -march=broadwell esbsimd.c 
*/ 

#include <stdio.h> 
#include <immintrin.h> 

int do_operation(int i){   /* some arbitrary do_operation() */ 
    printf("i = %d\n",i); 
    return 0; 
} 

int main(){ 

    __m128i compare = _mm_set_epi8(0xFF,0,0,0, 0,0,0,0, 0,0,0,0xFF, 0,0,0,0); /* Take some randon value for compare */ 
    int   k = _mm_movemask_epi8(compare); 

    while (k){ 
     int i=_tzcnt_u32(k);        /* Count the number of trailing zero bits in k. BMI1 instruction set, Haswell or newer. */ 
     do_operation(i); 
     k=_blsr_u32(k);          /* Clear the lowest set bit in k.              */ 
    } 
    return 0; 
} 

/* 
Output: 

i = 4 
i = 15 

*/