What is the fastest way to check the leading characters in a char array?

Question

I reached a bottleneck in my code, so the main issue of this question is performance.

I have a hexadecimal checksum and I want to check the leading zeros of an array of chars. This is what I am doing:

bool starts_with (char* cksum_hex, int n_zero) {
  bool flag {true};
  for (int i=0; i<n_zero; ++i)
    flag &= (cksum_hex[i]=='0');
  return flag;
}

The above function returns true if the cksum_hex has n_zero leading zeros. However, for my application, this function is very expensive (60% of total time). In other words, it is the bottleneck of my code. So I need to improve it.

I also checked std::string::starts_with which is available in C++20 and I observed no difference in performance:

// I have to convert cksum to string
std::string cksum_hex_s (cksum_hex);
cksum_hex_s.starts_with("000");     // checking for 3 leading zeros

For more information I am using g++ -O3 -std=c++2a and my gcc version is 9.3.1.

Questions

• What is the faster way of checking the leading characters in a char array?
• Is there a more efficient way of doing it with std::string::starts_with?
• Does the bitwise operations help here?

Answer 1

If you modify your function to return early

bool starts_with (char* cksum_hex, int n_zero) {
  for (int i=0; i<n_zero; ++i)
  {
    if (cksum_hex[i] != '0') return false;
  }
  return true;
}

It will be faster in case of big n_zero and false result. Otherwise, maybe you can try to allocate a global array of characters '0' and use std::memcmp:

// make it as big as you need
constexpr char cmp_array[4] = {'0', '0', '0', '0'};
bool starts_with (char* cksum_hex, int n_zero) {
    return std::memcmp(cksum_hex, cmp_array, n_zero) == 0;
}

The problem here is that you need to assume some max possible value of n_zero.

Live example

=== EDIT ===

Considering the complains about no profiling data to justify the suggested approaches, here you go:

• Benchmark results comparing early return implementation with memcmp implementation
• Benchmark results comparing memcmp implementation with OP original implementation

Data used:

const char* cs1 = "00000hsfhjshjshgj";
const char* cs2 = "20000hsfhjshjshgj";
const char* cs3 = "0000000000hsfhjshjshgj";
const char* cs4 = "0000100000hsfhjshjshgj";

memcmp is fastest in all cases but cs2 with early return impl.

Answer 2

Presumably you also have the binary checksum? Instead of converting it to ASCII text first, look at the 4*n high bits to check n nibbles directly for 0 rather than checking n bytes for equality to '0'.

e.g. if you have the hash (or the high 8 bytes of it) as a uint64_t or unsigned __int128, right-shift it to keep only the high n nibbles.

I showed some examples of how they compile for x86-64 when both inputs are runtime variables, but these also compile nicely to other ISAs like AArch64. This code is all portable ISO C++.

---

bool starts_with (uint64_t cksum_high8, int n_zero)
{
    int shift = 64 - n_zero * 4;       // A hex digit represents a 4-bit nibble
    return (cksum_high8 >> shift) == 0;
}

clang does a nice job for x86-64 with -O3 -march=haswell to enable BMI1/BMI2

high_zero_nibbles(unsigned long, int):
        shl     esi, 2
        neg     sil                  # x86 shifts wrap the count so 64 - c is the same as -c
        shrx    rax, rdi, rsi        # BMI2 variable-count shifts save some uops.
        test    rax, rax
        sete    al
        ret

