C++17 Parallel Algorithms: Execution Policies, Toolchain Support, and Why Exceptions Call terminate

What the execution policies say

C++17 added overloads of most standard algorithms that take an execution policy as the first argument:

#include <algorithm>
#include <execution>
#include <vector>

std::vector<int> v = /* ... */;

std::sort(std::execution::seq, v.begin(), v.end());        // sequential, same as no policy
std::sort(std::execution::par, v.begin(), v.end());        // may use multiple threads
std::sort(std::execution::par_unseq, v.begin(), v.end());  // threads and vectorization
std::sort(std::execution::unseq, v.begin(), v.end());      // C++20: vectorization only

A policy is a permission, not a command. par tells the library it may run your element access functions — the lambdas, comparators and predicates you pass — on several threads concurrently. The library may still run everything on the calling thread. In exchange, you promise that those functions are safe to run that way:

Policy	Callback may run on	Callback must not
seq	the calling thread, in order	—
par	multiple threads concurrently	race on shared data
par_unseq	multiple threads, interleaved within a thread	race, lock mutexes, allocate, or otherwise synchronize
unseq (C++20)	the calling thread, interleaved (SIMD)	lock, allocate, synchronize

The par_unseq restriction is the one people miss. “Interleaved” means the library may start the callback for element 1, then for element 2, before finishing element 1 — which is what vectorization does. A std::mutex inside such a callback can deadlock against itself, and new may take a lock inside the allocator. If the callback needs a lock, use par.

---

Toolchain support: the first thing to check

This is where most “parallel algorithms did nothing” reports come from.

• GCC / libstdc++ (9 and later) implements the policies on top of Intel oneTBB. Without TBB available, <execution> still compiles and runs, but serially. With it, link explicitly: g++ -O2 -std=c++17 app.cpp -ltbb. Some distributions need the libtbb-dev package, and older TBB versions are incompatible with some GCC versions, which shows up as compile errors inside <execution>.
• MSVC supports par natively in its standard library, using the Windows thread pool; no extra library is needed. Its par_unseq largely behaves like par; the vectorization permission is not exploited everywhere.
• Clang / libc++ support arrived late and has been partial and behind an experimental flag (-fexperimental-library). Clang with libstdc++ behaves like GCC.
• NVIDIA’s nvc++ can offload par algorithms to a GPU (-stdpar), which is the case where these policies shine most.

The first time I benchmarked std::sort(std::execution::par, ...) on Linux and saw no speedup, the cause was simply that nothing linked TBB. Nothing warns you: the program is correct, just serial. Check with a quick timing or a profiler’s thread view before drawing conclusions about the algorithm.

---

Sorting, transforming, reducing

#include <algorithm>
#include <cmath>
#include <execution>
#include <numeric>
#include <vector>

std::vector<double> data(10'000'000);
std::iota(data.begin(), data.end(), 1.0);

// transform: independent per-element work, a good fit
std::transform(std::execution::par, data.begin(), data.end(), data.begin(),
               [](double x) { return std::sqrt(x); });

// sort: parallel merge sort internally
std::sort(std::execution::par, data.begin(), data.end());

// reduce, not accumulate
double total = std::reduce(std::execution::par, data.begin(), data.end(), 0.0);

// transform_reduce: map then reduce in one pass, no temporary vector
std::vector<int> v(1'000'000);
std::iota(v.begin(), v.end(), 1);
long long sumSquares = std::transform_reduce(
    std::execution::par, v.begin(), v.end(), 0LL, std::plus<>{},
    [](int x) { return static_cast<long long>(x) * x; });

Why reduce and not accumulate

std::accumulate is defined as a strict left-to-right fold, so it cannot be parallelized and has no policy overload. std::reduce is allowed to group and reorder the operations, which is what makes parallel execution possible. The price: the operation must be associative and commutative for the result to be deterministic.

Integer addition is. Floating-point addition is not exactly associative, so a parallel reduce over double can give results that differ in the last bits from a sequential sum, and can differ between runs or thread counts. For most purposes that is fine; for results that must be bit-reproducible (tests comparing exact values, financial totals), use seq or compensated summation.

Note the initial value’s type sets the accumulator type: std::reduce(par, v.begin(), v.end(), 0) with a large std::vector<int> accumulates in int and overflows, while 0LL accumulates in long long.

---

The contract you must keep

No data races

long long sum = 0;
// Data race: many threads read-modify-write sum at once
std::for_each(std::execution::par, v.begin(), v.end(), [&](int x) { sum += x; });

// Correct: express it as a reduction
long long sum2 = std::reduce(std::execution::par, v.begin(), v.end(), 0LL);

The racy version usually produces a total that is too small, differs from run to run, and never crashes, which is why it survives testing on small inputs. Making sum a std::atomic<long long> removes the race but serializes every addition on one cache line and is often slower than the sequential loop. When you find yourself sharing state across element callbacks, the algorithm is almost always the wrong one; look for a reduction, a scan, or a partition of the output.

Reading an element that another invocation writes is also a race:

// Race: element 0 is written by one invocation and read by all others
std::for_each(std::execution::par, v.begin(), v.end(), [&](int& x) { x = v[0] + 1; });

Exceptions call std::terminate

This is the most important difference from the sequential algorithms, and it is often described incorrectly:

std::vector<int> v = {1, 2, -3, 4};
try {
    std::for_each(std::execution::par, v.begin(), v.end(), [](int x) {
        if (x < 0) throw std::runtime_error("negative");
    });
} catch (const std::exception& e) {
    std::cout << "caught: " << e.what() << '\n';   // never reached
}

terminate called after throwing an instance of 'std::runtime_error'
  what():  negative

With any of the standard execution policies, including seq, an exception escaping an element access function calls std::terminate. The try block does not help. (The algorithms can still throw std::bad_alloc themselves if they fail to allocate temporary storage; that one is catchable.) The practical consequence: code that validates by throwing from inside a callback must be restructured before adding a policy — validate first, or have callbacks record failures (for example into a per-element status array) and check after the call.

Do not depend on element identity or order

for_each with par visits elements in unspecified order and on unspecified threads. Code that computes an index from the element’s address (&p - &pixels[0]) or that assumes element i is processed before i + 1 is relying on details the policies do not promise. When the index matters, iterate over indices instead:

std::vector<int> idx(width * height);
std::iota(idx.begin(), idx.end(), 0);             // 0, 1, 2, ...
std::for_each(std::execution::par, idx.begin(), idx.end(), [&](int i) {
    int x = i % width, y = i / width;
    out[i] = blur3x3(in, x, y);                    // reads in, writes only out[i]
});

A materialized index vector looks wasteful next to std::views::iota, but the iota view’s iterator only advertises itself as an input iterator to pre-C++20 iterator traits, while the parallel overloads require forward iterators, so passing it is not guaranteed to compile or to be split across threads. Reading from a separate input buffer and writing only to out[i] makes each invocation independent by construction. That is the shape of every stencil-style operation (blur, convolution, cellular automata) that parallelizes cleanly.

---

Which algorithms take a policy

Most of <algorithm> has policy overloads: sort, stable_sort, partial_sort, nth_element, for_each, for_each_n, transform, copy, copy_if, fill, find, find_if, count, count_if, all_of/any_of/none_of, min_element/max_element, replace, remove_if, unique, merge and more. <numeric> adds the parallel-friendly reduce, transform_reduce, inclusive_scan, exclusive_scan and their transform variants.

Some do not, because they are inherently sequential or already logarithmic:

std::binary_search(std::execution::par, v.begin(), v.end(), 2);
// error: no matching function for call to 'binary_search(const __pstl::execution::v1::parallel_policy&, ...)'

binary_search, lower_bound, upper_bound, equal_range, accumulate, partial_sum, iota and the heap-building algorithms (make_heap, push_heap, pop_heap, sort_heap) have no policy overloads; the read-only is_heap and is_heap_until do. The ranges versions in std::ranges (C++20) also do not take execution policies.

The parallel overloads also require forward iterators at minimum, and in practice perform well only with random-access iterators. Passing std::list iterators compiles but gives the library little to split.

---

When it pays off

Parallel execution has a fixed cost: dispatching work to a thread pool and joining it. It wins when the total work is large compared with that cost, and when the work is compute-bound rather than memory-bound.

• Good fits: sorting millions of elements, expensive per-element transforms (math, parsing, hashing), reductions over large arrays, independent per-pixel or per-record processing.
• Poor fits: small inputs (hundreds or low thousands of cheap elements), work that is mostly memory traffic (a plain copy or fill can saturate memory bandwidth with one or two cores), callbacks that contend on shared state.

There is no universal size threshold; it depends on the per-element cost, the core count and the library. Measure with realistic data, and measure seq too — on a laptop running on battery, or in a container limited to one CPU, par can simply be slower.

The parallel algorithms also do not compose with other parallelism in the program. Calling a par algorithm from inside each of 16 worker threads, all sharing one TBB or Windows thread pool, oversubscribes the machine. Use them at the top level of a computation, or use a task framework directly when you already manage threads.

---

Related Articles

• C++20 Ranges Introduction
• C++ std::sort
• C++ std::thread Basics
• C++ std::atomic: Atomic Operations, Memory Order, and compare_exchange