我有一个字节数组，保存在内存中。如何最快地判断数组中所有的字节是否都为零？
快速检查字符数组是否为零的方法
21
- Claudiu
1
请仅返回翻译后的文本：dup of https://dev59.com/QnI_5IYBdhLWcg3wK_3E - 把友情留在无盐
7个回答
30
现在，除了在x86处理器上使用SSE之类的SIMD扩展外，您最好迭代数组并将每个值与0进行比较。
在遥远的过去，为数组中的每个元素执行比较和条件分支（除了循环分支本身）被认为是昂贵的，取决于您可以期望非零元素何时（或早期）出现在数组中，您可能选择完全不使用循环内的条件语句，仅使用按位或运算符检测任何设置的位，并将实际检查推迟到循环完成后。
然而，随着当今的流水线超标量处理器设计完备分支预测，所有非SSE方法在循环内几乎无法区分。如果说有什么不同的话，那就是将每个元素与零进行比较并且在循环早期跳出（一旦遇到第一个非零元素即可）可能会在长期内比
在遥远的过去，为数组中的每个元素执行比较和条件分支（除了循环分支本身）被认为是昂贵的，取决于您可以期望非零元素何时（或早期）出现在数组中，您可能选择完全不使用循环内的条件语句，仅使用按位或运算符检测任何设置的位，并将实际检查推迟到循环完成后。
int sum = 0;
for (i = 0; i < ARRAY_SIZE; ++i) {
sum |= array[i];
}
if (sum != 0) {
printf("At least one array element is non-zero\n");
}
然而，随着当今的流水线超标量处理器设计完备分支预测，所有非SSE方法在循环内几乎无法区分。如果说有什么不同的话，那就是将每个元素与零进行比较并且在循环早期跳出（一旦遇到第一个非零元素即可）可能会在长期内比
sum |= array[i]方法更有效（该方法总是遍历整个数组），除非您希望数组几乎总是由零组成（在这种情况下，通过使用GCC的-funroll-loops使sum |= array[i]方法真正无分支可能会给您更好的结果--请参见下面针对Athlon处理器的数字，结果可能因处理器型号和制造商而异）。#include <stdio.h>
int a[1024*1024];
/* Methods 1 & 2 are equivalent on x86 */
int main() {
int i, j, n;
# if defined METHOD3
int x;
# endif
for (i = 0; i < 100; ++i) {
# if defined METHOD3
x = 0;
# endif
for (j = 0, n = 0; j < sizeof(a)/sizeof(a[0]); ++j) {
# if defined METHOD1
if (a[j] != 0) { n = 1; }
# elif defined METHOD2
n |= (a[j] != 0);
# elif defined METHOD3
x |= a[j];
# endif
}
# if defined METHOD3
n = (x != 0);
# endif
printf("%d\n", n);
}
}
$ uname -mp
i686 athlon
$ gcc -g -O3 -DMETHOD1 test.c
$ time ./a.out
real 0m0.376s
user 0m0.373s
sys 0m0.003s
$ gcc -g -O3 -DMETHOD2 test.c
$ time ./a.out
real 0m0.377s
user 0m0.372s
sys 0m0.003s
$ gcc -g -O3 -DMETHOD3 test.c
$ time ./a.out
real 0m0.376s
user 0m0.373s
sys 0m0.003s
$ gcc -g -O3 -DMETHOD1 -funroll-loops test.c
$ time ./a.out
real 0m0.351s
user 0m0.348s
sys 0m0.003s
$ gcc -g -O3 -DMETHOD2 -funroll-loops test.c
$ time ./a.out
real 0m0.343s
user 0m0.340s
sys 0m0.003s
$ gcc -g -O3 -DMETHOD3 -funroll-loops test.c
$ time ./a.out
real 0m0.209s
user 0m0.206s
sys 0m0.003s
- vladr
3
线程怎么样了？它会让程序运行更快吗？ - Kobor42
线程设置很繁琐，除非是非常大的数组，否则不值得这样做。（参见https://dev59.com/3m865IYBdhLWcg3wNLw7） - Taiki
不要忘记，如果您没有将数组分配到NUMA部分中，它将会序列化访问，即使它在L3缓存中也是如此。 - v.oddou
11
如果您愿意使用内联汇编，这里是一个简短快速的解决方案。
#include <stdio.h>
int main(void) {
int checkzero(char *string, int length);
char str1[] = "wow this is not zero!";
char str2[] = {0, 0, 0, 0, 0, 0, 0, 0};
printf("%d\n", checkzero(str1, sizeof(str1)));
printf("%d\n", checkzero(str2, sizeof(str2)));
}
int checkzero(char *string, int length) {
int is_zero;
__asm__ (
"cld\n"
"xorb %%al, %%al\n"
"repz scasb\n"
: "=c" (is_zero)
: "c" (length), "D" (string)
: "eax", "cc"
);
return !is_zero;
}
如果您不熟悉汇编语言，我将解释一下我们在这里做什么：我们将字符串的长度存储在一个寄存器中，并要求处理器扫描该字符串以查找零（我们通过将累加器的低8位设置为零来指定此操作，即%%al），每次迭代减少该寄存器的值，直到遇到非零字节。现在，如果字符串全部为零，则该寄存器也将为零，因为它已经被递减了length次。然而，如果遇到非零值，则检查零的"循环"会提前终止，因此该寄存器将不为零。然后，我们获取该寄存器的值，并返回其布尔否定。
对此进行分析得到以下结果：
$ time or.exe
real 0m37.274s
user 0m0.015s
sys 0m0.000s
$ time scasb.exe
real 0m15.951s
user 0m0.000s
sys 0m0.046s
这两个测试用例都在大小为100000的数组上运行了100000次。 or.exe 代码来自Vlad的答案。 在这两种情况下，函数调用均已被消除。
- susmits
4
如果我们采用位运算的方法并结合线程，会怎样呢？你能把这个任务交给线程池吗？ - Kobor42
repz scasb速度慢（每次1字节；快速字符串和ERMSB微码只能加速无条件的rep stos/movs，请参见https://agner.org/optimize/指令表）。更糟糕的是，**您的内联汇编约束存在错误/不安全**。它修改了RDI，因此您需要一个`"+D"`输出/输入约束。它还读取了不是`"m"`输入操作数的内存，并且您没有`"memory"`破坏。请参阅[如何指示内联ASM参数指向的内存可能被使用？](https://stackoverflow.com/q/56432259) - 一个虚拟的“m”约束可以避免内存破坏。 - undefined如果你要做任何与x86特定相关的事情，请使用SSE2的内嵌函数（_mm_loadu_si128 / _mm_cmpeq_epi8 / _mm_movemask_epi8）。或者可以使用_mm_or_si128将一些向量合并在一起，以分摊cmp/movemask的开销（或者使用SSE4.1的ptest函数）。 - undefined
关于您的分析结果，也许您在编译时禁用了优化？即使是在2010年的编译器没有自动向量化的情况下，使用标量代码应该仍然能够以每个时钟周期1字节的速度运行，除非前端瓶颈是早期没有uop缓存的CPU的问题。无论如何，每个周期1字节的速度是一个非常低的标准，很容易实现更快的速度。 - undefined
4
如果要在32位C中完成此操作，可能只需要将数组循环为32位整数数组并与0进行比较，然后确保末尾的内容也为0。
- WhirlWind
6
1请注意，这在技术上取决于特定的平台，但我无法想到任何不适用的平台。+1 - Billy ONeal
Billy - 我同意，但我猜想应该没问题，因为已标记为32位。 - WhirlWind
5实际上，只需对字符使用简单的for循环，并使用“-funroll-loops”进行编译，编译器将为您完成正确的操作。 - J-16 SDiZ
@Billy ONeal：如果“integer”表示
int，那么它在使用符号-幅度整数的任何平台上都无法工作，因为0和-0的位模式不能同时都是全零，但它们比较相等。所以你会得到错误的结果。我暂时想不起来这样的平台叫什么名字，而且我也不指望会用到这样的平台。你可以通过加载无符号整数来解决这个特定问题，或者更好的方法是使用uint32_t，因为它不允许有填充位。 - Steve Jessop4作为一名专业的游戏程序员，我已经花费了多年时间来优化代码。@J-16提出的问题需要一个快速的版本。我可以告诉你，在编写代码时如果只是简单地使用像“-funroll-loops”这样的编译器标志，通常只有约1%的机会能够生成最优化的代码。大多数情况下，你需要帮助编译器进行优化。 - Adisak
此答案假设数组的长度是整数大小的倍数，并且数组已对齐。强制对齐和填充并不总是可行的。有时候，您需要在一个数组中搜索零，而您无法控制其长度和对齐方式，并且其两端相邻的字节包含不相关的数据。 - kasperd
4
将检查的内存一分为二，并将第一部分与第二部分进行比较。
a.如果有任何不同，那么就不可能完全相同。
b.如果没有差异，则重复第一半。
最坏情况下需要2*N。内存效率高且基于memcmp。
不确定是否应该在实际生活中使用，但我喜欢自我比较的想法。
它适用于奇数长度。你明白为什么吗？:-)
bool memcheck(char* p, char chr, size_t size) {
// Check if first char differs from expected.
if (*p != chr)
return false;
int near_half, far_half;
while (size > 1) {
near_half = size/2;
far_half = size-near_half;
if (memcmp(p, p+far_half, near_half))
return false;
size = far_half;
}
return true;
}
- Kobor42
7
你还应该检查第一个元素是否为0，否则它会对任何每个字节相同的东西返回true，不是吗？ - Claudiu
1它还有
n + n/2 + n/4 + ... 次操作，这最多只是 2n，因此我认为它仍然是 O(n)... - Claudiu抱歉，有一些编辑。现在已经最终了。Clau，第一个字符已经被检查过了。“return *p == chr;”。你关于O（N）的想法是正确的。 - Kobor42
是的，因为有带额外参数填充的memset，那为什么memcheck也不能有呢？谁会用memset除了清零之外的操作呢？同样的人可能会使用memcheck进行其他操作。 :-) - Kobor42
3这个算法比较每个字节，并进行许多乱序存储器加载。由于它是
O(2n-1)=O(n)+O(n/2)+O(n/4)+...，因此只比较每个字节（或单词/双字等）与寄存器的东西会更快。任何算法都将受到内存限制（对于正面案例），因此最小化内存周期将带来最大的收益。memcmp()试图隐藏复杂性；它本身对于内存访问是O(n)。 - artless noise显示剩余2条评论
3
如果数组足够大，现代CPU的限制因素将是对内存的访问。确保提前合理地使用缓存预取功能（例如__dcbt或prefetchnta，如果你很快就要再次使用缓冲区，可以使用prefetch0），距离需要较远（即1-2K）。您还需要像SIMD或SWAR这样的方法来一次处理多个字节。即使是32位单词，其操作次数也会比每个字符版本少4倍。我建议展开或运算并将它们馈送到“或”树中。您可以在我的代码示例中看到我的意思--这利用了超标量能力，通过利用没有那么多中间数据依赖项的操作，同时执行两个整数操作（或者运算）。我使用8个树大小（4x4，然后2x2，然后1x1），但您可以根据CPU架构中有多少自由寄存器来扩展到更大的数量。
以下示例伪代码为内部循环（无引言/尾声）使用32位int，但您可以使用MMX / SSE或其他可用于您的位数（64/128位）。如果已将块预取到高速缓存中，则这将非常快速。此外，如果您的缓冲区未对齐，则可能需要在之前进行不对齐检查，并在之后进行检查，以确保您的缓冲区（在对齐后）不是32字节长度的倍数。
以下示例伪代码为内部循环（无引言/尾声）使用32位int，但您可以使用MMX / SSE或其他可用于您的位数（64/128位）。如果已将块预取到高速缓存中，则这将非常快速。此外，如果您的缓冲区未对齐，则可能需要在之前进行不对齐检查，并在之后进行检查，以确保您的缓冲区（在对齐后）不是32字节长度的倍数。
const UINT32 *pmem = ***aligned-buffer-pointer***;
UINT32 a0,a1,a2,a3;
while(bytesremain >= 32)
{
// Compare an aligned "line" of 32-bytes
a0 = pmem[0] | pmem[1];
a1 = pmem[2] | pmem[3];
a2 = pmem[4] | pmem[5];
a3 = pmem[6] | pmem[7];
a0 |= a1; a2 |= a3;
pmem += 8;
a0 |= a2;
bytesremain -= 32;
if(a0 != 0) break;
}
if(a0!=0) then ***buffer-is-not-all-zeros***
我建议将“一行”值的比较封装到一个函数中，然后使用缓存预取将其展开几次。
- Adisak
2
在ARM64上测试了两种实现方式，一种使用循环并在false时提前返回，另一种则将所有字节进行OR操作：
int is_empty1(unsigned char * buf, int size)
{
int i;
for(i = 0; i < size; i++) {
if(buf[i] != 0) return 0;
}
return 1;
}
int is_empty2(unsigned char * buf, int size)
{
int sum = 0;
for(int i = 0; i < size; i++) {
sum |= buf[i];
}
return sum == 0;
}
结果：
所有结果，单位为微秒：
is_empty1 is_empty2
MEDIAN 0.350 3.554
AVG 1.636 3.768
仅出现错误结果：
is_empty1 is_empty2
MEDIAN 0.003 3.560
AVG 0.382 3.777
仅返回真实结果：
is_empty1 is_empty2
MEDIAN 3.649 3,528
AVG 3.857 3.751
简介：仅在假结果概率非常小的数据集中，使用ORing算法的第二个算法由于省略了分支而表现更佳。否则，提前返回显然是优于的策略。
- Ortwin Gentz
1
Rusty Russel的
memeqzero非常快。它重复使用memcmp来进行重负载操作：https://github.com/rustyrussell/ccan/blob/master/ccan/mem/mem.c#L92。- zbyszek
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接