SIMD Performance Optimization
What is SIMD?
Single Instruction, Multiple Data. One instruction operates on multiple data elements (lanes) simultaneously.
Scalar: a + b → 1 operation
SIMD: [a0,a1,a2,a3] + [b0,b1,b2,b3] → 4 operations at once
Register Widths
| Extension | Width | u8 lanes | u32 lanes | f32 lanes |
|---|---|---|---|---|
| SSE | 128-bit | 16 | 4 | 4 |
| AVX2 | 256-bit | 32 | 8 | 8 |
| AVX-512 | 512-bit | 64 | 16 | 16 |
When SIMD Applies
- Data parallelism: Same operation on many elements
- Hot loops: Processing arrays, strings, pixels
- Compute-bound: Not memory带宽 limited
Signs You Need SIMD
- Byte-by-byte processing in hot paths
- String/array transformations
- Image/audio processing
- Cryptography, compression
- Search, pattern matching
Manual Vectorization
Basic Loop Vectorization
// Scalar
for (int i = 0; i < n; i++)
c[i] = a[i] + b[i];
// Vectorized (4 elements at a time)
for (int i = 0; i < n; i += 4) {
__m128i va = _mm_loadu_si128(&a[i]);
__m128i vb = _mm_loadu_si128(&b[i]);
__m128i vc = _mm_add_epi32(va, vb);
_mm_storeu_si128(&c[i], vc);
}
Residual Iterations
Handle non-multiple-of-VF lengths:
int main_loop = n - (n % 4);
for (int i = 0; i < main_loop; i += 4) { /* vectorized */ }
for (int i = main_loop; i < n; i++) { /* scalar */ }
Aliasing
Pointers may overlap. Use restrict or runtime checks:
void process(float* restrict a, float* restrict b, int n);
Reductions
Sum/product across all lanes requires horizontal operations.
Sum Reduction
// Horizontal add (slow - serial dependencies)
__m128 sum4(__m128 v) {
v = _mm_hadd_ps(v, v); // [a0+a1, a2+a3, b0+b1, b2+b3]
v = _mm_hadd_ps(v, v); // [a0+a1+a2+a3, ..., ..., ...]
return _mm_cvtss_f32(v);
}
// Better: pairwise addition in registers
float sum_array(float* a, int n) {
__m256 acc = _mm256_setzero_ps();
for (int i = 0; i < n; i += 8)
acc = _mm256_add_ps(acc, _mm256_loadu_ps(&a[i]));
// Final reduction: 8 floats → 1
__m128 lo = _mm256_castps256_ps128(acc);
__m128 hi = _mm256_extractf128_ps(acc, 1);
return _mm_cvtss_f32(_mm_add_ps(lo, hi));
}
Reduction Rules
- Operation must be associative (addition, min, max, AND, OR, XOR)
- Floating-point: use
-ffast-mathif precision loss is acceptable - Commutativity helps: reorder operands for parallelism
Conditional Code (If-Conversion)
Branches prevent vectorization. Convert to branchless operations.
Masked Selection
// Branchy (hard to vectorize)
for (int i = 0; i < n; i++)
if (cond[i])
out[i] = a[i] + b[i];
// Branchless (vectorizes well)
__m256 cond = _mm256_cmp_ps(a, b, _CMP_GT_OQ);
__m256 result = _mm256_add_ps(a, b);
__m256 out = _mm256_blendv_ps(original_out, result, cond);
Blend Instructions
_mm_blendv_ps(a, b, mask): Select from a or b based on mask- Mask: all 1s = select from b, all 0s = select from a
- Generates branchless code
Rules for Conditional Vectorization
- Compute both branches unconditionally
- Use blend to select result
- Beware: dividing by zero, out-of-bounds still executes
- Profile: doubling work may not pay off if branch is predictable
Shuffles and Swizzles
Common Shuffles
// Broadcast/splat: all lanes same value
__m256 all = _mm256_broadcastss_ps(&x);
// Interleave: [a0,b0,a1,b1,...]
__m256 r = _mm256_unpacklo_ps(a, b);
// Rotate lanes
__m256 r = _mm256_roti_epi32(v, 1); // Rotate right by 1
Swizzle Patterns
// Rust core::simd
let shuffled = simd_swizzle!(v, [3, 2, 1, 0]); // Reverse
let broadcast = simd_swizzle!(v, [0, 0, 0, 0]); // Splat
Strided Access
Gather/Scatter
Load from non-contiguous memory:
// Gather: load from indices [i0, i1, i2, i3]
__m128i indices = _mm_set_epi32(i3, i2, i1, i0);
__m128i values = _mm_i32gather_epi32(base, indices, 4);
// Scatter: store to indices
_mm_i32scatter_epi32(base, indices, values, 4);
Note: Gather/scatter are slower than sequential loads on most CPUs.
Practical Patterns
Byte/Nibble Operations
// Lookup table via shuffle
// Map ASCII to base64 index
__m128i shifts = _mm_srli_epi32(bytes, 4); // High nibble
__m128i lookup = _mm_shuffle_epi8(table, shifts);
Population Count
// Bit count via parallel sums
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
SIMD in Rust
Setup
# Cargo.toml
[dependencies]
portable-simd = "0.3"
Or use nightly:
#![feature(portable_simd)]
use core::simd::prelude::*;
Basic Example
#![feature(portable_simd)]
use core::simd::prelude::*;
const LANES: usize = 32;
fn process(data: &mut [u8]) {
let chunks = data.chunks_exact_mut(LANES);
for chunk in chunks {
let mut v = Simd::<u8, LANES>::from_slice(chunk);
v += Simd::splat(13u8); // Add 13 to each byte
chunk.copy_from_slice(&v.as_array());
}
// Handle remainder
}
Key Types
Simd<T, N>: Vector of N elements of type TMask<T, N>: Boolean vector for selectionLaneCount<N>: Compile-time lane count
Useful Methods
// Splat: all lanes same value
let v = Simd::splat(42u8);
// Load/store
let v = Simd::from_slice(&data[..LANES]);
v.copy_to_slice(&mut output[..LANES]);
// Arithmetic (element-wise)
let sum = a + b;
let product = a * b;
// Comparison (returns Mask)
let mask = a.simd_gt(b);
// Select
let result = mask.select(if_true, if_false);
// Cast between lane sizes
let words = bytes.cast::<u16>();
SIMD in Go
Go doesn't have native SIMD intrinsics. Use assembly or libraries.
Assembly
// mul_avx2.s
#include "textflag.h"
TEXT ·MulAdd(SB), NOSPLIT, $0-32
MOVQ x0+0(FP), AX
MOVQ x1+8(FP), BX
MOVQ x2+16(FP), CX
MOVQ x3+24(FP), DX
VPBROADCASTMB2Q K1, DX
VPMADDUBSW Y0, K1, Y0
VPMADDWD Y0, Y1, Y0
VADDPD Y0, Y2, Y0
MOVQ Y0, ret+0(FP)
RET
Libraries
github.com/gammons/simd: Simple wrappersgithub.com/aclements/go-misc: SIMD primitives- Compile with AVX flags:
-ldflags="-s -w" -ldflags="-march=native"
SIMD in Java
Java uses SIMD via JVM auto-vectorization and VarHandle/MethodHandles.
Auto-Vectorization
JIT auto-vectorizes when:
- Simple loops with straight-line code
- No bounds checks in hot path
- Primitive arrays (not ArrayLists)
// JIT will vectorize this
for (int i = 0; i < n; i++)
c[i] = a[i] + b[i];
// JIT will NOT vectorize (aliasing unclear)
for (int i = 0; i < n; i++)
c[i] = a[i+1] + a[i];
Manual SIMD in Java
// Use JDK.incubator.foreign for intrinsics
// Or use libraries like fastutil, Koloboke
Checklist
- Profile first - confirm CPU-bound, not memory
- Identify hot loop with homogeneous operations
- Choose lane count (16/32/64 based on CPU)
- Handle residual elements (scalar tail)
- Avoid branches in hot path
- Use masks for conditional code
- Align loads/stores where possible
- Measure: SIMD should be 2-4x faster
- Test on target CPU architecture
Common Pitfalls
- Premature SIMD: Profile first
- Memory-bound: SIMD won't help if memory is bottleneck
- Branchy code: Convert to branchless or lose gains
- Alignment: Unaligned loads work but are slower
- Tail handling: Forgetting remainder causes bugs
- Over-generalization: SIMD for 4 elements is slower than scalar