2-minute read: the Magic Touch of Parallel Algorithms

In the previous article we made our program run faster by replacing std::endl with '\n' when writing to a file. Our flamegraph for the same program, after this modification, looks like this:

As you can see, what takes most of the time in our program now is the function sort_lines. Let’s have a look at the source code of this function:

 void sort_lines(std::vector<std::string>& lines) {
     std::sort(lines.begin(), lines.end());
 }

This is a simple call to std::sort, so we could naively conclude there is nothing possible to optimize. However, this is not true.

Almost all modern CPUs have more than one core nowadays but the standard C++ library is somewhat stuck in the past. Sorting can be done on more than one CPU simultaneously, and there exist parallel implementations of std::sort that can take advantage of more than one core.

Parallel algorithms in the standard library

If you are C++17, the std::sort algorithm takes an additional parameter called ExecutionPolicy. Developers can use it to specify what flavor of the algorithm they prefer. Here is our modified implementation:

void sort_lines(std::vector<std::string>& lines) {
    std::sort(std::execution::par_unseq, lines.begin(), lines.end());
}

With std::execution::par_unseq we are instructing the standard C++ library to use the parallel version of std::sort algorithm. Many algorithms of the standard C++ library accept this parameter, e.g. std::sort, std::find, std::find_if, std::count, std::for_each, std::transform, std::transform_reduce and many other.

If you are using an older C++ version, GCC’s standard C++ library offers Parallel Mode. Parallel mode is not enabled by default, and you can enable it in two ways:

• Recompile your program with -D_GLIBCXX_PARALLEL. This will instruct the standard library to use parallel algorithms whenever available or
• Use the algorithms from __gnu_parallel namespace, in our case __gnu_parallel::sort.

Our current implementation looks like this:

void sort_lines(std::vector<std::string>& lines) {
#if __cplusplus >= 201703L
    std::sort(std::execution::par_unseq, lines.begin(), lines.end());
#else
    __gnu_parallel::sort(lines.begin(), lines.end());
#endif
}

We are choosing the std::sort implementation depending on the version of C++ version.

The flamegraph (with GCC’s parallel mode libstdc++) looks like this:

The runtime of sort_lines function went down from 440 ms to 150 ms. The whole program’s runtime went down from 650 ms to 390 ms with a very simple change!

Like what you are reading? Follow us on LinkedIn or Twitter and get notified as soon as new content becomes available.
Need help with software performance? Contact us!