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

Question

我编写了一种算法，使用英特尔内部函数并行执行多个单精度运算。我的算法每次迭代的结果是单个 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 是在矢量比较结果上分支的标准方法，或将其用于 index a lookup table of shuffle masks )。

movemask/popcnt 很有用 when left-packing , 根据您存储的元素数量(洗牌后)增加目标指针。

#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 个洗牌/添加步骤才能将 8 个元素减少到 1 个，并且您将得到一个负数。

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