# 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 ```c // 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: ```c 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: ```c void process(float* restrict a, float* restrict b, int n); ``` --- ## Reductions Sum/product across all lanes requires horizontal operations. ### Sum Reduction ```c // 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-math` if precision loss is acceptable - Commutativity helps: reorder operands for parallelism --- ## Conditional Code (If-Conversion) Branches prevent vectorization. Convert to branchless operations. ### Masked Selection ```c // 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 1. Compute both branches unconditionally 2. Use blend to select result 3. Beware: dividing by zero, out-of-bounds still executes 4. Profile: doubling work may not pay off if branch is predictable --- ## Shuffles and Swizzles ### Common Shuffles ```c // 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 // 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: ```c // 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 ```c // 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 ```c // 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 ```toml # Cargo.toml [dependencies] portable-simd = "0.3" ``` Or use nightly: ```rust #![feature(portable_simd)] use core::simd::prelude::*; ``` ### Basic Example ```rust #![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::::from_slice(chunk); v += Simd::splat(13u8); // Add 13 to each byte chunk.copy_from_slice(&v.as_array()); } // Handle remainder } ``` ### Key Types - `Simd`: Vector of N elements of type T - `Mask`: Boolean vector for selection - `LaneCount`: Compile-time lane count ### Useful Methods ```rust // 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::(); ``` --- ## SIMD in Go Go doesn't have native SIMD intrinsics. Use assembly or libraries. ### Assembly ```go // 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 wrappers - `github.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) ```java // 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 ```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 1. **Premature SIMD**: Profile first 2. **Memory-bound**: SIMD won't help if memory is bottleneck 3. **Branchy code**: Convert to branchless or lose gains 4. **Alignment**: Unaligned loads work but are slower 5. **Tail handling**: Forgetting remainder causes bugs 6. **Over-generalization**: SIMD for 4 elements is slower than scalar