Skip to content
Tutorials Center
My learning

Topics

Lesson 140 of 171 ยท Concurrency

Parallel Algorithms and Execution Policies

Speed up STL algorithms with C++17 execution policies - seq, par, par_unseq and unseq, parallel reduce and transform_reduce, and the rules for safe callbacks.

Most of the algorithms you already know, such as std::sort, std::transform and std::reduce, accept an optional first argument called an execution policy. It is a tiny tag object that tells the library: "you may run this work on several threads, or with SIMD instructions, if that helps." You don't create threads, you don't write locks, and the call still looks like the sequential one. That makes policies the cheapest way to use more than one core, provided the work is big enough and your callback is safe to run in parallel.

In this lesson you'll learn the four policies in <execution>, which algorithms take them, how reduce differs from accumulate, what rules your lambdas must follow, and when parallelism makes a program slower instead of faster. It builds on the STL algorithms, numeric algorithms and the threads and mutex lessons.

The four execution policies

The header <execution> defines one global object for each policy:

Policy object Meaning
std::execution::seq Run sequentially on the calling thread, in the usual order
std::execution::par May run on several threads; each element is still processed by one thread at a time
std::execution::unseq (C++20) May interleave iterations in one thread using vector (SIMD) instructions
std::execution::par_unseq May use threads and vectorization

The stronger the policy, the fewer things your callback may do. With par, calls from different threads can overlap, so shared data needs protection. With par_unseq and unseq, even two iterations on the same thread may be interleaved, so the callback must not take a mutex at all: if iteration A locks and gets interleaved with iteration B on the same thread, B waits for a lock A can never release.

flowchart LR
    A["Algorithm call<br/>(policy, range)"] --> B{"Policy?"}
    B -->|seq| C["One thread, in order"]
    B -->|par| D["Chunks on a thread pool"]
    B -->|unseq| E["One thread, SIMD lanes"]
    B -->|par_unseq| F["Thread pool + SIMD lanes"]

The policy only grants permission. The library may still run everything sequentially.

