如何确定内存段是否全部为零

Question

我是说，我使用malloc分配了一段内存，可能是1k，也可能是20字节... 假设指针为pMem 我如何知道pMem所引用的内容是否全部为Zero或\0？ 我知道memcmp，但第二个参数应该是另一个内存地址... 谢谢

- StevenWang

Answer 1

正如其他人已经建议的那样，你可能想要使用memset或calloc。

但是如果你真的想要检查一个内存区域是否全为零，可以将其与自身向左移一位后进行比较。

bool allZero = pMem[0] == '\0' && !memcmp(pMem, pMem + 1, length - 1);

其中length表示您想要归零的字节数。

- Mark Byers

---

好的，采用较慢的方式调用memcmp函数（针对两个具有不同对齐方式的缓冲区），以便进行两倍所需的内存访问，适用于一个内存受限任务... 真是个好主意！ - Pascal Cuoq

帕斯卡，讽刺并不必要。 - Rob Kennedy

那是一个比简单的for循环慢得多的东西。 - Kirill V. Lyadvinsky

虽然聪明，但这个答案比必要的慢。一个简单的for循环是正确的答案（无论是手写的还是来自“算法”）。你必须查看内存中的每个字节才能知道每个字节的值是否为0。唯一不成立的方式是如果你可以做出假设，比如“如果这个字节是0，则下一个字节也是0”。当然，这只是一个例子，在你的情况下并不适用。 - GManNickG

你忽略了处理器自身的缓存。你无法准确猜测这种情况，必须进行测量。这应该很简单，只是我现在没有时间。如果没有其他人来做，我回家后会去做。 - Mark Byers

Answer 2

由于Mark的回答引起了一些争议：

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#ifndef count
    #define count 1000*1000
#endif
#ifndef blocksize
    #define blocksize 1024
#endif

int checkzeros(char *first, char *last) {
    for (; first < last; ++first) {
        if (*first != 0) return 0;
    }
    return 1;
}

int main() {
    int i;
    int zeros = 0;

    #ifdef EMPTY
        /* empty test loop */
        for (i = 0; i < count; ++i) {
            char *p = malloc(blocksize);
            if (*p == 0) ++zeros;
            free(p);
        }
    #endif

    #ifdef LOOP
        /* simple check */
        for (i = 0; i < count; ++i) {
            char *p = malloc(blocksize);
            if (checkzeros(p, p + blocksize)) ++zeros;
            free(p);
        }
    #endif

    #ifdef MEMCMP
        /* memcmp check */
        for (i = 0; i < count; ++i) {
            char *p = malloc(blocksize);
            if (*p == 0 && !memcmp(p, p + 1, blocksize - 1)) ++zeros;
            free(p);
        }
    #endif

    printf("%d\n", zeros);
    return 0;
}

测试结果（Cygwin，Windows XP，Core 2 Duo T7700 @ 2.4 GHz）：

$ gcc-4 cmploop.c -o cmploop -pedantic -Wall -O2 -DEMPTY && time ./cmploop
1000000

real    0m0.500s
user    0m0.405s
sys     0m0.000s

$ gcc-4 cmploop.c -o cmploop -pedantic -Wall -O2 -DLOOP && time ./cmploop
1000000

real    0m1.203s
user    0m1.233s
sys     0m0.000s

$ gcc-4 cmploop.c -o cmploop -pedantic -Wall -O2 -DMEMCMP && time ./cmploop
1000000

real    0m2.859s
user    0m2.874s
sys     0m0.015s

所以，对于我来说，memcmp所花费的时间大约是(2.8-0.4)/(1.2-0.4)=3倍长。看到其他人的结果会很有意思-我的所有malloc分配的内存都被清零，因此我每次比较都得到最坏情况下的时间。

对于更小的块（和更多的块），比较时间不太显著，但memcmp仍然较慢：

$ gcc-4 cmploop.c -o cmploop -pedantic -Wall -O2 -DEMPTY -Dblocksize=20 -Dcount=10000000 && time ./cmploop
10000000

real    0m3.969s
user    0m3.780s
sys     0m0.030s

$ gcc-4 cmploop.c -o cmploop -pedantic -Wall -O2 -DLOOP -Dblocksize=20 -Dcount=10000000 && time ./cmploop
10000000

real    0m4.062s
user    0m3.968s
sys     0m0.015s

$ gcc-4 cmploop.c -o cmploop -pedantic -Wall -O2 -DMEMCMP -Dblocksize=20 -Dcount=10000000 && time ./cmploop
10000000

