C++17: New Parallel Algorithms of the Standard Template Library

Contents[Show]

The idea is quite simple. The Standard Template (STL) has more than 100 algorithms for searching, counting, and manipulating ranges and their elements. With C++17, 69 of them are overloaded and a few new ones are added. The overloaded and new algorithm can be invoked with a so-called execution policy. By using the execution policy, you can specify whether the algorithm should run sequential, parallel, or parallel and vectorized.

My previous post was mainly about overloaded algorithms. In case you are curious, read the post Parallel Algorithm of the Standard Template Library.

Today, I'm writing about the seven new algorithms. Here are they.

```std::for_each_n

std::exclusive_scan
std::inclusive_scan

std::transform_exclusive_scan
std::transform_inclusive_scan

std::parallel::reduce
std::parallel::transform_reduce
```

Besides std::for_each_n these names are quite unusual. So let me make a short detour and write a little bit about Haskell.

Modernes C++ Mentoring

Stay informed about my mentoring programs. Subscribe for the news.

A short detour

To make the long story short. All new functions have a pendant in the pure functional language Haskell.

• for_each_n is called map in Haskell.
• exclusive_scan and inclusive_scan are called scanl and scanl1 in Haskell.
• transform_exclusive_scan and transform_inclusive_scan is a composition of the Haskell functions map and scanl or scanl1.
• reduce is called foldl or foldl1 in Haskell.
• transform_reduce is a composition of the Haskell functions map and foldl or foldl1.

Before I show you, Haskell, in action, let me say a few words about the different functions.

• map applies a function to a list.
• foldl and foldl1 apply a binary operation to a list and reduces the list to a value. foldl needs in contrary to foldl1 an initial value.
• scanl and scanl1 apply the same strategy such as foldl and foldl1 but they produce all intermediate values. So you get back a list.
• foldl, foldl1, scanl, and scanl1 start their job from the left.

Now comes the action. Here is Haskell's interpreter shell.

