memchr is not necessarily implemented with SIMD

If you'd like however I can provide some reference code from my compiler that you can use to improve on:

https://github.com/steve-chavez/CParseC/blob/d710e788ade33c909c15d96e43ba8b568664465e/cparsec.h#L26

	// https://graphics.stanford.edu/~seander/bithacks.html#HasLessInWord
	constexpr bool has_zero(uint32_t v) noexcept {
		return (((v)-0x01010101UL) & ~(v)&0x80808080UL);
	}

	constexpr bool has_zero(uint64_t v) noexcept {
		return (((v)-0x0101010101010101ULL) & ~(v)&0x8080808080808080ULL);
	}

The idea is to load anywhere from 4-8 bytes at a time and use the above to check for zeros. You can do more bit hackery after the loop exits (because you're guaranteed to have found your 0*). But the main thing is that even if we're dealing with hardware that potentially has SIMD instructions, it'll struggle to outperform this loop:

while (!has_zero(ch32)) {
//increment pointer by 4 etc...
}

godbolt link for reference: https://godbolt.org/z/qWG63zrvd

Just a follow up, to cut down the code to a single loop, you'd work with the function like this:

constexpr uint64_t mask_zero(uint64_t v) noexcept {
	return (((v)-0x0101010101010101ULL) & ~(v) & 0x8080808080808080ULL);
}

Where the location of any 0 is masked by a 0x80. You only care about the leading one so performing a reverse bitscan is the last step.

unsigned long rbs;
auto r = _BitScanReverse64(&rbs,mask_zero(bits));

Retrieves the one based index of the guaranteed zero*, shifted by 3. 32 -> 4.

This last step, in theory should be the optimized result of a simple bitscan loop.

add: CPC_USE_STRING_H for strlen on cpc_slice_from_cstr

@Andersama

Hey @Andersama, many thanks for the feedback!

You're right in that memchr is not necessarily SIMD, I've added a note in the README telling it's implementation specific.

Regarding cpc_slice_from_cstr, it was intentionally kept very naive (a poor man's strlen). I've checked some strlen implementations:

musl word by word scan: https://git.musl-libc.org/cgit/musl/tree/src/string/strlen.c
glibc does SSE: https://github.com/bminor/glibc/blob/master/sysdeps/x86_64/multiarch/strlen-sse2.S

So for now I've decided to rely on strlen (https://github.com/steve-chavez/CParseC/issues/3) instead of adding optimizations myself but I might revisit in the future. (I'm still stabilizing the library API).

Thanks again for the pointers 😃

@steve-chavez

@steve-chavez just to point out, it appears that musl word by word scan is essentially this, with an added first step to handle alignment, although I'm not a fan of preprocessor defines.

I'd double check on their implementation, but they've got all the added parts I'd have commented on. They used void* to detect the native register size to essentially pick between the 4 vs 8 byte implementations, and they made a point of dealing with the alignment of the incoming pointer.

I'd probably skip the preprocessor mess, and maybe test/benchmark whether the trailing loop vs a single calculated step is better. I'd suspect working with the mask would be better. However I'd bet they made a point of testing that, so I'd be curious why they have the brute force loop as the end step.

Managed to have a non-memchr version of SIMD on #13, faster too!

I've also removed strlen usage, although I've just gone back to the simple byte-by-byte scan, improving it is TODO.

@steve-chavez

I see what you did there @steve-chavez, you can take the has_zero bithack so that you have a faster fallback even if there isn't simd support. See: https://graphics.stanford.edu/~seander/bithacks.html#ValueInWord

//We may want to know if any byte in a word has a specific value. To do so, we can XOR the value to test with a word that has been filled with the byte values in which we're interested. Because XORing a value with itself results in a zero byte and nonzero otherwise, we can pass the result to haszero.
#define hasvalue(x,n) \
(haszero((x) ^ (~0UL/255 * (n))))
//Stephen M Bennet suggested this on December 13, 2009 after reading the entry for haszero.

The (~0UL/255 * (n)) is a way to splat n as a byte into a long, essentially the idea here is that the original test works using xor operations to determine where a 0 is, ergo, we can take the input, xor it with a bye we're interested ahead of time, and now it effectively becomes a has_byte_value because we've transformed the input such that now it's offset in such a way n now behaves like 0.

// Essentially your simd algorithm but*
for (size_t i = 0; i < input_length; i++) {
    uint32_t test = 0; // like your algorithm*
    uint32_t splat_byte_from_input = (~0u / 255 * (input[i])); 
    for (size_t j = 0; j < test_characters_len/sizeof(uint32_t);j++) {
         test = test | mask_byte_value((uint32_t*)any_of_these)[j], splat_byte);
    }
    if (test) //builtin_clz etc... etc.. return
}

Now it'd be kind of ridiculous to do this*, but in theory we can do a preprocessing phase with a buffer of 256 chars that are aligned, making sure that we repeat the last character to the next power of 2 boundary of interest. Then we can perform the simd-esque loop without worrying about alignment and the algorithm will work with just the above loop!

alignas(16) char aligned_input_buffer[256];
// copy the test_characters over
uint32_t i = 0;
for (;test_characters && *test_characters;test_characters++,i++)
  aligned_input_buffer[i] = *test_characters;
char last_char = aligned_input_buffer[i-1];//need an input character!
for (;i & 0xf != 0; i++) {
  aligned_input_buffer[i] = last_char;
}

You can do the same with your simd function. Take the inputs, copy them over to an aligned 256 byte buffer and you won't need a second loop!

Navigation Menu

Repository navigation

memchr is not necessarily implemented with SIMD #3

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

memchr is not necessarily implemented with SIMD #3

Description

Activity

Andersama commented on Jul 6, 2026

steve-chavez commented on Jul 12, 2026

Andersama commented on Jul 12, 2026

steve-chavez commented on Oct 12, 2026

Andersama commented on Oct 17, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions