9 August 2025 · 5 min
Last week, I was chatting with a student and I was explaining what SIMD instructions were. I was making the point that, in practice, all modern processors have SIMD instructions or the equivalent. Admittedly, some small embedded processors do not, but they lack many other standard features as well. SIMD stands for Single Instruction, Multiple Data, a type of parallel computing architecture that allows a single instruction to process multiple data elements simultaneously. For example, you can compare 16 bytes with 16 other bytes using a single instruction.
Suppose you have the following string: stuvwxyzabcdefgh. You want to know whether the string contains the character ‘e‘. What you can do with SIMD instructions is load the input string in a register, and then compare it (using a single instruction) with the string eeeeeeeeeeeeeeee. The result would be something equivalent to 0000000000001000 indicating that there is, indeed, a letter e in the input.
Our programming languages tend to abstract away these SIMD instructions and it perfectly possible to have a long career in the software industry without even knowing what SIMD is. In fact, I suspect that most programmers do not know about SIMD instructions. If you are programming web applications in JavaScript, it is not likely to come up as a topic. (Fun fact, there was an attempt to introduce SIMD in JavaScript by the JavaScript SIMD API.)
Yet if SIMD is everywhere but few people know about it, is it even needed ?
Suppose that you are looking for the first instance of a given character in a string. In C or C++, you might implement a function like so:
const char* naive_find(const char* start, const char* end, char character) { while (start != end) { if (*start == character) { return start; } ++start; } return end; }
The naive_find function searches for the first occurrence of a specific character within a range of characters defined by two pointers, start and end. It takes as input a pointer to the beginning of the range (start), a pointer to the end (end), and the character to find (character). The function iterates through the range character by character using a while loop, checking at each step if the current character (*start) matches the target character. If a match is found, the function returns a pointer to that position. Otherwise, it increments start to move to the next character. If no matching character is found before reaching end, the function returns end, indicating that the character was not found in the specified range. My function is not Unicode-aware, but it is still fairly generic.
What is wrong with this function? As implemented, it might require about 6 CPU instruction per character. Indeed, you have to compare the pointers, de-reference the pointer, compare the result, increment the point, and so forth. Either you or the compiler can improve this number somewhat, but that’s the basic result. Unfortunately, your processor may not be able to retire more than 6 instructions per cycle. In fact, it is likely that your processor might not even be able to sustain 6 instructions per cycle.
Thus, naively implemented, a simple search for a character in a string will run at the speed of your processor or less: if your processor runs at 4 GHz, you will run through the string at 4 GB/s. Importantly, that’s likely true irrespective of whether the string is small and fits in CPU cache, or whether it is large and located outside of the CPU cache.
Is that a problem ? Isn’t 4 GB/s very fast ? Well. It is slower than a disk. The disk in my aging PlayStation 5 has a bandwidth of 5 GB/s. You can go to Amazon and order a disk with a 15 GB/s bandwidth.
Instead, let us compare against the ‘find’ function that we implemented in the simdutf library, using SIMD instructions. The performance you get depends on the processor and the SIMD instructions it supports. Let me use my Apple M4 processor as a reference. It has relatively weak SIMD support with only 16-byte SIMD registers. It pales in comparison to recent AMD processors (Zen 5) which have full support for 64-byte SIMD registers. Still, we can use about 4 instructions per block of 16 bytes. That’s over 20 times fewer instructions per input character. For strings of a few kilobytes or more, I get the following speeds.
| naive search | 4 GB/s |
| simdutf::find | 110 GB/s |
That is, the simdutf::find function is more than 20 times faster because it drastically reduces the number of required instructions.
Given our current CPU designs, I believe the SIMD instructions are effectively a requirement to achieve decent performance (i.e., process data faster than it can be read from a disk) on common tasks like a character search.
The source code of my benchmark is available. You might also be interested by the simdutf library which offers many fast string functions.
Daniel Lemire, "Why do we even need SIMD instructions ?," in Daniel Lemire's blog, August 9, 2025, https://lemire.me/blog/2025/08/09/why-do-we-even-need-simd-instructions/.
[BibTeX]
A lot of DBs use SIMDs to move blocks of data. But a general purpose SIMD is not needed for that.
Usually that should be implemented elsewhere. ???
The AMD registers are 64-BIT, not 64-byte.
The SIMD registers are 64 bytes. The general-purpose registers are 64 bits.
They are 512 bit, regular registers are 64 bit
Way to make yourself look like a complete noob. They are 512 BITS, or 64 BYTES. Welcome to AVX512, jeez
It’s usually expressed in bits but the avx512 registers are 512bits = 64 bytes.
Naive_find() also suffers from the flaw that if called with end < start, start will be incremented until *start SEGVs.
One case where the loop guard (start < end) is probably safer.
I imagine non SIMD libc implementations of strchr()/memchr() load the string in 8 byte word chunks into a register and uses the fastest of a sequence of shifts, xors, masks to locate the specified character.
One case where the loop guard (start < end) is probably safer.
The simdutf library has these guards but I am not certain that the standard std::find does.
I imagine non SIMD libc implementations of strchr()/memchr() load the string in 8 byte word chunks into a register and uses the fastest of a sequence of shifts, xors, masks to locate the specified character.
You can do it with SWAR but it will generate substantially more instructions.
Please see my pull request that may significantly impact this benchmark: https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/pull/118
I love simd on the various platforms. I used to be very good at writing optimized simd code that screamed it was so fast. Compilers do a poor job. Generating good simd code. The problem is companies do not want to pay for CPU base simd anymore. They’ll just buy a faster computer and call it good enough.
Modern C libraries are using SIMD for many library functions. So even if you’re not using it, the library might.
I highly doubt that.
I find it typical dev behavior. Here a guy is just showing a base case to introduce SIMD and how it could be more performent in today’s typical CPU. Then the trolls creep out and try to one up or discredit his understanding.
Thanks for your post. Informative and served its purpose.
naive_find can be easily fixed by keeping start variable in CPU register. Every modification of variable in memory must reach memory which means ++start operation put CPU in wait for about 20 -25 cycles. Keeping it in register avoids the wait.
The ‘start’ variable (pointer) is likely kept in a register. The string content itself could not be kept in registers, there are not enough register files for that.
Start variable wont be in register. It must be declared as register. Exotic like fastcall long gone. String will be cached. Cache line is 64 bytes. (By accident?) Hence not a big difference between loading into SIMD register or keeping it in L1 cache.
My point was that naive_find may reach 90-100GB/sec with no doubt.
Cache or not, this is not the point here. The point is that you’ll still have to execute several instructions per cycle, and because your control flow depends on the result of every cycle, you cannot parallelize them (unless your cycle does speculative executions, but even then the results will be checked one by one.)
Dear Daniel,
thanks for your informative blog. I have a couple of questions (that may sound like I understand the topic more than I actually do); would appreciate your opinion:
(0) I’m unsure what you mean by “your processor may not be able to retire more than 6 instructions per cycle”. Is “retire” a typo?
(1) I assume with pipelining a modern CPU should be able to perform one char comparison per cycle, without SIMD. Since a char comparison takes two char inputs, that would mean 8GB/s, not 4GB/s, no?
(2) How does the picture change when you operate on doubles (where the basic unit of input is 8 bytes, not 1 byte) so you should be able to achieve 4GHz*16bytes=64GB/s without SIMD, no?
(3) How does the picture change if you’re doing multi-threading (which all performance sensitive applications, like databases, do anyway)? Then even your string example would achieve 4GB/s * 16cores=64GB/s, no?
1. Retiring is the correct term. We retire an instruction when its execution came to term. On modern processors, an instruction may be initiated by never completed.
2. If you do one character comparison per cycle, and you need to compare each character from your input with a target character, and your processor runs at 4 GHz, you will achieve 4 GB/s where the ‘GB’ relates to the size of the input string (not counting the target character).
3. Work on numerical types is outside the scope of my blog post, but SIMD was initially designed for numerical processing. I could have written an alternate blog post, motivated by numerical processing.
4. You can multithread but it won’t help you with your short string that fits in cache.
SIMD has its use cases. Consider Audio/Video/Games programming. e.g. with SSE in single ADD, MUL operations two audio channel with 2x oversampling could be calculated, or 4 voices of an instrument.
Wow a 15 Giga Byte per second disk at Amazon? I want this, if you have a link I take it. I have tested a lots of disks and never got anything close to this on a sustain basis.
What if found character – is last character – end?
It would be interesting for completeness to add a version that fetches a full word at a time. So often memory access dominates tight loops like the naive impl.
A modern processor can easily sustain one load per cycle, typically two loads or more. The Apple M4 can assuredly sustain two loads per cycle.
It’s been a while since I worked with SIMD. Back then the most annoying problem was alignment. It was quite a hassle to implement special handling for data located at the beginning and at the end of an unaligned chunk.
I believe there is a glibc routine “memchr” that performs better than the options presented, with the same functionality.
I have submitted a pull request.
https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/pull/119
Results on my box:
| Input Size (bytes) | memchr (GB/s) | std::find (GB/s) | simdutf::find (GB/s) | naive_find (GB/s) |
|——————–|——————|——————|———————–|——————-|
| 1024 | 105.96 | 4.91 | 28.97 | 3.65 |
| 8192 | 174.75 | 5.04 | 50.29 | 3.78 |
| 65536 | 120.42 | 5.06 | 57.73 | 3.79 |
| 524288 | 101.33 | 5.06 | 58.30 | 3.79 |
| 2097152 | 84.29 | 5.06 | 58.19 | 3.80 |
Investigating various functions is outside the scope of the blog post, but I have added memchr to the benchmark. It is likely that many reasonable implementations of std::find will call memchr although it seems GCC12 does not.
Results on Ice Lake processor (GCC12)
Results on Apple M4 (Apple LLVM 17)
Why doesn’t your compiler auto-vectorize such a simple function as the naive_find? … In general I think it’s better to let the compiler do the job (if it is capable) and keep the source code easy to read. I usually use Compiler Explorer so I can see what the assembly code ends up like and then take care to add restrict-qualifiers where there could be data-dependencies that prevent optimization until I get the result I want.
The blog post seeks to answer the question ‘“Why do we even need SIMD instructions ?’. If I autovectorize the naive version, it defeats the purpose of the blog post.