How can I know where the segment of memory is all Zero

Question

I mean, I malloc a segment of memory, maybe 1k maybe 20bytes.. assume the pointer is pMem How can I know the content pMem refered is all Zero or \0 . I know memcmp but the second parameter should another memory address... thanx

Answer 1

The function you want is called memset.

Call it like this:

memset(pMem, '\0', iMemSize);

Answer 2

You can use calloc if you want all 0s in the memory you allocate

Answer 3

As others have already suggested you probably want memset or calloc.

But if you actually do want to check if a memory area is all zero, you can compare it with itself but shifted by one.

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

where length is the number of bytes you want to be zero.

Answer 4

If you need the memory to be zero, just memset() it to zero; it's a waste of time to check whether it's zero first, because it probably isn't and you'll end up doing more work overall, checking and then setting.

However, if you really want to efficiently check a region of memory to see if it's all zero, you can memcmp() it against something else that's known to be all zero. You could allocate and zero one chunk of memory, for example, and then keep a pointer to it for use in comparing against other chunks of memory.

Answer 5

As you've noted, memcmp compares one block of memory to another. If you had another block of memory that you already knew was all zero, then you could use that reference block to compare with your candidate block to see whether they match.

It sounds like you don't have another block of memory, though. You just have one, and you want to know whether it's all zero. The standard libraries don't provide such a function, but it's easy to write your own:

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

If you want to allocate a new block of memory and have it be all zero right away, then use calloc instead of malloc. If you have a block of memory that you want to set to all zero, then use memset or std::fill.

Answer 6

If you're testing it, and then only going to use it if it's zero, then be aware you have a race-condition, because the method suggested by @Mark Byers doesn't have an atomic test/set operation. It'll be hard to get the logic correct in this case.

If you want to zero it if it's not already zero, then just set it to zero as that will be faster.

Answer 7

C++ solution:

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

Answer 8

Another C++ solution, slightly simpler than Kirill's. It is somewhat less efficient, though, as it traverses the entire sequence even when that sequence contains a non-zero element.

bool all_zeroes = std::count(pMem, pMem + length, 0) == length;

Answer 9

Since Mark's answer has provoked some controversy:

#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;
}

Results (cygwin, Windows XP, Core 2 Duo T7700 at 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

So, the memcmp is taking approximately (2.8 - 0.4) / (1.2 - 0.4) = 3 times as long, for me. It'd be interesting to see other people's results - all my malloced memory is zeroed, so I'm getting the worst-case time for each comparison, always.

With smaller blocks (and more of them) the comparison time is less significant, but memcmp is still slower:

$ 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

I am slightly surprised by this. I expected memcmp to at least compete, since I expect it to be inlined and to be optimised for small sizes known at compile time. Even changing it so that it tests an int at the start and then 16 bytes of memcmp, to avoid the unaligned worst case, doesn't speed it up much.

Answer 10

For large buffers:

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;

Remarks:
The core optimizations testing full CPU words - reading one is generally as expensive as a single byte.

The code assumes the buffer is well aligned (i.e. the address is a multiple of the CPU Word size). If not, a block similar to "remainder" needs to be put in front of the block test.

The additional code will of course be slower for small buffers - however, in this case one commonly assumes that these short durations don't matter.

If you prefer you can of course replace the loops with std::find_if.

---

Performance: 1: 3.9

(VS 2008, /Ox /Ot, 2,47 +/- 0,11 vs. 0,63 +/- 0,19, for 10000 repeats over 256000 bytes, statistics over 15 repeats first removed)

Discussion: From my experience analyzing C/C++ to assembly, I wouldn't expect a compiler to do this optimization - because it is a pessimization for small size, and optimization possibilities of that type are few and far between. The factor of roughly 4 confirms the assumpotion - as does looking at the disassembly.

Also, the total time is negligible for most applications, a cache miss will be far worse and affect both versions the same.

[edit] for the fun of it:

Overlapping memcmp clocks in at 1:1.4, which is vastly better than the single byte check (surprised me a little).

Note that the misaligned read makes that strongly platform dependent.

Answer 11

Poking around with Steve Jessops code for fun I found this variant

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

to be about 50% faster (no branches in the core loop). All bugs are mine.

[Edit]: As Steve points out, this version has a good worst case and a terrible best case (since they are the same). Only use it if a completely zeroed buffer is the only case that needs to be fast.

Answer 12

Worst case is when an array is not zero. You have to make two passes: one to check for zero and the other to set the array to zero. To save time, just force it to zeros.

Answer 13

More benchmarks:

Roughly based on Steve Jessop's sample. I've tested the following:

• Naive memcmp (allocate a separate block of zeros, and compare against that)
• "clever" memcmp ( compare the block against itself, shifted once)
• std::find_if
• A simple loop checking each byte

None of these make any assumptions about the array, and simply accept and work on an array of chars.

Finally, I made a fifth version, which casts the array to ints, and compares those. (This one obviously assumes that the size of the array is divisible by sizeof(int), so it is less general. But I added it to demonstrate that working with a reasonable chunk size is a much more useful optimization than messing around with memcpy and byte-wise comparisons.

Oh, and note that I just slapped this test together quickly, and I used one of Windows' timers because I'm lazy. :)

#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]);
}

My results are: (in milliseconds, for a million runs)

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

I think the takeaway point is pretty clear: Anything that does a bytewise comparison is slow. Really slow. Memcmp does more or less ok, but it's far from perfect. It is too general to be optimal.

The most efficient way to solve this problem is to process as much data at a time as possible. char is just silly. int is a good start, but 64- or 128-bit reads would probably perform far better still.