在C语言中，更快速地检查是否存在全零缓冲区的方法？

Question

我正在寻找更快的方法来完成这个任务：

int is_empty(char * buf, int size) 
{
    int i;
    for(i = 0; i < size; i++) {
        if(buf[i] != 0) return 0;
    }
    return 1;
}

我意识到我正在寻找微小的优化，除了在极端情况下不必要之外，但我知道存在一种更快的方法，我很好奇那是什么。

- Rob

---

笑话回答：int is_empty(char *buf, int size) { memset(buf, 0, size); return 1; } - Chris Lutz

顺便提一下，对于表示数组大小的值，您应该真正使用size_t而不是int。 - Chris Lutz

听起来需要使用达夫设备来完成这项工作！ - Michael Burr

@Rob - 你很可能会受到磁盘限制，不应该把重点放在这上面。在现代CPU上，10毫秒的磁盘读写操作相当于数百万个时钟周期。优化从磁盘读取数据的方式将会带来更好的结果。 - Michael

@Rob：http://kernelnewbies.org/Linux_2_6_28 看看1.13 FIEMAP。 - sambowry

Answer 1

在许多体系结构中，比较1个字节与4或8个字节甚至16个字节的时间相同。4个字节通常很容易（int或long），8个字节也是如此（long或long long）。16个字节或更高的字节可能需要内联汇编，例如使用矢量单元。

此外，分支预测错误会对性能造成很大影响，消除分支可能有所帮助。例如，如果缓冲区几乎总是为空，则不要针对每个块测试0，而是将它们进行位或运算，并测试最终结果。

---

在便携式C语言中表达这个问题很困难：将char*转换为long*会违反严格的别名。但幸运的是，您可以使用memcpy来表达一个不对齐的多字节加载，它可以别名任何东西。编译器将对其进行优化以得到所需的汇编代码。例如，这个正在进行的实现(https://godbolt.org/z/3hXQe7)在Godbolt编译器探索器上显示，您可以通过使用memcpy来加载两个连续的uint_fast32_t变量（通常为64位），并检查tmp1 | tmp2来获得良好的内部循环（有一些启动开销），因为许多CPU将根据OR结果设置标志，因此这让您以一个单词的价格检查两个单词。为了使它在没有有效未对齐加载的目标上高效编译，需要在启动代码中进行一些手动对齐，即使如此，gcc也可能不会内联那些无法证明对齐的加载的memcpy。

- derobert

---

+1 是关于分支信息的，因为海报正在寻求微观优化。 - Ben M

请注意，将1字节的组作为单个整数值进行比较会引起对齐问题，这使得安全地执行此操作变得困难。 - Chris Lutz

他所说的不是预测循环，而是预测测试缓冲区内容是否为零（并通过减少比较次数来改进）。 - Stephen Canon

对齐不会让事情变得太复杂。逐字节处理，直到达到所需的对齐位置，然后进入主循环使用更大的比较，最后在完成时使用一些单字节比较来清理剩余项。仅当处理可能具有不同相对对齐的多个缓冲区时，对齐才会带来实质性的困难。 - Stephen Canon

@StephenCanon 没错，在 simd 编程中，这甚至有一个名字。但是像你所说的那样，这远非“简单”。这会导致循环中到处都有分支使用，这在处理小缓冲区时会影响性能。 - v.oddou

Answer 2

灵感来自于Kieveli被否决的主意，有一个潜在的方法：

int is_empty(char *buf, size_t size)
{
    static const char zero[999] = { 0 };
    return !memcmp(zero, buf, size > 999 ? 999 : size);
}

请注意，您不能使此解决方案适用于任意大小。您可以这样做：

int is_empty(char *buf, size_t size)
{
    char *zero = calloc(size);
    int i = memcmp(zero, buf, size);
    free(zero);
    return i;
}

但任何动态内存分配都会比您所拥有的要慢。第一个解决方案之所以更快，只是因为它可以使用memcmp()，这将由库编写者用汇编语言进行手动优化，并且比您在C中编写的任何内容都要快。

编辑：其他人没有提到的一种优化，基于早期对缓冲区处于状态X的“可能性”的观察：如果缓冲区不为空，则很可能在开头或结尾时不为空？如果在结尾处可能会有垃圾，您可以从结尾开始检查，并可能看到一些良好的性能提升。

编辑2：感谢评论区的Accipitridae：

int is_empty(char *buf, size_t size)
{
    return buf[0] == 0 && !memcmp(buf, buf + 1, size - 1);
}

这基本上是将缓冲区与其自身进行比较，首先检查第一个元素是否为零。这样，任何非零元素都会导致 memcmp() 失败。我不知道这与使用其他版本相比如何，但我知道如果第一个元素为非零值，它将很快失败（甚至在我们进入循环之前）。如果您更有可能在末尾产生无用数据，请将 buf[0] 更改为 buf[size] 以获得相同的效果。

- Chris Lutz

---

另一方面，如果编译器不太蠢笨，那么智能 C 语言版本和 memcmp 版本都会受到内存带宽的限制，但 C 语言版本需要读取的内存量只有 一半。我预测，没有尝试的情况下，C 语言版本将比 memcmp 版本快至少 50%。 - Pascal Cuoq

a) 你正在比较哪些“C”版本？ b) 为什么memcmp()会花费更长时间？ - Chris Lutz

