Parallel algorithms
C++17 gave the standard algorithms an execution policy. std::execution::par asks the library to run the algorithm on several threads, and the algorithm decides how to split the range and how many workers to use.
The policy is a permission, not a command: an implementation may run it sequentially and still be conforming. On this build the parallel algorithms of libstdc++ run on the platform's thread pool, and the lesson shows what they compute rather than how many cores they used.
The policy also has seq for the sequential form with the same interface, and unseq for a loop the compiler may vectorise without threads. A program can choose between them at run time by passing one of the three objects, which is how a build can turn parallelism off.
The algorithms also have a version that takes a policy as the first argument, so a loop over a container of structs becomes the same call with one more argument in front of the range.
for_each with par
The first argument of an algorithm with a policy is the policy itself. for_each(par, begin, end, f) calls f on every element, and the calls may happen on several threads at once.
The program triples 1000 ones and prints the sum of the elements and the value of the last one. The answer is 3000 and 3, and the sequential form of the same loop would give the same numbers.
The function must be safe to call on different elements at the same time. Two calls that touch the same object are a data race whether the algorithm splits the range or not, and the library has no way to detect it.
#include <algorithm>
#include <execution>
#include <iostream>
#include <numeric>
#include <vector>
int main()
{
std::vector<int> values(1000, 1);
std::for_each(std::execution::par, values.begin(), values.end(),
[](int& value) { value *= 3; });
std::cout << std::accumulate(values.begin(), values.end(), 0) << ' ';
std::cout << values.back() << '\n';
}
g++ -std=c++23 -Wall -Wextra foreach.cpp -o foreach_par
./foreach_par
3000 3
reduce instead of accumulate
std::accumulate is a sequential fold: it threads one value through the range, so it cannot be split. std::reduce allows the operation to be applied in any grouping, which is what a parallel implementation needs.
The program sums 1 to 1000 with par and prints 500500. The addition is associative here, so the grouping does not matter and the result is exact.
Floating point addition is not associative, and a par reduce may produce a slightly different last digit than a sequential sum. That is allowed by the standard, and the reason a numeric result that must be reproducible is computed sequentially or with a fixed grouping.
#include <execution>
#include <iostream>
#include <numeric>
#include <vector>
int main()
{
std::vector<int> values(1000);
std::iota(values.begin(), values.end(), 1);
int total = std::reduce(std::execution::par, values.begin(), values.end(), 0);
std::cout << total << '\n';
}
g++ -std=c++23 -Wall -Wextra reduce.cpp -o reduce_par
./reduce_par
500500
The same sum with threads
The manual version splits the vector into four ranges, gives each to a thread and adds the four partial sums at the end. It is the shape the library uses, written out, and it shows the two parts that a parallel algorithm hides: the split and the join.
The four threads sum a quarter each and main adds the results after the joins. The total is 500500, the same as the reduce, and no thread touches a partial sum of another.
This version also shows the cost that the policy hides: four thread objects, four joins and a vector of results. For 1000 elements the sequential loop is faster, which is the subject of lesson 118.
#include <iostream>
#include <numeric>
#include <thread>
#include <vector>
int main()
{
std::vector<int> values(1000);
std::iota(values.begin(), values.end(), 1);
std::vector<int> partial(4, 0);
std::vector<std::thread> threads;
for (int part = 0; part < 4; ++part) {
threads.emplace_back([&values, &partial, part] {
auto first = values.begin() + part * 250;
auto last = first + 250;
partial[part] = std::accumulate(first, last, 0);
});
}
for (auto& thread : threads) {
thread.join();
}
std::cout << partial[0] + partial[1] + partial[2] + partial[3] << '\n';
}
g++ -std=c++23 -Wall -Wextra -pthread manual.cpp -o manual
./manual
500500
The include the policy needs
The execution policies live in <execution>, a header of their own. Algorithm headers do not bring them in, so a program that writes std::execution::par after including only <algorithm> does not compile.
The program includes algorithm and vector and asks for par. The compiler reports that execution is not a member of std, and a note suggests the missing include only in some versions, so the message is worth recognising.
The fix is one line at the top. The same error appears for std::execution::seq and std::execution::unseq, because all three names come from the same header.
#include <algorithm>
#include <vector>
int main()
{
std::vector<int> values{1, 2, 3};
std::for_each(std::execution::par, values.begin(), values.end(), [](int) {});
}
g++ -std=c++23 -Wall -Wextra include.cpp -o include
include.cpp: In function 'int main()':
include.cpp:8:24: error: 'std::execution' has not been declared; did you mean 'std::exception'?
8 | std::for_each(std::execution::par, values.begin(), values.end(), [](int) {});
| ^~~~~~~~~
Exercises
- Time the sequential and the parallel for_each on 10 million elements and compare the results.
- Replace reduce with transform_reduce and compute the sum of the squares of 1 to 1000.
- Change the manual version to two threads and check that the total is unchanged.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does
std::execution::parask for?Answer
Permission to run the algorithm on several threads
The policy allows parallelism, and the implementation decides how much of it to use.
-
Does par guarantee a speedup?
Answer
No, the overhead can make a small range slower
Splitting and joining cost time, and a small or cheap loop can lose more than it gains.
-
Which function must a par algorithm's lambda be?
Answer
Safe to call on different elements at the same time
The implementation may call it concurrently, so a shared write without synchronisation is a data race.
-
What does this program print?
#include <algorithm> #include <execution> #include <iostream> #include <numeric> #include <vector> int main() { std::vector<int> values(1000, 1); std::for_each(std::execution::par, values.begin(), values.end(), [](int& value) { value *= 3; }); std::cout << std::accumulate(values.begin(), values.end(), 0) << ' ' << values.back(); }Answer
3000 3
Each of the 1000 ones becomes 3, so the sum is 3000 and the last element is 3.
-
What does this program print?
#include <execution> #include <iostream> #include <numeric> #include <vector> int main() { std::vector<int> values(1000); std::iota(values.begin(), values.end(), 1); std::cout << std::reduce(std::execution::par, values.begin(), values.end(), 0); }Answer
500500
Integer addition is associative, so the parallel reduce gives the exact sum of 1 to 1000.
-
What does the manual thread version print?
Answer
500500
The four partial sums cover the whole vector, and adding them gives the same total.
-
Why can
std::accumulatenot be parallelised?Answer
It folds the range sequentially, one value at a time
The fold is a chain, and reduce exists because it allows the operation to be regrouped.
-
Why can a par reduce of doubles differ from a sequential sum?
Answer
Floating point addition is not associative, and the grouping differs
The standard allows any grouping, and the last bits of a double sum depend on it.
-
What does the compiler answer when
<execution>is missing?Answer
That execution is not a member of std
The name of the namespace is unknown without the header, so the lookup fails.
-
Which header declares the execution policies?
Answer
<execution>The policies are in their own header, separate from the algorithms that accept them.
The code on this page was built with g++ 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container. The programs whose section shows a compiler error were compiled until that error and were not run.
Article author: Arthur Isaev