repositories / dotfiles

dotfiles

bugabingas dorkfiles

owned by bugabinga

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

Raw

Assembly Performance Optimization

Based on Agner Fog's optimization manuals and instruction tables.

When to Use Assembly

Otherwise: trust the compiler. Modern compilers are very good at optimization.


CPU Microarchitecture

Execution Ports

Modern Intel/AMD CPUs have execution ports (typically 8-10). Each port handles specific operation types:

Latency vs Throughput

Example: ADD r64, r64
  Latency: 1 cycle
  Throughput: 0.25 cycles (4 per cycle)

Instruction Latency Table (x86-64)

Category Example Latency Throughput Notes
Integer ALU ADD, SUB, XOR 1 0.25 Most common
Integer Mul IMUL r64 3-4 1 AMD Zen = 3c
Integer Div IDIV r64 20-80 20-80 AVOID in loops
Load MOV R64, [mem] 4-5 0.25 Cache dependent
Store MOV [mem], R64 1-2 0.5
Branch Jcc 1 1 If predicted
Branch miss Mispredict 10-20 - Very expensive
POPCNT POPCNT r64, r64 3 1
LZCNT/TZCNT LZCNT r64, r64 3 1
BMI2 ANDN ANDN r64, r64, r64 1 0.25 Flag optimization
BMI2 BEXTR BEXTR r64, r64, r64 1 1
BMI2 LZCNT LZCNT r64, r64 3 1

SIMD Latency (AVX2)

Instruction Latency Throughput Ports
VADDPS 4 0.5 0,1
VMULPS 4 0.5 0,1
VFMADD132PS 4 0.5 0,1
VBROADCASTSS 3 1 2
VPERM2F128 3 1 5

Fast vs Slow Instructions

Use these (fast):

Avoid these (slow):


Memory Access

Latency

Memory Type Latency
L1 Cache ~4 cycles
L2 Cache ~12 cycles
L3 Cache ~40 cycles
RAM ~100-300 ns

Optimization Rules

  1. Use aligned loads when possible (faster on older CPUs)
  2. Prefetch data before use:
    prefetchnta [rsi + 64]   ; Non-temporal hint
    prefetcht0 [rsi + 64]    ; To L1
    
  3. Minimize memory stalls:
    • Interleave loads and arithmetic
    • Use registers, not memory, for frequently accessed data
    • Avoid cross-cache-line loads when possible

Cache Line

Prefetching

Hardware prefetch:

Software prefetch (use sparingly):

; Prefetch to L1, 64 bytes ahead
prefetcht0 [rsi + 64]

; Non-temporal (skip cache)
prefetchnta [rsi + 64]

When to prefetch:


Branch Prediction

Cost of Misprediction

Rules

  1. Make branches predictable:

    • Put common case in fall-through path
    • Avoid dependent conditions
  2. Conditional moves (cmov):

    ; Instead of:
    cmp rax, rbx
    jg .greater
    mov rcx, rdi
    jmp .done
    .greater:
    mov rcx, rsi
    .done:
    
    ; Use:
    cmp rax, rbx
    cmovg rcx, rsi    ; Conditional move
    cmovle rcx, rdi
    
  3. Loop unrolling reduces branch overhead:

    ; Unroll by 4
    .loop:
        add rax, [rsi]
        add rax, [rsi + 8]
        add rax, [rsi + 16]
        add rax, [rsi + 24]
        add rsi, 32
        dec rcx
        jnz .loop
    

Register Usage

Register Constraints

Fast Register Operations

Avoid Register Spills


Loop Optimization

Loop-Carried Dependencies

Long dependency chains prevent parallelism:

; BAD: Chain limits to 1 iteration per 3 cycles
mov eax, [rsi]
add eax, eax
mov [rdi], eax
add rsi, 4
add rdi, 4
dec rcx
jnz .loop

; GOOD: Independent iterations can run in parallel
vmovdqu ymm0, [rsi]
vmovdqu ymm1, [rsi + 32]
vaddps ymm0, ymm0, ymm0
vaddps ymm1, ymm1, ymm1
vmovdqu [rdi], ymm0
vmovdqu [rdi + 32], ymm1
add rsi, 64
add rdi, 64
sub rcx, 16
jnz .loop

