SIMD Vectorization

Every CPU runs a stream of instructions. For most of computing history, each instruction operated on one number at a time: add two integers, write the result, move on. The program loops over arrays element by element, one clock per value.

SIMD — Single Instruction, Multiple Data — breaks that constraint. Instead of one 32-bit add, a SIMD register packs four, eight, or sixteen values side by side, and a single instruction adds them all in parallel. The loop body does the same work; the hardware just runs it across a whole lane at once.

The idea is not new — Cray supercomputers used vector registers in the 1970s. But it became universal in 1996 when Intel shipped MMX, and has accelerated ever since: SSE (1999), SSE2 (2001), AVX (2011), AVX-512 (2017). Today every smartphone, laptop, and server runs SIMD every second without the programmer even noticing — the compiler handles it automatically.

Understanding SIMD matters for algorithm design because raw algorithmic improvements and SIMD often stack: a $O(n \log n)$ algorithm vectorized by $8\times$ beats both a slow $O(n)$ scalar loop and a fast $O(n)$ loop that ignores SIMD.

The demo below animates two strategies processing the same array of numbers. The scalar loop visits one element per step; the SIMD loop highlights a whole lane simultaneously.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label>{{label_array_size}} <strong id="sz-val">16</strong>
    <input id="sz" type="range" min="8" max="32" step="8" value="16">
  </label>
  <label>{{label_lane_width}} <strong id="lw-val">4</strong>×
    <input id="lw" type="range" min="1" max="8" step="1" value="4">
  </label>
</div>
<div class="arena">
  <div class="track">
    <div class="track-label">{{label_scalar}}</div>
    <div id="scalar-cells" class="cells"></div>
    <div class="step-info">{{label_steps}} <span id="scalar-steps">0</span></div>
  </div>
  <div class="track">
    <div class="track-label">{{label_simd}}</div>
    <div id="simd-cells" class="cells"></div>
    <div class="step-info">{{label_steps}} <span id="simd-steps">0</span></div>
  </div>
</div>
<div class="speedup-box" id="speedup-box"></div>
<div class="btns">
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; gap: 1.2rem; flex-wrap: wrap; margin-bottom: .8rem; font-size: .9rem; }
.controls label { display: flex; align-items: center; gap: .4rem; }
.controls input[type=range] { width: 90px; cursor: pointer; }
.arena { display: flex; flex-direction: column; gap: .7rem; margin-bottom: .8rem; }
.track { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; }
.track-label { width: 3.6rem; font-size: .78rem; font-weight: 700; color: #555; text-transform: uppercase; letter-spacing: .03em; }
.cells { display: flex; gap: 3px; flex-wrap: wrap; }
.cell { width: 28px; height: 28px; border-radius: 5px; background: #dde3ea; border: 1.5px solid #c5cdd7;
        display: flex; align-items: center; justify-content: center;
        font: 600 10px ui-monospace, monospace; color: #444; transition: background .12s, border-color .12s; }
.cell.active { background: #2563eb; border-color: #1d4ed8; color: #fff; }
.cell.done { background: #16a34a; border-color: #15803d; color: #fff; }
.step-info { font-size: .82rem; color: #666; margin-left: .3rem; }
.speedup-box { font-size: 1rem; font-weight: 700; min-height: 1.5em; margin-bottom: .5rem; color: #2563eb; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: not-allowed; }

// Code not found

Drag the lane width slider to see what 2×, 4×, or 8× parallelism looks like. The step counter tracks how many passes each strategy takes — the speedup is exactly the lane width, assuming the data fits and the loop has no cross-lane dependencies.

SIMD speedup looks like magic, but the rules are strict:

• Wide registers. A 256-bit AVX register holds eight 32-bit floats. One VADDPS instruction adds eight pairs simultaneously. The hardware cost is roughly the same as adding one pair — silicon area, not extra time.
• Throughput vs latency. A SIMD add still takes a few clock cycles to complete (latency), but a modern CPU can issue one per clock (throughput). With enough independent operations, the pipeline stays full.
• Alignment matters. Loading data into a SIMD register is fastest when the memory address is aligned to the register width (16, 32, or 64 bytes). Unaligned loads work on modern chips but can cost extra cycles.
• No cross-lane branches. Every lane executes the same instruction. If different elements need different code paths — a classic if inside a loop — the hardware masks inactive lanes, paying the cost of both branches.
• Gather and scatter are slow. Collecting non-contiguous values from memory into a lane (a gather) is supported but far slower than loading a contiguous block. Algorithm design for SIMD favors struct-of-arrays over array-of-structs layouts.
• Auto-vectorization. Modern compilers (GCC, Clang, MSVC) analyze loops and emit SIMD instructions automatically — if they can prove there are no loop-carried dependencies and memory aliases. A restrict keyword or #pragma omp simd hint is sometimes all it takes.

The theoretical speedup equals the lane count ($4\times$ for SSE, $8\times$ for AVX floats, $16\times$ for AVX-512 bytes). In practice, memory bandwidth and cache misses often cap the gain before the lane count does.

Almost every domain that processes large arrays of uniform data benefits from SIMD:

• Image and video processing: brighten every pixel, apply a blur kernel, decode a video frame — these are pure element-wise or sliding-window operations, ideal for SIMD. Modern codecs (AV1, H.265) are written almost entirely in hand-optimized SIMD.
• Machine learning: the inner loop of a matrix multiply is a dot product, and a dot product is a fused multiply-add over a lane. Neural network inference on a phone is fast because the CPU runs hundreds of SIMD multiply-accumulates per clock.
• Audio DSP: an FFT over 1024 samples processes eight lanes at once with AVX; reverb and EQ filters run at $8\times$ speed with no algorithm change.
• Database engines: columnar stores like DuckDB scan integer columns with SIMD comparisons, filtering millions of rows per millisecond.
• Cryptography: AES-NI is a dedicated SIMD extension that encrypts 128-bit blocks in a single instruction, making software AES competitive with hardware accelerators.
• Scientific computing: fluid simulations, molecular dynamics, and weather models are dominated by floating-point stencils that vectorize almost perfectly.

Whenever a compression codec, a graphics shader, or a search engine feels instant, SIMD is usually one of the reasons.

SIMD vectorization is one of those ideas that looks like a hardware detail but reaches into every corner of software. The algorithm stays the same; the machine just stops processing one lane at a time.

The constraint — same instruction, all lanes — is also the design pressure that has shaped data layouts, compiler internals, and even mathematical libraries for decades. Every time you use a photo filter, stream music, or run a neural network on your phone, a SIMD unit is quietly doing eight things at once.

The next frontier is even wider: AVX-512 doubles the lane width again, and GPU compute takes the same idea to thousands of lanes in parallel. But the core insight is unchanged: if the work is the same for every element, there is no reason to do it one at a time.