更快地检查C中的全零缓冲区?

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

另外,一个分支的错误预测真的很伤人,这可能有助于消除分支。例如,如果缓冲区几乎总是空的,而不是针对0测试每个块,请将它们放在一起并测试最终结果。

在便携式C中很难表达这一点:铸造A char* 到 long* 违反严格的别名。但幸运的是你可以使用 memcpy 可移植地表示一个未对齐的多字节加载,该加载可以别名任何内容。编译器将把它优化到您想要的ASM。

例如,这个正在进行的工作实现( https://godbolt.org/z/3hXQe7 )在Godbolt编译器资源管理器上,您可以从连续加载两个命令中得到一个良好的内部循环(有一些启动开销)。 uint_fast32_t vars(通常是64位)和memcpy,然后检查 tmp1 | tmp2 ,因为许多CPU将根据或结果设置标志,所以这允许您检查两个字的价格为1。

要让它高效地为没有有效未对齐负载的目标编译,需要在启动代码中进行一些手动对齐,即使这样,gcc也可能不会内联 曼皮西 对于无法证明对齐的负载。

一种潜在的方式,灵感来自 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);
}

这基本上将缓冲区与自身进行比较,并进行初始检查,以查看第一个元素是否为零。这样,任何非零元素都会导致 MEMPP() 失败。我不知道这与使用另一个版本相比会有什么不同,但是我知道如果第一个元素不是零,它将很快失败(甚至在循环之前)。如果你最后更可能有拐杖,改变 buf[0] 到 buf[size] 以达到同样的效果。

使用简单的基准测试缓冲区零度的四个功能:

#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

如果您的程序是仅限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
}

托马斯

编辑:更新了Tony D的修复程序

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

$ 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

它可以通过逐字比较稍微优化一些,但是您需要担心对齐等问题。

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

