SIMD Programming

Single Instruction, Multiple Data — the hardware capability that consistently separates the fastest data structure implementations from the rest. SIMD processes 16–64 bytes per instruction using vector registers (SSE, AVX2, AVX-512, NEON), transforming sequential comparisons into batch operations.

Where SIMD dominates data structures

In Rust

pulp provides portable SIMD on stable Rust with runtime CPU feature detection and dispatch. The standard library's std::simd is still unstable. hashbrown uses SIMD for Swiss Table probing. simdjson has Rust bindings via simd-json.

The key insight

SIMD is not just for numerical computing. Its biggest impact is in metadata scanning — checking multiple candidates simultaneously in hash maps, trees, and filters. This pattern, pioneered by swiss-table, has become a universal technique for high-performance data structure design.

The 16-byte _mm_cmpeq_epi8 is the canonical example. Stored alongside each slot, a 1-byte fingerprint summarizes the actual key; broadcasting the looked-up fingerprint across an SSE register and comparing it against 16 metadata bytes in one instruction filters out ~99.2% of slots without ever touching the key data. boost-unordered-flat-map, abseil-flat-hash-map, hashbrown, folly-f14, and Go 1.24's built-in map all rely on variations of this pattern — even Go, which uses portable 64-bit integer SIMD emulation rather than hardware vector instructions. See fastest-hash-map-2025 for the full hash map landscape.

SIMD memcpy and dynamic-array growth

SIMD's other major contribution to data structures is bulk memory transfer during reallocation. AVX2-optimized memcpy achieves 2–20× faster copying than scalar code on large aligned blocks, processing 256 bits per instruction; AVX-512 doubles that to 512 bits. For a 1 GB std::vector<int> reallocation, the difference between scalar and AVX-512 copying is the difference between memory-bandwidth-bound and instruction-throughput-bound — at the bandwidth limit either way, but reaching it with far fewer instructions issued.

Modern memcpy/memmove in glibc and musl already use SIMD internally and dispatch to the widest available instruction set at runtime. The remaining lever is alignment: passing an aligned destination to memcpy lets the implementation use aligned-load instructions, which are faster than unaligned ones on older microarchitectures and avoid cache-line splits everywhere. Crates like xsimd::aligned_allocator ensure dynamic arrays produce aligned buffers; Rust's Vec is naturally aligned to std::mem::align_of::<T>(). See fastest-dynamic-arrays for where SIMD memcpy fits in the hierarchy of dynamic-array optimizations and trivial-relocatability for which types qualify for the memcpy path during vector growth.