What are the fastest parallel C++ sorting implementations to sort int/float?

user_13863388 0
Viewed 121

I'm benchmarking different parallel CPU sorting implementations.

Data:

  • n >= 8000000000 elements of type int/long/float/double
  • various data distributions (e.g., uniform/staggered/normal/...)

Hardware:

  • CPU: 2x AMD EPYC 7742 with 64 Cores (128 cores total)
  • RAM: 1TB

So far, I have:

  • std::sort with the std::execution::par_unseq execution policy,

  • __gnu_parallel::sort, and

  • thrust::sort with the OMP backend.

Are there any other established sorting implementations where the source code is available to use?

I know about PARADIS but its source code is not available as it is commercialized.

c++17 c++11 c++
1 Answers

What are the fastest parallel C++ sorting implementations to sort int/float?

It depends a lot.... And you can reimplement PARADIS in your own C++ library.

Consider also:

  • Using OpenCL to run sub-sorting of small arrays on your GPGPU.
  • if you are sorting arrays of many millions of numbers, transmitting (perhaps using XDR) subarrays to sort to other nodes (or other cores) in some cloud computer, then running a merge sort on sorted subarrays
  • using qsort(3) and compiling and linking your entire application with GCC invoked as gcc -Wall -Wextra -O3 -flto (and perhaps even compiling GNU libc with it)

If you know more about those 8G numbers (e.g. you are sure that all of them are between 1 and 1000000 for ints, or all of them are between -1.0 and 3.0 for floats) you could code something more specific. If you are certain they follow some normal distribution, you probably could code something wiser.

My guess is that CPU cache considerations (e.g. if you have to use std::atomic) would matter a lot on performance

A possible approach (if you can afford spending many weeks on that question) is to generate several C++ routines, compile them as plugins and dlopen(3) these plugins, and benchmark and compare their performance. Another approach would be to use dynamic programming techniques coupled with machine code generation (using asmjit) at runtime to generate sorting routines suited to the particular data you have.

Don't forget to enable optimizations in your C++ compiler: with a recent GCC, compile and link using g++ -Wall -flto -O3

Pitrat's book Artificial Beings, the conscience of a conscious machine and the RefPerSys system, could be inspirational.

user_8411080
Related