Parallel Algorithms
C++17 added a tiny extra argument to more than eighty STL algorithms that lets you ask the standard library to spread the work across multiple cores — and that one argument opens up a whole new category of undefined behavior sequential code never had to think about.
For decades, calling std::sort or std::accumulate on a vector meant the standard library would walk that container from start to finish on a single core, no matter how many cores the machine actually had sitting idle. C++17 changed that by adding execution policies to algorithms in <algorithm> and <numeric> — a small extra first argument that tells the algorithm how it is allowed to execute: strictly in the original order, spread across multiple threads, or spread across threads and vectorized within each thread. The algorithm's signature and its logic barely change; what changes is the contract between you and the implementation about what the callable you hand it is allowed to assume about when and where it runs. This page works through the three execution policies, why parallel execution introduces data races that never existed in the sequential versions of the same calls, and how to reason about whether parallelizing a given algorithm is actually going to make anything faster.
Execution Policies as an Extra Argument
The header <execution> defines three policy tag objects in namespace std::execution: std::execution::seq, std::execution::par, and std::execution::par_unseq. Passing one of these as the first argument to an overloaded algorithm selects a parallel-aware version of that algorithm; omitting the policy entirely still compiles and behaves exactly as it always did, so no existing code breaks.
Both calls sort the same range and produce the same final order. The only difference is the policy argument, which changes how the implementation is permitted to get there — not what the correct result is.
This applies to a wide swath of the library: sort, for_each, transform, reduce, find, count, copy, and dozens more all gained policy-taking overloads. The policy is purely about execution strategy — it never changes the mathematical result of a correctly written, race-free call.
#include <algorithm>
#include <execution>
#include <vector>
std::vector<int> values = {5, 3, 8, 1, 9, 2};
// Old, single-threaded call — still valid, still the default.
std::sort(values.begin(), values.end());
// New: same algorithm, explicitly allowed to use multiple threads.
std::sort(std::execution::par, values.begin(), values.end());std::execution::seq — Sequential, but Explicit
std::execution::seq requests exactly the same behavior as calling the algorithm with no policy at all: one thread, elements processed in a defined, deterministic order. It exists mainly to make intent explicit in code that also uses par or par_unseq elsewhere, or as a documented fallback once profiling shows that parallelizing a particular call did not pay off.
Nothing here runs any differently than the policy-free version — seq is a statement of intent, not an optimization.
#include <algorithm>
#include <execution>
#include <vector>
std::vector<int> data = {4, 2, 7, 1};
std::for_each(std::execution::seq, data.begin(), data.end(), [](int& x) { x *= 2; });std::execution::par — Multiple Threads, New Rules
std::execution::par permits the implementation to split the range across multiple threads and invoke your callable — the comparator, the loop body, the transform function — from more than one thread at once, in an unspecified order across those threads. Within any single thread, execution stays sequenced normally; what is new is that two invocations on two different elements might now be running literally at the same time on two different cores.
total += x is a read-modify-write on ordinary memory. Under std::execution::par, that line can execute concurrently from several threads, and unsynchronized concurrent writes to the same variable are a data race — the final value of total is undefined, and in practice it will usually come out lower than the correct 1,000,000 because some increments get lost.
Replacing the plain int with std::atomic<int> makes each increment a single indivisible operation, so concurrent threads can safely add to it at the same time without corrupting the result. This is the fix for the race above, not a workaround — it makes the shared mutation actually correct under a parallel policy.
#include <algorithm>
#include <execution>
#include <vector>
std::vector<int> counter_source(1'000'000, 1);
int total = 0;
// DANGEROUS: total is read and written from multiple threads with no
// synchronization at all — this is a data race and the behavior is undefined.
std::for_each(std::execution::par, counter_source.begin(), counter_source.end(),
[&total](int x) { total += x; });#include <algorithm>
#include <atomic>
#include <execution>
#include <vector>
std::vector<int> counter_source(1'000'000, 1);
std::atomic<int> total{0};
std::for_each(std::execution::par, counter_source.begin(), counter_source.end(),
[&total](int x) { total += x; });std::execution::par_unseq — Parallel and Vectorized
std::execution::par_unseq permits everything par does, plus vectorization: element access functions may additionally be interleaved with each other on a single thread, the way SIMD instructions process several elements' worth of work in lockstep within one instruction. That extra freedom comes with a stricter rulebook. Because two logically separate iterations can be woven together at the instruction level on the same thread, a callable used under par_unseq must not do anything that could block waiting on another iteration to make progress — no locking a mutex, no memory allocation in general (the standard leaves this implementation-defined and unsafe to rely on), and no calling non-vectorization-safe library functions.
Each call to the lambda only reads its own element and writes back to that same position — there is nothing here that could conflict if two of these calls happen to be interleaved on the same thread.
This exact code would be legal (if a little contended) under std::execution::par, because par guarantees each invocation runs to completion on its own thread. Under par_unseq the same code has undefined behavior, since the standard permits the implementation to interleave the two invocations' instructions on one thread, and a mutex lock inside that interleaving can never be relied on to make progress correctly.
#include <algorithm>
#include <cmath>
#include <execution>
#include <vector>
std::vector<double> values(1'000'000, 2.0);
// Safe: pure arithmetic, no shared mutable state, no locking, no allocation.
std::transform(std::execution::par_unseq, values.begin(), values.end(), values.begin(),
[](double x) { return std::sqrt(x) * 3.0; });#include <algorithm>
#include <execution>
#include <mutex>
#include <vector>
std::mutex m;
std::vector<int> log_entries;
std::vector<int> values(1000, 1);
// UNSAFE under par_unseq: taking a mutex assumes the current "iteration"
// can block until another one releases the lock — but under par_unseq,
// that other iteration might be interleaved on the very same thread and
// never get a chance to run to the unlock, which can deadlock.
std::for_each(std::execution::par_unseq, values.begin(), values.end(), [&](int x) {
std::lock_guard<std::mutex> lock(m);
log_entries.push_back(x);
});Exceptions Under a Parallel Policy
Sequential STL algorithms propagate exceptions from user callables normally — an exception thrown inside the lambda passed to a plain std::for_each unwinds the stack exactly like an exception thrown anywhere else. Algorithms invoked with a parallel policy (par or par_unseq) behave differently: if any invocation of the element access function throws, std::terminate is called. The exception does not propagate back to the caller in a catchable way.
This program calls std::terminate the moment the lambda throws for x == 0, regardless of the surrounding try/catch. If a callable used with a parallel policy can fail, it must handle that failure internally (returning a status value, storing it in a thread-safe result slot) rather than throwing.
#include <algorithm>
#include <execution>
#include <stdexcept>
#include <vector>
std::vector<int> values = {1, 2, 0, 4};
try
{
std::for_each(std::execution::par, values.begin(), values.end(), [](int x) {
if (x == 0)
throw std::runtime_error("zero encountered");
});
}
catch (const std::exception&)
{
// This catch block is never reached — the program terminates instead.
}reduce vs accumulate — Why Order Matters
std::accumulate folds a range left to right, applying the combining operation in a strictly defined order — that makes it correct for non-associative operations like floating-point subtraction, but it also makes it fundamentally unparallelizable: element five's contribution genuinely depends on the folded result of elements one through four. std::reduce, added in C++17 alongside the execution policies, does the same job but explicitly permits the implementation to combine elements in any order and grouping, which is exactly what makes it safe to run under std::execution::par.
Both calls compute the same sum here because addition on these values is associative and commutative. reduce requires the combining operation to have those properties (the default is std::plus<>) precisely because it reserves the right to reorder and regroup the work across threads.
std::transform_reduce combines a transform step with a reduction in one parallel-friendly pass — for example, summing the squares of a range without materializing an intermediate transformed vector at all.
transform_reduce applies the unary transform (squaring) to each element and folds the results with the binary reduction (addition) — since both steps here are pure, allocation-free arithmetic, this is a legitimate use of par_unseq.
#include <execution>
#include <numeric>
#include <vector>
std::vector<int> values(1'000'000, 1);
// accumulate has no parallel overload — it is inherently sequential.
long long total_seq = std::accumulate(values.begin(), values.end(), 0LL);
// reduce may combine elements out of order and across threads.
long long total_par = std::reduce(std::execution::par, values.begin(), values.end(), 0LL);#include <execution>
#include <numeric>
#include <vector>
std::vector<double> values = {1.0, 2.0, 3.0, 4.0};
double sum_of_squares = std::transform_reduce(
std::execution::par_unseq, values.begin(), values.end(),
0.0, std::plus<>(), [](double x) { return x * x; });Performance Considerations — Parallelism Is Not Free
Spinning up parallel work has real overhead: scheduling tasks onto a thread pool, splitting the range into chunks, and synchronizing at the end all cost time before a single element gets processed. For a vector of 20 ints, std::sort(std::execution::par, ...) will typically be slower than the plain sequential sort — the coordination overhead dwarfs the actual comparison work. Parallel policies tend to pay off only once the total data size and the per-element work are both large enough that the coordination cost is a small fraction of the total.
The standard does not require an implementation to actually run par or par_unseq calls in parallel — it only permits it. A given standard library may fall back to sequential execution for small inputs, or may not have a highly optimized parallel backend at all. Never assume adding a policy guarantees a speedup; measure with realistic data sizes on the target platform.
Best Practices and the Key Mental Model
Default to no policy (or std::execution::seq for clarity) until profiling shows a specific algorithm call is a bottleneck on data large enough to matter. When you do reach for std::execution::par, treat the callable as if it were being called concurrently from an unknown number of threads: no unsynchronized shared mutable state, prefer atomics or per-thread accumulation with a final combine step over locking when possible, and assume any thrown exception ends the program. Reserve std::execution::par_unseq for callables that are pure functions of their input — no shared state, no synchronization primitives, no allocation — since vectorized interleaving on a single thread breaks any code that assumes one iteration finishes before another starts.
The mental model that ties all of this together: a sequential algorithm makes one promise — elements are processed in order, one at a time. A parallel policy trades that promise for permission to use more hardware, and it is entirely on you to make sure your callable doesn't depend on the promise it just gave up.
What is the practical difference between std::execution::seq and calling an algorithm with no execution policy at all?
None in terms of behavior — both process elements on a single thread in a defined, deterministic order. std::execution::seq exists to make that choice explicit in source code, often alongside other calls that do use par or par_unseq.
Why does std::execution::par_unseq forbid taking a mutex inside the callable, when std::execution::par allows it?
par guarantees each element's invocation runs to completion on a single thread before that thread moves to another element, so a lock-and-unlock pair is safe. par_unseq additionally permits interleaving different elements' instructions on the same thread, so a thread could get stuck waiting on a lock held by an invocation that is itself paused mid-interleave on that same thread, risking a deadlock the standard does not guarantee will resolve.
Why does std::accumulate have no parallel-policy overload, while std::reduce does?
std::accumulate is specified to fold left to right in a strict, defined order, so each step depends on the previous one's exact result — that dependency chain cannot be split across threads. std::reduce is specified to allow combining elements in any order and grouping, which requires the combining operation to be associative and commutative but is exactly what makes it safe to execute in parallel.
What happens if a callable passed to an algorithm invoked with std::execution::par throws an exception, and how does that differ from the sequential version of the same call?
std::terminate is called immediately — the exception does not propagate to a surrounding try/catch. The sequential version of the same algorithm (no policy, or std::execution::seq) propagates the exception normally, so callers can catch and handle it.
Why might adding std::execution::par to std::sort on a small vector make the program slower rather than faster?
Parallel execution has real coordination overhead — splitting the range into chunks, scheduling work across a thread pool, and synchronizing at the end. For a small range, that overhead outweighs the actual comparison work, so the sequential version, which has none of that overhead, finishes faster.
This program compiles and usually runs without crashing. Is its output reliably 100? Explain what is actually wrong with it.
No — the output is not reliably 100, even though it might print 100 on many runs. total += x is an unsynchronized read-modify-write on a plain long long, and std::execution::par permits the lambda to run concurrently on multiple threads. Concurrent unsynchronized writes to the same variable are a data race, which is undefined behavior; in practice this usually manifests as an undercount when two threads' increments overlap and one gets lost, but the standard does not guarantee any particular outcome. Fixing it requires std::atomic<long long> total, or accumulating per-thread partial sums and combining them at the end, or simply using std::reduce instead of a hand-rolled for_each with a shared accumulator.
Write a C++ program that uses std::execution::par_unseq with std::transform to compute the elementwise cube of a large vector of doubles in place, and prints the first five results.
The transform lambda only reads its own element and writes its result back to the same position, with no shared mutable state, no allocation, and no synchronization — exactly the kind of pure, elementwise operation that par_unseq is designed for, since it is safe even if the implementation interleaves several elements' instructions on the same thread.
Write a C++ program that computes the sum of squares of a vector of ints using std::transform_reduce with std::execution::par, and compares it against the same computation done sequentially with std::accumulate after a manual transform, printing both results.
transform_reduce applies the squaring lambda to each element and combines the results with std::plus<>(), both of which are associative and commutative, so running it under std::execution::par produces the same total (55) as the hand-written sequential loop — parallel execution changes only the order and location of the additions, never the mathematically correct result for an associative, commutative operation.
#include <algorithm>
#include <execution>
#include <vector>
#include <iostream>
int main()
{
std::vector<int> data(100, 1);
long long total = 0;
std::for_each(std::execution::par, data.begin(), data.end(),
[&total](int x) { total += x; });
std::cout << total << "\n";
return 0;
}