C++ / CONCURRENCY AND PARALLELISM
Parallel algorithms and execution policies
Call standard algorithms with std::execution policies, pick reduce over accumulate, and know what promises par and par_unseq demand of your callable.
What you will learn
- Pass std::execution::par as the first argument to opt an algorithm into parallelism
- Swap accumulate and inner_product for reduce and transform_reduce
- Guard shared state with atomics; never do sum += x inside a par lambda
- Avoid mutexes and allocation under par_unseq, where calls interleave on one thread
Understanding Parallel algorithms and execution policies
C++17 added policy-taking overloads to roughly seventy algorithms in <algorithm> and <numeric>. The policy is the first argument: std::sort(std::execution::par, v.begin(), v.end()). The policy objects live in <execution> and are seq, par, par_unseq, plus unseq from C++20. Each is an object of a distinct type, so the choice is made by overload resolution at compile time; you cannot store a policy in a variable and pick one at runtime without writing two call sites or templating on the policy type.
The right mental model is that a policy is a promise you make about your element-access functions, not an order to spawn threads. par promises that invocations may happen on the calling thread and on library threads in any order, so they must not race on shared state. par_unseq promises more: invocations may also be interleaved with each other on a single thread, as happens when the body is vectorised, so the body must not take a lock or assume it runs to completion before the next one starts. If an exception escapes an element-access function under any policy, std::terminate is called instead of the exception reaching your catch block.
Some algorithms have no policy overload at all, and the reason is instructive. accumulate, inner_product and partial_sum are specified as strict left-to-right folds, so splitting the range would change the defined result; their reorderable counterparts are reduce, transform_reduce and inclusive_scan/exclusive_scan, which require an associative operation (and commutative for reduce). That same freedom to regroup is why a parallel float sum is not bit-identical to a serial one, and why par rarely pays off on a std::list, where the library cannot cheaply split the range into chunks.
<algorithm>
<execution>
<iostream>
<numeric>
<vector>
int main() {
std::vector<long long> v(10);
std::iota(v.begin(), v.end(), 1); // no policy overload: iota is inherently ordered
std::vector<long long> squares(v.size());
std::transform(std::execution::par, v.begin(), v.end(), squares.begin(),
[](long long x) { return x * x; });
long long total = std::reduce(std::execution::par, squares.begin(), squares.end(), 0LL);
auto evens = std::count_if(std::execution::par, v.begin(), v.end(),
[](long long x) { return x % 2 == 0; });
std::cout << "squares.front() = " << squares.front() << '\n';
std::cout << "squares.back() = " << squares.back() << '\n';
std::cout << "sum of squares = " << total << '\n';
std::cout << "even inputs = " << evens << '\n';
}
An execution policy is a compile-time promise that your element-access callables are independent and reorderable, not a command to create threads.
Worked examples
reduce and transform_reduce instead of accumulate
Shows the parallel-friendly shape of a fold and why accumulate cannot take a policy.
<execution>
<functional>
<iostream>
<numeric>
<vector>
int main() {
std::vector<int> price{3, 7, 2, 10};
std::vector<int> qty{4, 1, 5, 2};
int revenue = std::transform_reduce(std::execution::par,
price.begin(), price.end(), qty.begin(),
0, std::plus<>{}, std::multiplies<>{});
int serial = std::accumulate(price.begin(), price.end(), 0);
std::cout << "revenue (parallel transform_reduce) = " << revenue << '\n';
std::cout << "price sum (serial accumulate) = " << serial << '\n';
}
Example explained
Line 1transform_reduce takes two callables: multiplies<> maps each pair price[i], qty[i], and plus<> folds the mapped values.
Line 2The mapping step is independent per element, so only the fold needs a combining rule, which is why plus<> must be associative.
Line 3accumulate is called with no policy because none exists for it; its result is defined as a left fold, so it cannot be split.
Line 4Swapping plus<> for minus<> would still compile but the answer would become unspecified, since subtraction is not associative.
Disjoint writes are safe, shared writes are not
Demonstrates that a par lambda may freely modify its own element but must use an atomic for anything shared.
<algorithm>
<atomic>
<execution>
<iostream>
<vector>
int main() {
std::vector<int> v(1000, 1);
std::atomic<long long> calls{0};
std::for_each(std::execution::par, v.begin(), v.end(), [&calls](int& x) {
x *= 3; // writes only its own element
calls.fetch_add(1, std::memory_order_relaxed); // shared, so it must be atomic
});
bool tripled = std::all_of(std::execution::par, v.begin(), v.end(),
[](int x) { return x == 3; });
std::cout << "v[0] = " << v[0] << '\n';
std::cout << "calls = " << calls.load() << '\n';
std::cout << "all tripled: " << tripled << '\n';
}
Example explained
Line 1Each invocation gets a reference to one distinct element, so x *= 3 touches memory no other invocation touches.
Line 2calls is shared by every invocation, so it must be atomic; a plain long long here would be a data race and undefined behaviour.
Line 3The policy overload of for_each returns void and guarantees no ordering, so only order-independent side effects such as fetch_add are meaningful.
Line 4The all_of call reads the vector after for_each returns; a parallel algorithm completes all element accesses before it returns, so no extra synchronisation is needed.
Important notes
A policy is permission, not obligation: a conforming implementation may run par entirely serially, so never rely on parallelism for correctness or for progress.
reduce over floating point is not bit-reproducible against accumulate, because the grouping of partial sums is unspecified; if you need an exact reference value, keep a serial path.
Common mistakes
Capturing a long long sum by reference and writing sum += x inside a par lambda: that is a data race, so the total comes out too low and changes from run to run.
Writing std::accumulate(std::execution::par, ...) and expecting it to work: it does not compile, because accumulate has no policy overload; std::reduce is the parallel form.
Locking a mutex inside a par_unseq lambda: two interleaved invocations on the same thread can try to lock it twice and hang the program.
Try it yourself
Change, predict, then run
Fill a std::vector<float> with 1.0f/i for i from 1 to 1000000, sum it with std::reduce under std::execution::seq and again under par, and print both with nine significant digits to see whether they agree bit for bit. Then increment a std::atomic<long long> inside a std::for_each(std::execution::par, ...) over the same vector and confirm it ends at 1000000.
Open the C++ workspaceCheck your understanding
You replace std::accumulate(v.begin(), v.end(), 0.0f, op) with std::reduce(std::execution::par, v.begin(), v.end(), 0.0f, op) and the total now varies slightly between runs. What is the most likely explanation?
- The par policy introduces a data race on the accumulator, corrupting the total.
- std::reduce is allowed to skip elements when the thread pool is saturated.
- std::reduce may group and combine partial results in any order, so floating-point rounding lands differently.
- Calling op from more than one thread is unsafe because float is not an atomic type.
Show answer
reduce is specified in terms of an unspecified grouping of the range, so partial sums are formed in different orders and rounding error accumulates differently; accumulate is a strict left fold and therefore reproducible. Option 0 is the tempting answer, but the library synchronises its own partial results — a race would only exist if op itself touched shared state.