有什么快速方法可以计算大型连续数组中零值字节的数量？ (或者相反，非零字节的数量。)总的来说，我的意思是 2¹⁶ 字节或更大。数组的位置和长度可以由任何字节对齐组成。

朴素的方式:

int countZeroBytes(byte[] values, int length)
{
    int zeroCount = 0;
    for (int i = 0; i < length; ++i)
        if (!values[i])
            ++zeroCount;

    return zeroCount;
}

对于我的问题，我通常只维护zeroCount 并根据对values 的特定更改更新它。但是，我希望在对 values 进行任意批量更改后重新计算 zeroCount 的快速通用方法。我敢肯定有一种有点笨拙的方法可以更快地完成这项工作，但唉，我只是一个笨拙的新手。

编辑:一些人询问过零检查数据的性质，所以我将对其进行描述。 (不过，如果解决方案仍然是通用的，那就太好了。)

基本上，设想一个由 voxels 组成的世界(例如 Minecraft )，程序生成的地形被分成立方 block ，或者有效地索引为三维数组的内存页面。每个体素都作为与独特 Material (空气、石头、水等)相对应的独特字节进行自由加权。许多 block 仅包含空气或水，而其他 block 包含 2-4 个大量体素(泥土、沙子等)的不同组合，实际上 2-10% 的体素是随机异常值。大量存在的体素往往沿每个轴高度聚集。

不过，零字节计数方法似乎在许多不相关的场景中都有用。因此，需要一个通用的解决方案。

最佳答案

这是 How to count character occurrences using SIMD 的特例对于 c=0，要计算匹配项的 char(字节)值。请参阅 Q&A，了解优化良好的手动矢量化 AVX2 实现 char_count (char const* vector, size_t size, char c); 具有比这更紧密的内部循环，避免将每个 vector 减少为 0/-1 分别匹配标量。

这将以 O(n) 的形式进行，因此您能做的最好的事情就是减少常量。一种快速修复方法是删除分支。如果零是随机分布的，这会给出与我下面的 SSE 版本一样快的结果。这可能是因为 GCC 向量化了这个循环。但是，对于零的长时间运行或零的随 secret 度小于 1%，下面的 SSE 版本仍然更快。

int countZeroBytes_fix(char* values, int length) {
    int zeroCount = 0;
    for(int i=0; i<length; i++) {
        zeroCount += values[i] == 0;
    }
    return zeroCount;
}

我最初认为零点的密度很重要。事实证明并非如此，至少对于 SSE 而言并非如此。无论密度如何，使用 SSE 都要快得多。

编辑:实际上，它确实取决于密度，只是零的密度必须小于我的预期。1/64 个零(1.5% 的零)是 1/4 中的一个零SSE 注册所以分支预测不能很好地工作。然而，1/1024 零(0.1% 零)更快(见时间表)。

如果数据有很长的零序列，SIMD 甚至更快。

您可以将 16 个字节打包到 SSE 寄存器中。然后，您可以使用 _mm_cmpeq_epi8 一次将所有 16 个字节与零进行比较。然后，为了处理零运行，您可以对结果使用 _mm_movemask_epi8，大多数情况下它将为零。在这种情况下，您可以获得高达 16 的加速(对于前半部分 1 和后半部分 0，我获得了超过 12 倍的加速)。

这是一个以秒为单位的 2^16 字节的时间表(重复 10000 次)。

                     1.5% zeros  50% zeros  0.1% zeros 1st half 1, 2nd half 0
countZeroBytes       0.8s        0.8s       0.8s        0.95s
countZeroBytes_fix   0.16s       0.16s      0.16s       0.16s
countZeroBytes_SSE   0.2s        0.15s      0.10s       0.07s

您可以在 http://coliru.stacked-crooked.com/a/67a169ddb03d907a 查看最后 1/2 零的结果

#include <stdio.h>
#include <stdlib.h>
#include <emmintrin.h>                 // SSE2
#include <omp.h>

int countZeroBytes(char* values, int length) {
    int zeroCount = 0;
    for(int i=0; i<length; i++) {
        if (!values[i])
            ++zeroCount;
    }
    return zeroCount;
}

int countZeroBytes_SSE(char* values, int length) {
    int zeroCount = 0;
    __m128i zero16 = _mm_set1_epi8(0);
    __m128i and16 = _mm_set1_epi8(1);
    for(int i=0; i<length; i+=16) {
        __m128i values16 = _mm_loadu_si128((__m128i*)&values[i]);
        __m128i cmp = _mm_cmpeq_epi8(values16, zero16);
        int mask = _mm_movemask_epi8(cmp);
        if(mask) {
            if(mask == 0xffff) zeroCount += 16;
            else {
                cmp = _mm_and_si128(and16, cmp); //change -1 values to 1
                //hortiontal sum of 16 bytes
                __m128i sum1 = _mm_sad_epu8(cmp,zero16);
                __m128i sum2 = _mm_shuffle_epi32(sum1,2);
                __m128i sum3 = _mm_add_epi16(sum1,sum2);
                zeroCount += _mm_cvtsi128_si32(sum3);
            }
        }
    }
    return zeroCount;
}

int main() {
    const int n = 1<<16;
    const int repeat = 10000;
    char *values = (char*)_mm_malloc(n, 16);
    for(int i=0; i<n; i++) values[i] = rand()%64;  //1.5% zeros
    //for(int i=0; i<n/2; i++) values[i] = 1;
    //for(int i=n/2; i<n; i++) values[i] = 0;
    
    int zeroCount = 0;
    double dtime;
    dtime = omp_get_wtime();
    for(int i=0; i<repeat; i++) zeroCount = countZeroBytes(values,n);
    dtime = omp_get_wtime() - dtime;
    printf("zeroCount %d, time %f\n", zeroCount, dtime);
    dtime = omp_get_wtime();
    for(int i=0; i<repeat; i++) zeroCount = countZeroBytes_SSE(values,n);
    dtime = omp_get_wtime() - dtime;
    printf("zeroCount %d, time %f\n", zeroCount, dtime);       
}

关于c++ - 快速计算数组中零值字节的数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20927710/