real    0m4.391s
user    0m4.296s
sys     0m0.015s

我对此稍感惊讶。我原以为memcmp至少会竞争一下，因为我预计它会被内联并优化大小在编译时已知的情况。即使将其更改为在开始处测试int，然后进行16字节的memcmp，以避免不对齐的最坏情况，也没有明显加快速度。

- Steve Jessop

---

+1 用实际测试来验证！等我有时间的时候，我也会尝试制作自己的基准测试。顺便问一下，你使用的是什么CPU/操作系统？这可能也会产生影响。 - Mark Byers

同样适用于memcpy，顺便说一下... :( - xtofl

“outrageous”的例子：int i = <something>; int j; memcpy(&j, &i, sizeof(int)); return j;。这个memcpy被优化成了无操作，它只是在第一步中使用EAX来处理i。好吧，在这个问题中没有寄存器技巧的机会，也没有可以消除的多余变量，但我希望那种有能力做16字节同对齐的memcmp比较的人也能够在4个字里完成（再加上一点点工作来确定差异的符号，如果有的话）。或者其他的什么方法。 - Steve Jessop

是的，并/或在释放之前将一些数据写入它们。请查看malloc实现是否在分配之前清除它们，或者仅仅因为它是进程的新鲜存储器而清零。如果数据不是零，几乎任何事情都应该非常快，因为它可以提前退出（尽管参见Per Ekman的答案，其中一个不退出，并且受益于零情况）。 - Steve Jessop

在一个没有填充零的缓冲区（从new char[]中随机垃圾），memcmp仍然比循环字符快近2倍，但与循环整数完全相同。 - Pavel Minaev

Answer 3

如果你正在测试它，并且只有在它为零时才使用它，那么请注意你会遇到竞争条件，因为@Mark Byers建议的方法没有原子测试/设置操作。在这种情况下，很难正确地得出逻辑。

如果你想要在它不为零时将其清零，那么直接将它设置为零会更快。

- Douglas Leeder

Answer 4

C ++解决方案：

bool all_zeroes = 
  (find_if( pMem, pMem+len, bind2nd(greater<unsigned char>(), 0)) == (pMem+len));

- Kirill V. Lyadvinsky

Answer 5

正如您所注意到的那样，memcmp用于比较一块内存和另一块内存。如果您有另一块您已经知道全是零的内存块，那么您可以使用该参考块与候选块进行比较，以查看它们是否匹配。

不过，听起来您没有另一块内存块。您只有一块，并且想知道它是否全部为零。标准库并没有提供这样的函数，但编写自己的函数很容易：

bool is_all_zero(char const* mem, size_t size)
{
  while (size-- > 0)
    if (*mem++)
      return false;
  return true;
}

如果您想分配一个新的内存块并且希望它立即全部为零，则使用 calloc 而不是 malloc 。如果您有一个要设置为全部为零的内存块，则使用 memset 或 std :: fill 。

- Rob Kennedy

---

如果内存很大，这个比较会花费很多时间。 - StevenWang

除非硬件提供特殊支持，否则检查缓冲区是否全为零需要读取缓冲区。这是无法避免的。至少在这个答案中，缓冲区只被读取了一次。 - Pascal Cuoq

Pascal Cuoq：您是否测量了性能，还是只是在猜测？如果您已经进行了测量，请发布结果-我非常想看看。对我来说，并不明显memcpy解决方案必须要两次访问内存-处理器也有缓存，而且比内存快得多。无论哪种方案更好，我都非常想看到结果。此外，我认为衡量性能是标准的最佳实践，而不是猜测。 - Mark Byers

Pascal Couq：我进行了一个快速测试，结果显示，即使将该函数更改为宏并进行内联，对于100字节的10M次分配，在我的硬件上也没有显着提高速度。等我有时间时（大约8小时后），我会发布更详细的结果。 - Mark Byers

在这两种情况下，性能影响可以忽略不计-主要的性能损失来自对malloc的调用。 - Mark Byers

@Mark Byers：它可能不会在物理上两次接触内存。但是它将导致额外的依赖关系。每个比较都必须等待检索两个值，而不仅仅是一个值。即使它们都必须从缓存中检索（这通常是情况），这仍然比将一个对象在内存中与已知的编译时常量进行比较要慢。 - jalf

Answer 6

对于大缓冲区：

typedef int tNativeInt;  // __int64 on 64 bit platforms with 32 bit ints

// test most of the buffer using CPU Word size
tNativeInt * ptr = reinterpret_cast<tNativeInt *>(buffer);
tNativeInt * end = ptr + bufSize / sizeof(tNativeInt);
for(;ptr < end;++ptr)
  if (*ptr != 0)
    return false;

// check remainder
char * ptrc = reinterpret_cast<char *>(ptr);
char * endc = ptrc + bufSize % sizeof(tNativeInt);
for(; ptrc<endc; ++ptrc)
  if (*ptrc != 0)
    return false;

备注：
核心优化测试全CPU字 - 读取一个字节通常与单个字节一样昂贵。

代码假定缓冲区对齐良好（即地址是CPU Word大小的倍数）。如果不是，则需要在块测试之前放置类似于“remainder”的块。

当然，对于小缓冲区，附加代码会更慢 - 但在这种情况下，人们普遍认为这些短暂的持续时间无关紧要。

如果您愿意，当然可以用std :: find_if替换循环。

性能：1：3.9

（VS 2008，/ Ox / Ot，对于256000字节的10000次重复，2.47 +/- 0.11 vs. 0.63 +/- 0.19， 统计数据超过15次首先删除）

讨论：从我分析C / C ++到汇编的经验来看，我不会期望编译器进行此优化 - 因为它对于小的size而言是一种恶化， 而且那种类型的优化可能性很少。大约4的因素证实了这种假设 - 看起来反汇编也是如此。

另外，对于大多数应用程序来说，总时间是微不足道的，缓存未命中将更糟，并且影响两个版本相同。

[编辑]为了好玩：

重叠的memcmp在1：1.4时钟，这比单个字节检查要好得多（有点让我惊讶）。

请注意，不对齐的读取使其强烈依赖于平台。

- peterchen

---

我会期望编译器进行这种优化（不是一次读取一个字节，而是一次读取几个字）。例如，您是否观察到使用 -O2 会带来更好的性能？ - Per Knytt

这取决于缓冲区是从malloc返回的事实。这在问题中已经说明了，所以还好，只要知道您不能使用任何旧的char来作为缓冲区，因为它可能不对齐。此外，reinterpret_cast到tNativeInt并且取消引用是未定义的，但我们可以假设该平台支持它。 - Steve Jessop

@Per：请查看更新。... @Steve：premainder的实现留给读者作为练习;) - peterchen