That last point matters: a policy is a permission, not a promise. An implementation is allowed to ignore it. libstdc++ (GCC's library) runs parallel algorithms on the oneTBB library when it is installed, and falls back to plain sequential execution when it is not. MSVC and libc++ have their own backends. So your code is correct either way, and the results must not depend on which one you get.

Your first parallel algorithm

Passing a policy is just one extra argument. This program sorts a vector and sums squares with a parallel policy. The results are exactly what you would get sequentially.

C++ Sorting and summing with policies

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Notice what did not change: the iterator pair, the comparator, the lambda. Only the first argument is new. The policy overloads exist for most algorithms in <algorithm> and <numeric>: for_each, transform, copy, fill, find, count, all_of/any_of, sort, stable_sort, partition, merge, reduce, transform_reduce, inclusive_scan, exclusive_scan and more.

Two limits to remember. The policy overloads require forward iterators or better, because the work has to be split among threads, so they don't work with input iterators such as std::istream_iterator. And the C++20 ranges algorithms (std::ranges::sort and friends) have no policy overloads at all, so you use the classic iterator-pair versions when you want parallelism.

reduce versus accumulate

std::accumulate is defined as a strict left-to-right fold: ((init + a) + b) + c. That order cannot be split among threads. std::reduce is its parallel-friendly sibling: it may group and reorder the operations, so the operation must be associative and commutative.

For integers, addition is both, and the result is identical. For floating point numbers, addition is not associative, so reduce can give a slightly different answer than accumulate, and the answer can differ between runs.

C++ Why reduce needs an associative operation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The first result is deterministic because accumulate fixes the order. Calling reduce with std::minus<> would be a bug: the standard says the behavior is nondeterministic, since threads may combine chunks in any order. Whenever you switch from accumulate to reduce, ask: "does my operation give the same result for any grouping and any order of the operands?" If not, keep accumulate.

transform_reduce fuses a map and a reduce into one parallel pass: it applies a function to each element and then combines the results. It is the parallel form of a dot product (inner_product), and it avoids building an intermediate vector.

Rules for the callbacks you pass

A parallel algorithm calls your lambda from several threads, possibly overlapping. The rule is the same as for any multithreaded code: no data races. Concretely:

  • Reading shared data is fine. Writing to the same variable from several elements is not.
  • Each iteration may write only to its own element (that is what transform into a separate output does).
  • With par_unseq and unseq, the callback must not allocate memory in ways that take locks, must not lock a mutex, and must not use blocking synchronization. In the standard's words, such functions must be vectorization-safe.
  • Exceptions: if a callback exits with an exception under a parallel policy, the library calls std::terminate. There is no try/catch around your algorithm that can save you, so handle errors inside the lambda.

The most common mistake is a shared accumulator:

C++
long long total = 0;
std::for_each(std::execution::par, v.begin(), v.end(),
              [&](int x) { total += x; });   // DATA RACE: undefined behavior

The fixes, in order of preference, are to use reduce or transform_reduce, which have no shared state; to use a std::atomic if you really need a shared counter (see atomics); or to hold a mutex, which is allowed under par but not par_unseq, and usually destroys the speed-up.

This example uses an atomic counter and a per-element write, both safe under par:

C++ Safe shared state under par

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Does it actually get faster?

Not always. Starting a task pool, splitting the range and joining the results costs time. For a few thousand cheap operations, a sequential loop wins easily. Parallelism pays off when:

  • the range is large (hundreds of thousands of elements or more) or each element is expensive to process;
  • the work per element is independent;
  • the algorithm is not memory-bandwidth bound (a plain sum of a huge array often saturates memory before it saturates the cores).

Measure with realistic data on realistic hardware. Our in-browser runner has a single CPU, so you would see no speed-up there even if the library used threads, which is why the examples above show correctness rather than timing.

Building for parallelism also depends on the toolchain. With GCC you typically link oneTBB (-ltbb); without it, the algorithms still compile and run, just sequentially. Newer standards are adding another, more general model, std::execution senders and receivers (C++26), which describes asynchronous work as composable graphs and can target thread pools or GPUs. The policies in this lesson are the established part and are available today in every major compiler.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does passing std::execution::par to an algorithm guarantee?

    A policy is a permission. Implementations may use threads or fall back to sequential execution, so you never get a guarantee of speed or of thread use.
  2. 2. Why is std::reduce(std::execution::par, v.begin(), v.end(), 0, std::minus<>{}) a bug?

    reduce may combine elements in any grouping and order, so the operation must be associative and commutative. Use accumulate when order matters.
  3. 3. What happens if a lambda throws an exception inside an algorithm running under a parallel policy?

    Parallel algorithms call std::terminate when a callback exits with an exception, so errors must be handled inside the callback.
  4. 4. Which of these is NOT allowed in a callback used with std::execution::par_unseq?

    With par_unseq, iterations can be interleaved on one thread, so a lock taken by one iteration could block another iteration on the same thread forever. Blocking synchronization is not allowed.

Summary

  • Execution policies (seq, par, unseq, par_unseq in <execution>) are an extra first argument that lets many STL algorithms run in parallel or vectorized.
  • A policy is a permission: results must be correct whether or not the library actually uses threads.
  • Use std::reduce and std::transform_reduce instead of accumulate and inner_product for parallel sums, but only with associative and commutative operations.
  • Callbacks must be free of data races; par_unseq additionally forbids locks and blocking calls, and an exception means std::terminate.
  • Policy overloads need forward iterators and are not available for std::ranges algorithms.
  • Parallelism only helps with big or expensive workloads, so measure before you commit.

Next: you have finished the concurrency tools; continue with Modern C++ Features, a tour of what C++20 and C++23 added to the language.