Faster approach to checking for an all-zero buffer in C?

by

On many architectures, comparing 1 byte takes the same amount of time as 4 or 8, or sometimes even 16. 4 bytes is normally easy (either int or long), and 8 is too (long or long long). 16 or higher probably requires inline assembly to e.g., use a vector unit.

Also, a branch mis-predictions really hurt, it may help to eliminate branches. For example, if the buffer is almost always empty, instead of testing each block against 0, bit-or them together and test the final result.

Expressing this is difficult in portable C: casting a char* to long* violates strict aliasing. But fortunately you can use memcpy to portably express an unaligned multi-byte load that can alias anything. Compilers will optimize it to the asm you want.

For example, this work-in-progress implementation (https://godbolt.org/z/3hXQe7) on the Godbolt compiler explorer shows that you can get a good inner loop (with some startup overhead) from loading two consecutive uint_fast32_t vars (often 64-bit) with memcpy and then checking tmp1 | tmp2, because many CPUs will set flags according to an OR result, so this lets you check two words for the price of one.

Getting it to compile efficiently for targets without efficient unaligned loads requires some manual alignment in the startup code, and even then gcc may not inline the memcpy for loads where it can’t prove alignment.

More Related Contents:

  1. optimized sum of an array of doubles in C [duplicate]
  2. Improve INSERT-per-second performance of SQLite
  3. Why does the order of the loops affect performance when iterating over a 2D array?
  4. Is there a performance difference between i++ and ++i in C?
  5. Is it safe to read past the end of a buffer within the same page on x86 and x64?
  6. Efficient 4×4 matrix vector multiplication with SSE: horizontal add and dot product – what’s the point?
  7. Why is memcmp so much faster than a for loop check?
  8. Inline function v. Macro in C — What’s the Overhead (Memory/Speed)?
  9. Competitive programming: "Time exceeded error"
  10. Why does C++ code for testing the Collatz conjecture run faster than hand-written assembly?
  11. Why does glibc’s strlen need to be so complicated to run quickly?
  12. Can the linker inline functions?
  13. clflush to invalidate cache line via C function
  14. Why is this code using strlen heavily 6.5x slower with GCC optimizations enabled?
  15. Matrix multiplication: Small difference in matrix size, large difference in timings
  16. Is ‘switch’ faster than ‘if’?
  17. Efficiency: arrays vs pointers
  18. When is optimization premature? [closed]
  19. How many GCC optimization levels are there?
  20. How to concatenate two integers in C
  21. How to determine the size of an allocated C buffer? [duplicate]
  22. Why changing value of SO_RCVBUF doesn’t work?
  23. When is assembly faster than C? [closed]
  24. Best timing method in C?
  25. How does the CPU cache affect the performance of a C program
  26. Is there any way to peek at the stdin buffer?
  27. A better way to replace many strings – obfuscation in C#
  28. How can I flush unread data from a tty input queue on a UNIX system?
  29. How much overhead can the -fPIC flag add?
  30. Efficient 4×4 matrix multiplication (C vs assembly)

Leave a Comment