SIMD

2026-11-18 ยท vectorization simd

notes / DOCS

CPU Optimisation

FLOPS = floating point operations per second

peak FLOPS = #cores * FLOPS/insn * insn/cycle * Hz

Check out the example on Compiler Explorer

void mul4(float* arr) {
    for (int i = 0; i < 4; i++) {
        const float f = arr[i];
        arr[i] = f * f;
    }
}

without optimisations

"mul4(float*)":
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-24], rdi
        mov     DWORD PTR [rbp-4], 0
        jmp     .L2
.L3:
        mov     eax, DWORD PTR [rbp-4]
        cdqe
        lea     rdx, [0+rax*4]
        mov     rax, QWORD PTR [rbp-24]
        add     rax, rdx
        movss   xmm0, DWORD PTR [rax]
        movss   DWORD PTR [rbp-8], xmm0
        mov     eax, DWORD PTR [rbp-4]
        cdqe
        lea     rdx, [0+rax*4]
        mov     rax, QWORD PTR [rbp-24]
        add     rax, rdx
        movss   xmm0, DWORD PTR [rbp-8]
        mulss   xmm0, xmm0
        movss   DWORD PTR [rax], xmm0
        add     DWORD PTR [rbp-4], 1
.L2:
        cmp     DWORD PTR [rbp-4], 3
        jle     .L3
        nop
        nop
        pop     rbp
        ret

same thing with -O3

"mul4(float*)":
        movups  xmm0, XMMWORD PTR [rdi]
        mulps   xmm0, xmm0
        movups  XMMWORD PTR [rdi], xmm0
        ret

lmaoo

Some things that are happening

  1. loop unrolling
  2. simd vectorisation

Interestingly the example code given is worse than the compiler optimisation if compiled without optimisations

#include <immintrin.h>

void mul4(float* arr) {
    __m128 f = _mm_loadu_ps(arr);
    f = _mm_mul_ps(f, f);
    _mm_storeu_ps(arr, f);
}

and the worse asm (unoptimised ofcourse)

"mul4(float*)":
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-104], rdi
        mov     rax, QWORD PTR [rbp-104]
        mov     QWORD PTR [rbp-88], rax
        mov     rax, QWORD PTR [rbp-88]
        movups  xmm0, XMMWORD PTR [rax]
        movaps  XMMWORD PTR [rbp-16], xmm0
        movaps  xmm0, XMMWORD PTR [rbp-16]
        movaps  XMMWORD PTR [rbp-64], xmm0
        movaps  xmm0, XMMWORD PTR [rbp-16]
        movaps  XMMWORD PTR [rbp-80], xmm0
        movaps  xmm0, XMMWORD PTR [rbp-64]
        mulps   xmm0, XMMWORD PTR [rbp-80]
        movaps  XMMWORD PTR [rbp-16], xmm0
        mov     rax, QWORD PTR [rbp-104]
        mov     QWORD PTR [rbp-24], rax
        movaps  xmm0, XMMWORD PTR [rbp-16]
        movaps  XMMWORD PTR [rbp-48], xmm0
        movaps  xmm0, XMMWORD PTR [rbp-48]
        mov     rax, QWORD PTR [rbp-24]
        movups  XMMWORD PTR [rax], xmm0
        nop
        nop
        pop     rbp
        ret

trust your compiler guys

What is SIMD

Single Instruction Multiple Data (SSE/AVX in x86)

Used heavily wherever CPU is dominant

Register Types:

16 bytes 32 bytes 64 bytes
32 bit flt __m128 __m256 __m512
64 bit flt __m128d __m256d __m512d
32/64bit int __m128i __m256i __m512i

Instruction Types

Can be

Can be

// Add
static inline v3 operator+(const v3 &A, const v3 &B) {
  xmm Result = _mm_add_ps(xmm(A), xmm(B));
  return (v3)Result;
}

