pid7

engineering ideas into reality

--:--:-- IST

Searching through 150 GiB of Text per Second with SIMD

Sep 2, 2026•4 min read•777 words

Writing an algorithm to search a single byte from a given payload is as easy as it can get. One just has to perform a byte-by-byte scan to find the needle (the substring) from the given haystack (the payload).

For every iteration of a 64-byte window from the haystack, one would fetch a cache line (64 bytes on modern x86 cpu) from DRAM into L1D and execute the following workflow:

  • issue a scalar load using movzx
  • compare a single byte
  • branch if the match is found
  • continue otherwise for all 64 bytes
asm 
.loop:
      movzx   al, byte [rdi]
      cmp     al, sil
      je      .match
      inc     rdi
      loop    .loop
byte-by-byte scan in x64 asm
Interactive Visualizer [001] visualization of byte-by-byte scan

On a machine with a 2.5 GHz cpu, we can churn through ~2.14 GiB of payload per second[1], where the maximum memory bandwidth is about 18.70 GiB per second[2]. So the potential maximum is about 770% higher (~8.7x) than the baseline rate.

This is because the execution is bounded by the instruction execution time, i.e. compute-bound[4], and not the rate at which payload is fed from memory, i.e. memory-bound[3].

§ SWAR #

SIMD within a register, a.k.a. SWAR, is a technique for processing multiple data elements using a single GPR with bitwise arithmetic.

Instead of scanning one byte at a time, with SWAR, we broadcast the needle across a 64-bit register, load eight bytes per iteration instead of one into a GPR, and check all eight byte lanes simultaneously.

rust 
let needle_qword = (needle as u64) * 0x0101_0101_0101_0101;
let chunk = ptr::read_unaligned(ptr.add(i) as *const u64);

let x = chunk ^ needle_qword;
let match_mask = !((x & 0x7F7F_7F7F_7F7F_7F7F)
      .wrapping_add(0x7F7F_7F7F_7F7F_7F7F) | x)
      & 0x8080_8080_8080_8080;

if match_mask != 0 {
    return Some(i + (match_mask.trailing_zeros() / 8) as usize);
}
SWAR byte-matching loop step w/ 64-bit registers using bitwise zero-byte detection

If the needle is matched, the mask marks the position, allowing trailing_zeros / 8 to find the match index with zero branching. This bitwise technique avoids branch mispredictions by turning conditional control into arithmetic.

Interactive Visualizer [002] visualization of SWAR scan

SWAR reaches about 9.25 GiB/sec throughput for cache-resident payloads on the same machine as the baseline, providing a >4.3x improvement in throughput. However, it still relies on multiple sequential ALU operations per eight bytes and remains constrained to 64-bit GPR widths.

§ SIMD #

Single Instruction Multiple Data, a.k.a. SIMD, enables hardware-level support for operating on multiple pieces of data at the exact same time, i.e. SWAR with dedicated hardware execution units.

So instead of working with standard 64-bit GPRs, the cpu is equipped with dedicated vector registers, whose sizes range from 128 bits (16 bytes) to 512 bits (64 bytes). With these wide registers, a single cpu instruction can process an entire block of data in parallel, drastically multiplying throughput.

info
These vector capabilities are cpu-specific hardware features exposed via ISA extensions. For instance, ARM processors include the 128-bit NEON extension, modern x86_64 contains 256-bit AVX2, while higher-end server processors feature 512-bit extensions like AVX512BW.

§ AVX512BW #

AVX512 features 512-bit ZMM vector registers, which hold up to 64 bytes—matching the exact width of an x86 cpu's cache line. A single vpcmpeqb instruction tests all 64 bytes simultaneously against the needle and writes the result directly into a 64-bit opmask register __mmask64.

rust 
let v_needle = _mm512_set1_epi8(needle as i8);

let v = _mm512_loadu_si512(ptr.add(i) as *const _);
let mask = _mm512_cmpeq_epi8_mask(v, v_needle);

if mask != 0 {
    return Some(i + mask.trailing_zeros() as usize);
}
AVX512BW (512-bit) byte-matching step scanning a full cache line (64-bytes)
tip
By loading a full cache line at a time and evaluating 64 bytes in a single instruction, the compute bottleneck completely disappears.
Interactive Visualizer [003] visualization of SIMD scan
note
Running this routine on an AWS EC2 Intel Xeon Platinum 8488C achieves ~149.73 GiB/sec throughput with ~203.8 ns of latency for a completely L1D cache-resident workload.

For completely L1D cache-resident payloads we get ~150 GiB/sec of throughput, and for DRAM-bound payloads (256 MiB to 1 GiB) we reach ~11.2–12.1 GiB/sec, fully saturating the single-core memory bandwidth ceiling.

§ Memory Wall #

One might wonder, if AVX512BW achieves ~150 GiB/sec for cache-resident workloads while AVX2 hits ~75–80 GiB/sec, why do both top out at ~11.2 to ~12.1 GiB/sec once the payload becomes DRAM-bound?