Strength Reduction

Replace expensive operations with cheaper ones:

; BAD
imul rax, rax, 4

; GOOD
lea rax, [rax * 4]    ; Multiply by 4 via addressing

Loop Unrolling

Reduces branch overhead, enables more ILP:

; Unroll 4x
.loop:
    add rax, [rsi]
    add rax, [rsi + 8]
    add rax, [rsi + 16]
    add rax, [rsi + 24]
    add rsi, 32
    dec rcx
    jnz .loop

SIMD (SSE/AVX)

Instruction Selection

Data Type SSE AVX2 AVX-512
8-bit 16 32 64
16-bit 8 16 32
32-bit 4 8 16
64-bit 2 4 8

Key Instructions

; Load/Store
movdqu xmm0, [rsi]      ; Unaligned load
vmovdqu ymm0, [rsi]     ; AVX unaligned

; Arithmetic
vaddps ymm0, ymm1, ymm2 ; Vector add
vmulps ymm0, ymm1, ymm2  ; Vector multiply
vfma213ps ymm0, ymm1, ymm2 ; FMA: a + b * c

; Blend/Select
vpblendvb ymm0, ymm1, ymm2, ymm3 ; Variable blend
vblendvps ymm0, ymm1, ymm2, ymm3 ; Select based on sign

; Horizontal ops (rarely useful - dependencies)
vhaddps xmm0, xmm1, xmm2 ; Horizontal add (slow!)

Alignment


Function Calls

Cost

Inlining

Inline small, hot functions:

; Inlined instead of call
; Just add the instructions directly

Stack Frame

Minimal frame = faster:

; Minimal prologue
push rbp
mov rbp, rsp
; ... code ...
pop rbp
ret

; No frame pointer
; (omit push rbp / mov rbp, rsp)

Data Layout

Array of Structures (AoS)

struct Point { float x, y, z; };
Point points[1000];

Good when accessing all fields of each point.

Structure of Arrays (SoA)

struct Points {
    float x[1000], y[1000], z[1000];
};

Better for SIMD - load all x values at once.

Decision

Alignment

; Ensure 32-byte alignment for AVX
align 32
my_data:
    db 1024 dup(0)

Multi-Threading Considerations

Cache Coherency

struct PerThreadData {
    long counter;
    char pad[64 - sizeof(long)];  // Prevent false sharing
};

NUMA

Hyper-Threading


Instruction Selection


Common Patterns

Sum Array

; Scalar (slow)
xor eax, eax
.loop:
    add eax, [rsi]
    add rsi, 4
    dec rcx
    jnz .loop

; SIMD (fast)
vxorps ymm0, ymm0, ymm0        ; zero
.loop:
    vaddps ymm1, ymm1, [rsi]
    add rsi, 32
    sub rcx, 8
    jnz .loop
    vextractf128 xmm1, ymm1, 1
    vhaddps ymm1, ymm1, ymm1   ; Horizontal sum
    vhaddps xmm1, xmm1, xmm1
    vmovd eax, xmm1

Memcpy (large blocks)

; Use REP MOVSB for large blocks
mov rcx, rsi    ; count
rep movsb       ; OS handles efficiently

Profiling

Tools

Key Metrics


Checklist


Common Mistakes

  1. Premature optimization: Profile first
  2. Over-optimizing: Compiler may know better
  3. Ignoring memory: Memory is often the bottleneck
  4. Not considering CPU: Different CPUs have different characteristics
  5. Forgetting alignment: Unaligned access can be slow
  6. Long dependency chains: Parallelize where possible
Markdown source
# Assembly Performance Optimization

Based on Agner Fog's optimization manuals and instruction tables.

## When to Use Assembly

- Hot inner loops that compilers don't optimize well
- SIMD operations not available in language
- Specific CPU features (BMI2, AVX-512)
- Critical latency paths
- Algorithm optimization (crypto, compression)

Otherwise: trust the compiler. Modern compilers are very good at optimization.

---

## CPU Microarchitecture

### Execution Ports

Modern Intel/AMD CPUs have execution ports (typically 8-10). Each port handles
specific operation types:

- Port 0: ALU, FP add, SIMD
- Port 1: ALU, FP mul, SIMD
- Port 2: Load, address generation
- Port 3: Store address
- Port 4: Store data
- Port 5: ALU, branch
- Port 6: Branch
- Port 7: ALU (fast)

### Latency vs Throughput

- **Latency**: Cycles to complete one instruction
- **Throughput**: Instructions per cycle (IPC)

```
Example: ADD r64, r64
  Latency: 1 cycle
  Throughput: 0.25 cycles (4 per cycle)
```

### Instruction Latency Table (x86-64)

| Category    | Example             | Latency | Throughput | Notes             |
| ----------- | ------------------- | ------- | ---------- | ----------------- |
| Integer ALU | ADD, SUB, XOR       | 1       | 0.25       | Most common       |
| Integer Mul | IMUL r64            | 3-4     | 1          | AMD Zen = 3c      |
| Integer Div | IDIV r64            | 20-80   | 20-80      | AVOID in loops    |
| Load        | MOV R64, [mem]      | 4-5     | 0.25       | Cache dependent   |
| Store       | MOV [mem], R64      | 1-2     | 0.5        |                   |
| Branch      | Jcc                 | 1       | 1          | If predicted      |
| Branch miss | Mispredict          | 10-20   | -          | Very expensive    |
| POPCNT      | POPCNT r64, r64     | 3       | 1          |                   |
| LZCNT/TZCNT | LZCNT r64, r64      | 3       | 1          |                   |
| BMI2 ANDN   | ANDN r64, r64, r64  | 1       | 0.25       | Flag optimization |
| BMI2 BEXTR  | BEXTR r64, r64, r64 | 1       | 1          |                   |
| BMI2 LZCNT  | LZCNT r64, r64      | 3       | 1          |                   |

### SIMD Latency (AVX2)

| Instruction  | Latency | Throughput | Ports |
| ------------ | ------- | ---------- | ----- |
| VADDPS       | 4       | 0.5        | 0,1   |
| VMULPS       | 4       | 0.5        | 0,1   |
| VFMADD132PS  | 4       | 0.5        | 0,1   |
| VBROADCASTSS | 3       | 1          | 2     |
| VPERM2F128   | 3       | 1          | 5     |

### Fast vs Slow Instructions

**Use these (fast)**:

- LEA for arithmetic: `lea rax, [rbx + rcx * 4]`
- CMP + CMOV: conditional moves
- POPCNT, LZCNT, TZCNT for bit operations
- ANDN (BMI2): combines not + and in one instruction
- BEXTR (BMI2): combined extract + mask
- SIMD for parallel ops
- XOR reg, reg: zero register

**Avoid these (slow)**:

- DIV, IDIV: 20-80 cycles - use reciprocal multiplication
- CALL/RET: 2-4 cycles overhead
- Complex addressing modes in loops
- Integer to FP conversion (CVTSI2SS)
- PUSH/POP in tight loops

---

## Memory Access

### Latency

| Memory Type | Latency     |
| ----------- | ----------- |
| L1 Cache    | ~4 cycles   |
| L2 Cache    | ~12 cycles  |
| L3 Cache    | ~40 cycles  |
| RAM         | ~100-300 ns |

### Optimization Rules

1. **Use aligned loads** when possible (faster on older CPUs)
2. **Prefetch** data before use:
   ```asm
   prefetchnta [rsi + 64]   ; Non-temporal hint
   prefetcht0 [rsi + 64]    ; To L1
   ```
3. **Minimize memory stalls**:
   - Interleave loads and arithmetic
   - Use registers, not memory, for frequently accessed data
   - Avoid cross-cache-line loads when possible

### Cache Line

- Size: 64 bytes
- Load one full cache line, not individual bytes
- Sequential access = hardware prefetch kicks in

### Prefetching

Hardware prefetch:

- Detects sequential access patterns
- Triggered after 2+ cache misses
- Works across page boundaries on modern CPUs

Software prefetch (use sparingly):

```asm
; Prefetch to L1, 64 bytes ahead
prefetcht0 [rsi + 64]

; Non-temporal (skip cache)
prefetchnta [rsi + 64]
```

