{"id":5195,"date":"2017-02-19T09:13:48","date_gmt":"2017-02-19T09:13:48","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/parallel-algorithm-of-the-standard-template-library\/"},"modified":"2017-02-19T09:13:48","modified_gmt":"2017-02-19T09:13:48","slug":"parallel-algorithm-of-the-standard-template-library","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/parallel-algorithm-of-the-standard-template-library\/","title":{"rendered":"Parallel Algorithms of the Standard Template Library"},"content":{"rendered":"

The idea is quite simple. The Standard Template has more than 100 algorithms for searching, counting, and manipulating ranges and their elements. With C++17, 69 are overloaded, and a few new ones are added. The overloaded and new algorithms can be invoked with a so-called execution policy. Using the execution policy, you can specify whether the algorithm should run sequentially, parallel, or parallel and vectorized.<\/p>\n

 <\/p>\n

<\/p>\n

A first example<\/h2>\n

Vectorization stands for the SIMD<\/a> (S<\/strong>ingle I<\/strong>nstruction, M<\/strong>ultiple D<\/strong>ata) extensions of the instruction set of a modern processor. SIMD enables your processor to execute one operation in parallel on several data.<\/p>\n

The policy tag chooses which overloaded variant of an algorithm is used. How does that work?<\/p>\n

\n\n\n\n
\n
 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13<\/pre>\n<\/td>\n
\n
vector<int<\/span>> v = ...\r\n\r\n\/\/ standard sequential sort<\/span>\r\nstd::sort(v.begin(), v.end());\r\n\r\n\/\/ sequential execution<\/span>\r\nstd::sort(std::parallel::seq, v.begin(), v.end());\r\n\r\n\/\/ permitting parallel execution<\/span>\r\nstd::sort(std::parallel::par, v.begin(), v.end());\r\n\r\n\/\/ permitting parallel and vectorized execution<\/span>\r\nstd::sort(std::parallel::par_unseq, v.begin(), v.end());\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
The example shows you can even use the classic variant of std::sort<\/span> (line 4). On contrary, you explicitly specify in C++17 whether the sequential (line 7), parallel (line 10) or parallel and vectorized (line 13) version is used.<\/p>\n
You have to keep two points in mind.<\/p>\n<\/p>\n
Two special points<\/h2>\n
On the one hand, an algorithm will not always be performed parallel and vectorized if you use the execution policy <\/em>std::parallel<\/span>::par_unseq.<\/span> On the other hand, you, as the user, are responsible for correctly using the algorithm.<\/p>\n
Parallel and vectorized execution<\/h3>\n
Whether an algorithm runs in a parallel and vectorized way depends on many points. It depends if the CPU and the operating system support SIMD instructions. Additionally, it’s a question of the compiler and the optimization level you used to translate your code.<\/p>\n
 <\/p>\n
\n\n\n\n
\n
 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10<\/pre>\n<\/td>\n
\n
const<\/span> int<\/span> SIZE= 8;\r\n\r\nint<\/span> vec[]={1,2,3,4,5,6,7,8};\r\nint<\/span> res[SIZE]={0,};\r\n\r\nint<\/span> main(){\r\n  for<\/span> (int<\/span> i= 0; i < SIZE; ++i) {\r\n    res[i]= vec[i]+5;\r\n  }\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
Line 8 is the key line in the small program. Thanks to the compiler explorer https:\/\/godbolt.org\/ <\/a>, it is quite easy to generate the assembler instructions for clang 3.6 with and without maximum optimization (-03).  <\/a><\/p>\n
Without Optimisation<\/h4>\n
Although my time fiddling with assembler instruction is long gone, it’s evident that all is done sequentially.<\/p>\n
\"seq\"<\/p>\n
With maximum optimization<\/h4>\n
I get instructions that run in parallel on several data by using maximum optimization.<\/p>\n
\"vec\"<\/p>\n
The move operation (movdqa)<\/span> and the add operation (paddd) <\/span>use the special registers xmm0<\/span> and xmm1.<\/span> Both registers are so-called SSE registers and have 128 Bits. SSE<\/a> stands f\u00fcr S<\/strong>treaming S<\/strong>IMD E<\/strong>xtensions. <\/p>\n
Hazards of data races and deadlocks<\/h3>\n
The algorithm does not automatically protect from data races<\/a> and deadlocks<\/a>. Example?<\/p>\n
 <\/p>\n
\n
int<\/span> numComp= 0;\r\n\r\nstd::vector<int<\/span>> vec={1,3,8,9,10};\r\n\r\nstd::sort(std::parallel::vec, vec.begin(), vec.end(), \r\n         [&numComp](int<\/span> fir, int<\/span> sec){ numComp++; return<\/span> fir < sec; });\r\n         \r\n<\/pre>\n<\/div>\n
 <\/p>\n
The small code snippet has a data race. numComp<\/span> counts the number of operations. That means, in particular, that numComp<\/span> is modified in the lambda function; therefore, the code snippet has a data race. To be well-defined, numComp<\/span> has to be an atomic variable.<\/p>\n
The static versus dynamic execution policy<\/h2>\n
Sorry to say, but the execution policy made it not in the C++17 standard. We have to wait for C++20.<\/em><\/strong><\/p>\n
Creating a thread is expensive; therefore, it makes no sense to sort a small container in a parallel (std::parallel::par<\/span>) or parallel and vectorised (std::parallel:par_unseq<\/span>) fashion. The administrative overhead of dealing with threads will outweigh the benefit of parallelization. It even gets worse if you use a divide and conquer algorithm<\/a> such as quicksort.<\/p>\n
 <\/p>\n
\n\n\n\n
\n
 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11<\/pre>\n<\/td>\n
\n
template<\/span> <class<\/span> ForwardIt<\/span>>\r\nvoid<\/span> quicksort(ForwardIt first, ForwardIt last){\r\n  if<\/span>(first == last) return<\/span>;\r\n  auto<\/span> pivot = *std::next(first, std::distance(first,last)\/2);\r\n  ForwardIt middle1 = std::partition(std::parallel::par, first, last, \r\n                      [pivot](const<\/span> auto<\/span>& em){ return<\/span> em < pivot; });\r\n  ForwardIt middle2 = std::partition(std::parallel::par, middle1, last, \r\n                      [pivot](const<\/span> auto<\/span>& em){ return<\/span> !(pivot < em); });\r\n  quicksort(first, middle1);\r\n  quicksort(middle2, last);\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
The issue is that the number of threads is too big for your system. To solve this issue, C++17 supports a dynamic execution policy.<\/p>\n
\n\n\n\n
\n
 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18<\/pre>\n<\/td>\n
\n
std::size_t<\/span> threshold= ...;  \/\/ some value <\/span>\r\n\r\ntemplate<\/span> <class<\/span> ForwardIt<\/span>>\r\nvoid<\/span> quicksort(ForwardIt first, ForwardIt last){\r\n  if<\/span>(first == last) return<\/span>;\r\n  std::size_t<\/span> distance= std::distance(first,last);\r\n  auto<\/span> pivot = *std::next(first, distance\/2);\r\n\r\n  std::parallel::execution_policy exec_pol= std::parallel::par;\r\n  if<\/span> ( distance < threshold ) exec_pol= std::parallel_execution::seq;\r\n\r\n  ForwardIt middle1 = std::partition(exec_pol, first, last, \r\n                      [pivot](const<\/span> auto<\/span>& em){ return<\/span> em < pivot; });\r\n  ForwardIt middle2 = std::partition(exec_pol, middle1, last, \r\n                      [pivot](const<\/span> auto<\/span>& em){ return<\/span> !(pivot < em); });\r\n  quicksort(first, middle1);\r\n  quicksort(middle2, last);\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
I use in lines 9 and 10 the dynamic execution policy. By default, quicksort will run in parallel (line 9). If the length of the range is smaller than a given threshold<\/span> (line 1), quicksort will run sequentially (line 10).<\/p>\n
All algorithms<\/h2>\n
69 of the algorithms of the STL support a parallel or a parallel and vectorized execution. Here they are.<\/p>\n
\"ParallelAlgorithmn\"<\/p>\n
In addition, we get eight new algorithms.<\/p>\n
New algorithms<\/h3>\n
The new variation of  std::for_each <\/span>and the new algorithms std::for_each_n, std::exclusive_scan, std::inclusive_scan, std::transfom_exclusive_scan<\/span> , std::transform_inclusive_scan, std::reduce<\/span> <\/span>and<\/span> std::transform_reduce<\/span> <\/span>are in the std<\/span> namespace. <\/span><\/p>\n
\n
std::for_each\r\nstd::for_each_n\r\nstd::exclusive_scan\r\nstd::inclusive_scan\r\nstd::transform_exclusive_scan\r\nstd::transform_inclusive_scan\r\nstd::reduce\r\nstd::transform_reduce
\r\n<\/pre>\n<\/div>\n
Let’s have closer look at std::transform_reduce.<\/span><\/p>\n
transform becomes map<\/h3>\n
The Haskell known function map<\/span> is called std::transform<\/span> in C++.  If that is not a broad hint. When substituting the name std::transform_reduce<\/span> <\/span>transform with map, I will get <\/span><\/span>std::map_reduce. <\/span>MapReduce <\/a>is the well-known parallel framework that maps each value to a new value in the first phase and reduces all values to the result in the second phase.
<\/span><\/p>\n
The algorithm is directly applicable in C++17. Of course, my algorithm will not run on a big, distributed system, but the strategy is the same; therefore, I map in the map phase each word to its length and reduce in the reduce phase the lengths of all words to their sum. The result is the sum of the lengths of all words.<\/p>\n
 <\/p>\n
\n
std::vector<std::string> str{\"Only\"<\/span>,\"for\"<\/span>,\"testing\"<\/span>,\"purpose\"<\/span>};\r\n\r\n\r\nstd::size_t<\/span> result= std::transform_reduce(std::parallel::par, \r\n                         str.begin(), str.end(), \r\n                         [](std::string s){ return<\/span> s.length(); }, \r\n                         0, [](std::size_t<\/span> a, std::size_t<\/span> b){ return<\/span> a + b; });\r\n\r\nstd::cout << result << std::endl;      \/\/   21<\/span>\r\n<\/pre>\n<\/div>\n
 <\/p>\n
The 0 is the initial element for the reduction.<\/p>\n
What’s next?<\/h2>\n
With the next pos<\/a>t, I will go three years further. In C++20, we get atomic smart pointers. Following their C++11 pendants, they are called std::atomic_shared_ptr<\/span> and std::atomic_weak_ptr. <\/span><\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
The idea is quite simple. The Standard Template has more than 100 algorithms for searching, counting, and manipulating ranges and their elements. With C++17, 69 are overloaded, and a few new ones are added. The overloaded and new algorithms can be invoked with a so-called execution policy. Using the execution policy, you can specify whether […]<\/p>\n","protected":false},"author":21,"featured_media":5192,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[367],"tags":[],"class_list":["post-5195","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-multithreading-c-17-and-c-20"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5195","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=5195"}],"version-history":[{"count":0,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5195\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/5192"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=5195"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=5195"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=5195"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}