The simple answer is, for a memory-bound workload (which ours gracefully is 😎), SIMD width becomes irrelevant. The IPC for a single cpu core collapses from 3.10 down to 0.28 because the vector engine spends 90% of its time idling, stalled on memory requests.

In a single-threaded linear scan, memory throughput is governed by Little's Law,

Throughput=Concurrent LFBs×64 bytesDRAM Latency\text{Throughput} = \frac{\text{Concurrent LFBs} \times 64\text{ bytes}}{\text{DRAM Latency}}

On modern x86_64 processors, a single cpu core has a fixed, small pool of Line Fill Buffers (typically 12–32) to track in-flight cache line misses. While modern multi-channel memory subsystems (like 8-channel DDR5) can deliver 300+ GiB/sec across all cores, a single thread runs out of LFBs and hits a hard ~11–12 GiB/sec single-core memory wall, no matter how wide its vector registers are.

task
Check out Ashwa for the full implementation and detailed benchmark suite across x86_64, AArch64, and WASM.

#glossary

GiB
A gibibyte is a standard unit of digital information storage equal to 230 bytes2^{30}\text{ bytes} (1,073,741,824 bytes1{,}073{,}741{,}824\text{ bytes} or 1,024 MiB1{,}024\text{ MiB}), based on binary powers of two.
GPR
General Purpose Registers are high-speed architectural cpu registers (e.g., RAX, RDI, RSI in x86_64) used to hold temporary data operands and memory addresses for arithmetic and logic operations.
DRAM
Dynamic Random Access Memory is the primary volatile system memory where each bit of data is stored in an integrated circuit capacitor, requiring periodic refreshing.
Cache Line
The minimum unit of data transferred between main memory (DRAM) and cpu caches, typically 64 bytes on modern x86 and ARM architectures.
LFB
Line Fill Buffers are hardware buffers inside a cpu core that manage outstanding in-flight cache misses and track data transfers from DRAM into cpu caches.
ALU
Arithmetic Logic Unit is a fundamental digital circuit within a cpu execution core that carries out arithmetic and bitwise logic operations.
ISA
Instruction Set Architecture is the part of cpu architecture defining supported instructions, data types, registers, memory models, and fundamental hardware features.
IPC
Instructions Per Cycle is a performance metric measuring the average number of completed instructions executed per clock cycle by a cpu core.
L1D
Level 1 Data Cache is the fastest and smallest hardware memory cache integrated directly into a cpu core for data access.
SIMD
Single Instruction Multiple Data is a hardware execution model that operates on multiple data elements simultaneously with a single instruction.
SWAR
SIMD Within A Register is a software technique for operating on multiple data lanes in parallel inside standard general-purpose registers using bitwise arithmetic.

#references

  1. [1]
    Calculated for a single core running at 2.5 GHz2.5\text{ GHz} processing ≈1.087 cycles/byte\approx 1.087\text{ cycles/byte} (including loop/branch overhead):
    Throughput=2.5×109 cycles/s1.087 cycles/byte×10243 bytes/GiB≈2.14 GiB/sec(2.30 GB/s)\text{Throughput} = \frac{2.5 \times 10^9\text{ cycles/s}}{1.087\text{ cycles/byte} \times 1024^3\text{ bytes/GiB}} \approx \mathbf{2.14\text{ GiB/sec}} \quad (2.30\text{ GB/s})
    Benchmark implementation and measurements available on GitHub Gist.
    ↩
  2. [2]
    Measured memory bandwidth from the STREAM Triad benchmark on the dual-channel DDR4 test machine:
    Bandwidth=20,083.66 MB/s=20,083.66×106 bytes/s230 bytes/GiB≈18.70 GiB/sec(20.08 GB/s)\begin{aligned} \text{Bandwidth} &= 20{,}083.66\text{ MB/s} \\ &= \frac{20{,}083.66 \times 10^6\text{ bytes/s}}{2^{30}\text{ bytes/GiB}} \\ &\approx \mathbf{18.70\text{ GiB/sec}} \quad (\mathbf{20.08\text{ GB/s}}) \end{aligned}
    Note that while the multi-array STREAM Triad reaches ≈18.70 GiB/sec\approx 18.70\text{ GiB/sec}, single-core sequential read scans max out the core's Line Fill Buffers at ≈12.1 GiB/sec\approx 12.1\text{ GiB/sec} on this hardware.
    ↩
  3. [3]
    A memory-bound workload is one whose throughput is constrained by memory subsystem latency or bandwidth, meaning compute units spend idle cycles waiting for data to arrive from DRAM or cache.
    ↩
  4. [4]
    A compute-bound workload is one whose throughput is constrained by instruction execution throughput (ALU ports, instruction decoding, or branch overhead) rather than the rate at which data is fed from memory.
    ↩