**When to prefetch**:

- Loop with complex access pattern
- Known distance ahead (e.g., 10+ iterations)
- Not needed for sequential access (hardware handles it)

---

## Branch Prediction

### Cost of Misprediction

- ~10-20 cycles penalty
- Avoid unpredictable branches in hot code

### Rules

1. **Make branches predictable**:
   - Put common case in fall-through path
   - Avoid dependent conditions

2. **Conditional moves** (cmov):
   ```asm
   ; Instead of:
   cmp rax, rbx
   jg .greater
   mov rcx, rdi
   jmp .done
   .greater:
   mov rcx, rsi
   .done:

   ; Use:
   cmp rax, rbx
   cmovg rcx, rsi    ; Conditional move
   cmovle rcx, rdi
   ```

3. **Loop unrolling** reduces branch overhead:
   ```asm
   ; Unroll by 4
   .loop:
       add rax, [rsi]
       add rax, [rsi + 8]
       add rax, [rsi + 16]
       add rax, [rsi + 24]
       add rsi, 32
       dec rcx
       jnz .loop
   ```

---

## Register Usage

### Register Constraints

- Use caller-saved (rax, rcx, rdx, rsi, rdi, r8-r11) for temporary values
- Use callee-saved (rbx, rbp, r12-r15) for values that must survive function
  calls

### Fast Register Operations

- XOR to zero: `xor eax, eax` (2 bytes, fast)
- Load constant: `mov eax, 12345` (5 bytes)
- Better: `mov eax, 12345` / `mov rsi, rax` / `xor eax, eax`

### Avoid Register Spills

- Keep working set in registers
- If spilling: you're doing too much in one function

---

## Loop Optimization

### Loop-Carried Dependencies

Long dependency chains prevent parallelism:

```asm
; BAD: Chain limits to 1 iteration per 3 cycles
mov eax, [rsi]
add eax, eax
mov [rdi], eax
add rsi, 4
add rdi, 4
dec rcx
jnz .loop

; GOOD: Independent iterations can run in parallel
vmovdqu ymm0, [rsi]
vmovdqu ymm1, [rsi + 32]
vaddps ymm0, ymm0, ymm0
vaddps ymm1, ymm1, ymm1
vmovdqu [rdi], ymm0
vmovdqu [rdi + 32], ymm1
add rsi, 64
add rdi, 64
sub rcx, 16
jnz .loop
```

### Strength Reduction

Replace expensive operations with cheaper ones:

```asm
; BAD
imul rax, rax, 4

; GOOD
lea rax, [rax * 4]    ; Multiply by 4 via addressing
```

### Loop Unrolling

Reduces branch overhead, enables more ILP:

```asm
; Unroll 4x
.loop:
    add rax, [rsi]
    add rax, [rsi + 8]
    add rax, [rsi + 16]
    add rax, [rsi + 24]
    add rsi, 32
    dec rcx
    jnz .loop
```

---

## SIMD (SSE/AVX)

### Instruction Selection

| Data Type | SSE | AVX2 | AVX-512 |
| --------- | --- | ---- | ------- |
| 8-bit     | 16  | 32   | 64      |
| 16-bit    | 8   | 16   | 32      |
| 32-bit    | 4   | 8    | 16      |
| 64-bit    | 2   | 4    | 8       |

### Key Instructions

```asm
; Load/Store
movdqu xmm0, [rsi]      ; Unaligned load
vmovdqu ymm0, [rsi]     ; AVX unaligned

; Arithmetic
vaddps ymm0, ymm1, ymm2 ; Vector add
vmulps ymm0, ymm1, ymm2  ; Vector multiply
vfma213ps ymm0, ymm1, ymm2 ; FMA: a + b * c

; Blend/Select
vpblendvb ymm0, ymm1, ymm2, ymm3 ; Variable blend
vblendvps ymm0, ymm1, ymm2, ymm3 ; Select based on sign

; Horizontal ops (rarely useful - dependencies)
vhaddps xmm0, xmm1, xmm2 ; Horizontal add (slow!)
```

### Alignment