This even works for n=16 (shift=0) to test all 64 bits. It fails for n_zero = 0 to test none of the bits; it would encounter UB by shifting a uint64_t by a shift count >= its width. (On ISAs like x86 that wrap out-of-bounds shift counts, code-gen that worked for other shift counts would result in checking all 16 bits. As long as the UB wasn't visible at compile time...) Hopefully you're not planning to call this with n_zero=0 anyway.

Other options: create a mask that keeps only the high n*4 bits, perhaps shortening the critical path through cksum_high8 if that's ready later than n_zero. Especially if n_zero is a compile-time constant after inlining, this can be as fast as checking cksum_high8 == 0. (e.g. x86-64 test reg, immediate.)

bool high_zero_nibbles_v2 (uint64_t cksum_high8, int n_zero) {
    int shift = 64 - n_zero * 4;         // A hex digit represents a 4-bit nibble
    uint64_t low4n_mask = (1ULL << shift) - 1;
    return cksum_high8 & ~low4n_mask;
}

Or use a bit-scan function to count leading zero bits and compare for >= 4*n. Unfortunately it took ISO C++ until C++20 <bit>'s countl_zero to finally portably expose this common CPU feature that's been around for decades (e.g. 386 bsf / bsr); before that only as compiler extensions like GNU C __builtin_clz.

This is great if you want to know how many and don't have one specific cutoff threshold.

bool high_zero_nibbles_lzcnt (uint64_t cksum_high8, int n_zero) {
    // UB on cksum_high8 == 0.  Use x86-64 BMI1 _lzcnt_u64 to avoid that, guaranteeing 64 on input=0
    return __builtin_clzll(cksum_high8) > 4*n_zero;
}

#include <bit>
bool high_zero_nibbles_stdlzcnt (uint64_t cksum_high8, int n_zero) {
    return std::countl_zero(cksum_high8) > 4*n_zero;
}

compile to (clang for Haswell):

high_zero_nibbles_lzcnt(unsigned long, int):
        lzcnt   rax, rdi
        shl     esi, 2
        cmp     esi, eax
        setl    al                    # FLAGS -> boolean integer return value
        ret

All these instructions are cheap on Intel and AMD, and there's even some instruction-level parallelism between lzcnt and shl.

See asm output for all 4 of these on the Godbolt compiler explorer. Clang compiles 1 and 2 to identical asm. Same for both lzcnt ways with -march=haswell. Otherwise it needs to go out of its way to handle the bsr corner case for input=0, for the C++20 version where that's not UB.

---

To extend these to wider hashes, you can check the high uint64_t for being all-zero, then proceed to the next uint64_t chunk.

---

Using an SSE2 compare with pcmpeqb on the string, pmovmskb -> bsf could find the position of the first 1 bit, thus how many leading-'0' characters there were in the string representation, if you have that to start with. So x86 SIMD can do this very efficiently, and you can use that from C++ via intrinsics.

Answer 3

You can make a buffer of zeros large enough for you than compare with memcmp.

const char *zeroBuffer = "000000000000000000000000000000000000000000000000000";

if (memcmp(zeroBuffer, cksum_hex, n_zero) == 0) {
   // ...
}

Answer 4

Things you want to check to make your application faster:

1. Can the compiler inline this function in places where it is called?

Either declare the function as inline in a header or put the definition in the compile unit where it is used.

2. Not computing something is faster than computing something more efficiently

Are all calls to this function necessary? High cost is generally the sign of a function called inside a high frequency loop or in an expensive algorithm. You can often reduce the call count, hence the time spent in the function, by optimizing the outer algorithm

3. Is n_zero small or, even better, a constant?

Compilers are pretty good at optimizing algorithm for typically small constant values. If the constant is known to the compiler, it will most likely remove the loop entirely.

4. Does the bitwise operation help here?

It definitely has an effect and allows Clang (but not GCC as far as I can tell) to do some vectorization. Vectorization tend to be faster but that's not always the case depending on your hardware and actual data processed. Whether it is an optimization or not might depend on how big n_zero is. Considering you are processing checksums, it should be pretty small so it sounds like a potential optimization. For known n_zero using bitwise operation allows the compiler to remove all branching. I expect, though I did not measure, this to be faster.

std::all_of and std::string::starts_with should be compiled exactly as your implementation except they will use && instead of &.

Answer 5

Adding my two cents to this interesting discussion, though a little late to the game, I gather you could use std::equal, it's a fast method with a slightly different approach, using a hardcoded string with the maximum number of zeros, instead of the number of zeros.

This works passing to the function pointers to the begin and end of the string to be searched, and to string of zeros, specifically iterators to begin and end, end pointing to position of one past of the wanted number of zeros, these will be used as iterators by std::equal:

Sample

bool startsWith(const char* str, const char* end, const char* substr, const char* subend) {
    return  std::equal(str, end, substr, subend);
}

int main() {

    const char* str = "000x1234567";
    const char* substr = "0000000000000000000000000000";
    std::cout << startsWith(&str[0], &str[3], &substr[0], &substr[3]); 
}

Using the test cases in @pptaszni's good answer and the same testing conditions:

const char* cs1 = "00000hsfhjshjshgj";
const char* cs2 = "20000hsfhjshjshgj";
const char* cs3 = "0000000000hsfhjshjshgj";
const char* cs4 = "0000100000hsfhjshjshgj";

The result where as follows:

Slower than using memcmp but still faster (except for false results with low number of zeros) and more consistent than your original code.

Answer 6

Unless n_zero is quite high I would agree with others that you may be misinterpreting profiler results. But anyway:

• Could the data be swapped to disk? If your system is under RAM pressure, data could be swapped out to disk and need to be loaded back to RAM when you perform the first operation on it. (Assuming this checksum check is the first access to the data in a while.)

• Chances are you could use multiple threads/processes to take advantage of a multicore processor.

• Maybe you could use statistics/correlation of your input data, or other structural features of your problem.

  • For instance, if you have a large number of digits (e.g. 50) and you know that the later digits have a higher probability of being nonzero, you can check the last one first.
  • If nearly all of your checksums should match, you can use [[likely]] to give a compiler hint that this is the case. (Probably won't make a difference but worth a try.)

Answer 7

Use std::all_of

return std::all_of(chsum_hex, chsum_hex + n_zero, [](char c){ return c == '0'; })