Vectorized Execution Policies in C++ with SIMD

Modern C++ provides standardized execution policies that allow standard library algorithms to run concurrently and vectorize automatically. This article explores how vectorized execution policies—specifically std::execution::unseq and std::execution::par_unseq—grant compilers the semantic freedom to emit Single Instruction, Multiple Data (SIMD) hardware instructions, how these policies alter loop execution guarantees, and the rules developers must follow to achieve optimal vectorized performance.

Understanding Execution Policies

C++17 introduced execution policies in the <execution> header to parallelize standard algorithms in <algorithm> and <numeric>. These policies dictate how iterations of an algorithm may be scheduled:

  • std::execution::seq: Traditional sequential execution on the calling thread.
  • std::execution::par: Multi-threaded execution across multiple threads, where iterations cannot interleave on the same thread.
  • std::execution::par_unseq: Multi-threaded and unsequenced (vectorized) execution.
  • std::execution::unseq (C++20): Single-threaded, unsequenced execution intended specifically for SIMD vectorization.

The Mechanism: Unsequenced Execution

The critical distinction enabling SIMD is the "unsequenced" guarantee. Under standard sequential or parallel policies, an operation inside an iteration must complete before the next iteration begins on that same thread. This prevents traditional loop vectorization if the compiler cannot mathematically prove the absence of dependencies.

When you pass std::execution::unseq or std::execution::par_unseq to an algorithm like std::transform or std::for_each, you provide a contract to the compiler: individual iterations may be interleaved arbitrarily on a single thread. The compiler interprets this guarantee as permission to process multiple data elements simultaneously within CPU vector registers (such as x86 SSE/AVX or ARM NEON).

How Compilers Map Algorithms to SIMD

Modern C++ toolchains translate vectorized policies into SIMD through a multi-tier pipeline:

  1. Semantic Lowering: The standard library implementation lowers the algorithm into an unrolled loop decorated with internal compiler pragmas (such as #pragma clang loop vectorize(enable) or OpenMP SIMD directives).
  2. Vector Register Packing: The compiler loads contiguous elements of input sequences into hardware vector registers (e.g., eight 32-bit integers into a 256-bit AVX2 register).
  3. Vectorized Arithmetic: The operation provided in the lambda or function object executes across all packed lanes in a single CPU cycle using instructions like vpaddd (vector packed add).
  4. Masking and Remainder Handling: If the data size is not an exact multiple of the vector register width, the compiler automatically generates a vectorized masked load/store or a scalar tail loop to handle remaining elements safely.

Vectorization with std::transform and std::reduce

Vectorization yields significant performance gains in data-parallel computations. For example, computing the sum of elements using std::reduce:

#include <vector>
#include <numeric>
#include <execution>

std::vector<float> data(10'000'000, 1.5f);

// Emits vectorized instructions (e.g., AVX vaddps)
float total = std::reduce(std::execution::unseq, data.begin(), data.end(), 0.0f);

Because std::reduce does not guarantee a strict left-to-right evaluation order, the compiler can accumulate multiple intermediate partial sums in vector lanes before performing a final horizontal reduction across the register.

Constraints and Safety Rules for SIMD Execution

To leverage SIMD through standard library algorithms without undefined behavior, developers must adhere to strict constraints:

  • No Synchronization Primitives: You cannot acquire mutexes, use condition variables, or perform memory allocations inside the invoked function. If one SIMD lane were to block waiting for a lock held by another lane on the same thread, the execution would deadlock.
  • No Non-Atomic Shared State: Modifying shared variables across iterations causes data races or vector hazards. Only lock-free atomic operations are permitted, though atomics inside SIMD loops generally negate vectorization efficiency.
  • Memory Contiguity: SIMD hardware works best with continuous chunks of memory. Vectorized execution policies are most effective when applied to contiguous iterators, such as those provided by std::vector, std::array, or std::span. Iterating over non-contiguous structures like std::list forces gather/scatter operations, significantly degrading performance.