// Subtract
static inline v3 operator-(const v3 &A, const v3 &B) {
  xmm Result = _mm_sub_ps(xmm(A), xmm(B));
  return (v3)Result;
}

// Multiply
static inline v3 operator*(const v3 &A, const v3 &B) {
  xmm Result = _mm_mul_ps(xmm(A), xmm(B));
  return (v3)Result;
}

// Divide
static inline v3 operator/(const v3 &A, const v3 &B) {
  xmm Result = _mm_div_ps(xmm(A), xmm(B));
  return (v3)Result;
}

// Negate (Multiply by -1)
static inline v3 operator-(const v3 &A) {
  __m128 NegativeOne = _mm_set1_ps(-1.0f);
  xmm Result = _mm_mul_ps(xmm(A), NegativeOne);
  return (v3)Result;
}

and more like sqrt, min, store etc

Example

#include <immintrin.h>

float* add(const float* a, const float* b, size_t size) {
    float* result{new float[size]};
    const auto vecx{size - (size%4)};
    unsigned i{0};

    for (; i < vecx; i += 4) {
        __m128 areg {_mm_loadu_ps(a + i)};
        __m128 breg {_mm_loadu_ps(b + i)};
        _mm_storeu_ps(result + i, _mm_add_ps(areg, breg));
    }

    for (; i < size; i++) {
        result[i] = a[i] + b[i];
    }

    return result;
}

just doing

for (size_t i = 0; i < size; i++) {
  f[i] = a[i] + b[i];
}

would also autovectorize, and better too

SSE Memory Optimisations

Memory Alignment

Aligned _mm_load_ps

Mis-aligned _mm_loadu_ps

we want to align with compiler directives

struct V{short s[3];} __attribute__ ((aligned(8)))  // 6 bytes + 2 bytes padding
char c[2] __attribute__ ((aligned(8)));             // 2 bytes + 6 bytes padding
struct A{char a; int b;} __attribute__ ((packed))   // 1 byte + 4 bytes NO PADDING

Pointer Aliasing

the same memory location can be accessed using different names

void foo(int* a, int* b, int*c) {
    *a = 42;
    *b = 23;
    *c = *a;
}
"foo":
        mov     DWORD PTR [rdi], 42
        mov     DWORD PTR [rsi], 23
        mov     eax, DWORD PTR [rdi] # extra indirection
        mov     DWORD PTR [rdx], eax
        ret

if a and b pointed to the same memory location then the compiler doesn't know if *a is 42 or 23

You can use restrict to promise the compiler that aliasing doesn't occur with those pointers (c99 keyword, __restrict__ in c++)

void foo(int* restrict a, int* b, int*c) {
    *a = 42;
    *b = 23;
    *c = *a;
}
"foo":
        mov     DWORD PTR [rdi], 42
        mov     DWORD PTR [rsi], 23
        mov     DWORD PTR [rdx], 42 # compiler trusts *a = 42
        ret

GCC Auto Vectorisation

const int SIZE{1 << 16};
void simpleloop(double *a, double *b) {
    for (int i{0}; i < SIZE; i++) {
        a[i] += b[i];
    }
}

Compiles both versions -> with and without aliasing

g++ -O -ftree-vectorize -fopt-info-vec -fopt-info-vec-missed -march=native 
"simpleloop(double*, double*)":
        mov     rax, rdi
        sub     rax, rsi
        sub     rax, 8
        cmp     rax, 16  
        jbe     .L5
        mov     eax, 0
.L3:
        vmovupd ymm0, YMMWORD PTR [rsi+rax]
        vaddpd  ymm0, ymm0, YMMWORD PTR [rdi+rax]
        vmovupd YMMWORD PTR [rdi+rax], ymm0
        add     rax, 32
        cmp     rax, 524288
        jne     .L3
        ret
.L5:
        mov     eax, 0
