Everyone should know SIMD

Everyone Should Know SIMD

SIMD has a reputation for being complex. I've met many very good software engineers who dismiss it as something too complex to learn or a niche optimization meant for only the highest-performance software, not useful in everyday programming.

I think that's wrong. SIMD can be simple to understand, and common "process N values at a time" SIMD code to speed up a naive for loop almost always follows the same general shape. Once you learn the basics, writing SIMD is just about as easy as a for loop. And when it's not, it's usually a good sign to skip it for now.

Every developer should know at least that much SIMD.

This post uses Zig for examples but is a general piece that applies to any programming language. Support for SIMD instructions varies by programming language and I hope that more programming languages expose these generic concepts in the future!

I hate that I have to do this for every post now, but I also want to note this was completely hand-written with no AI assistance.

Background: What Is SIMD?

If you already know what SIMD is, skip this section.

SIMD allows a CPU to operate on multiple values in parallel. For example, instead of comparing one byte at a time, a CPU can compare 4, 8, or even more bytes with a single instruction.

If you ever see loops like this in your code:

for (byte in bytes) { /* ... */ }
for (character in string) { /* ... */ }
for (value in array) { /* ... */ }

There is an opportunity to use SIMD. SIMD turns those into this:

for (8 byte chunk in bytes) { /* ... */ }

This results in a localized speedup that directly maps to the parallelism: you process data 4x, 8x, or even faster.

The only real requirement for this to pay off is that you need to be regularly processing a large enough number of bytes. If you're doing these for loops across data that is only ever a handful or dozens of bytes, it's not worth it. But if this is iterating over hundreds, thousands, millions of bytes, the payoff will be huge.

That's the basics. Projects such as simdutf and simdjson take this to an extreme and use SIMD techniques that can be difficult to understand. But you do not need to write algorithms like those to benefit from SIMD. The common case is dramatically simpler.

The Common Shape

The common "process N values at a time" SIMD code follows the same five steps:

• Broadcast any constants you need and initialize vector accumulators, if any.
• Loop over input one vector-width chunk at a time.
• Perform the comparison or arithmetic across all lanes in parallel.
• Reduce or store the vector result as needed.
• Handle the remaining elements with a scalar tail. A scalar tail is just your normal loop from before vectorizing, but it only processes the remainder that doesn't fit into a full vector.

As you do this more and more, you'll begin to naturally decompose every for loop into these five steps and writing SIMD becomes nearly as natural as writing a scalar loop.

A Real Example

Let's look at a real example from Ghostty. We'll look at the scalar implementation, the SIMD implementation, and then map it back to the common shape above.

I have a slice of decoded codepoints that I want to consume until I see a value at or below 0xF (a C0 control character). Terminals are mostly plain characters to be printed, so we try to batch all those together. So this loop finds the end of the next printable run as quickly as possible.

The scalar loop is one line:

while (end < cps.len and cps[end] > 0xF) end += 1;

It processes one codepoint at a time. It is easy to understand.

Here is the generic vector version with no CPU-specific intrinsics and no comments. I will explain it in detail later.

if (simd.lanes(u32)) |lanes| {
    const V = @Vector(lanes, u32);
    const threshold: V = @splat(0xF);
    while (end + lanes <= cps.len) : (end += lanes) {
        const values: V = cps[end..][0..lanes].*;
        const greater_than_threshold = values > threshold;
        if (@reduce(.And, greater_than_threshold)) continue;
        const mask: std.meta.Int(.unsigned, lanes) = @bitCast(greater_than_threshold);
        end += @ctz(~mask);
        break;
    }
}
while (end < cps.len and cps[end] > 0xF) end += 1;

12 more lines of code.

This can improve the loop's throughput by up to 4x with ARM NEON (including Apple Silicon), 8x with AVX2 (most modern x86 CPUs), and 16x with AVX-512 (some Intel CPUs and AMD Zen 4 and newer).

In real-world end-to-end throughput from terminal program to finalized terminal state on an AVX2 Intel desktop, this was more like a 5x speedup. You always lose some of the ideal speedup due to the other stuff around the SIMD code, but... that's still 5x!

Okay, now I understand that those 12 lines are going to look really alien to someone not familiar with the concepts. So now let's back up and explain it step by step, mapping it directly to the shape previously mentioned.

Step 1: Broadcast Constants

Let's start with the first three lines:

if (simd.lanes(u32)) |lanes| {
    const V = @Vector(lanes, u32);
    const threshold: V = @splat(0xF);

simd.lanes(u32) is a helper in Ghostty that returns the number of u32 values the target CPU can process at once. These individual values are called lanes. On ARM this returns 4, AVX2 returns 8, and AVX-512 returns 16. If the target doesn't have a vector size we want to use, it returns null and we skip all of this code and do zero SIMD work.

@Vector(lanes, u32) creates the vector type. If lanes is 8, then V is a single value containing eight u32 values that the CPU can operate on in parallel. And so on.

Finally, we need to compare every value to 0xF. A vector comparison requires a vector on both sides, so @splat(0xF) copies, or broadcasts, 0xF into every lane. The result is a vector that looks like this:

{ 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF }

This is step 1: prepare the vector type and broadcast any constants. Some algorithms also initialize a vector accumulator here, but this algorithm doesn't need one.

Step 2: Loop One Vector at a Time

Next, we loop over one complete vector at a time:

while (end + lanes <= cps.len) : (end += lanes) {
    const values: V = cps[end..][0..lanes].*;

If lanes is 8, we only enter the loop when at least eight values remain. Inside the loop, we load those eight values into the vector values. At the end of every loop, end += lanes moves forward by eight values instead of one.

The requirement for a complete vector is important. If only five values remain, we can't load an eight-lane vector. There are various tricks to handle this, but we do the easy thing and handle them via our scalar tail, which I'll explain later in step 5.

This is step 2: load and loop over the input one vector-width chunk at a time. You can see the lane-count speedup here!

Step 3: Perform the SIMD Operation

Now we perform the comparison:

const greater_than_threshold = values > threshold;

Both values and threshold are vectors, so this maps to a vector operation (a literal vector CPU instruction). The one > compares every lane in values to every corresponding lane in threshold. If there are eight lanes, this is equivalent to performing the scalar comparison cps[end] > 0xF eight times, but it does it in one CPU instruction instead.

The result is another vector with one boolean per lane. Conceptually, it looks something like this:

values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
threshold:              { 0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF  }
greater_than_threshold: { true, true, true, false, true, true, true, true }

This is the actual SIMD operation. There is no explicit inner loop. The > operator applies to every lane in parallel.

Comparisons are only one example. This could be addition, multiplication, minimum, maximum, or any other operation supported by the vector type. The point is the code still has the same shape.