(1) and (2) define a list of integers and a list of strings. In (3), I apply the lambda function (\a -> a * a) to the list of ints. (4) and (5) are more sophisticated. The expression (4) multiplies (*) all pairs of integers starting with the 1 as a neutral element of the multiplication.  Expression (5) does the corresponding for the addition. The expressions (6), (7), and (9) are quite challenging to read for the imperative eye. You have to read them from right to left. scanl1 (+) . map(\a -> length a (7) is a function composition. The dot (.) symbol compose the two functions. The first function maps each element to its length, the second function adds the list of lengths together. (9) is similar to 7. The difference is, that foldl produces one value and requires an initial element. This is 0. Now, the expression (8) should be readable. The expression successively joins two strings with the ":" character.

I think you wonder why I write in a C++ blog so much challenging stuff about Haskell. That is for two good reasons. At first, you know the history of the C++ functions. And second,  it's a lot easier to understand the C++ function if you compare them with the Haskell pendants.

The seven new algorithms

I promised, it may become a little bit difficult to read.

```// newAlgorithm.cpp

#include <hpx/hpx_init.hpp>
#include <hpx/hpx.hpp>
#include <hpx/include/parallel_numeric.hpp>
#include <hpx/include/parallel_algorithm.hpp>
#include <hpx/include/iostreams.hpp>

#include <string>
#include <vector>

int hpx_main(){

hpx::cout << hpx::endl;

// for_each_n

std::vector<int> intVec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};                        // 1
hpx::parallel::for_each_n(hpx::parallel::execution::par,                       // 2
intVec.begin(), 5, [](int& arg){ arg *= arg; });

hpx::cout << "for_each_n: ";
for (auto v: intVec) hpx::cout << v << " ";
hpx::cout << "\n\n";

// exclusive_scan and inclusive_scan
std::vector<int> resVec{1, 2, 3, 4, 5, 6, 7, 8, 9};
hpx::parallel::exclusive_scan(hpx::parallel::execution::par,                   // 3
resVec.begin(), resVec.end(), resVec.begin(), 1,
[](int fir, int sec){ return fir * sec; });

hpx::cout << "exclusive_scan: ";
for (auto v: resVec) hpx::cout << v << " ";
hpx::cout << hpx::endl;

std::vector<int> resVec2{1, 2, 3, 4, 5, 6, 7, 8, 9};

hpx::parallel::inclusive_scan(hpx::parallel::execution::par,                   // 5
resVec2.begin(), resVec2.end(), resVec2.begin(),
[](int fir, int sec){ return fir * sec; }, 1);

hpx::cout << "inclusive_scan: ";
for (auto v: resVec2) hpx::cout << v << " ";
hpx::cout << "\n\n";

// transform_exclusive_scan and transform_inclusive_scan
std::vector<int> resVec3{1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<int> resVec4(resVec3.size());
hpx::parallel::transform_exclusive_scan(hpx::parallel::execution::par,         // 6
resVec3.begin(), resVec3.end(),
resVec4.begin(), 0,
[](int fir, int sec){ return fir + sec; },
[](int arg){ return arg *= arg; });

hpx::cout << "transform_exclusive_scan: ";
for (auto v: resVec4) hpx::cout << v << " ";
hpx::cout << hpx::endl;

std::vector<std::string> strVec{"Only","for","testing","purpose"};             // 7
std::vector<int> resVec5(strVec.size());

hpx::parallel::transform_inclusive_scan(hpx::parallel::execution::par,         // 8
strVec.begin(), strVec.end(),
resVec5.begin(), 0,
[](auto fir, auto sec){ return fir + sec; },
[](auto s){ return s.length(); });

hpx::cout << "transform_inclusive_scan: ";
for (auto v: resVec5) hpx::cout << v << " ";
hpx::cout << "\n\n";

// reduce and transform_reduce
std::vector<std::string> strVec2{"Only","for","testing","purpose"};

std::string res = hpx::parallel::reduce(hpx::parallel::execution::par,         // 9
strVec2.begin() + 1, strVec2.end(), strVec2[0],
[](auto fir, auto sec){ return fir + ":" + sec; });

hpx::cout << "reduce: " << res << hpx::endl;

// 11
std::size_t res7 = hpx::parallel::parallel::transform_reduce(hpx::parallel::execution::par,
strVec2.begin(), strVec2.end(),
[](std::string s){ return s.length(); },
0, [](std::size_t a, std::size_t b){ return a + b; });

hpx::cout << "transform_reduce: " << res7 << hpx::endl;

hpx::cout << hpx::endl;

return hpx::finalize();
}

int main(int argc, char* argv[]){

// By default this should run on all available cores
std::vector<std::string> const cfg = {"hpx.os_threads=all"};

// Initialize and run HPX
return hpx::init(argc, argv, cfg);
}
```

Before I show you the output of the program and explain the source code, I have to make a general remark. As far as I know, there is no implementation of the parallel STL available. Therefore, I used the HPX implementation that uses the namespace hpx. So, if you replace the namespace hpx with std and write the code in the hpx_main function you know, what the STL algorithm will look like.

In correspondence to Haskell, I use a std::vector of ints (1) and strings (7).

The for_each_n algorithm in (2) maps the first n ints of the vector to its power of 2.

exclusive_scan (3) and inclusive_scan (5) are quite similar. Both apply a binary operation to their elements. The difference is, that exclusive_scan excludes in each iteration the last element. Here you have the corresponding Haskell expression: scanl (*) 1 ints.

The transform_exclusive_scan (6) is quite challenging to read. Let me try it. Apply in the first step the lambda function [](int arg){ return arg *= arg; } to each element of the range from resVec3.begin() to resVec3.end(). Then apply in the second step the binary operation [](int fir, int sec){ return fir + sec; } to the intermediate vector. That means, sum up all elements by using the 0 as initial element. The result goes to resVec4.begin(). To make the long story short. Here is Haskell: scanl (+) 0 . map(\a -> a * a) \$ ints.

The transform_inclusive_scan function in (8) is similar. This function maps each element to its length. Once more in Haskell: scanl1 (+) . map(\a -> length a) \$ strings.

Now, the reduce function should be quite simple to read. It puts ":" characters between each element of the input vector. The resulting string should not start with a ":" character. Therefore, the range starts at the second element (strVec2.begin() + 1) and the initial element is the first element of the vector: strVec2[0]. Here is Haskell: foldl1 (\l r -> l ++ ":" ++ r) strings.

If you want to understand the transform_reduce expression in (11), please read my post  Parallel Algorithm of the Standard Template Library. I have more to say about the function. For the impatient readers. The concise expression in Haskell: foldl (+) 0 . map (\a -> length a) \$ strings.

Studying the output of the program should help you.

Final remarks

Each of the seven new algorithms exists in different flavors. You can invoke them with and without an initial element, with and without specifying the execution policy. You can invoke the function that requires a binary operator such as std::scan and std::parallel::reduce even without a binary operator. In this case, the addition is used as default. In order to execute the algorithm in parallel or in parallel and vectorized, the binary operator has to be associative. That makes a lot of sense because the algorithm can quite easily run on many cores. For the details, read the Wikipedia article on prefix_sum. Here are further details to the new algorithms: extensions for parallelism.

What's next?

Sorry, that was a long post. But making two posts out of it makes no sense. In the next post, I write about the performance-improved interface of the associative containers (sets and maps) and the unified interface of the STL containers at all.

Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, Marko, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Animus24, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Evangelos Denaxas, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Matthieu Bolt, Stephen Kelley, Kyle Dean, Tusar Palauri, Dmitry Farberov, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, and Phillip Diekmann.

Thanks in particular to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, Ralf Abramowitsch, John Nebel, Mipko, and Alicja Kaminska.

My special thanks to Embarcadero

My special thanks to PVS-Studio

Seminars

I'm happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.

Standard Seminars (English/German)

Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.

Modernes C++,

Tags: C++17

0 #1 Hartmut Kaiser 2017-05-10 12:53
Hey Rainer, just as a small addition: in HPX we have implemented both, the old and the new parameter sequences for those algorithms where the sequences differ between the Parallelism TS and C++17. We have also adapted the names (which differ slightly as well). We will phase out the old signatures over time. Thanks!
0 #2 Rainer Grimm 2017-05-11 04:32
Quoting Hartmut Kaiser:
Hey Rainer, just as a small addition: in HPX we have implemented both, the old and the new parameter sequences for those algorithms where the sequences differ between the Parallelism TS and C++17. We have also adapted the names (which differ slightly as well). We will phase out the old signatures over time. Thanks!

Thanks Hartmut,
I will change the post.
0 #3 Leopoldo 2017-06-20 07:17
Excellent post. I used to be checking continuously this weblog and I'm inspired!

Extremely useful info particularly the closing part :) I deal with such info much.

