CODEWITHSUNDEEP
c++
Matthieu M.
Matthieu M.

Reputation: 299760

Fastest way to find first occurrence of byte in buffer

Disclaimer

I am looking for the fastest way to identify the first occurrence of a given byte in a byte buffer.

This is reminiscent of looking for the first occurrence of a character in a string except that:

The basic solution is:

size_t search(char const* buffer, size_t length, char c) {
    return std::find(buffer, buffer + length, c) - buffer;
}

However, a quick round-trip with the Godbolt compiler (-O2 -msse2 -mavx) does not show any hint of a vectorized instruction, only some unrolling, so I am wondering whether this is the optimal.

Is there a faster way to find the first occurrence of a given byte in a buffer?

Note: only the first occurrence matters.

Note: I am exclusively concerned with modern x86_64 CPUs on Linux, though I encourage answers to be as generic as possible and mention assumptions clearly.

Upvotes: 6

Views: 2517

Answers (1)

David Haim
David Haim

Reputation: 26476

you can use memchr , which is usually implemented as an intrinsic function, and is usually (from my experience) much faster than any hand-rolled loop.

http://en.cppreference.com/w/c/string/byte/memchr

Edit: at least on VC++ (and I bet on GCC as well, I haven't checked), std::find will use memchr anyway if you look for a byte , so I would check if memchr actually make the program run faster.

Upvotes: 4

Related Questions