Fastest way to find first occurrence of byte in buffer

Question

Disclaimer

I have read What is the fastest substring search algorithm?, which may be suboptimal for the single character case.
strchr requires a NUL-terminated string

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 byte buffer is not NUL-terminated, instead I have an explicit length (and possibly embedded NUL characters)
the byte buffer is not allocated in a string or vector, I am only handed down a slice (aka, pointer & length)

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.

Maybe try memchr - it's like strchr but it doesn't require a NUL-terminated string ? — Paul R
– Paul R, Commented Nov 16, 2016 at 13:14
It’s dismaying that std::find isn’t optimised to take advantage of compiler intrinsics on GCC. Somebody should write a patch, it’s such an obvious optimisation. — Konrad Rudolph
– Konrad Rudolph, Commented Nov 16, 2016 at 13:46
@KonradRudolph: I am quite surprised as well, especially since according to David Haim the optimization is done on VC++. Maybe a concern about inlining? (As in, a pure C++ implementation can be compile-time evaluated, an assembly one cannot) — Matthieu M.
– Matthieu M., Commented Nov 16, 2016 at 13:48
@MatthieuM. at least on VC++, all the strXXX and memXXX functions will be compile-time evaluated on compile time if the data is known on compile time. I don't think it's a technical issue that prevent GCC from using it — David Haim
– David Haim, Commented Nov 16, 2016 at 13:55
@DavidHaim: Ah, probably because resolving to intrinsics, the compiler knows what their functionality is. — Matthieu M.
– Matthieu M., Commented Nov 16, 2016 at 13:56

David Haim · Accepted Answer · 2016-11-16 13:22:23Z

4

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.

edited Nov 16, 2016 at 13:22

answered Nov 16, 2016 at 13:14

David Haim

26.7k4 gold badges50 silver badges88 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Matthieu M. Over a year ago

An explanation of memchr implementation can be found here. Notes from BurntSushi's Rust memchr crate hint that libc's memchr is slowish on Windows though.

Matthieu M. Over a year ago

From Godbolt, no, std::find on a char is not reduced to a memchr by gcc (6.2).

David Haim Over a year ago

@MatthieuM. so here is a something to try out :)

Matthieu M. Over a year ago

Yes, it's a really good contender certainly; especially since I don't have to care about Windows compatibility in my case.

Collectives™ on Stack Overflow

Fastest way to find first occurrence of byte in buffer

1 Answer 1

4 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Linked

Related