![\"timelineParallelSTL\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2021\/07\/timelineParallelSTL.png\")
<\/p>\nGCC supports my favorite C++17 feature: the Standard Template Library (STL) parallel algorithms. I recognized this a few days ago, and I’m happy to write a post about it and share my enthusiasm.<\/p>\n
<\/p>\n
<\/p>\n
<\/p>\n
The Microsoft compiler has supported parallel algorithms since its beginning but sadly, neither GCC nor Clang. I have to be precise; GCC 9 allows you to use parallel algorithms. Before I show you examples with performance numbers in my next post, I want to write about the parallel algorithms of the STL and give you the necessary information.<\/p>\n
The Standard Template Library has more than 100 algorithms for searching, counting, and manipulating ranges and their elements. With C++17, 69 get new overloads, and new ones are added. The overloaded and new algorithms can be invoked with a so-called execution policy. Using an execution policy, you can specify whether the algorithm should run sequentially, in parallel, or parallel with vectorization. For using the execution policy, you have to include the header <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n The expression Here are the assembler instructions. Each addition is done sequentially.<\/p>\n By using the highest optimization level, -O3, special registers such as An overload of an algorithm without an execution policy and an overload of an algorithm with a sequential execution policy <\/p>\n If an exception occurs during the usage of an algorithm with an execution policy, With C++17, 69 of the STL algorithms got new overloads, and new algorithms were added.<\/p>\n Here are the 69 algorithms with parallelized versions.<\/p>\n The new algorithm in C++17, which are designed for parallel execution, are in the Admittedly this description is not easy to digest, but if you already know You may wonder why we need While <\/p>\n <\/p>\n <\/p>\n The two following graphs show the different processing strategies of <\/p>\n The associativity of the callable allows the<execution><\/code>.<\/p>\nExecution Policy<\/h3>\n
\nThe C++17 standard defines three execution policies:<\/div>\n\n
std::execution::sequenced_policy<\/code><\/li>\nstd::execution::parallel_policy<\/code><\/li>\nstd::execution::parallel_unsequenced_policy<\/code><\/li>\n<\/ul>\nThe corresponding policy tag specifies whether a program should run sequentially, in parallel, or in parallel with vectorization.<\/div>\n\n
std::execution::seq<\/code>: runs the program sequentially<\/li>\n<\/ul>\n\n
std::execution::par<\/code>: runs the program in parallel on multiple threads<\/li>\n<\/ul>\n\n
std::execution::par_unseq<\/code>: runs the program in parallel on multiple threads and allows the interleaving of individual loops; permits a vectorized version with SIMD<\/a> (S<\/strong>ingle I<\/strong>nstruction M<\/strong>ultiple D<\/strong>ata).<\/li>\n<\/ul>\nThe usage of the execution policy std::execution::par<\/code> or std::execution::par_unseq<\/code> allows the algorithm to run parallel or parallel and vectorized. This policy is a permission and not a requirement.<\/code><\/code><\/div>\nThe following code snippet applies to all execution policies.<\/div>\n\nstd::<\/span>vector<<\/span>int<\/span>><\/span> v =<\/span> {1<\/span>, 2<\/span>, 3<\/span>, 4<\/span>, 5<\/span>, 6<\/span>, 7<\/span>, 8<\/span>, 9<\/span>};\r\n\r\n\/\/ standard sequential sort <\/span>\r\nstd::<\/span>sort(v.begin(), v.end()); \/\/ (1)<\/span>\r\n\r\n\/\/ sequential execution<\/span>\r\nstd::<\/span>sort(std::<\/span>execution::<\/span>seq, v.begin(), v.end()); \/\/ (2)<\/span>\r\n\r\n\/\/ permitting parallel execution<\/span>\r\nstd::<\/span>sort(std::<\/span>execution::<\/span>par, v.begin(), v.end()); \/\/ (3)<\/span>\r\n\r\n\/\/ permitting parallel and vectorized execution<\/span>\r\nstd::<\/span>sort(std::<\/span>execution::<\/span>par_unseq, v.begin(), v.end()); \/\/ (4)\r\n<\/span><\/pre>\n<\/div>\nThe example shows that you can still use the classic variant of std::sort<\/code> (4). Besides, in C++17, you can specify explicitly whether the sequential (2), parallel (3), or parallel and vectorized (4) version should be used.<\/div>\n <\/div>\n<\/div>\n<\/div>\nParallel and Vectorized Execution<\/h3>\n
Whether an algorithm runs in a parallel and vectorized way depends on many factors. For example, it depends on whether the CPU and the operating system support SIMD instructions. It also depends on the compiler and the optimization level you used to translate your code.<\/div>\nThe following example shows a simple loop for filling a vector.<\/div>\n <\/div>\n\nconst<\/span> int<\/span> SIZE =<\/span> 8<\/span>;\r\n \r\nint<\/span> vec[] =<\/span> {1<\/span>, 2<\/span>, 3<\/span>, 4<\/span>, 5<\/span>, 6<\/span>, 7<\/span>, 8<\/span>};\r\nint<\/span> res[] =<\/span> {0<\/span>, 0<\/span>, 0<\/span>, 0<\/span>, 0<\/span>, 0<\/span>, 0<\/span>, 0<\/span>};\r\n \r\nint<\/span> main<\/span>() {\r\n for<\/span> (int<\/span> i =<\/span> 0<\/span>; i <<\/span> SIZE; ++<\/span>i) {\r\n res[i] =<\/span> vec[i]+<\/span>5<\/span>;\r\n }\r\n}\r\n<\/pre>\n<\/div>\n res[i] = vec[i] + 5<\/code> is the crucial line in this small example. Thanks to Compiler Explorer<\/a>, we can look closer at the assembler instructions generated by clang 3.6.<\/p>\nWithout Optimization<\/h4>\n
![\"seq\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/seq.png\")
<\/p>\nWith Maximum Optimization<\/h4>\n
xmm0<\/code> are used that can hold 128 bits or 4 ints. This special register means that the addition takes place in parallel on four vector elements.<\/p>\n![\"vec\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/vec.png\")
<\/p>\nstd::execution::seq<\/code> differ in one aspect: exceptions.<\/p>\nExceptions<\/h3>\n
std::terminate<\/code><\/a> it is called. std::terminate<\/code> calls the installedstd::terminate_handler<\/code><\/a>. The consequence is that per default std::abort<\/code><\/a> is called, which causes abnormal program termination. The handling of exceptions is the difference between an algorithm\u2019s invocation without an execution policy and an algorithm with a sequential std::execution::seq<\/code> execution policy. The invocation of the algorithm without an execution policy propagates the exception, and, therefore, the exception can be handled.<\/p>\nAlgorithms<\/h3>\n
![\"allAlgorithm\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2021\/07\/allAlgorithm.png\")
<\/h4>\nThe New Algorithms<\/h4>\n
std<\/code> namespace and need the header <numeric><\/code>.<\/p>\n\n
std::exclusive_scan: <\/code>Applies from the left a binary callable up to the range’s ith (exclusive) element. The left argument of the callable is the previous result\u2014stores intermediate results.<\/li>\nstd::inclusive_scan<\/code>: Applies from the left a binary callable up to the range’s ith (inclusive) element. The left argument of the callable is the previous result\u2014stores intermediate results.<\/li>\nstd::transform_exclusive_scan<\/code>: First applies a unary callable to the range and then applies std::exclusive_scan<\/code>.<\/li>\nstd::transform_inclusive_scan<\/code>: First applies a unary callable to the range and then applies std::inclusive_scan<\/code>.<\/li>\nstd::reduce<\/code>: Applies a binary callable to the range.<\/li>\nstd::transform_reduce<\/code>: Applies first a unary callable to one or a binary callable to two ranges and then std::reduce<\/code> to the resulting range.<\/li>\n<\/ul>\nstd::accumulat<\/code>e and std::partial_sum<\/code>, the reduce and scan variations should be pretty familiar. std::reduce<\/code> is the parallel pendant to std::accumulate and scan the parallel pendant to partial_sum. The parallel execution is the reason that std::reduce<\/code> needs an associative and commutative callable. The corresponding statement holds for the scan variations contrary to the partial_sum variations. To get the full details, visit cppreferenc.com\/algorithm<\/a>.<\/p>\nstd::reduce<\/code> for parallel execution because we already have std::accumulate<\/code>. The reason is that std::accumulate<\/code> it processes its elements in an order that cannot be parallelized.<\/p>\nstd::accumulate<\/code> versus std::reduce<\/code><\/h4>\n std::accumulate<\/code> processes its elements from left to right, std::reduce<\/code> and does it in an arbitrary order. Let me start with a small code snippet using std::accumulate<\/code> and std::reduce<\/code>. The callable is the lambda function [](int a, int b){ return a * b; }<\/code>.<\/p>\n\nstd::<\/span>vector<<\/span>int<\/span>><\/span> v{1<\/span>, 2<\/span>, 3<\/span>, 4<\/span>};\r\n\r\nstd::<\/span>accumulate(v.begin(), v.end(), 1<\/span>, [](int<\/span> a, int<\/span> b){ return<\/span> a *<\/span> b; });\r\nstd::<\/span>reduce(std::<\/span>execution::<\/span>par, v.begin(), v.end(), 1<\/span> , [](int<\/span> a, int<\/span> b){ return<\/span> a *<\/span> b; });\r\n<\/pre>\n<\/div>\n std::accumulate<\/code> and std::reduce<\/code>.<\/p>\n\n
std::accumulate<\/code> starts at the left and successively applies the binary operator.<\/li>\n<\/ul>\n![\"AccumulateNew\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2021\/07\/AccumulateNew.png\")
<\/p>\n\n
std::reduce<\/code> applies the binary operator in a non-deterministic way.<\/li>\n<\/ul>\n![\"ReduceNew\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2021\/07\/ReduceNew.png\")
<\/p>\n std::reduce<\/code> algorithm to apply the reduction step on arbitrary adjacents pairs of elements. The intermediate results can be computed in an arbitrary order thanks to commutativity.<\/p>\nWhat’s next?<\/h2>\n