# 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