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

我编写了一种使用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;
    }
}

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

最佳答案

硬件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具有独立的功能位，因此从理论上讲，可能有一个带有AVX的CPU(或虚拟机)，但没有硬件popcnt，但实际上，我不必担心。 (popcnt随SSE4.2一起引入，而AVX暗示SSE4.2)

即使您希望将向量寄存器中的结果用于某些内容，vmovmskps/popcnt/movd可能还是比将0/-1元素与整数添加水平添加更好的顺序。这将需要3个shuffle/add步骤以将8个元素减少到1个，并且总和为负数。

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