在C中检查全零缓冲区的更快方法？
我正在寻找一种更快的方法来完成这个：
int is_empty(char * buf, int size) { int i; for(i = 0; i < size; i++) { if(buf[i] != 0) return 0; } return 1; } 我知道我正在寻找一个微观优化，除非在极端情况下，但我知道存在更快的方法，我很好奇它是什么。
在许多体系结构中，比较1个字节花费的时间与4或8相同，有时甚至是16个.4个字节通常很容易（int或long），8个也是（long或long long）。 16或更高版本可能需要内联组装，例如，使用矢量单元。
此外，分支误预测真的很痛，它可能有助于消除分支机构。 例如，如果缓冲区几乎总是为空，而不是针对0测试每个块，而是将它们或它们一起测试最终结果。
一种潜在的方式，受到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]以获得相同的效果。
使用简单基准测试来测试缓冲区的zeroness的四个函数：
#include #include #include #include #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，则可以使用内联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 }
托马斯
编辑：更新托尼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大小的变量检查缓冲区（它应该对齐）。
脱离我的头脑（未编译的，未经测试的代码如下 – 这里几乎肯定至少有一个错误。这只是一般的想法）：
/* 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;
查看快速memcpy – 它可以适用于memcmp（或memcmp对照常量值）。
使用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个字节。
我看到很多人都说关于对齐问题会阻止你进行单词大小的访问，但这并不总是正确的。 如果您正在寻找可移植代码，那么这肯定是一个问题，但x86实际上会容忍错位访问。 例如，如果在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函数的配置文件信息然后重新编译它，它将愿意通过对齐检查将循环展开为字大小的比较。 您还可以使用-funroll-all-loops强制执行此行为
Hackers Delight的书籍/网站都是关于优化的C /汇编。 来自该网站的很多很好的参考资料也是相当及时的（AMD64，NUMA技术也是如此）。
有没有人提到展开循环？ 在任何这些循环中，循环开销和索引都将是重要的。
此外，缓冲区实际上是空的概率是多少？ 这是你必须检查所有这一切的唯一情况。 如果缓冲区中通常有一些垃圾，那么循环应该很早就停止，所以没关系。
如果你计划将它清零，如果它不为零，那么用memset(buf, 0, sizeof(buf))清除它可能会更快，无论它是否已经为零。
您在问题中表示您正在寻找最不可能的不必要的微优化。 在“正常”情况下，托马斯和其他人的ASM方法应该给你最快的结果。
不过，这是忘记了大局。 如果您的缓冲区非常大，那么从一开始就必须进行线性搜索绝对不是最快的方法。 假设您的cp替换非常适合查找大的连续空区域，但在数组末尾有一些非空字节。 所有线性搜索都需要读取整个数组。 另一方面，快速启发算法可以搜索任何非零元素，并且对于足够大的数据集，可以更快地中止。
因此，在进行任何类型的微优化之前，我会仔细查看缓冲区中的数据，看看是否能为您提供任何模式。 对于单个“1”，随机分布在缓冲区中，线性搜索（忽略线程/并行化）将是最快的方法，在其他情况下不一定如此。
初始C代码的内联汇编版本（没有错误检查，如果uiSize是== 0和/或数组未分配exception将生成。也许使用try {} catch()因为这可能比添加大量的更快检查代码。或者像我一样，尝试不调用具有无效值的函数（通常不起作用）。至少添加一个NULL指针检查和一个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的返回值，请告诉我。
如何从大小循环到零（更便宜的检查）：
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]; }
int is_empty(char * buf, int size) { return buf[0] == '\0'; }
如果你的缓冲区不是字符串，我认为这是检查的最快方法…
memcmp（）会要求你创建一个相同大小的缓冲区，然后使用memset将它全部设置为0.我怀疑那会更快……
将缓冲区转换为int并将其迭代，就像它是一个int数组而不是char数组一样。 迭代次数减少到：
size / sizeof(int)
您还可以展开循环。 在某些架构上， Duff的设备可能会带来收益，但这绝不是给定的。
编辑：答案不好
一种新颖的方法可能是
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); }
我想我有一个很好的解决方案。 创建一个虚拟归零数组并使用memcmp（）。 我就是做这个的。
最初的C算法几乎和VALID C一样慢。如果你坚持使用C然后尝试“while”循环而不是“for”：
int i = 0; while (i< MAX) { // operate on the string i++; }
这几乎是你用C编写的最快的一维字符串操作循环，除非你可以强制编译器将i放入一个带有“register”关键字的寄存器中，但我被告知这几乎总是被现代编译器所忽略。
同时搜索一个常量大小的数组来检查它是否为空是非常浪费的，并且0也不是空的，它是数组中的值。
更好的速度解决方案是使用动态数组（int * piBuffer）和存储当前大小的变量（unsigned int uiBufferSize），当数组为空时指针为NULL，uiBufferSize为0。这两个作为受保护的成员变量。 人们也可以轻松地为动态数组编写一个模板，它可以存储32位值，无论是基本类型还是指针，对于原始类型，没有任何方法可以测试“空”（我将其解释为“未定义”），但是您当然可以定义0来表示可用条目。 对于数组指针，您应该将所有条目初始化为NULL，并在刚刚释放该内存时将条目设置为NULL。 并且NULL表示“无所事事”，因此这是表示空的非常方便的方式。 不应该在真正复杂的算法中使用动态resize的数组，至少在开发阶段，不会有太多可能出错的事情。 首先应该首先使用STL容器（或经过良好测试的替代方案）实现算法，然后当代码工作时，可以将测试容器交换为简单的动态数组（如果您可以避免过于频繁地调整数组大小，则代码将同时执行更快，更安全。
对于复杂和酷的代码更好的解决方案是使用std :: vector或std :: map（或任何容器类STL，自行开发或第三方），具体取决于您的需求，但查看您的代码我会说std ::矢量就够了。 STL容器是模板，所以它们也应该非常快。 使用STL容器存储对象指针（总是存储对象指针而不是实际对象，复制每个条目的整个对象将真正搞乱你的执行速度）和动态数组用于更基本的数据（位图，声音等），即原始类型。 通常。
我通过研究x86汇编语言手册，独立提出了REPE SCASW解决方案，我同意使用这个字符串操作指令的例子是最快的。 具有单独的比较，跳转等指令的另一个汇编示例几乎肯定更慢（但仍然比初始C代码快得多，因此仍然是一个好的post），因为字符串操作是所有现代CPU中最高度优化的，他们甚至可能有自己的逻辑电路（谁都知道？）。
REPE SCASD不需要获取新指令也不需要增加指令指针，这就是像我这样的汇编新手可以提出的东西，而且最重要的是硬件优化，字符串操作对于几乎所有各种现代软件，特别是多媒体应用（复制PCM声音数据，未压缩的位图数据等），因此每次设计新的80x86芯片时，优化这些指令必须具有非常高的优先级。 我用它来制作一种新颖的2d精灵碰撞算法。
它说我不允许有意见，所以请考虑以下客观评估：现代编译器（UNMANAGED C / C ++，几乎所有其他东西都是托管代码而且速度很慢）都非常擅长优化，但它不能避免对于非常特定的任务，编译器会生成冗余代码。 人们可以看一下编译器输出的程序集，这样一个人就不必完全从头开始翻译一个复杂的算法，即使这样做很有趣（对于某些人而言）并且以更难的方式执行代码会更有价值，但是无论如何，使用“for”循环的算法，特别是关于字符串操作的算法，通常可以非常显着地优化，因为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
这是2行，它与C行完全相同（它使用寄存器而不是内存地址，这是更快，但可以说这不是与C行完全相同，但这是语义），多少这个例子的优化取决于现代编译器的优化程度，我对此一无所知，但基于实现最少和更快assembly线算法的目标的算法分析通常效果很好，我得到了很好的结果首先在C / C ++中实现算法而不关心优化，然后在汇编中进行转换和优化。 每条C线变成许多assembly线的事实往往使得一些优化非常明显，而且一些指令比其他指令更快：
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 ％组装，即使它只被调用一次:)或使用az旋转矩阵旋转俄罗斯方块90度：P任何人这样做真棒！
如果有人有一些建设性的纠正，这不是非常伤害，那么我很乐意听到它，我几乎完全由我自己编码，所以我并没有真正受到任何影响。 我曾经付过一个漂亮的加拿大游戏开发者来教我的Direct3d，虽然我可以很容易地读一本书，但是在某些领域有点高于我水平的另一个编码员的互动很有趣。
一般来说感谢良好的内容。 我想我会回答一些更简单的问题，稍稍回答一下。