从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

设置为字节的0xff意思是我需要以do_operation(i) 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);
            }
        }
}

我首先提取128位向量（cmp_low和cmp_high）的第一和第二64位整数。然后，我用于popcount计算设置为的字节0xff数（设置为1的位数除以8）。最后，我pext用来获取没有零的位置，像这样：

0x0706050403020100
0x000000ff00ff0000
        |
      PEXT
        |
0x0000000000000402

我想找到一个更快的解决方案，以提取位置设置为字节0xff的compare矢量。更确切地说，是非常往往只设置为0，1或2个字节0xff的compare载体，我想用这个信息来避免一些分支。

Answer 1

以下是如何减少测试数量的简要概述：

• 首先使用一个函数将 128 位整数的每个字节的所有 lsb 或 msb 投影到一个 16 位值中（例如，在 X86 cpu: 上有一个SSE2汇编指令，pmovmskb英特尔和 MS 编译器支持它的_mm_movemask_pi8内在，和 gcc 也有一个内在的: __builtin_ia32_ppmovmskb128, );

• 然后将该值分成 4 个半字节；

• 定义函数来处理半字节的每个可能值（从 0 到 15）并将它们放入数组中；

• 最后调用由每个半字节索引的函数（使用额外的参数来指示它是 16 位中的哪个半字节）。

Answer 2

由于在您的情况下，compare向量中通常只有 0、1 或 2 个字节设置为 0xff，因此位掩码上的短 while 循环可能比基于pext 指令的解决方案更有效。另请参见我的答案上类似的问题。

/*
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

*/