10

If I have an unsigned char *data pointer and I want to check whether size_t length of the data at that pointer is NULL, what would be the fastest way to do that? In other words, what's the fastest way to make sure a region of memory is blank?

I am implementing in iOS, so you can assume iOS frameworks are available, if that helps. On the other hand, simple C approaches (memcmp and the like) are also OK.

Note, I am not trying to clear the memory, but rather trying to confirm that it is already clear (I am trying to find out whether there is anything at all in some bitmap data, if that helps). For example, I think the following would work, though I have not tried it yet:

- BOOL data:(unsigned char *)data isNullToLength:(size_t)length {
    unsigned char tester[length] = {};
    memset(tester, 0, length);
    if (memcmp(tester, data, length) != 0) {
        return NO;
    }
    return YES;
}

I would rather not create a tester array, though, because the source data may be quite large and I'd rather avoid allocating memory for the test, even temporarily. But I may just being too conservative there.

UPDATE: Some Tests

Thanks to everyone for the great responses below. I decided to create a test app to see how these performed, the answers surprised me, so I thought I'd share them. First I'll show you the version of the algorithms I used (in some cases they differ slightly from those proposed) and then I'll share some results from the field.

The Tests

First I created some sample data:

    size_t length = 1024 * 768;
    unsigned char *data = (unsigned char *)calloc(sizeof(unsigned char), (unsigned long)length);
    int i;
    int count;
    long check;
    int loop = 5000;

Each test consisted of a loop run loop times. During the loop some random data was added to and removed from the data byte stream. Note that half the time there was actually no data added, so half the time the test should not find any non-zero data. Note the testZeros call is a placeholder for calls to the test routines below. A timer was started before the loop and stopped after the loop.

    count = 0;
    for (i=0; i<loop; i++) {
        int r = random() % length;
        if (random() % 2) { data[r] = 1; }
        if (! testZeros(data, length)) {
            count++;
        }
        data[r] = 0;
    }

Test A: nullToLength. This was more or less my original formulation above, debugged and simplified a bit.

- (BOOL)data:(void *)data isNullToLength:(size_t)length {
    void *tester = (void *)calloc(sizeof(void), (unsigned long)length);
    int test = memcmp(tester, data, length);
    free(tester);
    return (! test);
}

Test B: allZero. Proposal by Carrotman.

BOOL allZero (unsigned char *data, size_t length) {
    bool allZero = true;
    for (int i = 0; i < length; i++){
        if (*data++){
            allZero = false;
            break;
        }
    }
    return allZero;
}

Test C: is_all_zero. Proposed by Lundin.

BOOL is_all_zero (unsigned char *data, size_t length)
{
    BOOL result = TRUE;
    unsigned char* end = data + length;
    unsigned char* i;

    for(i=data; i<end; i++) {
        if(*i > 0) {
            result = FALSE;
            break;
        }
    }

    return result;
}

Test D: sumArray. This is the top answer from the nearly duplicate question, proposed by vladr.

BOOL sumArray (unsigned char *data, size_t length) {
    int sum = 0;
    for (int i = 0; i < length; ++i) {
        sum |= data[i];
    }
    return (sum == 0);
}

Test E: lulz. Proposed by Steve Jessop.

BOOL lulz (unsigned char *data, size_t length) {
    if (length == 0) return 1;
    if (*data) return 0;
    return memcmp(data, data+1, length-1) == 0;
}

Test F: NSData. This is a test using NSData object I discovered in the iOS SDK while working on all of these. It turns out Apple does have an idea of how to compare byte streams that is designed to be hardware independent.

- (BOOL)nsdTestData: (NSData *)nsdData length: (NSUInteger)length {
    void *tester = (void *)calloc(sizeof(void), (unsigned long)length);
    NSData *nsdTester = [NSData dataWithBytesNoCopy:tester length:(NSUInteger)length freeWhenDone:NO];
    int test = [nsdData isEqualToData:nsdTester];
    free(tester);
    return (test);
}

Results

So how did these approaches compare? Here are two sets of data, each representing 5000 loops through the check. First I tried this on the iPhone Simulator running on a relatively old iMac, then I tried this running on a first generation iPad.

On the iPhone 4.3 Simulator running on an iMac:

// Test A, nullToLength:  0.727 seconds
// Test F, NSData:        0.727
// Test E, lulz:          0.735
// Test C, is_all_zero:   7.340
// Test B, allZero:       8.736
// Test D, sumArray:     13.995

On a first generation iPad:

// Test A, nullToLength: 21.770 seconds
// Test F, NSData:       22.184
// Test E, lulz:         26.036
// Test C, is_all_zero:  54.747
// Test B, allZero:      63.185
// Test D, sumArray:     84.014

These are just two samples, I ran the test many times with only slightly varying results. The order of performance was always the same: A & F very close, E just behind, C, B, and D. I'd say that A, F, and E are virtual ties, on iOS I'd prefer F because it takes advantage of Apple's protection from processor change issues, but A & E are very close. The memcmp approach clearly wins over the simple loop approach, close to ten times faster in the simulator and twice as fast on the device itself. Oddly enough, D, the winning answer from the other thread performed very poorly in this test, probably because it does not break out of the loop when it hits the first difference.

Community
  • 1
  • 1
