更快地检查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;
}

我意识到我正在寻找一种微观优化,除非在极端情况下,但我知道存在更快的方法,我很好奇它是什么.

Answer 1

在许多体系结构中,比较1个字节花费的时间与4或8相同,有时甚至是16个.4个字节通常很容易(int或long),8个也是(long或long long).16或更高版本可能需要内联组装,例如,使用矢量单元.

此外,分支误预测真的很痛,它可能有助于消除分支机构.例如,如果缓冲区几乎总是为空,而不是针对0测试每个块,而是将它们或它们放在一起并测试最终结果.

在便携式C中表达这一点很难:强制转换char*为long*违反严格的别名.但幸运的是,您可以使用memcpy可移植的方式表达可以对任何内容进行别名的未对齐多字节加载.编译器会根据您的需要优化它.

例如,Godbolt编译器资源管理器中的这项正在进行的实现(https://godbolt.org/z/3hXQe7)表明,您可以通过加载两个连续的uint_fast32_t变量来获得良好的内部循环(带有一些启动开销)64位)用memcpy然后检查tmp1 | tmp2,因为许多CPU会根据OR结果设置标志,所以这可以让你检查两个单词的价格.

如果没有高效的未对齐负载,有效地为目标进行编译需要在启动代码中进行一些手动对齐,即使gcc可能也没有内联memcpy无法证明对齐的负载.

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]获得相同的效果.

Answer 3

使用简单基准测试来测试缓冲区的zeroness的四个函数:

#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

Answer 4

如果您的程序仅限x86或仅x64,则可以使用内联assambler轻松优化.REPE SCASD指令将扫描缓冲区,直到找到非EAX双字.

由于没有等效的标准库函数,因此编译器/优化器可能无法使用这些指令(由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
}

托马斯

编辑:更新Tony D的修复

Answer 5

上面给出的基准(/sf/answers/104614961/)并不准确.他们暗示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快得多.

(为答案道歉,而不是评论,没有声誉)

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

这是非常优化的.循环做三件事:

• 增加偏移量
• 将偏移量与大小进行比较
• 将base + offset中内存中的字节数据与0进行比较

通过逐字逐句比较可以略微优化它,但是你需要担心对齐等等.

当所有其他方法都失败时,先测量,不要猜测.

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;

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个字节.