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.

I would use `std::sort` in parallel on slices (or sub-arrays), then use some merge sort. BTW, you need at least C++11 — Basile Starynkevitch, Feb 14 '15 at 21:57
BTW, are you sure that your data is large enough to want a parallel sort... What is the typical data size? — Basile Starynkevitch, Feb 14 '15 at 21:58
@BasileStarynkevitch Average data array size is about 9-11 Gb. I need to sort small parts, so the question is how to do it fast. — HackSaw, Feb 14 '15 at 22:14

Ciro Santilli OurBigBook.com · Answer 1 · 2021-04-03T16:11:17.207

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?

Baum mit Augen · Accepted Answer · 2018-03-27T10:49:27.447

14

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.

edited Mar 27 '18 at 10:49

answered Feb 14 '15 at 22:35

Baum mit Augen

49,044
25
144
182

Good method, liked it. But how can I use this sort to the structures array of custom size? In standard qsort() we have begin, end, count, size and comparer parameter, but in gnu_parallel::sort() we haven't size parameter. So how to sort custom array of structures with this function? – HackSaw Feb 15 '15 at 15:22
@HackSaw `std::sort(std::begin(myArray), std::end(myArray), comp);` if it is a compile time sized array, `std::sort(myArray, myArray + lengthOfArray, comp);` if `myArray` is a pointer. The `comp` is optional and will use `operator<` by default. – Baum mit Augen Feb 15 '15 at 15:25
Just to clear. If `myArray` is a pointer to an array of structures, the `lengthOfArray` consists of `sizeof(arraytype) * numberOfElements`, right? It's not just `numberOfElements`? – HackSaw Feb 15 '15 at 16:59
@HackSaw No, the actual number of elements. E.g. `int* p = new int[50]` would be sorted by `std::sort(p, p+50)`. – Baum mit Augen Feb 15 '15 at 17:04
@BaummitAugen What exactly is meant by "if no instantiation of a container is passed between the two translation units." . Does this mean none of these types https://en.cppreference.com/w/cpp/container defined here passed to the function call in the other library which was not compiled using parallel mode ? – Invictus Jun 20 '23 at 22:03
@Invictus As far as the documentation goes, you probably cannot rely on passing anything from the standard library working. De facto, it will likely only affect some subset of available classes. However, there is support for parallel algorithms in standard C++ by now, so you can also use that without any needing to worry about this. – Baum mit Augen Jul 31 '23 at 19:12

C++ parallel sort

2 Answers2

Linked