Fastest way to check mass data if null in C?

Question

I have a mass of data, maybe 4MB. Now want to check if all bits in it are 0.

Eg: Here is the data:

void* data = malloc(4*1024*1024);
memset(data, 0, 4*1024*1024);

Check if all bits in it are 0. Here is my solution which is not fast enough:

int dataisnull(char* data, int length)
{
    int i = 0;
    while(i<length){
        if (data[i]) return 0;
        i++;
    }
    return 1;
}

This code might have some things to improve in performance. For example, in 32/64 bits machine, checking 4/8 bytes at a time may be faster.

So I wonder what is the fastest way to do it?

Answer 1

You can handle multiple bytes at a time and unroll the loop:

int dataisnull(const void *data, size_t length) {
    /* assuming data was returned by malloc, thus is properly aligned */
    size_t i = 0, n = length / sizeof(size_t);
    const size_t *pw = data;
    const unsigned char *pb = data;
    size_t val;
#define UNROLL_FACTOR  8
#if UNROLL_FACTOR == 8
    size_t n1 = n - n % UNROLL_FACTOR;
    for (; i < n1; i += UNROLL_FACTOR) {
        val = pw[i + 0] | pw[i + 1] | pw[i + 2] | pw[i + 3] |
              pw[i + 4] | pw[i + 5] | pw[i + 6] | pw[i + 7];
        if (val)
            return 0;
    }
#endif
    val = 0;
    for (; i < n; i++) {
        val |= pw[i];
    }
    for (i = n * sizeof(size_t); i < length; i++) {
        val |= pb[i];
    }
    return val == 0;
}

Depending on your specific problem, it might be more efficient to detect non zero values early or late:

• If the all zero case is the most common, you should compute cumulate all bits into the val accumulator and test only at the end.
• If the all zero case is rare, you should check for non zero values more often.

The unrolled version above is a compromise that tests for non zero values every 64 or 128 bytes depending on the size of size_t.

Depending on your compiler and processor, you might get better performance by unrolling less or more. You could also use intrinsic functions available for your particular architecture to take advantage of vector types, but it would be less portable.

Note that the code does not verify proper alignment for the data pointer:

• it cannot be done portably.
• it assumes the data was allocated via malloc or similar, hence properly aligned for any type.

As always, benchmark different solutions to see if it makes a real difference. This function might not be a bottleneck at all, writing a complex function to optimize a rare case is counterproductive, it makes the code less readable, more likely to contain bugs and much less maintainable. For example, the assumption on data alignment may not hold if you change memory allocation scheme or if you use static arrays, the function may invoke undefined behavior then.

Answer 2

The following checks if the first byte is what you want, and all subsequent pairs of bytes are the same.

int check_bytes(const char * const data, size_t length, const char val)
{
    if(length == 0) return 1;
    if(*data != val) return 0;
    return memcmp(data, data+1, length-1) ? 0 : 1;
}

int check_bytes64(const char * const data, size_t length, const char val)
{
    const char * const aligned64_start = (char *)((((uintptr_t)data) + 63) / 64 * 64);
    const char * const aligned64_end = (char *)((((uintptr_t)data) + length) / 64 * 64);
    const size_t start_length = aligned64_start - data;
    const size_t aligned64_length = aligned64_end - aligned64_start;
    const size_t end_length = length - start_length - aligned64_length;

    if (!check_bytes(data, start_length, val)) return 0;
    if (!check_bytes(aligned64_end, end_length, val)) return 0;

    return memcmp(aligned64_start, aligned64_start + 64, aligned64_length-64) ? 0 : 1;
}

A more elaborate version of this function should probably pass cache-line-aligned pointers to memcmp, and manually check the remaining blocks(s) instead of just the first byte.

Of course, you will have to profile on your specific hardware to see if there is any speed benefit of this method vs others.

If anyone doubts whether this works, ideone.

Answer 3

I once wrote the following function for my own use. It assumes that the data to check is a multiple of a constant chunk size and aligned properly for a buffer of machine words. If this is not given in your case, it is not hard to loop for the first and last few bytes individually and only check the bulk with the optimized function. (Strictly speaking, it is undefined behavior even if the array is properly aligned but the data has been written by any type that is incompatible with unsigned long. However, I believe that you can get pretty far with this careful breaking of the rules here.)

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool
is_all_zero_bulk(const void *const p, const size_t n)
{
  typedef unsigned long word_type;
  const size_t word_size = sizeof(word_type);
  const size_t chunksize = 8;
  assert(n % (chunksize * word_size) == 0);
  assert((((uintptr_t) p) & 0x0f) == 0);
  const word_type *const frst = (word_type *) p;
  const word_type *const last = frst + n / word_size;
  for (const word_type * iter = frst; iter != last; iter += chunksize)
    {
      word_type acc = 0;
      // Trust the compiler to unroll this loop at its own discretion.
      for (size_t j = 0; j < chunksize; ++j)
        acc |= iter[j];
      if (acc != 0)
        return false;
    }
  return true;
}

The function itself is not very smart. The main ideas are:

• Use large unsigned machine words for data comparison.
• Enable loop unrolling by factoring out an inner loop with a constant iteration count.
• Reduce the number of branches by ORing the words into an accumulator and only comparing it every few iterations against zero.
• This should also make it easy for the compiler to generate vectorized code using SIMD instructions which you really want for code like this.

Additional non-standard tweaks would be to annotate the function with __attribute__ ((hot)) and use __builtin_expect(acc != 0, false). Of course, the most important thing is to turn on your compiler's optimizations.