在C语言中检查大量数据是否为空的最快方法是什么？

Question

我有一大堆数据，大约4MB。现在想检查其中的所有位是否都为0。

例如： 这里是数据:

void* data = malloc(4*1024*1024);
memset(data, 0, 4*1024*1024);

检查它所有的位是否为0。这是我的解决方案，但速度不够快：

int dataisnull(char* data, int length)
{
    int i = 0;
    while(i<length){
        if (data[i]) return 0;
        i++;
    }
    return 1;
}

这段代码可能在性能方面有一些需要改进的地方。例如，在32/64位机器上，每次检查4/8个字节可能会更快。

那么我想知道最快的方法是什么？

- Ringo_D

---

你需要在循环中增加data的值吗？ - Andy Turner

使用 SIMD 来加速处理数据。 - Dai

此外，您不需要执行 if(data[i]) return 0; 吗？ - Magisch

如果您想在分配时将数据清零，那么使用calloc比使用malloc更快且效率更高。 - phuclv

可能是 Faster approach to checking for an all-zero buffer in C? 的重复问题，尽管该问题并没有很好的答案 :/ 另外还发现了一个相关问题 Using C/Intel assembly, what is the fastest way to test if a 128-byte memory block contains all zeros?。 - Peter Cordes

Answer 1

您可以一次处理多个字节并展开循环：

int dataisnull(const void *data, size_t length) {
    /* assuming data was returned by malloc, thus is properly aligned */
    size_t i = 0, n = length / sizeof(size_t);
    const size_t *pw = data;
    const unsigned char *pb = data;
    size_t val;
#define UNROLL_FACTOR  8
#if UNROLL_FACTOR == 8
    size_t n1 = n - n % UNROLL_FACTOR;
    for (; i < n1; i += UNROLL_FACTOR) {
        val = pw[i + 0] | pw[i + 1] | pw[i + 2] | pw[i + 3] |
              pw[i + 4] | pw[i + 5] | pw[i + 6] | pw[i + 7];
        if (val)
            return 0;
    }
#endif
    val = 0;
    for (; i < n; i++) {
        val |= pw[i];
    }
    for (i = n * sizeof(size_t); i < length; i++) {
        val |= pb[i];
    }
    return val == 0;
}

根据您的具体问题，早期或晚期检测非零值可能更有效： - 如果全零情况最常见，则应将所有位累积到“val”累加器中，并仅在末尾测试。 - 如果全零情况很少见，则应更经常检查非零值。

上面展开的版本是一个妥协，根据size_t的大小每64或128个字节测试一次非零值。

根据您的编译器和处理器，通过取消展开或增加展开来获得更好的性能。您还可以使用特定架构可用的内在函数来利用向量类型，但这样做会使代码不太可移植。

请注意，该代码未验证数据指针的正确对齐方式： - 这无法以可移植的方式完成。 - 它假设数据是通过malloc或类似方法分配的，因此对于任何类型都正确对齐。

与往常一样，请对不同的解决方案进行基准测试，看是否真的有所不同。这个函数可能根本不是瓶颈，编写复杂的函数来优化罕见情况是适得其反的，它使代码难以阅读，更容易包含错误，并且维护起来更困难。例如，如果更改内存分配方案或使用静态数组，则关于数据对齐的假设可能不成立，那么该函数可能会引起未定义的行为。

- chqrlie

---

如果数据的有效类型不是size_t或具有相同符号的类型，则该代码将在C99、C11或C14中引发未定义行为。需要注意的是，根据C99的别名规则，int和long是不同的类型；即使两者与size_t大小相同，它们中最多只有一个对于别名规则而言是等效的类型。您的方法在大多数合理的C方言中都是可行的，但在标准定义的C99、C11或C14中不适用。 - supercat

编译器非常复杂和不可预测。我担心由于编译器无法在编译时验证传入指针的对齐方式，它将产生昂贵的指令（许多快速指令仅适用于对齐地址）。此外，在不同级别的优化下查看汇编代码可能会揭示编译器已经尝试展开循环并分组分支（推测执行）。 - orion

循环展开是否真的提高了速度？这似乎是编译器应该非常擅长的事情。GCC有-funroll-loops选项可以自动完成此操作。 - Davidmh

@supercat：我确认上述核心在DS9K上可能无法按预期工作：我甚至无法在那里尝试测试它，因为其中央单元尚未从上次UB中恢复过来，守护程序仍在其中飞进飞出。 - chqrlie

@PeterCordes 主循环仅在第 18 至 40 行之间。 - orion

Answer 2