I was looking for this particular info for a long time.
Thank you and best of luck.
0 #4 cau nang rua oto 2017-06-23 15:48
Hello there, You have done an excellent job. I'll definitely digg it and individually recommend
to my friends. I'm sure they will be benefited from this web site.
0 #5 9apps 2017-07-18 06:15
I'm curious to find out what blog platform you're working with?

I'm having some small security issues with my latest website and I'd like to find something more safe.
Do you have any solutions?
0 #6 Laverne 2017-07-19 15:08
I like it whenever people get together and share views. Great site, stick
with it!
0 #7 Emelia 2017-09-01 04:19
Heⅼlo ｖery nice blog!! Guy .. Excellent .. Amazing ..

Ι'll bookmark your blog аnd take the feeds alѕo?

I'm һappy tto find a ⅼot of uѕeful info right
һere ѡithin thhe ρut up, we neeɗ develop morе techniques ᧐n thijs regard, thanks for sharing.

. . . . .

Subscribe to the newsletter (+ pdf bundle)

 Email Please enable the javascript to submit this form

Visitors

Today 7

Yesterday 6417

Week 12908

Month 33655

All 10955116

Currently are 794 guests and no members online

• C++ Core Guidelines: A Short Detour to Contracts in C++20

It would be nice if you put up a disclaimer that contracts did not make it into c++ 20, and this ...

• No New New: Raw Pointers Removed from C++

APRIL FOOLS PRANKs have a ONE DAY LIFESPAN. When left up beyond that they are simply disinformation ...

• No New New: Raw Pointers Removed from C++

This is an APRIL FOOLS PRANK

• The Bridge Pattern

There is a small typo in the article: Bridget Pattern :-)

• The Bridge Pattern

Thank you for this nice description. The implementation of move semantics can be simplified and inlined ...