How C++ Vectorization Optimizes CPU Loops

Vectorization optimization in C++ is the process through which modern compilers transform scalar, iterative loops into parallel Single Instruction, Multiple Data (SIMD) hardware instructions. This article examines the mechanics of this transformation, exploring how compilers analyze memory safety and dependencies, map operations to wide hardware registers, and handle non-uniform loop boundaries to maximize arithmetic throughput on contemporary processors.

The Scalar Baseline vs. SIMD Execution

In standard scalar execution, a C++ for loop processing an array performs arithmetic operations sequentially. The CPU processes one data element per instruction cycle using standard general-purpose registers (such as 32-bit or 64-bit integer or floating-point registers).

void add_arrays(float* a, float* b, float* c, int n) {
    for (int i = 0; i < n; ++i) {
        c[i] = a[i] + b[i];
    }
}

Without vectorization, the compiled machine code reads a[i] and b[i], executes a single addition instruction (such as addss in x86-64), writes the result to c[i], and increments the index i. This represents Single Instruction, Single Data (SISD) processing.

Vectorization leverages SIMD architectures (such as Intel SSE/AVX/AVX-512 or ARM NEON). These architectures feature wide vector registers ranging from 128 to 512 bits in size. A 256-bit register, for example, can hold eight 32-bit floating-point numbers simultaneously. Auto-vectorization transforms the loop so that a single instruction executes the addition for eight elements in parallel.

Compiler Feasibility Analysis

Before converting scalar logic to SIMD instructions, the compiler must verify that parallelization will not alter program semantics. This involves three critical checks:

  1. Loop-Carried Dependencies: The compiler inspects the loop for data hazards. If iteration i depends on the outcome of iteration i - 1 (a Read-After-Write dependency), the loop cannot be naively vectorized because elements cannot be processed concurrently.
  2. Pointer Aliasing: In C++, two pointers of the same type may reference overlapping memory regions. If pointer c overlaps with a or b, writing to c[i] might alter the value of a[i+1]. Compilers will either fail to vectorize, generate runtime alias checks, or require hints like the __restrict__ qualifier to guarantee disjoint memory.
  3. Control Flow and Uniformity: Branches or conditional statements inside the loop can inhibit vectorization. Compilers convert simple conditionals into masked vector operations or blend instructions, ensuring that control flow does not diverge between elements in the same vector lane.

The Transformation: Strip-Mining and Loop Peeling

Once determined safe, the compiler restructures the loop through a technique called strip-mining. The loop iterations are divided into chunks matching the width of the target SIMD register.

If the target architecture supports AVX2 (256-bit vectors) and the array contains 32-bit floats, the vector width (\(W\)) is 8 elements. The transformation divides the single loop into distinct phases:

  • Prolog (Peeling Loop): Vector instructions often perform significantly faster when memory addresses are aligned to 16-, 32-, or 64-byte boundaries. If the input pointer is not aligned, the compiler executes a few scalar iterations until an aligned boundary is reached.
  • Vector Kernel (Main Loop): The core computation runs in steps of \(W\) (e.g., i += 8). The compiler replaces scalar loads with vector loads (vmovups or vmovaps), scalar arithmetic with vector arithmetic (vaddps), and scalar stores with vector stores.
  • Epilog (Remainder Loop): Because total iterations (\(n\)) might not be an exact multiple of the vector width, trailing iterations are executed either using scalar instructions or masked vector operations that disable unused vector lanes.

Mapping to CPU Instructions

At the machine level, the arithmetic logic is translated directly into SIMD instructions. In an unoptimized x86-64 binary, the loop body relies on instructions such as:

movss   xmm0, DWORD PTR [rsi+rax*4]
addss   xmm0, DWORD PTR [rdx+rax*4]
movss   DWORD PTR [rdi+rax*4], xmm0
inc     rax
cmp     rax, rcx
jne     .LOOP

Under auto-vectorization (e.g., targeting AVX2), the compiled assembly converts into parallel register operations utilizing 256-bit ymm registers:

vmovups ymm0, YMMWORD PTR [rsi+rax*4]
vaddps  ymm0, ymm0, YMMWORD PTR [rdx+rax*4]
vmovups YMMWORD PTR [rdi+rax*4], ymm0
add     rax, 8
cmp     rax, r8
jb      .VECTOR_LOOP

In this optimized state, each instruction processes eight floating-point additions simultaneously. By reducing loop counter increments, branch evaluations, and pipeline stalls, vectorization maximizes the utilization of the CPU's internal execution units and drastically increases arithmetic performance.