- AVX/AVX-512: 32/64-byte alignment preferred
- Unaligned works but slightly slower on older CPUs

---

## Function Calls

### Cost

- Direct call: ~2 cycles
- Indirect (via register): ~4 cycles
- Function prologue/epilogue: ~2-3 cycles each

### Inlining

Inline small, hot functions:

```asm
; Inlined instead of call
; Just add the instructions directly
```

### Stack Frame

Minimal frame = faster:

```asm
; Minimal prologue
push rbp
mov rbp, rsp
; ... code ...
pop rbp
ret

; No frame pointer
; (omit push rbp / mov rbp, rsp)
```

---

## Data Layout

### Array of Structures (AoS)

```c
struct Point { float x, y, z; };
Point points[1000];
```

Good when accessing all fields of each point.

### Structure of Arrays (SoA)

```c
struct Points {
    float x[1000], y[1000], z[1000];
};
```

Better for SIMD - load all x values at once.

### Decision

- SIMD operations: use SoA
- Random access to complete objects: use AoS
- Cache line utilization: SoA better for streaming

### Alignment

```asm
; Ensure 32-byte alignment for AVX
align 32
my_data:
    db 1024 dup(0)
```

- 16-byte: SSE
- 32-byte: AVX/AVX2
- 64-byte: AVX-512
- Padding to avoid false sharing in multi-threaded code: 64 bytes

---

## Multi-Threading Considerations

### Cache Coherency

- Threads modify shared data = cache invalidation
- False sharing: different threads modify same cache line
- Solution: pad to 64 bytes

```c
struct PerThreadData {
    long counter;
    char pad[64 - sizeof(long)];  // Prevent false sharing
};
```

### NUMA

- Memory access time depends on CPU socket
- Allocate memory on the CPU that will use it
- Use local memory affinity

### Hyper-Threading

- Two threads share execution resources
- SMT benefit depends on instruction mix
- If one thread is memory-bound, other can use CPU units
- Test: sometimes disabling HT improves performance

---

## Instruction Selection

---

## Common Patterns

### Sum Array

```asm
; Scalar (slow)
xor eax, eax
.loop:
    add eax, [rsi]
    add rsi, 4
    dec rcx
    jnz .loop

; SIMD (fast)
vxorps ymm0, ymm0, ymm0        ; zero
.loop:
    vaddps ymm1, ymm1, [rsi]
    add rsi, 32
    sub rcx, 8
    jnz .loop
    vextractf128 xmm1, ymm1, 1
    vhaddps ymm1, ymm1, ymm1   ; Horizontal sum
    vhaddps xmm1, xmm1, xmm1
    vmovd eax, xmm1
```

### Memcpy (large blocks)

```asm
; Use REP MOVSB for large blocks
mov rcx, rsi    ; count
rep movsb       ; OS handles efficiently
```

---

## Profiling

### Tools

- `perf stat`: Cycle counts, cache misses
- `perf record`: Sample with hardware counters
- `vtune`: IntelVTune visualizer
- `uops.info`: Micro-op details

### Key Metrics

- **CPI**: Cycles per instruction (lower is better)
- **Branch misses**: Misprediction rate
- **L1/L2/L3 miss rate**: Memory access efficiency
- **Port utilization**: Which execution units are busy

---

## Checklist

- [ ] Profile first - confirm it's a bottleneck
- [ ] Use aligned loads for hot data
- [ ] Avoid memory stalls - interleave loads/compute
- [ ] Make branches predictable
- [ ] Use conditional moves instead of branches
- [ ] Minimize register spills
- [ ] Use SIMD for data parallelism
- [ ] Unroll loops to reduce overhead
- [ ] Use fast instructions (lea, cmov, popcnt)
- [ ] Avoid slow instructions (div, idiv)
- [ ] Consider inlining
- [ ] Verify with profiling

---

## Common Mistakes

1. **Premature optimization**: Profile first
2. **Over-optimizing**: Compiler may know better
3. **Ignoring memory**: Memory is often the bottleneck
4. **Not considering CPU**: Different CPUs have different characteristics
5. **Forgetting alignment**: Unaligned access can be slow
6. **Long dependency chains**: Parallelize where possible