.L2:
        vmovsd  xmm0, QWORD PTR [rdi+rax]
        vaddsd  xmm0, xmm0, QWORD PTR [rsi+rax]
        vmovsd  QWORD PTR [rdi+rax], xmm0
        add     rax, 8
        cmp     rax, 524288
        jne     .L2
        ret

Notice the beginning is comparing

(a - b) - 8 <= 16
a - b <= 24

which implies their memory regions are closer than 32 bytes and thus overlap => aliasing

something we can avoid by using

void simpleloop(double* __restrict__ a, double* b) {}

immediate fix

"simpleloop(double*, double*)":
        mov     eax, 0
.L2:
        vmovupd ymm0, YMMWORD PTR [rsi+rax]       # unaligned mov
        vaddpd  ymm0, ymm0, YMMWORD PTR [rdi+rax]
        vmovupd YMMWORD PTR [rdi+rax], ymm0       # unaligned mov
        add     rax, 32
        cmp     rax, 524288
        jne     .L2
        ret

This is still unaligned and you can align it further. I would rather not

Rules

  1. countable loops
  2. no backwards loop-carried dependencies?
  3. no function calls except supported math instructions (sin, sqrt, etc)
  4. straight line code -> no switch
  5. hot loop must be vectorized -> innermost loop

some more

Fused-Multiply-Add

single instruction to do a * b + c

Advanced Matrix Extensions

simd on 2D tile/matrix

for matrix multiply/accumulate

what the actual fuck is a sapphire rapid

More Optimisations

Branchless Filtering

is a thing

larger registers => larger branch prediction masks i assume

#include <immintrin.h>

// keep prices > threshold, without branching
int filter_above(const double *prices, double threshold,
  double *out, int n) {
  __m512d thresh = _mm512_set1_pd(threshold);
  int count = 0;
  for (int i = 0; i < n; i += 8) {
    __m512d p = _mm512_loadu_pd(&prices[i]);
    __mmask8 mask = _mm512_cmp_pd_mask(p, thresh, _CMP_GT_OQ);
    _mm512_mask_compressstoreu_pd(&out[count], mask, p);
    count += _mm_popcnt_u32(mask);
  }
  return count;
}

didn't compile for me on compiler-explorer so idk

Horizontal Reductions

"max across a vector" queries

_mm512_reduce_max_pd does this apparently good for you

#include <immintrin.h>

double best_bid(const double *bids, int n) {
  __m512d best = _mm512_set1_pd(-__builtin_inf());
  int i = 0;
  for (; i + 8 <= n; i += 8) {
    __m512d v = _mm512_loadu_pd(&bids[i]);
    best = _mm512_max_pd(best, v);
  }
  double result = _mm512_reduce_max_pd(best);
  for (; i < n; i++) // tail
    result = bids[i] > result ? bids[i] : result;
  return result;
}

Gather/Scatter

gather stuff to put together a contiguous vector, omg look they give you _mm512_i32gather_pd to do this fuck off

because stuff usually isn't contiguous where you want it

#include <immintrin.h>

// gather quotes at 8 arbitrary price-level indices
__m512d gather_levels(const double *book, const int *idx) {
  __m512i vidx = _mm512_loadu_si512((const void*)idx);
  return _mm512_i32gather_pd(vidx, book, sizeof(double));
}

General Optimisations

Branch Prediction

  1. cmov and the ternary operator
  2. boolean arithmetic
  3. bitwise masking
  4. precomputed lookup tables
  5. compiler hints
  6. profile guided optimisation

Cache Usage

  1. cache warming
  2. software memory prefetching
  3. struct compaction and alignment
  4. contiguous memory blocks
  5. false sharing
  6. cache partitioning

Memory Allocation

  1. memory pools
  2. huge pages and tlb optimisations

  1. improving perfromance with simd intrinsics
  2. Core Dumped
  3. Rules
  4. Mitchell H Ghossty blog
  5. C++ Ultra-Low Latency