Parallel Algorithms & Execution Policies
Leverage the C++17 parallel STL to parallelize sorting, transformation, and reduction with execution policies. Understand when parallelism helps, Amdahl's law, and practical thread pool design.
Parallel STL — Easy Parallelism
C++17 added execution policies to most
This is the easiest way to add parallelism to C++: take your existing std::sort, std::transform, or std::for_each call, prepend std::execution::par, and let the implementation do the rest. Of course, you must ensure your operations are safe for concurrent execution (no data races in predicates, no shared mutable state).
Execution Policies Explained
There are three standard execution policies defined in
#include <algorithm>
#include <execution>
#include <vector>
#include <iostream>
#include <chrono>
int main() {
std::vector<int> data(10'000'000);
std::iota(data.begin(), data.end(), 0);
// Sequential — same as no policy
auto t1 = std::chrono::high_resolution_clock::now();
std::sort(std::execution::seq, data.begin(), data.end(),
std::greater<>{});
auto t2 = std::chrono::high_resolution_clock::now();
// Parallel — may use multiple threads
std::sort(std::execution::par, data.begin(), data.end());
auto t3 = std::chrono::high_resolution_clock::now();
// Parallel + vectorized — threads AND SIMD
std::sort(std::execution::par_unseq, data.begin(), data.end(),
std::greater<>{});
auto t4 = std::chrono::high_resolution_clock::now();
auto ms = [](auto a, auto b) {
return std::chrono::duration_cast<std::chrono::milliseconds>(b - a).count();
};
std::cout << "seq: " << ms(t1, t2) << "ms\n";
std::cout << "par: " << ms(t2, t3) << "ms\n";
std::cout << "par_unseq: " << ms(t3, t4) << "ms\n";
return 0;
}std::reduce vs std::accumulate
std::accumulate processes elements strictly left-to-right and cannot be parallelized. std::reduce (C++17) allows the implementation to process elements in any order and combine partial results — enabling parallel execution. The operation must be associative and commutative for reduce to produce correct results.
#include <numeric>
#include <execution>
#include <vector>
#include <iostream>
int main() {
std::vector<double> data(1'000'000, 1.0);
// Sequential accumulate — always left-to-right
double sum1 = std::accumulate(data.begin(), data.end(), 0.0);
// Parallel reduce — may split and combine in any order
double sum2 = std::reduce(std::execution::par,
data.begin(), data.end(), 0.0);
// Transform-reduce: parallel dot product
std::vector<double> a(1'000'000, 2.0);
std::vector<double> b(1'000'000, 3.0);
double dot = std::transform_reduce(
std::execution::par,
a.begin(), a.end(), b.begin(),
0.0); // default: multiply + add
std::cout << "accumulate: " << sum1 << "\n";
std::cout << "reduce: " << sum2 << "\n";
std::cout << "dot product: " << dot << "\n"; // 6'000'000
return 0;
}When using parallel execution policies, the callable (predicate, transform function, reduction operator) you pass to the algorithm may be invoked concurrently from multiple threads. If your callable accesses shared mutable state, you have a data race:
``cpp``
int count = 0;
std::for_each(std::execution::par, v.begin(), v.end(),
[&count](int x) {
if (x > 0) ++count; // DATA RACE! Multiple threads increment count
});
Use std::atomic, thread-local accumulators, or better yet, use std::reduce / std::count_if which handle the aggregation safely.
Amdahl's Law — When Parallelism Helps
Amdahl's law states that the maximum speedup from parallelism is limited by the sequential fraction of your program. If 10% of the work must be done sequentially, then even with infinite threads, the maximum speedup is 10x.
Speedup = 1 / (S + P/N), where S is the sequential fraction, P is the parallel fraction, and N is the number of threads.
Parallelism also has overhead: thread creation, synchronization, cache contention, and false sharing. For small data sets, the overhead can exceed the benefit. Rules of thumb:
- Sort: Parallel std::sort typically helps above ~100K elements.
- Transform/for_each: Benefits above ~10K elements with non-trivial work per element.
- Reduce: Benefits above ~100K elements or with expensive operations.
- Always measure — profile with and without std::execution::par.
Practical Thread Pool Overview
The C++ standard does not provide a thread pool (as of C++23), but the pattern is straightforward: a fixed set of worker threads pulls tasks from a shared queue. Here is a minimal sketch.
#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>
#include <functional>
#include <vector>
class ThreadPool {
std::vector<std::thread> workers_;
std::queue<std::function<void()>> tasks_;
std::mutex mtx_;
std::condition_variable cv_;
bool stop_ = false;
public:
explicit ThreadPool(size_t n) {
for (size_t i = 0; i < n; ++i) {
workers_.emplace_back([this] {
while (true) {
std::function<void()> task;
{
std::unique_lock lock(mtx_);
cv_.wait(lock, [this] {
return stop_ || !tasks_.empty();
});
if (stop_ && tasks_.empty()) return;
task = std::move(tasks_.front());
tasks_.pop();
}
task(); // run outside the lock
}
});
}
}
void enqueue(std::function<void()> task) {
{
std::lock_guard lock(mtx_);
tasks_.push(std::move(task));
}
cv_.notify_one();
}
~ThreadPool() {
{
std::lock_guard lock(mtx_);
stop_ = true;
}
cv_.notify_all();
for (auto& w : workers_) w.join();
}
};
int main() {
ThreadPool pool(4);
for (int i = 0; i < 20; ++i) {
pool.enqueue([i] {
std::cout << "Task " << i << " on thread "
<< std::this_thread::get_id() << "\n";
});
}
// pool destructor waits for all tasks
return 0;
}Prefer std::execution::par over hand-rolled parallelism for standard algorithms — the implementation knows your hardware. Always verify that your callable is free of data races and side effects. Use std::reduce instead of std::accumulate when you need parallelism. Benchmark with realistic data sizes; for small inputs, sequential may be faster. Remember that par_unseq forbids calling anything that acquires a lock (including memory allocation on some platforms).
- C++17 execution policies (
seq,par,par_unseq) add parallelism to standard algorithms with minimal code changes std::reduceis the parallel-friendly replacement forstd::accumulate— your operation must be associative and commutative- Amdahl's law limits speedup: the sequential portion of your code becomes the bottleneck
- Parallel algorithms have overhead — only beneficial for sufficiently large data sets or expensive per-element work
- Always ensure callables passed to parallel algorithms are free of data races
- Thread pools reuse a fixed set of threads to avoid the cost of thread creation for many small tasks
Quiz — Test Your Knowledge
(15 XP)1. Why can't `std::accumulate` be used with execution policies?
2. What constraint does `std::execution::par_unseq` place on the callable?
3. According to Amdahl's law, what is the maximum speedup if 20% of a program is sequential?