Introduction to SIMD

SIMD (Single Instruction Multiple Data) is a class of instruction sets that allow a single instruction to operate on multiple data streams simultaneously. In contrast, the conventional approach — a single instruction operating on a single data stream — is known as SISD (Single Instruction Single Data). To support SIMD, CPUs are physically designed with dedicated vector registers that are typically wider than general-purpose registers (e.g., 128 bits). Note that vector registers and SIMD instruction sets vary across CPU architectures.

SIMD plays a critical role in modern high-performance programming and is already widely used in database kernels.

image

image

SIMD Instruction Set Extensions

Different CPU architectures support different SIMD extensions:

  • x86: SSE, AVX, AVX2 (Advanced Vector Extensions 2), AVX-512 (Advanced Vector Extensions-512)
  • ARM: NEON
  • LoongArch: LSX, LASX
  • RISC-V: RVV

x86 Instruction Set Evolution

Here is the x86 SIMD extension timeline: 1997 ─► MMX │ 1999 ─► SSE │ 2000 ─► SSE2 │ 2003 ─► SSE3 │ 2004 ─► SSSE3 │ 2006 ─► SSE4.1 → SSE4.2 (2008) │ 2011 ─► AVX │ 2013 ─► AVX2 + FMA (Fused Multiply-Add) + BMI/BMI2 │ 2017 ─► AVX-512 family │ 2020+ ─► AMX (Advanced Matrix Extensions)

Check your CPU’s supported SIMD extensions:

postgres@slpc:~$ grep flags /proc/cpuinfo | head -n 1
flags		: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon rep_good nopl xtopology tsc_reliable nonstop_tsc cpuid tsc_known_freq pni pclmulqdq ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand hypervisor lahf_lm abm 3dnowprefetch pti ssbd ibrs ibpb stibp fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdseed adx smap clflushopt clwb sha_ni xsaveopt xsavec xgetbv1 xsaves avx_vnni arat umip gfni vaes vpclmulqdq rdpid movdiri movdir64b fsrm md_clear serialize flush_l1d arch_capabilities

This system supports sse, sse2, ssse3, sse4_1, sse4_2, avx, avx2 (256-bit vector operations), and avx_vnni (AI/neural-network optimized). This consumer machine lacks AVX-512 support.

ARM Instruction Set Evolution

ARM SIMD extension timeline:

1998 ─► NEON (ARMv7) │ 2011 ─► VFPv4 + NEON enhancements │ 2013 ─► ARMv8 AArch64 + NEON extensions │ 2016 ─► ARMv8.2 FP16 support │ 2018 ─► ARMv8.2 Dot Product / Int8 │ 2019 ─► ARMv8.4 BF16 support │ 2020 ─► ARMv9 + SVE2 (Scalable Vector Extension) │ 2022 ─► SVE2.1 / SVE2.2

SIMD Programming Approaches

Three approaches to vectorization:

  • Compiler auto-vectorization
  • Assembly language
  • Intrinsics

image

Auto-Vectorization

Modern compilers provide SIMD optimization via auto-vectorization. With optimization enabled, the compiler attempts to combine scalar operations into vector instructions. See Auto-Vectorization in LLVM. In other words, even if you write scalar code, the compiler may transform it into more efficient SIMD instructions.

image

However, the compiler must guarantee program correctness, so auto-vectorization only kicks in under specific conditions:

  • Loop vectorization: exploiting vector parallelism across loop iterations
  • Superword-level parallelism (SLP) vectorization: exploiting vector parallelism within basic blocks

Taking loop vectorization as an example, the process involves:

  • Legality analysis: Identify vectorizable loops through dependency analysis. If data dependencies are detected, vectorization is blocked. Additional constraints include memory legality and contiguity.
  • Profitability analysis: Vectorization has overhead and is not universally faster than scalar code. If the compiler estimates negligible gain, it skips vectorization.
  • IR transformation: Perform the actual vectorized code transformation, generating SIMD instructions.

With the default optimization level (e.g., -O2), the compiler only performs basic optimizations. Auto-vectorization typically requires -O3. Common compiler flags:

  • -O3: Enable all optimizations, including auto-vectorization.
  • -fopt-info-vec: Show auto-vectorization optimization info (GCC).
  • -fopt-info-vec-missed: Show failed auto-vectorization attempts (GCC).
  • -Rpass=loop-vectorize: Show auto-vectorization info (Clang).
  • -Rpass-missed=loop-vectorize: Show failed vectorization attempts (Clang).
  • -Rpass-analysis=loop-vectorize: Show vectorization analysis, including failure reasons.
  • -march=native: Use the current CPU’s instruction set extensions.
  • #pragma GCC ivdep: Ignore vector dependencies (for complex loops).
  • pragma GCC unroll N: Unroll loops to enable vectorization.
