计算__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非常有效地为每个元素提供高位作为整数位掩码.(比较/ 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所以假元素不变.)