以下代码用于检查第一个字节是否符合要求，以及后续的每一对字节是否相同。

int check_bytes(const char * const data, size_t length, const char val)
{
    if(length == 0) return 1;
    if(*data != val) return 0;
    return memcmp(data, data+1, length-1) ? 0 : 1;
}

int check_bytes64(const char * const data, size_t length, const char val)
{
    const char * const aligned64_start = (char *)((((uintptr_t)data) + 63) / 64 * 64);
    const char * const aligned64_end = (char *)((((uintptr_t)data) + length) / 64 * 64);
    const size_t start_length = aligned64_start - data;
    const size_t aligned64_length = aligned64_end - aligned64_start;
    const size_t end_length = length - start_length - aligned64_length;

    if (!check_bytes(data, start_length, val)) return 0;
    if (!check_bytes(aligned64_end, end_length, val)) return 0;

    return memcmp(aligned64_start, aligned64_start + 64, aligned64_length-64) ? 0 : 1;
}

一种更为详细的函数版本可能应该传递缓存行对齐指针给memcmp，并手动检查其余块(而不仅仅是第一个字节)。当然，您需要在特定硬件上进行性能分析，以查看此方法与其他方法相比是否有速度优势。如果有人怀疑这是否有效，请参考ideone。

- Nicu Stiurca

---

这个解决方案并不是很高效：memcmp给出的指针是未对齐的，它不能使用比较多字节的优化代码来提高效率。此外，从内存中比较字节的效率要低于将字节与常量值进行比较。我没有投反对票，但我理解那些投反对票的人。 - chqrlie

@chqrlie 不一定，这取决于 memcmp 的实现方式。其中一些会检查指针是否对齐，并相应地更改算法。 - Jabberwocky

@chqrlie，我认为对于特定平台而言，与主题发起者提供的解决方案相比，memcmp应该得到更多的优化。此外，问题涉及由malloc分配的内存块，因此可以使用memcmp来考虑mem对齐。因此，我认为答案仍然非常好。也许应该考虑所提出的解决方案在特定任务中的适用性，但这是不在主题范围内的。 - dmi

他的意思是由于 data, data+1，两个指针不能够对齐。 - user694733

@supercat 严格的别名规则（或任何其他语言规则）不适用于 C 标准库函数的实现。只要 memcmp 的行为符合标准，内部代码就可以使用任何类型。这些函数甚至不必用 C 编写。 - user694733

Answer 3

我曾为自己编写了以下函数。它假设要检查的数据是常量块大小的倍数，并且对于机器字缓冲区进行了适当的对齐。如果在您的情况下没有给出这些条件，也不难单独循环前几个和后几个字节，仅使用优化的函数检查大块。 （严格来说，即使数组已正确对齐但数据是由与 unsigned long 不兼容的任何类型编写的，它也是未定义行为。但是，我相信您可以通过此处谨慎打破规则来取得很大进展。）

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool
is_all_zero_bulk(const void *const p, const size_t n)
{
  typedef unsigned long word_type;
  const size_t word_size = sizeof(word_type);
  const size_t chunksize = 8;
  assert(n % (chunksize * word_size) == 0);
  assert((((uintptr_t) p) & 0x0f) == 0);
  const word_type *const frst = (word_type *) p;
  const word_type *const last = frst + n / word_size;
  for (const word_type * iter = frst; iter != last; iter += chunksize)
    {
      word_type acc = 0;
      // Trust the compiler to unroll this loop at its own discretion.
      for (size_t j = 0; j < chunksize; ++j)
        acc |= iter[j];
      if (acc != 0)
        return false;
    }
  return true;
}

该函数本身并不是非常智能。其主要思想如下：

• 使用大的无符号机器字进行数据比较。
• 通过将具有恒定迭代计数的内部循环分解出来，启用循环展开。
• 通过将字与累加器OR在一起，并且仅在几次迭代后与零进行比较，从而减少分支数量。
• 这还应该使编译器轻松生成使用SIMD指令的向量化代码，这对于此类代码确实是所需的。

额外的非标准调整包括使用__attribute__ ((hot))注释函数并使用__builtin_expect(acc != 0, false)。当然，最重要的是打开编译器的优化选项。

- 5gon12eder

---

请注意，在C99、C11和C14中，如果数据以除word_type或其有符号等价类型之外的任何类型写入，则该函数将调用未定义行为。也许有一天标准委员会将承认，一种良好的语言应包括使用比"char"更大的类型来操作"原始内存"的手段，但目前还没有。 - supercat

@supercat 是的，我知道。这是一种“祈求好运”的方法。 - 5gon12eder