// Traverse and sum an array (scalar style)
long long traverse_array(Array* arr) {
    long long sum = 0;
    for (size_t i = 0; i < arr->size; i++) {
        sum += arr->data[i];
    }
    return sum;
}

Compiling with -O3 and -fopt-info-vec reveals successful vectorization:

postgres@slpc:$ gcc -o array array.c -O3 -march=native -fopt-info-vec
array.c:39:26: optimized: loop vectorized using 32 byte vectors   # SIMD optimization applied
array.c:39:26: optimized: loop vectorized using 16 byte vectors

Using gcc -S -O3 -march=native -o array.s array.c to inspect the generated assembly:

	.file	"array.c"
	.text
	.p2align 4
	.globl	traverse_array
	.type	traverse_array, @function
traverse_array:
.LFB53:
	.cfi_startproc
	endbr64
	movq	8(%rdi), %rcx
	testq	%rcx, %rcx
	je	.L9
	leaq	-1(%rcx), %rax
	movq	(%rdi), %rsi
	cmpq	$6, %rax
	jbe	.L10
	movq	%rcx, %rdx
	movq	%rsi, %rax
	vpxor	%xmm0, %xmm0, %xmm0
	shrq	$3, %rdx
	salq	$5, %rdx
	addq	%rsi, %rdx
	.p2align 4,,10
	.p2align 3
.L4:
	vpmovsxdq	(%rax), %ymm1
	vmovdqu	(%rax), %ymm3
	addq	$32, %rax
	cmpq	%rdx, %rax
	vpaddq	%ymm0, %ymm1, %ymm1
	vextracti128	$0x1, %ymm3, %xmm0
	vpmovsxdq	%xmm0, %ymm0
	vpaddq	%ymm1, %ymm0, %ymm0
	jne	.L4
	vmovdqa	%xmm0, %xmm2
	vextracti128	$0x1, %ymm0, %xmm0
	movq	%rcx, %rdx
	vpaddq	%xmm0, %xmm2, %xmm2     SIMD instruction
	andq	$-8, %rdx
	testb	$7, %cl
	vpsrldq	$8, %xmm2, %xmm0
	vpaddq	%xmm0, %xmm2, %xmm0
	vmovq	%xmm0, %rax
	je	.L20
	vzeroupper
.L3:
// ... remaining scalar tail handling ...

The assembly clearly uses AVX instructions (vpmovsxdq, vpaddq, etc.). Another useful tool is godbolt, which generates assembly from online code.

Auto-vectorization leverages the compiler’s capabilities, but developers can also add hints to guide the compiler where it cannot automatically determine safety — for example, #pragma GCC ivdep.

// Tips for helping the compiler auto-vectorize

// ❌ Patterns that hinder vectorization
void bad_vectorization(float *a, float *b, float *c, int n) {
    // Problem 1: aliasing — compiler can't determine if arrays overlap
    for (int i = 0; i < n; i++) {
        c[i] = a[i] + b[i];
    }
}

// ✅ Improved version
void good_vectorization(float * restrict a, 
                        float * restrict b, 
                        float * restrict c, 
                        int n) {
    // Tip 1: Use restrict keyword (promise no aliasing)
    // Tip 2: Simple loop structure
    // Tip 3: Contiguous memory access pattern
    for (int i = 0; i < n; i++) {
        c[i] = a[i] + b[i];
    }
}

// 🎯 Compiler flags (GCC/Clang):
// -O3              : enable auto-vectorization
// -ftree-vectorize : explicitly enable vectorization
// -fopt-info-vec   : output vectorization report
// -march=native    : optimize for the local CPU

Note that vectorization hints differ across compilers. See also: TiFlash: Compiler-Driven Auto-Vectorization Compiler Optimizations (12): LLVM Auto-Vectorization LLVM Auto-Vectorization

Intrinsics

While SIMD can be programmed in assembly, the barrier to entry is high. Intrinsics provide a more accessible alternative. Intrinsics are compiler built-in functions — similar to inline functions — that map directly to CPU SIMD instruction set extensions. They allow developers to write SIMD code in high-level languages without using assembly. Intrinsics are not real function calls; they are replaced with the corresponding machine instructions at compile time, delivering near-assembly performance with a lower learning curve.

Intrinsics are available for x86 (SSE, AVX, AVX2, AVX-512), ARM (NEON), RISC-V (RVV), and other architectures. They are provided through headers (e.g., <immintrin.h> for AVX). Function names typically start with _mm or _mm256, indicating the vector width (128 or 256 bits).

