C++ Module 11 – Iterators, algorithms and ranges
C++ parallel algorithms and execution policies
Run standard C++ algorithms in parallel with execution policies, build them with GCC and TBB or Apple clang, and write element functions without data races.
What you will learn
- Run standard algorithms in parallel with the four execution policies
- Build parallel algorithm code with GCC and TBB, and with Apple clang
- Prevent data races in the functions passed to parallel algorithms
- Compare the timings of execution policies within one toolchain, with the load they ran under
Before you start
What you’ll learn · Before you start
What you will learn
- Run standard algorithms in parallel with the four execution policies
- Build parallel algorithm code with GCC and TBB, and with Apple clang
- Prevent data races in the functions passed to parallel algorithms
- Compare the timings of execution policies within one toolchain, with the load they ran under
Before you start
On this page
Adding std::execution::par to a std::sort of 10 million integers cut its time from 1,463 ms to 605 ms with
Apple clang 21, and gained nothing with GCC 16, whose library ran the call on a single thread. The C++ parallel
algorithms are the familiar algorithms called with such a policy. std::sort, std::for_each,
std::transform_reduce and most other algorithms of <algorithm> and <numeric> accept one of the
execution policy: An object of <execution>, such as std::execution::par, passed as the first argument of a standard algorithm to say which kinds of concurrency it may use: other threads, interleaved calls on one thread, both or neither. It permits parallelism; it does not force it. of <execution>: seq, par, par_unseq and, since C++20,
unseq.
A policy is a permission, not a command. The library may still run everything on the calling thread, and the
functions you pass must be safe to run at the same time as each other. GCC’s libstdc++ runs par on the TBB library
and needs -ltbb, and without TBB it quietly runs on one thread, while Apple clang’s libc++ needs
-fexperimental-library and runs the work on Apple’s libdispatch.
A policy permits threads, interleaving, both or neither
Execution policies tell an algorithm which kinds of concurrency it may use. The four differ in two permissions: whether the calls may run on other threads, and whether calls on one thread may be interleaved with each other, which is what vector instructions need:
| Policy | Several threads | Interleaved calls |
|---|---|---|
seq, C++17 |
no | no |
par, C++17 |
yes | no |
par_unseq, C++17 |
yes | yes |
unseq, C++20 |
no | yes |
seqruns the calls one after another on the calling thread, like the algorithm without a policy.parmay spread the calls over several threads, so they must not race with each other, but they may take a lock.par_unseqmay also interleave calls on one thread, so the function must not lock a mutex or wait for another call.unseqinterleaves calls on the calling thread only: vector instructions without extra threads.
Locks are therefore allowed with seq and par only.
Two rules hold whatever the policy. With par or par_unseq, two calls that access the same memory, at least one of
them writing, without synchronisation, are a
Two accesses to the same memory from different threads, at least one of them a write, with no synchronisation between them. In C++ a data race is undefined behaviour: not merely a wrong result, but no guarantee about the program at all.,
which is undefined behaviour: What a program does when it breaks a rule for which the C++ standard sets no requirements, such as reading past the end of an array. The compiler may assume it never happens, so the result can change with the compiler and the optimisation level. More in “Object lifetime and undefined behaviour in C++”. And with any policy, an exception that leaves one
of the calls ends the program through std::terminate: The function C++ calls when exception handling cannot go on, for example when no handler matches a throw or an exception tries to leave a noexcept function. By default it calls std::abort, which ends the program with SIGABRT. More in “C++ exceptions: throw, catch and stack unwinding”, instead of reaching your
catch. Answer three questions about your function, and the table rules out the policies it may not use:
Answer the questions above: the table then marks what fits your case and says why the rest does not.
| Policy | Other threads | Interleaved calls | Function may lock | Unsynchronised shared writes |
|---|---|---|---|---|
| std::execution::seq | Poor no: every call on the calling thread | Poor no: one call after another | Good yes | Good allowed: calls never overlap |
| std::execution::par | Good yes: calls may spread over threads | Poor no: calls on one thread stay in order | Good yes, if they cannot deadlock | Poor a data race: undefined behaviour |
| std::execution::par_unseq | Good yes: calls may spread over threads | Good yes: calls on one thread may interleave | Poor no: interleaved calls can deadlock | Poor a data race: undefined behaviour |
| std::execution::unseq | Poor no: the calling thread only (C++20) | Good yes: calls may interleave | Poor no: interleaved calls can deadlock | Poor unsequenced writes: undefined behaviour |
How the answers decide
- “Does the function lock a mutex or wait for another call?” Yes, it locks or waits: rules out std::execution::par_unseq and std::execution::unseq. These policies may interleave calls on one thread, so one call could wait for a lock that another call on the same thread holds.
- “Do the calls write the same memory without synchronisation, such as one shared counter?” Yes, they share it: rules out std::execution::par, std::execution::par_unseq and std::execution::unseq. Calls that may overlap or interleave turn those writes into a data race or unsequenced writes, undefined behaviour either way; only seq runs one call at a time.
- “Can the function throw an exception?” Yes, it may throw: adds a caveat to std::execution::seq, std::execution::par, std::execution::par_unseq and std::execution::unseq. An exception that leaves a call ends the program through std::terminate under every policy, instead of reaching your catch.
- “Does the function lock a mutex or wait for another call?” No, it never waits and “Do the calls write the same memory without synchronisation, such as one shared counter?” No, each call writes its own element: Independent calls may use any policy; par_unseq permits the most, threads and interleaving together, and the library still decides what it uses.
Checkpoint
Check: What each execution policy permits
Without TBB, GCC runs par on one thread and says nothing
Where a call with std::execution::par ends up depends on the toolchain:
Where a call with std::execution::par ends up on each toolchain
Text description of the diagram
The figure starts from the call std::sort(std::execution::par, ...) and shows what each toolchain does with it.
GCC 16 with libstdc++: 1. If the headers of TBB are found and the program is linked with -ltbb, the calls run on TBB's worker threads. 2. If TBB is not found, libstdc++ uses its serial backend, and every call runs on one thread, without any warning.
Apple clang 21 with libc++: 1. Without -fexperimental-library, the program does not compile, because std::execution::par does not exist. 2. With -fexperimental-library, the calls run on the worker threads of libdispatch, Apple's system thread pool.
This program asks each library which backend runs its parallel algorithms, through macros that are the libraries’ own
internal names rather than standard ones, and counts the threads that ran the calls of one for_each over a million
elements:
// What runs the parallel algorithms of this standard library, and how many threads one parallel for_each used.
// The backend macros are each library's own internal names, not standard ones; the thread count is measured.
#include <version>
#include <algorithm>
#include <execution>
#include <print>
#include <thread>
#include <vector>
int main() {
#if defined(_PSTL_PAR_BACKEND_TBB)
std::println("libstdc++, backend: Intel TBB");
#elif defined(_PSTL_PAR_BACKEND_SERIAL)
std::println("libstdc++, backend: serial (TBB was not found)");
#elif defined(_LIBCPP_PSTL_BACKEND_LIBDISPATCH)
std::println("libc++, backend: libdispatch");
#elif defined(_LIBCPP_PSTL_BACKEND_STD_THREAD)
std::println("libc++, backend: std::thread");
#elif defined(_LIBCPP_PSTL_BACKEND_SERIAL)
std::println("libc++, backend: serial");
#endif
#ifdef __cpp_lib_parallel_algorithm
std::println("__cpp_lib_parallel_algorithm is {}", __cpp_lib_parallel_algorithm);
#else
std::println("__cpp_lib_parallel_algorithm is not defined");
#endif
// Each call records the thread that ran it in its own element, so no two calls write the same memory.
std::vector<std::thread::id> ran_on(1'000'000);
std::for_each(std::execution::par, ran_on.begin(), ran_on.end(),
[](std::thread::id& slot) { slot = std::this_thread::get_id(); });
std::ranges::sort(ran_on);
const auto threads = std::ranges::distance(ran_on.begin(), std::ranges::unique(ran_on).begin());
std::println("threads that ran the calls: {}", threads);
} from session import run
# GCC 16 without TBB, then Apple clang 21 without and with -fexperimental-library.
run("""
g++-16 -std=c++23 -O2 backend.cpp -o backend && ./backend
clang++ -std=c++23 -O2 backend.cpp -o backend 2>&1 | grep 'error:'
clang++ -std=c++23 -O2 -fexperimental-library backend.cpp -o backend && ./backend
""") Output
$ g++-16 -std=c++23 -O2 backend.cpp -o backend && ./backend libstdc++, backend: serial (TBB was not found) __cpp_lib_parallel_algorithm is 201603 threads that ran the calls: 1 $ clang++ -std=c++23 -O2 backend.cpp -o backend 2>&1 | grep 'error:' backend.cpp:29:35: error: no member named 'par' in namespace 'std::execution' $ clang++ -std=c++23 -O2 -fexperimental-library backend.cpp -o backend && ./backend libc++, backend: libdispatch __cpp_lib_parallel_algorithm is not defined threads that ran the calls: 6
This output changes from run to run: libdispatch decides at run time how many of its threads take part, so the last count changes from run to run.
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 backend_session.py
GCC 16 compiled the file, defined __cpp_lib_parallel_algorithm, and ran every call on one thread. Without the
headers of TBB, libstdc++ falls back to its serial backend, and neither the compiler nor the linker says so. The
libstdc++ manual states the dependency: the parallel
algorithms need TBB 2018 or newer, linked with -ltbb. Today that is oneTBB, the libtbb-dev package on Debian and
Ubuntu and the tbb formula of Homebrew on macOS.
Apple clang 21 rejected std::execution::par until -fexperimental-library was given, because libc++ still treats its
parallel algorithms as experimental, and with the flag it ran the calls on 6 threads of libdispatch, Apple’s
system thread pool. It defines no feature-test macro for them, so #ifdef __cpp_lib_parallel_algorithm says no on
the toolchain that runs in parallel and yes on the one that does not. Count threads, as this program does, when you
need to know: the C++ parallel algorithms give no sign of their own when they run on one thread. Apple’s linker may
also warn that libc++experimental.a “was built for newer macOS version” than the
program; the warning is harmless, and the sessions on this page leave it out.
Key idea
A policy only permits parallelism: count the threads that ran the calls, because a toolchain without its backend runs on one thread without a word.
Checkpoint
Check: What runs par on each toolchain
A parallel sort pays only where the library runs it in parallel
// Sorting 10 million random integers with each execution policy: the median of 3 runs of each, in milliseconds.
#include <algorithm>
#include <chrono>
#include <cstdlib> // getloadavg: provided by macOS and glibc, not by standard C++ or POSIX
#include <execution>
#include <print>
#include <random>
#include <thread>
#include <vector>
// Times one sort of a copy of data with the given policy, in milliseconds.
template <class Policy>
double sort_ms(const Policy& policy, const std::vector<int>& data) {
std::vector<int> v = data; // the same unsorted input every time
const auto start = std::chrono::steady_clock::now();
std::sort(policy, v.begin(), v.end());
const auto stop = std::chrono::steady_clock::now();
if (!std::ranges::is_sorted(v)) std::abort();
return std::chrono::duration<double, std::milli>(stop - start).count();
}
double median(std::vector<double> times) {
std::ranges::sort(times);
return times[times.size() / 2];
}
int main() {
std::mt19937 gen(42);
std::vector<int> data(10'000'000);
for (int& x : data) x = static_cast<int>(gen());
double load = 0;
getloadavg(&load, 1);
std::println("{} hardware threads, load average {:.0f}", std::thread::hardware_concurrency(), load);
// Three rounds, each timing the three policies in turn, so that a slower or faster moment of the computer
// affects all three alike.
std::vector<double> seq_ms, par_ms, par_unseq_ms;
for (int round = 0; round < 3; ++round) {
seq_ms.push_back(sort_ms(std::execution::seq, data));
par_ms.push_back(sort_ms(std::execution::par, data));
par_unseq_ms.push_back(sort_ms(std::execution::par_unseq, data));
}
const double seq = median(seq_ms), par = median(par_ms), par_unseq = median(par_unseq_ms);
std::println("seq {:5.0f} ms", seq);
std::println("par {:5.0f} ms {:.1f}x", par, seq / par);
std::println("par_unseq {:5.0f} ms {:.1f}x", par_unseq, seq / par_unseq);
} from session import run
run("""
g++-16 -std=c++23 -O2 sort_time.cpp -o sort_time && ./sort_time
clang++ -std=c++23 -O2 -fexperimental-library sort_time.cpp -o sort_time && ./sort_time
""") Output
$ g++-16 -std=c++23 -O2 sort_time.cpp -o sort_time && ./sort_time 18 hardware threads, load average 48 seq 3035 ms par 3637 ms 0.8x par_unseq 4178 ms 0.7x $ clang++ -std=c++23 -O2 -fexperimental-library sort_time.cpp -o sort_time && ./sort_time 18 hardware threads, load average 52 seq 1463 ms par 605 ms 2.4x par_unseq 672 ms 2.2x
This output changes from run to run: Times depend on what else the computer is doing, so only the shape of the output is fixed.
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 sort_time_session.py
GCC 16’s three policies took 3,035, 3,637 and 4,178 ms. Without TBB, the parallel sort of libstdc++’s serial backend
calls the same sequential std::sort, so the three lines measure one algorithm three times, and their differences
are not parallel work. Apple clang’s par sorted the same 10 million integers 2.4 times faster than its seq, and
par_unseq 2.2 times faster, at a load average of 52: other programs wanted more threads than the machine’s 18
hardware threads, so this speed-up is what a busy machine gives, not the best case. The libraries also differ
before any policy is involved: libc++’s sequential sort took less than half the time of libstdc++’s, so compare
policies within one toolchain, never across two.
Checkpoint
Check: Timing a parallel sort
Practise: policies, backends and timings
Try the policies, the two backends and the sort timings, one question at a time; every choice tells you why.
Practice that adapts to you
Practise this lesson
10 questions about 9 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
Data races and exceptions in element functions, reproduced Pro: opens with a Pro, Premium or Ultimate pass
Most bugs in parallel algorithm code come from the function passed to the algorithm, not from the algorithm itself. This part reproduces the two classic ones, a shared counter and an exception, and shows the fixes and the tool that finds the first.
In this part:
- A shared counter, counted wrong, and two ways to count right
- Reading the ThreadSanitizer report
- An exception under any policy ends the program
5 runnable examples (C++, Python) · about 6 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
When par pays, measured: input size, work per element and cores Pro: opens with a Pro, Premium or Ultimate pass
A parallel algorithm pays only when each thread gets enough work to outweigh the cost of starting and joining it. This part measures where that happens for light and heavy work on this 18-thread machine, and turns the results into rules of thumb with numbers.
In this part:
- Light and heavy work at five input sizes
- Worked numbers: what limits the speed-up
1 diagram · 2 runnable examples (C++, Python) · about 6 minutes
Opening this part with your pass…Pro part. It opens with the same pass as the part above.
The histogram exercise, four ways, measured and checked Pro: opens with a Pro, Premium or Ultimate pass
A histogram is the smallest program that shows every trade-off of parallel algorithms at once: shared state, atomics, contention and reductions. This part solves the exercise four ways, times each version and checks the correct ones with ThreadSanitizer.
In this part:
- Your turn: parallelise a histogram
- Four versions
- Measured, and checked with ThreadSanitizer
2 runnable examples (C++, Python) · about 4 minutes
Opening this part with your pass…Pro part. It opens with the same pass as the part above.
Interview questions
-
Fresher to mid · Warm-up
What is the difference between std::execution::par and std::execution::par_unseq, and when may you use each?
Both let a standard algorithm run its calls on several threads. With par, the calls on any one thread still run one after another, so the function may take a lock, as long as it avoids data races and deadlocks. With par_unseq, the library may also interleave several calls on one thread, as vector instructions do, so the function must not lock a mutex or wait for another call: one interleaved call could wait for a lock that another holds on the same thread. Use par for work that needs synchronisation, and par_unseq for independent arithmetic on each element, such as a transform over numbers. Both permit parallelism without forcing it, and with either one, an exception that leaves the function ends the program with std::terminate.
-
Mid to senior
You changed a hot std::sort to std::execution::par. A colleague's Mac build sorts 2.4 times faster, but the Linux service built with GCC shows no gain at all. What do you check, in what order, and how do you stop it happening again?
-
Mid to senior
A parallel for_each builds a histogram by incrementing counters in a shared array, and the totals come out too low. Fix it, and compare the possible fixes for correctness and speed on an 18-core machine.
-
Mid to senior
A batch job validates records with std::for_each(std::execution::par, …), and the validator throws on a bad record. In testing, the job sometimes dies in std::terminate instead of reporting the record. Explain the behaviour and redesign the error handling.
Key takeaways
- An execution policy (
seq,par,par_unseq,unseq) is the first argument that lets a standard algorithm run in parallel, vectorised, or both; it permits, it does not force. - With
parandpar_unseq, the function you pass must not race on shared data; withpar_unseqandunseqit must not lock or wait either. - An exception that leaves an element function ends the program with
std::terminate, under every policy. - GCC’s libstdc++ needs TBB and
-ltbbfor real parallelism and silently runs on one thread without it, while Apple clang’s libc++ needs-fexperimental-library, so count the threads to know what you got. - Compare policies within one toolchain and report the machine’s load, because the two libraries’ sequential sorts already differ by a factor of two.
Terms in this lesson
- execution policy
- An object of <execution>, such as std::execution::par, passed as the first argument of a standard algorithm to say which kinds of concurrency it may use: other threads, interleaved calls on one thread, both or neither. It permits parallelism; it does not force it.
References
- Working Draft, Programming Languages: C++ (N4950), 22.12 Execution policies and 27.3 Parallel algorithms (ISO/IEC JTC1/SC22/WG21)
- P0024R2: The Parallelism TS Should be Standardized (ISO/IEC JTC1/SC22/WG21)
- P1001R2: Target Vectorization Policies from Parallelism V2 TS to C++20 (ISO/IEC JTC1/SC22/WG21)
- The GNU C++ Library Manual: Status (C++ 2017, note 3 on the Parallel Algorithms) (GNU Project)
- Using libc++: Enabling experimental C++ library features (LLVM Project)
- ThreadSanitizer (Clang documentation) (LLVM Project)
- Dispatch (Apple Developer documentation) (Apple)
- oneAPI Threading Building Blocks (oneTBB) (UXL Foundation)
- tbb (Homebrew formula) (Homebrew)
- libtbb-dev (Debian package) (Debian)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress