计算 __mm256 向量中非零条目数的最快方法是什么？

Question

我编写了一种算法，使用 Intel 内部函数并行执行多个单精度运算。我的算法每次迭代的结果是单个 256 位向量 (__m256) 中非零条目的数量。

例如：

 00000000  FFFFFFFF  00000000  00000000  00000000  FFFFFFFF  FFFFFFFF  FFFFFFFF

其中迭代的结果是 4。

计算向量中非零条目数的最快方法是什么？

目前我正在做这样的事情：

float results[8];
_mm256_storeu_ps(results, result_vector);

int count = 0;
for (uint32_t idx = 0; idx < 8; ++idx)
{
    if (results[idx] != 0)
    {            
        ++count;
    }
}

这种方法工作得很好，但我想知道是否有更有效的方法，也许是不涉及商店的方法。

Answer 1

硬件 popcnt 指令是您最好的选择。它很快，并且 vmovmskps 也非常有效地为您提供每个元素的高位作为整数位掩码。（compare / movemask 是对矢量比较结果进行分支的标准方法，或将其用于）。

movemask / popcnt 很有用，可以根据存储的元素数量（洗牌后）增加目标指针。

#include <immintrin.h>

// use only with compare-results.
// or to count elements with their sign-bit set
unsigned count_true(__m256 v) {
    unsigned mask = _mm256_movemask_ps(v);
    return _mm_popcnt_u32(mask);
}

popcnt 有一个独立于 AVX 的功能位，所以理论上可能有一个 CPU（或虚拟机）带有 AVX 但不是硬件 popcnt，但实际上我不会担心的。 (popcnt是SSE4.2引入的，AVX隐含SSE4.2)

即使您希望将结果存储在矢量寄存器中，vmovmskps / popcnt / movd 的顺序也可能比使用整数加法水平添加 0 / -1 元素更好。这将需要 3 shuffle/add 个步骤才能将 8 个元素减少到 1 个，并且您将得到一个负数。

我主要提到这一点是因为在某些情况下将比较结果视为整数 0 / -1 很有用。例如要有条件地增加计数器向量，cmpps / psubd 就可以了。（0 + x = x，所以假元素不变。）

计算 __mm256 向量中非零条目数的最快方法是什么？

What is the fastest way to count the number of nonzero entries in an __mm256 vector?

algorithm

vector

simd

avx

avx2