Core principles:

  • Mapping: Each intrinsic function corresponds to one or more SIMD instructions. The compiler (GCC, Clang, MSVC) directly translates these functions into hardware instructions at compile time — no function call overhead.
  • Vector operations: Intrinsics operate on vector registers (e.g., __m128 for 128-bit, __m256 for 256-bit), processing multiple data elements simultaneously (e.g., 8 floats with AVX2).
  • Type safety: Specific types (e.g., __m256) enforce correct alignment and typing. Misaligned accesses can degrade performance or cause crashes.
  • Compiler integration: Intrinsics can be combined with auto-vectorization but offer finer control. The target instruction set must be specified at compile time (e.g., -mavx2), otherwise scalar fallback code is generated.
  • Limitations: Intrinsics require hardware support; CPU features should be checked at runtime (e.g., via cpuid). Unsupported instructions cause illegal instruction exceptions.

References:

Although the more powerful AVX-512 exists, its consumer-platform support is uneven. AVX2 enjoys broad hardware support, so we use it for the following examples.

Vectorization Example 1
#include <immintrin.h>  // AVX2 header
#include <stdio.h>

// Scalar version (unoptimized)
void array_add_scalar(float *a, float *b, float *c, int n) {
    for (int i = 0; i < n; i++) {
        c[i] = a[i] + b[i];
    }
}

// AVX2 optimized version (processes 8 floats at a time)
void array_add_avx2(float *a, float *b, float *c, int n) {
    int i = 0;
	// handling n < 8 omitted...
    for (; i + 7 < n; i += 8) {  // main loop: 8-way parallel
        __m256 va = _mm256_loadu_ps(&a[i]);  // load 8 floats into a vector register (unaligned)
        __m256 vb = _mm256_loadu_ps(&b[i]);
        __m256 vc = _mm256_add_ps(va, vb);   // vector addition
        _mm256_storeu_ps(&c[i], vc);          // store the result
    }
    // remainder: process leftover elements with scalar code
    for (; i < n; i++) {
        c[i] = a[i] + b[i];
    }
}

int main() {
    float a[16] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
    float b[16] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
    float c[16];
    array_add_avx2(a, b, c, 16);
    for (int i = 0; i < 16; i++) printf("%.0f ", c[i]);  // output: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
    return 0;
}

Compile:

# Enable AVX2
gcc -mavx2 -O3 example.c -o example

The function _mm256_loadu_ps loads 256 bits of floating-point values from memory into a vector register.

/// Loads 8 single-precision floating point values from an unaligned
///    memory location pointed to by \a __p into a vector of [8 x float].
///
/// \headerfile <x86intrin.h>
///
/// This intrinsic corresponds to the <c> VMOVUPS </c> instruction.
///
/// \param __p
///    A pointer to a memory location containing single-precision floating
///    point values.
/// \returns A 256-bit vector of [8 x float] containing the moved values.
static __inline __m256 __DEFAULT_FN_ATTRS
_mm256_loadu_ps(float const *__p)
{
  struct __loadu_ps {
    __m256_u __v;
  } __attribute__((__packed__, __may_alias__));
  return ((const struct __loadu_ps*)__p)->__v;
}

image

image

Vectorization Example 2

Array accumulation with vectorization:

float sum_scalar(float *a, size_t n) {
    float s = 0.0f;
    for (size_t i = 0; i < n; i++) {
        s += a[i];
    }
    return s;
}

float sum_avx2(float *a, int n)
{
    size_t i = 0; 
    __m256 vsum = _mm256_setzero_ps(); // initialize vector register to zero
    for (; i +7 < n; i += 8) {
        __m256 v = _mm256_loadu_ps(&a[i]); // load 8 floats into a vector register
        vsum = _mm256_add_ps(vsum, v); // vector addition
    }

    // horizontal reduction: sum the elements within the vector register
    float tmp[8];
    _mm256_storeu_ps(tmp, vsum); // store vector register to a temporary array
    float sum = tmp[0] + tmp[1] + tmp[2] + tmp[3] + tmp[4] + tmp[5] + tmp[6] + tmp[7];

    // process remaining elements
    for (; i < n; i++) {
        sum += a[i];
    }

    return sum;
}

image

image

Programming references:

SIMD in PostgreSQL

SIMD enables vectorized execution of operations on x86, including JSON string parsing, ASCII string detection, and subtransaction ID searches.

