Phi*_*lip 7 c c++ bit-manipulation
什么是计算大型连续数组中零值字节数的快速方法？(或者相反,非零字节的数量.)大,我的意思是2 16字节或更大.数组的位置和长度可以包含任何字节对齐.
天真的方式:
int countZeroBytes(byte[] values, int length)
{
int zeroCount = 0;
for (int i = 0; i < length; ++i)
if (!values[i])
++zeroCount;
return zeroCount;
}
对于我的问题,我通常只是zeroCount根据具体的更改维护和更新它values.但是,我希望zeroCount在发生任意批量更改后,有一种快速,通用的重新计算方法values.我确信有一种比较快速的方法可以更快地实现这一点,但是,唉,我只是一个新手twiddler.
编辑: 一些人已经询问数据的性质是零检查,所以我将描述它.(不过,如果解决方案仍然普遍,那就太好了.)
基本上,设想一个由体素组成的世界(例如Minecraft),将程序生成的地形分隔成立方块,或者将有效的内存页面编入索引为三维数组.每个体素都是飞行加权,作为对应于独特材料(空气,石头,水等)的唯一字节.许多块仅包含空气或水,而其他块包含大量2-4种体素(污垢,沙子等)的不同组合,有效地2-10%的体素是随机异常值.大量存在的体素往往沿着每个轴高度聚集.
但是,似乎零字节计数方法在许多不相关的场景中都很有用.因此,需要一般的解决方案.
我提供了这个 OpenMP 实现，它可以利用每个处理器本地缓存中的数组来实际并行读取它。
nzeros_total = 0;
#pragma omp parallel for reduction(+:nzeros_total)
for (i=0;i<NDATA;i++)
{
if (v[i]==0)
nzeros_total++;
}
一个快速基准测试，包括使用朴素实现（与OP在问题中编写的相同）运行1000次for循环与OpenMP实现，也运行1000次，为两种方法花费最佳时间，数组为65536零值元素概率为 50% 的整数，在 QuadCore CPU 上使用 Windows 7，并使用 VStudio 2012 Ultimate 进行编译，得到以下数字：
DEBUG RELEASE
Naive method: 580 microseconds. 341 microseconds.
OpenMP method: 159 microseconds. 99 microseconds.
注意：我已经尝试过，#pragma loop (hint_parallel(4))但显然，这并没有导致天真的版本执行得更好，所以我的猜测是编译器已经应用了这种优化，或者根本无法应用。而且，并#pragma loop (no_vector)没有导致幼稚版本的性能变差。
这将成为O（n），因此您能做的最好的事情就是减少常数。一种快速的解决方法是删除分支。如果将零随机分配，则产生的结果与下面的SSE版本一样快。这可能是由于GCC对这个循环进行了矢量化。但是，对于长时间运行的零或小于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的速度要快得多。
编辑：实际上，它确实取决于密度，只是零的密度必须小于我的预期。 1/64个零（1.5％的零）是1/4个SSE寄存器中的一个零，因此分支预测效果不佳。但是，1/1024零（0.1％零）更快（请参阅时间表）。
如果数据长期运行零，则SIMD甚至更快。
您可以将16个字节打包到SSE寄存器中。然后，您可以使用一次将所有16个字节与零进行比较_mm_cmpeq_epi8。然后，要处理零次运行，您可以使用_mm_movemask_epi8结果，大多数情况下它将为零。在这种情况下，您可以将速度提高到16（对于前半部分1和后半部分零，我获得了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);
}