我看到使用原始汇编语言，32位或64位取决于1:4或1:8的改进，而在C中只有1:4的改进。 - ephemient

ephemient: 你是否明确地使用 __int64？在64位平台上，sizeof(int) == 32位是一个常见的选择。 - peterchen

Answer 7

在与Steve Jessops代码玩耍时，我发现了这个变体。

int checkzeros(char *f, char *l) {
        char a = 0;
        while (f < l) {
                a |= *f++;
        }
        if (a) {
                return 0;
        }
        return 1;
}

核心循环中没有分支，速度约快50%。所有错误都是我的。

[编辑]：正如Steve所指出的那样，这个版本有一个好的最坏情况和一个可怕的最佳情况（因为它们是相同的）。只有在完全清零的缓冲区是唯一需要快速的情况下才使用它。

- Per Knytt

---

好的观点 - 如果您期望checkzeros为真，则此版本很好，如果缓冲区包含随机数据，则不好。在这种情况下，我的循环将以255/256的概率在一个字节后退出，而您的循环始终运行到结束，因此我希望我的循环速度比您的快50％以上。 - Steve Jessop

Answer 8

更多基准测试：

大致基于Steve Jessop的样例。我测试了以下内容：

- Naive memcmp（分配一个单独的零块，并与之比较） - “聪明”的memcmp（将块与自身进行比较，向左移动一次） - std::find_if - 一个简单的循环检查每个字节

这些都不对数组做任何假设，只是接受并处理一个char类型的数组。

最后，我创建了第五个版本，将数组转换为int类型，然后进行比较。（这显然假设数组的大小可被sizeof(int)整除，因此不太通用。但我添加了它以证明使用合理的块大小比玩弄memcpy和逐字节比较更有用。

哦，注意我只是匆忙地拼凑了这个测试，并使用了Windows的计时器，因为我懒惰。 :)

#include <cstdlib>
#include <string>
#include <cstdio>
#include <algorithm>

#include <windows.h>

enum {
    count = 1000*1000,
    blocksize = 1024
};