A git log --all --grep='SIMD' in the current codebase reveals:

  • doc: PG 16 relnotes, SIMD improvements (release-16.sgml, John Naylor)
  • Introduce helper SIMD functions for small byte arrays (simd.h / pg_lfind)
  • Optimize JSON escaping using SIMD (json.c)
  • Optimize xid/subxid searches in XidInMVCCSnapshot()
  • Optimize pg_memory_is_all_zeros() (memutils.h)
  • Optimize COPY FROM (FORMAT {text,csv}) using SIMD
  • Optimize hex_encode()/hex_decode() using SIMD
  • Compute CRC32C using AVX-512
  • Use ARM Advanced SIMD (NEON) intrinsics where available
  • Refactor some SIMD and popcount macros, and more

CRC32C Checksums

CRC-32C is an efficient cyclic redundancy check widely used for detecting errors in data transmission and storage. PostgreSQL uses it for data integrity — WAL log checksums, data page checksums, and the pg_control file. CRC-32C computation significantly impacts PG performance, so platform-specific optimizations are employed, including Intel SSE 4.2 instruction support. The latest PG code supports x86, ARM, and LoongArch64 instruction optimizations.

 /*
 * pg_crc32c.h
 *	  Routines for computing CRC-32C checksums.
 *
 * The speed of CRC-32C calculation has a big impact on performance, so we
 * jump through some hoops to get the best implementation for each
 * platform. Some CPU architectures have special instructions for speeding
 * up CRC calculations (e.g. Intel SSE 4.2), on other platforms we use the
 * Slicing-by-8 algorithm which uses lookup tables.
 */

#if defined(USE_SSE42_CRC32C)
/*
 * Use either Intel SSE 4.2 or AVX-512 instructions.
 */
#include <nmmintrin.h>

#define COMP_CRC32C(crc, data, len) \
	((crc) = pg_comp_crc32c_dispatch((crc), (data), (len)))
#define FIN_CRC32C(crc) ((crc) ^= 0xFFFFFFFF)

extern pg_crc32c pg_comp_crc32c_sse42(pg_crc32c crc, const void *data, size_t len);
#ifdef USE_AVX512_CRC32C_WITH_RUNTIME_CHECK
extern pg_crc32c pg_comp_crc32c_avx512(pg_crc32c crc, const void *data, size_t len);
#endif

#elif defined(USE_ARMV8_CRC32C)
/* Use ARMv8 CRC Extension instructions. */
#define COMP_CRC32C(crc, data, len) \
	((crc) = pg_comp_crc32c_armv8((crc), (data), (len)))
#define FIN_CRC32C(crc) ((crc) ^= 0xFFFFFFFF)
extern pg_crc32c pg_comp_crc32c_armv8(pg_crc32c crc, const void *data, size_t len);

#elif defined(USE_LOONGARCH_CRC32C)
/* Use LoongArch CRCC instructions. */
#define COMP_CRC32C(crc, data, len) \
	((crc) = pg_comp_crc32c_loongarch((crc), (data), (len)))
#define FIN_CRC32C(crc) ((crc) ^= 0xFFFFFFFF)
extern pg_crc32c pg_comp_crc32c_loongarch(pg_crc32c crc, const void *data, size_t len);

#elif defined(USE_ARMV8_CRC32C_WITH_RUNTIME_CHECK)
/* Use ARMv8 with runtime feature check. */
extern pg_crc32c pg_comp_crc32c_sb8(pg_crc32c crc, const void *data, size_t len);
extern pg_crc32c (*pg_comp_crc32c) (pg_crc32c crc, const void *data, size_t len);
extern pg_crc32c pg_comp_crc32c_armv8(pg_crc32c crc, const void *data, size_t len);

#else
/* Fall back to slicing-by-8 algorithm. */
// ...

PostgreSQL already supports LoongArch optimizations — impressive!

SIMD Compatibility Layer

Since SIMD depends on hardware instruction sets, platform-specific adaptation is necessary. PG provides a unified platform abstraction (SIMD compatibility layer) so callers are decoupled from specific instruction sets and use only the wrapper interface. See PG’s simd.h:

static inline void
vector32_load(Vector32 *v, const uint32 *s)
{
#ifdef USE_SSE2
	*v = _mm_loadu_si128((const __m128i *) s);
#elif defined(USE_NEON)
	*v = vld1q_u32(s);
#endif
}

SIMD in Database Systems

Vectorized execution engines are now standard in many databases — not just OLAP systems, but increasingly OLTP databases as well.

See also: TiFlash: Compiler-Driven Auto-Vectorization

These two references are highly recommended: Advanced Database Systems — Vectorization 1

Advanced Database Systems — Vectorization 2

References: Quickly Understand SIMD Compiler Optimizations (12): LLVM Auto-Vectorization LLVM Auto-Vectorization ARM SIMD Instruction Set Introduction SIMD Auto-Vectorization Survey TiFlash: Compiler-Driven Auto-Vectorization Advanced Database Systems — Vectorization 1 Advanced Database Systems — Vectorization 2