不必分配内存，你可以使用： buf[0]==0 && !memcmp(buf, buf+1, size-1)。 - Accipitridae

@Pascal - 通过计时，第一个memcmp()版本的速度几乎与OP版本相同，始终略微（如0.001秒）更快。 - Chris Lutz

你可能也想把那个static数组声明为const。这个版本可以轻松地进行内联，这可能是另一个微小的优势。 - caf

对于移位后的memcmp版本，您可以将其转换为int *并使用sizeof(int)而不是1。值得进行性能分析，也许领先的答案会说得更多。 - fuzzyTew

Answer 3

上面给出的基准测试结果 (https://dev59.com/QnI_5IYBdhLWcg3wK_3E#1494499) 不准确。它们暗示 func3 比其他选项快得多。

但是，如果您更改测试顺序，使 func3 先于 func2，那么您将看到 func2 更快。

在单个执行中运行组合基准时要小心...副作用很大，特别是当重用相同变量时。最好运行隔离的测试！

例如，将其更改为：

int main(){
  MEASURE( func3 );
  MEASURE( func3 );
  MEASURE( func3 );
  MEASURE( func3 );
  MEASURE( func3 );
}

给我：

func3: zero          14243
func3: zero           1142
func3: zero            885
func3: zero            848
func3: zero            870

对我来说，这真的很烦人，因为我看不出func3如何比func2快那么多。

(抱歉回答不是作为评论，没有声望)

- InfinitoTaco

Answer 4

四个用于测试缓冲区是否为零的函数，带有简单基准测试：

#include <stdio.h> 
#include <string.h> 
#include <wchar.h> 
#include <inttypes.h> 

#define SIZE (8*1024) 
char zero[SIZE] __attribute__(( aligned(8) ));

#define RDTSC(var)  __asm__ __volatile__ ( "rdtsc" : "=A" (var)); 

#define MEASURE( func ) { \ 
  uint64_t start, stop; \ 
  RDTSC( start ); \ 
  int ret = func( zero, SIZE ); \ 
  RDTSC( stop ); \ 
  printf( #func ": %s   %12"PRIu64"\n", ret?"non zero": "zero", stop-start ); \ 
} 


int func1( char *buff, size_t size ){
  while(size--) if(*buff++) return 1;
  return 0;
}

int func2( char *buff, size_t size ){
  return *buff || memcmp(buff, buff+1, size-1);
}

int func3( char *buff, size_t size ){
  return *(uint64_t*)buff || memcmp(buff, buff+sizeof(uint64_t), size-sizeof(uint64_t));
}

int func4( char *buff, size_t size ){
  return *(wchar_t*)buff || wmemcmp((wchar_t*)buff, (wchar_t*)buff+1, size/sizeof(wchar_t)-1);
}

int main(){
  MEASURE( func1 );
  MEASURE( func2 );
  MEASURE( func3 );
  MEASURE( func4 );
}

我的旧电脑的结果：

func1: zero         108668
func2: zero          38680
func3: zero           8504
func4: zero          24768

- sambowry

---

有趣的是，但是func3和func4需要一些细微的修正来解决非整数倍字长和对齐问题。 - Jason S

请参考@dissasorted在下面的回答，对这个基准测试进行观察：https://dev59.com/QnI_5IYBdhLWcg3wK_3E#29382742 - Andrew Smart

这可能会在未映射页面之前的1字节缓冲区上出现故障。但是，利用汇编优化的库函数是一个有趣的想法。检查16或32字节偏移可能更适合大输入，这样库函数就不需要执行不对齐的SIMD向量操作。然而，*(uint64_t*)buff 违反了严格别名规则 - 您需要使用 memcpy 加载它或声明GNU C may_alias 版本的类型：为什么glibc的strlen需要如此复杂才能快速运行？ - Peter Cordes

请参阅如何从C++中获取x86_64的CPU周期计数？。但是，对于64位代码中的rdtsc，“=A”不会产生您想要的结果。此外，请注意CPU频率预热效应：一开始很慢，然后变快。 - Peter Cordes

Answer 5

如果您的程序仅适用于x86或x64，您可以轻松使用内联汇编进行优化。REPE SCASD指令将扫描缓冲区直到找到非EAX dword为止。由于没有等效的标准库函数，因此没有编译器/优化器能够使用这些指令（如Sufian的代码所证实）。从头开始，如果您的缓冲区长度为4字节对齐，则可以使用类似以下的内容（MASM语法）：

_asm {
   CLD                ; search forward
   XOR EAX, EAX       ; search for non-zero
   LEA EDI, [buf]     ; search in buf
   MOV ECX, [buflen]  ; search buflen bytes
   SHR ECX, 2         ; using dwords so len/=4
   REPE SCASD         ; perform scan
   JCXZ bufferEmpty:  ; completes? then buffer is 0
}

Tomas

编辑：已根据Tony D的修改更新

- Tomas

---

最佳答案 - 获得赞同。您能否向我展示如何将此嵌入式ASM放入GCC / Clang C程序中？（这需要GAS语法吗？）是否有使用unsigned long longs的64位版本？ - fadedbee

+1 实用的方法 - 小问题：应该是 LEA EDI, ... 而不是 ESI，并且缺少 CLD 来保证方向标志被清除。 - Tony Delroy

小心使用内联汇编，因为它无法被编译器静态分析，并会在块前后引起完整的内存栅栏！在某些情况下，这可能非常糟糕。 - v.oddou

不幸的是，repe scasd 不比普通循环快。在英特尔CPU中，字符串存储和复制指令（rep stos和rep movs）具有优化的微码实现，但repe scas和repe cmps则没有。此外，@TonyD：所有常规ABI都要求在函数进入时清除方向标志。cld是一条指令的浪费。 - Peter Cordes

Answer 6

对于如此简单的事情，您需要查看编译器正在生成的代码。

$ gcc -S -O3 -o empty.s empty.c

同时需要汇编的内容：

        .text
        .align 4,0x90
.globl _is_empty
_is_empty:
        pushl       %ebp
        movl        %esp, %ebp
        movl        12(%ebp), %edx  ; edx = pointer to buffer
        movl        8(%ebp), %ecx   ; ecx = size
        testl       %edx, %edx
        jle L3
        xorl        %eax, %eax
        cmpb        $0, (%ecx)
        jne L5
        .align 4,0x90
L6:
        incl        %eax            ; real guts of the loop are in here
        cmpl        %eax, %edx
        je  L3
        cmpb        $0, (%ecx,%eax) ; compare byte-by-byte of buffer
        je  L6
L5:
        leave
        xorl        %eax, %eax
        ret
        .align 4,0x90
L3:
        leave
        movl        $1, %eax
        ret
        .subsections_via_symbols

这个非常优化。循环执行三件事情:

• 增加偏移量
• 将偏移量与大小进行比较
• 比较内存中基址+offset处的字节数据是否为0

可以通过逐个字比较来进一步优化，但是需要考虑对齐等问题。

当其他方法都失败时，先进行测量，不要猜测。

- Sufian

---

通过使用字符串指令REP SCASx，它可以进行更多的优化。 - Tomas

@Tomas：只有通过使用repe scasd一次检查多个字节。此汇编代码有点糟糕。它使用了两个寄存器的寻址模式，但仍然执行比较和分支，而不是使用inc设置的标志位。更好的方法是获取指向数组末尾的指针，并计算一个负索引向零递增。此外，Sufian：一次处理一个字或双字会大大优化，而不仅仅是轻微的优化。对于大缓冲区，可以提高两倍（字）或四倍（双字）。此外，现代英特尔CPU 显然无法微融合2个寄存器的寻址模式。 - Peter Cordes

Answer 7

尽可能使用int大小的变量来检查缓冲区（它应该对齐）。

以下是未编译、未经测试的代码（我随口说的，这里几乎肯定至少有一个错误。这只是给出了一般想法）：

/* check the start of the buf byte by byte while it's unaligned */
while (size && !int_aligned( buf)) {
    if (*buf != 0) {
        return 0;
    }

    ++buf;
    --size;
}


/* check the bulk of the buf int by int while it's aligned */

size_t n_ints = size / sizeof( int);
size_t rem = size / sizeof( int);

int* pInts = (int*) buf;

while (n_ints) {
    if (*pInt != 0) {
        return 0;
    }

    ++pInt;
    --n_ints;
}


/* now wrap up the remaining unaligned part of the buf byte by byte */

buf = (char*) pInts;

while (rem) {
    if (*buf != 0) {
        return 0;
    }

    ++buf;
    --rem;
}

return 1;

- Michael Burr

Answer 8

使用x86架构，你可以使用SSE一次性测试16字节：

#include "smmintrin.h" // note: requires SSE 4.1

int is_empty(const char *buf, const size_t size) 
{
    size_t i;
    for (i = 0; i + 16 <= size; i += 16)
    {
        __m128i v = _mm_loadu_si128((m128i *)&buf[i]);
        if (!_mm_testz_si128(v, v))
            return 0;
    }
    for ( ; i < size; ++i)
    {
        if (buf[i] != 0)
            return 0;
    }
    return 1;
}

这个程序可能通过循环展开进一步优化。

在现代带有AVX的x86 CPU上，你甚至可以使用256位SIMD，每次测试32个字节。

- Paul R

---

您可能会从一次测试64B（一个缓存行）中看到小的改进，通过将它们与OR语句一起使用并在结果上使用ptest。 （ptest有2个微操作，不与分支进行宏融合）。 每次迭代使用多个“por”指令应该有助于饱和两个加载端口，因为有循环开销。 还要注意，如果大小> = 16，则清理循环可以是对以最后一个字节结尾的非对齐负载的单个ptest。 这个负载与最后一个主循环迭代重叠是可以接受的，因为测试是否为零是幂等的。 - Peter Cordes

@PaulR：我的错误，未对齐的加载是可以的。你可能会在第一批中使用未对齐的加载获得更好的性能，然后对齐指针并在数组的其余部分使用对齐的加载。 - chqrlie

@chqrlie：你说的没错，但在现代CPU上，使用不对齐的加载时，影响很小。确保尽可能对齐仍然是值得的，但与旧CPU相比，不对齐加载的惩罚要少得多。 - Paul R

Answer 9

循环从尺寸到零（检查更便宜）如何？

int is_empty(char * buf, int size) 
{
    while(size --> 0) {
        if(buf[size] != 0) return 0;
    }
    return 1;
}

必须注意的是，我们可能无法超越编译器，因此请在编译器中启用最激进的速度优化，并假设您不太可能变得更快。

或者使用指针处理所有内容（未经测试，但很可能表现良好）：

int is_empty(char* buf, int size)
{
    char* org = buf;

    if (buf[size-1] == 1)
        return 0;

    buf[size-1] = 1;
    while(! *buf++);
    buf--;

    return buf == org[size-1];
}

- Aloys

---

我同意你的第一个评论（循环到零）。另一个微不足道的优化是删除索引的使用，即用 if (*buf++) return 0; 替换 if 语句。 - wovano

你的第二种方法很有趣！当然，如果允许写入缓冲区的话（通常情况下不允许），它才是有效的。而且代码中存在一些错误：当 size == 0 时会出现越界访问，buf[size-1] 的原始内容没有恢复，最后一条语句缺少一个 &。我也会避免对 buf[size-1] 进行不必要的地址计算（三次）。但我喜欢这种超越传统思维的方式，这种解决方案在某些场景下可能相对简单和高效 :) - wovano

Answer 10

我看到很多人说对齐问题会阻止你进行字大小的访问，但这并不总是正确的。如果你想编写可移植的代码，那么这肯定是一个问题，然而x86实际上可以容忍未对齐的访问。例如，只有在EFLAGS中打开对齐检查（当然buf实际上没有对齐）时，这才会在x86上失败。

int is_empty(char * buf, int size) {
 int i;
 for(i = 0; i < size; i+= 4) {
   if(*(int *)(buf + i) != 0) {
     return 0;
   }   
 }

 for(; i < size; i++) {
   if(buf[i] != 0) 
     return 0;
 }

 return 1;
}

无论编译器是否能够将原始循环转换为基于单词比较的循环以处理对齐问题，但在任何正常的优化级别下，它都不会这样做，因为缺乏信息。对于尺寸较小的情况，以这种方式展开循环会使代码变慢，并且编译器希望保守一些。

解决此问题的方法是利用基于配置文件的优化。如果您让GCC获取有关is_empty函数的配置文件信息，然后重新编译它，它将愿意将循环展开为基于单词的比较，并进行对齐检查。您还可以通过-funroll-all-loops强制执行此行为。

- Falaina