EFC
  • 1,890
  • 18
  • 39
  • 1
    possible duplicate of [fast way to check if an array of chars is zero](http://stackoverflow.com/questions/2589736/fast-way-to-check-if-an-array-of-chars-is-zero) – DarkDust Jul 01 '11 at 06:24
  • Why is this tagged C and Objective-C both? Which language are you using? – Lundin Jul 01 '11 at 06:27
  • Yup, looks like a dup to me too. Sorry. I hunted and hunted and didn't find that one before posting my question. Sigh. – EFC Jul 01 '11 at 06:29
  • @DarkDust It is not a duplicate unless the poster is using identical hardware as in that 32-bit x86 question you linked to. – Lundin Jul 01 '11 at 06:30
  • I am using Objective-C, but any C code will work in Objective-C, so I tagged for both. I mostly put the ObjC tag on in case there was something in that or the iOS frameworks that could provide a new approach to the problem. There's a lot I don't know about things like the Accelerate framework, for example, that might be applicable. – EFC Jul 01 '11 at 06:31
  • 1
    @Lundin: The top answer to the linked question is not using any architecture-dependent code and will work on ARM as well (both little- and big-endian). Even ARM has SIMD (called NEON). – DarkDust Jul 01 '11 at 06:49

6 Answers6

3

I think you should do it with an explicit loop, but just for lulz:

if (length == 0) return 1;
if (*pdata) return 0;
return memcmp(pdata, pdata+1, length-1) == 0;

Unlike memcpy, memcmp does not require that the two data sections don't overlap.

It may well be slower than the loop, though, because the un-alignedness of the input pointers means there probably isn't much the implementation of memcmp can do to optimize, plus it's comparing memory with memory rather than memory with a constant. Easy enough to profile it and find out.

Steve Jessop
  • 273,490
  • 39
  • 460
  • 699
2

If you're allocating the memory yourself, I'd suggest using the calloc() function. It's just like malloc(), except it zeros out the buffer first. It's what's used to allocate memory for Objective-C objects and is the reason that all ivars default to 0.

On the other hand, if this is a statically declared buffer, or a buffer you're not allocating yourself, memset() is the easy way to do this.

Dave DeLong
  • 242,470
  • 58
  • 448
  • 498
2

Not sure if it's the best, but I probably would do something like this:

bool allZero = true;
for (int i = 0; i < size_t; i++){
    if (*data++){
        //Roll back so data points to the non-zero char
        data--;
        //Do whatever is needed if it isn't zero.
        allZero = false;
        break;
    }
}

If you've just allocated this memory, you can always call calloc rather than malloc (calloc requires that all the data is zeroed out). (Edit: reading your comment on the first post, you don't really need this. I'll just leave it just in case)

Carrotman42
  • 1,744
  • 1
  • 14
  • 19
  • Yup, this approach works, and does not require allocating a test array, which I like. Is a loop the fastest way to go? I was hoping there was some c call or speedier framework tool. – EFC Jul 01 '11 at 06:25
  • I've never programmed in objective-C (just C/C++), but I figure a loop would be the fastest way to do it with just the language (no calls). I don't know of any c call to do it, but I'd love to hear of one if someone knows of one, though. – Carrotman42 Jul 01 '11 at 06:43
  • @Carrotman: Depending on the CPU, it might be faster to not do any conditional checks inside the loop body and just accumulate an int by `OR`ing the memory content, then checking that int after the loop. That way, the compiler can do all kind of optimizations like loop unrolling and using SIMD instructions which will theoretically make the *average* case faster. – DarkDust Jul 01 '11 at 07:00
  • 2
    @DarkDust: the effectiveness of that attempted optimization depends also on whether the input typically is all 0, and if not where the first non-zero byte is. Obviously if you're ORing together 1GB of memory but the first difference is in the second byte, then no amount of SIMD will help you. Basically the bigger the input, the better it is to exit early, so a refinement of your suggestion would be to use two loops - an inner loop as you describe that does a mid-sized chunk of data at a time, then an outer loop that can exit early. – Steve Jessop Jul 01 '11 at 09:31
1

Logic to get a value, check it, and set it will be at least as expensive as just setting it. You want it to be null, so just set it to null using memset().

djna
  • 54,992
  • 14
  • 74
  • 117
  • No, I don't want it to be null, I need to check whether it is null. In other words, I got the data from somewhere else, I just want to find out if it is blank or has any non-null at all. – EFC Jul 01 '11 at 06:09
1

This would be the preferred way to do it in C:

BOOL is_all_zero (const unsigned char* data, size_t length)
{
  BOOL result = TRUE;
  const unsigned char* end = data + length;
  const unsigned char* i;

  for(i=data; i<end; i++)
  {
    if(*i > 0)
    {
      result = FALSE;
      break;
    }
  }

  return result;
}

(Though note that strictly and formally speaking, a memory cell containing a NULL pointer mustn't necessarily be 0, as long as a null pointer cast results in the value zero, and a cast of a zero to a pointer results in a NULL pointer. In practice, this shouldn't matter as all known compilers use 0 or (void*) 0 for NULL.)

Lundin
  • 195,001
  • 40
  • 254
  • 396
0

Note the edit to the initial question above. I did some tests and it is clear that the memcmp approach or using Apple's NSData object and its isEqualToData: method are the best approaches for speed. The simple loops are clearer to me, but slower on the device.

EFC
  • 1,890
  • 18
  • 39