bool test_simple_loop(char* p){
    for (int i = 0; i < blocksize; ++i) {
        if (p[i] != 0) { return false; }
    }
    return true;
}

bool test_memcmp_clever(char* p){
    return *p == 0 && memcmp(p, p + 1, blocksize - 1) == 0;
}
bool test_memcmp_naive(char* p, char* ref){
    return memcmp(p, ref, blocksize) == 0;
}

struct cmp {
    template <typename T>
    bool operator()(T& x) {
        return x != 0;
    }
};
bool test_find_if(char* p){
    return std::find_if(p, p+blocksize, cmp()) == p+blocksize;
}

bool test_find_if_big(int* p){
    return std::find_if(p, p+blocksize, cmp()) == p+blocksize;
}

int main() {

    bool res = true;

    char *p = new char[blocksize];
    char *ref = new char[blocksize];

    std::fill(ref, ref+blocksize, 0);
    std::fill(p, p+blocksize, 0); // ensure the worst-case scenario, that we have to check the entire buffer. This will also load the array into CPU cache so the first run isn't penalized

    DWORD times[5];
    DWORD start;

    start = GetTickCount();
    for (int i = 0; i != count; ++i) {
        res &= test_memcmp_naive(p, ref);
    }
    times[0] = GetTickCount() - start;
    start = GetTickCount();
    for (int i = 0; i != count; ++i) {
        res &= test_memcmp_clever(p);
    }
    times[1] = GetTickCount() - start;
    start = GetTickCount();
    for (int i = 0; i != count; ++i) {
        res &= test_find_if(p);
    }
    times[2] = GetTickCount() - start;
    start = GetTickCount();
    for (int i = 0; i != count; ++i) {
        res &= test_simple_loop(p);
    }
    times[3] = GetTickCount() - start;
    start = GetTickCount();
    for (int i = 0; i != count; ++i) {
        res &= test_find_if_big(reinterpret_cast<int*>(p));
    }
    times[4] = GetTickCount() - start;

    delete[] p;
    delete[] ref;

    printf("%d\n", res);
    printf("%d\n%d\n%d\n%d\n%d\n", times[0], times[1], times[2], times[3], times[4]);
}

我的结果是：（以毫秒为单位，进行一百万次运行）

Naive memcmp: 546
"Clever" memcmp: 530
`find_if<char>`: 1466
Simple loop: 1358
`find_if<int`>: 343

我认为重点很明显： 任何按字节比较的操作都很慢。真的很慢。 Memcmp做得还可以，但远非完美。它太通用了，无法达到最优。 解决此问题的最有效方式是尽可能一次处理尽量多的数据。 char只是愚蠢的。 int是一个很好的开始，但64位或128位读取可能仍然表现更好。

- jalf

---

也许了解将memset设置为0的时间会很有趣。 - Viktor Sehr

我认为这将是最快的。您可以节省所有比较和内存访问的依赖关系。 - jalf

jalf：+1 感谢你花时间做这件事——对我来说，测试零的简单操作竟然能引起如此多的讨论真是很有趣！但我想知道为什么你声称 memcmp 比简单循环慢，而你自己的测试结果却显示它更快？我错过了什么吗？ - Mark Byers

抱歉如果之前表述不够清晰。我的意思是，相较于一个更大的字长的简单循环，它的速度要慢。std::find_if本质上与简单循环算法相同，因此我将其作为“更简单的循环，具有更大的字长”的代表。 - jalf

Answer 9

如果你想在分配的内存中全部为0，可以使用calloc。

- Himanshu

Answer 10

如果您需要将内存清零，只需使用memset()将其设置为零即可；先检查它是否为零是浪费时间的，因为它很可能不是零，并且您最终会做更多的工作来进行检查和设置。

然而，如果您真的想高效地检查一段内存区域是否全部为零，可以将其与其他已知全部为零的内容进行memcmp()比较。例如，您可以分配并清零一个内存块，然后保留指向它的指针以用于与其他内存块进行比较。

- Wyzard

---

使用memcmp对预分配的区域进行比较效率不高。每个要比较的地址需要两次内存读取。但第一点还是值得肯定的。 - jalf

为什么涉及两次读取的memcmp会高效？（可能足够快，但不是高效的） - peterchen

它并不是非常高效，但是它是正确和可移植的。一个人也可以使用循环并检查每个字节的值，但是memcmp()实现可能会使用更有效的方法，比较整个机器字而不是单个字节。 - Wyzard