x86 - 如何找到 AVX 向量中元素的索引？

Question

我正在尝试使用 AVX 编写硬件加速哈希表，其中每个存储桶都有固定大小(AVX 矢量大小)。问题是如何通过矢量实现快速搜索。

不完整的可能解决方案:

example target hash: 2

<1  7  8  9  2  6  3  5>  //  vector of hashes
<2  2  2  2  2  2  2  2>  //  mask vector of target hash
------------------------  //  equality comparison
<0  0  0  0 -1  0  0  0>  //  result of comparison
<0  1  2  3  4  5  6  7>  //  vector of indexes
------------------------  //  and operation
<0  0  0  0  4  0  0  0>  //  index of target hash

如何从最后一个向量中提取目标哈希的索引？

---

使用标量积的另一种(缓慢的)可能解决方案:

<1  7  8  9  2  6  3  5>  //  vector of hashes
<2  2  2  2  2  2  2  2>  //  mask vector of target hash
------------------------  //  equality comparison
<0  0  0  0 -1  0  0  0>  //  result of comparison
<0  1  2  3  4  5  6  7>  //  vector of indexes
------------------------  //  dot
            -4

Answer 1

适用于此的水平操作是 MOVMSKPS，它从 XMM/YMM 向量中提取掩码(基本上，它收集每个 channel 的最高位)。获得该索引后，您可以执行 TZCNT 或 LZCNT 以获取索引。

例子:

#include <intrin.h>
#include <immintrin.h>

int getIndexOf(int const values[8], int target)
{
    __m256i valuesSimd = _mm256_loadu_si256((__m256i const*)values);
    __m256i targetSplatted = _mm256_set1_epi32(target);
    __m256i equalBits = _mm256_cmpeq_epi32(valuesSimd, targetSplatted);
    unsigned equalMask = _mm256_movemask_ps(_mm256_castsi256_ps(equalBits));
    int index = _tzcnt_u32(equalMask);
    return index;
}