repositories / dotfiles

dotfiles

bugabingas dorkfiles

owned by bugabinga

opencode/skills/performance-optimization/performance-simd.md

Raw

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

Signs You Need SIMD


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


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

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

// 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

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


SIMD in Java

Java uses SIMD via JVM auto-vectorization and VarHandle/MethodHandles.

Auto-Vectorization

JIT auto-vectorizes when:

// 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


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
Markdown source
# 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::<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 T
- `Mask<T, N>`: Boolean vector for selection
- `LaneCount<N>`: 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::<u16>();
```

---

## 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