使用 __builtin_popcount 或其他内在函数来处理 _mm256_movemask_pd 比较位图的结果?

Using __builtin_popcount or other intrinsics to process the result of a _mm256_movemask_pd compare bitmap?

我有这段代码,我想最终实现本文中的位掩码评估算法的修改版本 - 使用 SIMD 调整树结构以进行处理 说明

#include <stdint.h>
#include <immintrin.h>
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdalign.h>

int main(void)
{
    __m256d avx_creg, res, avx_sreg;
    int bitmask;
    uint64_t key = 503;

    avx_sreg = _mm256_castsi256_pd(_mm256_set1_epi64x(key));
    alignas(32) uint64_t v[4]; 
    _mm256_store_pd((double*)v, avx_sreg);
    printf("v2_u64: %lld %lld %lld %lld\n", v[0], v[1],v[2],v[3]);
    uint64_t b[4]= {500,505,510,515};
    avx_creg = _mm256_castsi256_pd(
                   _mm256_loadu_si256((__m256i const *)&b));
    //
    alignas(32) uint64_t v1[4]; 
    _mm256_store_pd((double*)v1, avx_creg);
    printf("v2_u64: %lld %lld %lld %lld\n", v1[0], v1[1],v1[2],v1[3]);

    res      = _mm256_cmp_pd(avx_sreg, avx_creg, 30);
    bitmask  = _mm256_movemask_pd(res);
    int mmask = __builtin_popcount(bitmask);
    printf("mmask is %d\n",mmask);

    return 0;
}

上面的代码将mmask的值打印为1。所以这里是我完全不清楚的地方。我应该将数字“1”解释为数组索引,其中数组元素大于输入键,还是指设置的位数?

例如,如果我将密钥更改为 499,mmask 将打印为 0。

最后,如果我将密钥更改为 517,则 mmask 的值为 4。

有人可以澄清一下吗?我还有第二个问题,如果有人建议,我可以将其作为一个单独的问题提出。是否有可能从 AVX 内在函数中获取大于给定输入键的所有值?

movemask 通过从向量中获取每个元素的高位来生成整数位图。将其打印为十六进制或 base-2 以便更好地查看。

如果您只关心 0 与非零计数,只需检查 if(bitmask != 0)

if(bitmask == 0x0f) 检查它们是否全部正确。 (4 元素向量的 4 位)。


使用 popcount 找出有多少是正确的。 __builtin_popcnt 计算其输入中设置位的数量。

使用__builtin_ctz 查找第一个比较结果为真的元素的位置。 (如果向量是从内存中加载的,则从低内存地址到高内存地址计数)。请注意 __builtin_ctz 仅对非零输入有意义。例如在 memchr 循环中,只有在 _mm256_movemask_epi8(cmp_result) == 0 上跳出搜索循环后才能使用 ctz 来确定此向量中存在匹配项。 (epi8 因为我说的是字节搜索循环,不像你的 packed-double 比较)。

如果您已经需要 AVX2,您可能希望使用 BMI1 _lzcnt_u32(bitmask) 在位掩码 = 0 上获得定义明确的结果(32 个前导零)。 (因为我认为所有 AVX2 CPU 都有 BMI1。)


要迭代匹配项,您可以使用清除最低设置位操作,如果仍有任何位设置,则 ctz 到找出哪一个。参见 Clearing the lowest set bit of a number

x & (x-1) 将有效地编译为 BMI1 blsr 指令,如果您在启用 BMI1 的情况下进行编译,例如-march=haswell.

(为了让它正常工作,你肯定想要一个与你的向量元素大小匹配的 movemask,所以对于 64 位整数,将你的向量转换为 _pd 这样你就可以使用 _mm256_movemask_pd.)