C++ parallel sort

Question

I need to sort data blocks which are stored in an array of structures. Structures have no pointers. Each block has its counter number and coordinates of the place in an array where the data block equal to the structure block is. For example if we have a data array which we can divide in 4 blocks of NxN, we have 4 structure blocks in index array of structure blocks and each of them has its own number and position in data array with the help of which we can compute the pointer of the block in data array using index block. Sorting should be done with the comparer that compares two blocks in such way that the least of two blocks shold have least i-th number of data. For example comparer:

for( i = 0; i < N * N; ++i )
{
    if( a[i] < b[i] ) return -1;
    if( a[i] > b[i] ) return 1;
}

where a and b are pointers to the blocks of data array which we can get due to index array and pointer of the start of data array. Sorting shouldn't sort data array but index array. So the question is: what parallel algorithm can I use (except frameworks, libraries, I need exactly algorithms or standard language kits, like pthread or qt libs, or c/c++ standard libs) to avoid synchronization errors? The code or pseudocode would be helpful too.

Solution 1

If you are using libstdc++ (g++'s standard) as your standard library implementation, you can rely on its built in "Parallel Mode".

To use it, you need to compile with -fopenmp and have _GLIBCXX_PARALLEL defined during compilation. Here you can find more information on the usage as well as a list of the algorithms that gcc will consider for parallization.

Be aware of the following warning from the usage site:

Note that the _GLIBCXX_PARALLEL define may change the sizes and behavior of standard class templates such as std::search, and therefore one can only link code compiled with parallel mode and code compiled without parallel mode if no instantiation of a container is passed between the two translation units. Parallel mode functionality has distinct linkage, and cannot be confused with normal mode symbols.

Each individual parallel algorithm can also be called explicitly. You only need to compile with -fopenmp (and not the _GLIBCXX_PARALLEL flag), and include the parallel/numeric or parallel/algorithm depending on the function listed in this subsection of the documentation. Be aware that the parallel algorithms are in the __gnu_parallel namespace.

Solution 2

Parallel sorting is part of C++17

Implementation-wise, everything has aligned as of Ubuntu 19.10, where you can do just:

#include <execution>
#include <algorithm>

std::sort(std::execution::par_unseq, input.begin(), input.end());

and build and run with:

sudo apt install gcc libtbb-dev
g++ -ggdb3 -O3 -std=c++17 -Wall -Wextra -pedantic -o main.out main.cpp -ltbb
./main.out

That function call automatically spawns threads for you that do the parallel sort.

Further details at: Are C++17 Parallel Algorithms implemented already?

For an algorithm discussion, see: Which parallel sorting algorithm has the best average case performance?