SIMD: making every cycle count.

SIMD is not a wider instruction. It is a discipline for structuring work so that the wide instruction is even reachable.

The common framing is that vector intrinsics make loops faster by the register width. This often produces wider, slower code. The instruction is easy; arranging data, control flow, and memory to avoid stalls and branches is hard. l treats SIMD as the default shape of every primitive.

Width is a tactic, not a strategy

A 512-bit register holds sixteen 32-bit integers. The expectation is 16x, but you rarely see it. Width is the ceiling; discipline decides how close you get. Vectorized gathers from scattered memory can be slower than scalar streams. The win is layout, not instructions.

theoretical    -> 16x
branch in loop -> mispredict per lane
gather/scatter -> serialized memory ports
bandwidth      -> the line, not the lane, is the unit

The register width is the ceiling. Everything else is the discipline that decides how close you get to it. A correctly vectorized kernel that gathers from sixteen cache lines is slower than a scalar loop that streams one. The win is not in the instruction. It is in the layout that feeds the instruction.

Masks instead of branches

A branch inside a loop is a decision made one element at a time. A vector has no single answer to if; sixteen lanes may disagree. The scalar instinct is to peel out the disagreeing lanes. The SIMD instinct is to compute both sides and select:

// scalar - one decision per element
if x[i] < 0: y[i] = -x[i]
else:        y[i] =  x[i]

// simd - one decision per vector
m = x < 0          // mask, 16 lanes at once
y = select(m, -x, x)

The branch became a comparison and a blend. No misprediction, no pipeline flush, no divergence between lanes. This is the move that makes filters, clamps, null handling, and conditional reductions vectorizable at all. A predicate is not a fork in control flow; it is a value, computed in lanes, consumed in lanes. Once you stop branching, the comparator and the blend are the whole cost, and both run at one lane per cycle-equivalent across the full width.

In place, not scratch-plus-copy

The textbook vectorized partition writes matching elements to a scratch buffer, then copies the buffer back. Two passes, two times the memory traffic, and the copy is pure overhead. The disciplined version partitions in place using a compress-store: the mask drives a permutation, the survivors are packed to the front, and nothing is copied twice.

// scratch model - 2 passes, 2x traffic
for lane in x: if keep(lane): scratch.push(lane)
copy scratch -> x

// compressed-store - 1 pass, in place
m   = keep(x)
x   = compress(x, m)     // pack survivors, no scratch

This matters far beyond where. Partition is the inner step of sort, of join build, of group, of any operation that has to split a vector by a predicate. Halving its memory traffic compounds every time it is called inside a larger primitive. The kernel that does less copying wins, even when both kernels are “vectorized.”

kernel	vs. scalar (AVX-512)
clamp / abs (masked)	11x
where (compress-store)	8.4x
partition (in place)	6.2x
sum / avg (streamed)	9.7x

Why correct parallel code can still be slow

You can vectorize every loop, prove every result correct, and still leave most of the machine idle. Correctness is not throughput. The usual culprits are not arithmetic at all:

Gather and scatter serialize. A vector load from sixteen scattered addresses is not one wide load. It is sixteen loads dressed as one, bounded by the number of memory ports. A primitive that gathers has thrown away the thing that made it wide. The fix is upstream: arrange the data so the access is contiguous, and the gather disappears.

Bandwidth is the real ceiling. A cache line is 64 bytes, the unit the memory system actually moves. If your kernel touches one value per line, the other fifteen lanes are paying for bytes they never use. This is why l keeps vectors compressed in flight: fewer bytes per line means the wide instruction is fed, not starved.

Lane divergence wastes the width. If half the lanes take a slow path, the vector runs at the speed of its slowest lane. Branchless code removes divergence; sorted or grouped inputs remove it further by clustering like work together.

fast simd =
    contiguous reads
  + branchless lanes
  + bytes the line actually uses
  + no lane left waiting

Each of these is a property of the data and the surrounding code, not of the instruction you reached for. That is why “I vectorized it” and “it got faster” are different claims.

The runtime owns the discipline

None of this should be the programmer’s job. You write sum x, x < 100, where, asc x. The decision to use a mask instead of a branch, to compress-store instead of copy, to stream instead of gather, to fall back to scalar when the width cannot pay: that decision belongs to the runtime, which can see the physical layout and the size of the input.

if the layout keeps lanes fed and branch-free:
    run the wide kernel
else:
    narrow it, or fall back to scalar

SIMD width is not free performance. It is a budget the runtime spends only when the surrounding discipline has earned it. The small kernel becomes a masked reduction; the same verb at scale fans out across threads. The syntax never changes. The physical plan does.

k: the vector is the unit of expression. l: the lane is the unit of execution. SIMD: keep every lane fed, branch-free, and reading in line.

Every cycle counts because the wide instruction makes the cost of waste wider too. A stalled scalar wastes one cycle. A stalled vector wastes sixteen. The discipline exists so that the width is an asset, not an amplifier of the things you got wrong.

References

• Inoue, Taura, SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures
• Polychroniou, Raghavan, Ross, Rethinking SIMD Vectorization for In-Memory Databases
• Zhou, Ross, Implementing Database Operations Using SIMD Instructions
• Lemire, Boytsov, Decoding Billions of Integers per Second through Vectorization
• Gueron, Krasnov, Fast Quicksort Implementation Using AVX
• Intel, Intel 64 and IA-32 Architectures Optimization Reference Manual