上述基准( https://stackoverflow.com/a/1494499/2154139 )不准确。它们意味着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快得多。

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

尽可能使用int大小的变量检查缓冲区(应该对齐)。

在我的头脑中(下面是未编译、未测试的代码——几乎可以肯定这里至少有一个bug。这就给出了一般的想法):

/* 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;

使用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个字节。

这个 Hackers Delight 书籍/网站都是关于优化的C/assembly。该网站也提供了很多很好的参考资料,并且是最新的(amd64,numa技术也是)。

看看 fast memcpy -它可以适用于memcmp(或针对常量值的memcmp)。

我看到很多人都在谈论对齐问题,阻止你进行单词大小的访问,但这并不总是正确的。如果您希望生成可移植代码,那么这肯定是一个问题,但是x86实际上会容忍不对齐的访问。对于exmaple,只有在eflags中打开对齐检查时,x86才会失败(当然buf实际上不是字对齐)。

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函数的概要信息,然后重新编译它,它将愿意展开循环,通过对齐检查将其与word大小的比较进行比较。还可以使用-funcroll all循环强制执行此行为

有人提到展开循环吗?在任何这些循环中,循环开销和索引都是非常重要的。

另外,缓冲区实际上是空的概率是多少?这是唯一一个你必须检查的情况。 如果缓冲区中通常有一些垃圾,那么循环应该很早停止,所以这并不重要。

如果你计划把它清零,如果它不是零,用它清零可能会更快。 memset(buf, 0, sizeof(buf)) ,不管它是否已经为零。

你在你的问题中说,你正在寻找一个最可能不必要的微观优化。在“正常”情况下,Thomas和其他人的ASM方法应该给您最快的结果。

不过,这已经忘了大局。如果你的缓冲区真的很大,那么从一开始就进行线性搜索绝对不是最快的方法。假设您的CP替换非常擅长查找连续的大空区域,但在数组末尾有一些非空字节。所有线性搜索都需要读取整个数组。另一方面,一个受快速排序启发的算法可以搜索任何非零元素,并且可以更快地中止一个足够大的数据集。

所以在进行任何类型的微优化之前,我会仔细查看缓冲区中的数据,看看是否会给出任何模式。对于单个“1”,随机分布在缓冲区中的线性搜索(忽略线程/并行)将是最快的方法,在其他情况下不一定如此。

从大到零的循环怎么样(便宜的支票):

int is_empty(char * buf, int size) 
{
    while(size --> 0) {
        if(buf[i] != 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];
}

初始C代码的内联程序集版本(如果 uiSize 是 == 0 和/或数组未分配,将生成异常。也许用 try {} catch() 因为这可能比在代码中添加大量检查要快。或者像我一样,尽量不要调用具有无效值的函数(通常不起作用)。至少添加一个空指针检查和一个 size != 0 检查,这很容易。

 unsigned int IsEmpty(char* pchBuffer, unsigned int uiSize)
 {
    asm {
      push esi
      push ecx         

      mov esi, [pchBuffer]
      mov ecx, [uiSize]

      // add NULL ptr and size check here

      mov eax, 0

    next_char:
      repe scasb           // repeat string instruction as long as BYTE ptr ds:[ESI] == 0
                           // scasb does pointer arithmetic for BYTES (chars), ie it copies a byte to al and increments ESI by 1
      cmp cx,0             // did the loop complete?
      je all_chars_zero    // yes, array is all 0
      jmp char_not_zero    // no, loop was interrupted due to BYTE PTR ds:[ESI] != 0

    all_chars_zero:        
      mov eax, 1           // Set return value (works in MASM)
      jmp end  

    char_not_zero:
      mov eax, 0          // Still not sure if this works in inline asm

    end:
      pop ecx
      pop esi          
  }
}

这是写在飞行中,但它看起来足够正确,纠正是受欢迎的。如果有人知道如何设置内联asm的返回值,请务必告诉他。

我想我有一个很好的解决办法。 创建一个虚拟的零数组并使用memcmp()。我就是这么做的。

int is_empty(char * buf, int size)
{
   return buf[0] == '\0';
}

如果缓冲区不是字符串,我认为这是检查的最快方法…

memcmp()需要创建一个大小相同的缓冲区,然后使用memset将其全部设置为0。我怀疑那会更快…

编辑:错误答案

一种新颖的方法可能是

int is_empty(char * buf, int size) {
    char start = buf[0];
    char end = buff[size-1];
    buf[0] = 'x';
    buf[size-1] = '\0';
    int result = strlen(buf) == 0;
    buf[0] = start;
    buff[size-1] = end;
    return result;
}

为什么这么疯狂?因为strlen是更可能被优化的库函数之一。 存储和替换第一个字符是为了防止误报。存储和替换最后一个字符是为了确保它终止。

int is_empty(char * buf, int size) 
{
    int i, content=0;  
    for(i = 0; !content && i < size; i++)    
    {  
        content=content | buf(i);       // bitwise or  
    }  
    return (content==0);  
}

初始的C算法的速度和有效的C算法一样慢。 如果您坚持使用C,那么尝试“while”循环而不是“for”:

     int i = 0;
     while (i< MAX)
     {
        // operate on the string
        i++;
     }

这几乎是用C语言编写的最快的一维字符串操作循环,另外,如果你能强迫编译器用“register”关键字把我放入寄存器,但我听说现代编译器几乎总是忽略这一点。

同时搜索一个常量大小的数组来检查它是否为空是非常浪费的,而且0不是空的,它是数组中的值。

更好的速度解决方案是使用动态数组(int*pibuffer)和存储当前大小的变量(unsigned int uibuffersize),当数组为空时,指针为空,uibuffersize为0。用这两个作为受保护成员变量的类。还可以很容易地为动态数组编写模板,该模板将存储32位值(基元类型或指针),对于基元类型,实际上没有任何方法可以测试“空”(我将其解释为“未定义”),但您当然可以定义0来表示可用的项。对于数组指针,应将所有条目初始化为空,并在刚刚释放该内存时将条目设置为空。空值的意思是“无点”,所以这是表示空值的非常方便的方法。在真正复杂的算法中不应该使用动态调整大小的数组,至少在开发阶段不应该这样,因为有太多的事情会出错。至少应该首先使用STL容器(或经过良好测试的替代方法)实现算法,然后当代码工作时,可以将测试的容器替换为简单的动态数组(如果您可以避免过于频繁地调整数组的大小,则代码将更快且更安全。

对于复杂而酷的代码,更好的解决方案是根据您的需要使用std::vector或std::map(或任何容器类stl、国产或第三方),但看看您的代码,我会说std::vector就足够了。STL容器是模板,因此它们也应该非常快。使用stl容器来存储对象指针(总是存储对象指针而不是实际对象,为每个条目复制整个对象将真正扰乱您的执行速度)和动态数组来存储更基本的数据(位图、声音等)即基元类型。一般来说。

我通过研究x86汇编语言手册独立地提出了repe scasw解决方案,并且我同意使用这个字符串操作说明的示例是最快的。另一个具有单独比较、跳转等指令的汇编示例几乎肯定较慢(但仍然比最初的C代码快得多,因此仍然是一个很好的日志),因为字符串操作是所有现代CPU上最高度优化的操作之一,它们甚至可能有自己的逻辑电路(谁知道呢?).

repe scasd不需要获取新的指令,也不需要增加指令指针,这正是像我这样的装配新手所能想到的东西,而且最重要的是硬件优化,字符串操作对于几乎所有类型的现代软件,特别是多媒体应用程序(复制pcm声音数据,U压缩的位图数据等),因此每次设计新的80x86芯片时,优化这些指令必须具有很高的优先级。 我把它用于一个新的二维精灵碰撞算法。

它说我不允许有一个意见,所以考虑下面的一个客观的评估:现代编译器(非托管C/C++,几乎所有其他都是托管代码,并且慢如地狱)在优化方面是很好的,但是它不能避免,对于非常特定的任务,编译器生成冗余代码。我们可以看一下编译器输出的程序集,这样就不必从头开始翻译复杂的算法,即使这样做(对某些人来说)很有趣,而且用硬方法编写代码也更有好处,但是无论如何,使用“for”循环的算法,特别是字符串操作的算法,通常都是可选的。当for循环生成大量代码时,非常明显地进行了模拟,这通常是不需要的,例如: 对于(int i=1000;i>0;i--)dosomething();如果编译器不是很聪明(可能是),则此行生成6-10行程序集,但优化的程序集版本可以是:

      mov cx, 1000
    _DoSomething:
      // loop code....or call Func, slower but more readable
      loop _DoSomething

这是两行代码,它与C行代码完全相同(它使用寄存器而不是内存地址,这要快得多,但可以证明这与C行代码不完全相同,但这是语义),这个例子中的优化程度取决于现代编译器的优化程度,而我对此一无所知,但是算法和基于以最少的和更快的装配线来实现算法的目标的分析通常工作得很好,在C/C++中首先实现算法,而不关心优化,然后在汇编中翻译和优化它,我已经取得了很好的结果。每一条C线变成许多装配线的事实往往使一些优化变得非常明显,而且一些指令比其他指令更快:

      INC DX ; is faster than:
      ADD DX,1 ;if ADD DX,1 is not just replaced with INC DX by the assembler or the CPU
      LOOP ; is faster than manually decreasing, comparing and jumping
      REPxx STOSx/MOVSx/LODSx is faster than using cmp, je/jne/jea etc and loop
      JMP or conditional jumping is faster than using CALL, so in a loop that is executed VERY frequently (like rendering), including functions in the code so it is accessible with "local" jumps can also boost performance.

最后一位与这个问题非常相关,即快速字符串操作。 所以这篇文章并不是漫无目的的。

最后,以一种典型执行所需最少跳跃量的方式设计您的汇编算法。

另外,不要费心优化不经常调用的代码,使用探查器查看最经常调用的代码,并从中开始,任何每秒调用次数少于20次(并且完成速度远远超过1000 ms/20)的代码都不值得优化。查看它没有与计时器等同步,并且在完成后立即再次执行的代码。另一方面,如果你的渲染循环可以在一台普通的机器上执行100+fps,那么在经济上优化它是没有意义的,但是真正的编码人员喜欢编码,不关心经济性,他们将appstart()方法优化成100%的程序集,即使它只被调用一次:)或者使用z旋转矩阵将俄罗斯方块旋转90度:p任何这样做的人都是了不起的!

如果任何人有建设性的纠正,这不是很伤害,那么我很想听到它,我几乎完全自己编码,所以我没有真正接触到任何影响。我曾经付钱给一个优秀的加拿大游戏开发人员教我的Direct3D,虽然我可以很容易地读完一本书,但与另一个在某些领域略高于我水平的程序员的互动是很有趣的。

感谢大家的精彩内容。我想我会去回答一些简单的问题,再给我一点回报。