快速检查字符数组是否为零的方法

Question

我在内存中有一个字节数组.查看数组中所有字节是否为零的最快方法是什么？

Answer 1

如今,如果不使用SIMD扩展(例如x86处理器上的SSE),您可能会迭代数组并将每个值与0进行比较.

在遥远的过去,为数组中的每个元素执行比较和条件分支(除了循环分支本身)将被认为是昂贵的,并且取决于您可以期望非零元素的频率(或早期)出现在数组中,您可能选择在循环内完全没有条件,仅使用按位或检测任何设置位并推迟实际检查直到循环完成:

int sum = 0;
for (i = 0; i < ARRAY_SIZE; ++i) {
  sum |= array[i];
}
if (sum != 0) {
  printf("At least one array element is non-zero\n");
}

然而,今天的流水线超标量处理器设计完成了分支预测,所有非SSE方法在循环中都是无法区分的.如果有的话,将每个元素与零进行比较并尽早摆脱循环(一旦遇到第一个非零元素),从长远来看,可能比sum |= array[i]方法(总是遍历整个数组)更有效率,除非,也就是说,您希望您的阵列几乎总是由零组成(在这种情况下,sum |= array[i]通过使用GCC 使该方法真正无分支-funroll-loops可以为您提供更好的数字 - 请参阅下面的Athlon处理器数字,结果可能会有所不同处理器型号和制造商.)

#include <stdio.h>

int a[1024*1024];

/* Methods 1 & 2 are equivalent on x86 */  

int main() {
  int i, j, n;

# if defined METHOD3
  int x;
# endif

  for (i = 0; i < 100; ++i) {
#   if defined METHOD3
    x = 0;
#   endif
    for (j = 0, n = 0; j < sizeof(a)/sizeof(a[0]); ++j) {
#     if defined METHOD1
      if (a[j] != 0) { n = 1; }
#     elif defined METHOD2
      n |= (a[j] != 0);
#     elif defined METHOD3
      x |= a[j];
#     endif
    }
#   if defined METHOD3
    n = (x != 0);
#   endif

    printf("%d\n", n);
  }
}

$ uname -mp
i686 athlon
$ gcc -g -O3 -DMETHOD1 test.c
$ time ./a.out
real    0m0.376s
user    0m0.373s
sys     0m0.003s
$ gcc -g -O3 -DMETHOD2 test.c
$ time ./a.out
real    0m0.377s
user    0m0.372s
sys     0m0.003s
$ gcc -g -O3 -DMETHOD3 test.c
$ time ./a.out
real    0m0.376s
user    0m0.373s
sys     0m0.003s

$ gcc -g -O3 -DMETHOD1 -funroll-loops test.c
$ time ./a.out
real    0m0.351s
user    0m0.348s
sys     0m0.003s
$ gcc -g -O3 -DMETHOD2 -funroll-loops test.c
$ time ./a.out
real    0m0.343s
user    0m0.340s
sys     0m0.003s
$ gcc -g -O3 -DMETHOD3 -funroll-loops test.c
$ time ./a.out
real    0m0.209s
user    0m0.206s
sys     0m0.003s

Answer 2

如果您对使用内联汇编感到满意,这是一个简短的快速解决方案.

#include <stdio.h>

int main(void) {
    int checkzero(char *string, int length);
    char str1[] = "wow this is not zero!";
    char str2[] = {0, 0, 0, 0, 0, 0, 0, 0};
    printf("%d\n", checkzero(str1, sizeof(str1)));
    printf("%d\n", checkzero(str2, sizeof(str2)));
}

int checkzero(char *string, int length) {
    int is_zero;
    __asm__ (
        "cld\n"
        "xorb %%al, %%al\n"
        "repz scasb\n"
        : "=c" (is_zero)
        : "c" (length), "D" (string)
        : "eax", "cc"
    );
    return !is_zero;
}

如果您不熟悉汇编,我将解释我们在这里做什么:我们将字符串的长度存储在寄存器中,并要求处理器扫描字符串为零(我们通过设置低8位来指定它累加器的数量,即%%al为零),在每次迭代时减小所述寄存器的值,直到遇到非零字节.现在,如果字符串全为零,则寄存器也将为零,因为它已减少length次数.但是,如果遇到非零值,则检查零的"循环"会过早终止,因此寄存器不会为零.然后我们获取该寄存器的值,并返回其布尔否定.

对此进行分析得出以下结果:

$ time or.exe

real    0m37.274s
user    0m0.015s
sys     0m0.000s


$ time scasb.exe

real    0m15.951s
user    0m0.000s
sys     0m0.046s

(两个测试用例在大小为100000的数组上运行了100000次.or.exe代码来自Vlad的回答.在两种情况下都消除了函数调用.)