如何在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向量中提取一个掩码(基本上，它从每个车道收集顶部位)。一旦你得到了，你可以做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;
}