PPQSort (Parallel Pattern QuickSort)

Parallel Pattern Quicksort (PPQSort) is a efficient implementation of parallel quicksort algorithm, written by using only the C++20 features without using third party libraries (such as Intel TBB). PPQSort draws inspiration from pdqsort, BlockQuicksort and cpp11sort and adds some further optimizations.

• Focus on ease of use: Using only C++20 features, header only implementation, user-friendly API.
• Comprehensive test suite: Ensures correctness and robustness through extensive testing.
• Benchmarks shows great performance: Achieves impressive sorting times on various machines.

Integration

PPQSort is header only implementation. All the files needed are in include directory.

Add to existing CMake project using CPM.cmake:

include(cmake/CPM.cmake)
CPMAddPackage(
NAME PPQSort
GITHUB_REPOSITORY GabTux/PPQSort
VERSION 1.0.3 # change this to latest commit or release tag
)
target_link_libraries(YOUR_TARGET PPQSort::PPQSort)

Alternatively use FetchContent or just checkout the repository and add the include directory to the linker flags.

Usage

PPQSort has similiar API as std::sort, you can use ppqsort::execution::<policy> policies to specify how the sort should run.

// run parallel
ppqsort::sort(ppqsort::execution::par, input.begin(), input.end());

// Specify number of threads
ppqsort::sort(ppqsort::execution::par, input.begin(), input.end(), 16);

// provide custom comparator
ppqsort::sort(ppqsort::execution::par, input.begin(), input.end(), cmp);

// force branchless variant
ppqsort::sort(ppqsort::execution::par_force_branchless, input_str.begin(), input_str.end(), cmp);

PPQSort will by default use C++ threads, but if you prefer, you can link it with OpenMP and it will use OpenMP as a parallel backend. However you can still enforce C++ threads parallel backend even if linked with OpenMP:

#define FORCE_CPP
#include <ppqsort.h>
// ... rest of the code ...

Benchmark

We compared PPQSort with various parallel sorts. Benchmarks shows, that the PPQSort is one of the fastest parallel sorting algorithms across various input data and different machines.

Name	Algorithm	Memory usage	External dependencies	Highlight
PPQSort	Quicksort	in-place	None	parallel pattern quicksort algorithm
GCC BQS	Quicksort	in-place	OpenMP	allocating threads proportionally to subtask sizes
cpp11sort	Quicksort	in-place	None	Header-only, C++11 compliant
oneTBB parallel_sort	quicksort	out-place	oneTBB	Splits input to small tasks
poolSTL sort	Quicksort	in-place	None	Header-only, C++17 compliant
Boost block_indirect_sort	merging algorithm	out-place	Boost	Upper bounded small memory usage
AQsort	Quicksort	in-place	OpenMP	Allows the sorting of multiple datasets at once
MPQsort	Quicksort	in-place	OpenMP	Multiway Parallel Quicksort
IPS4o	Samplesort	in-place	oneTBB	Divides data into buckets and sort them recursively

Running on ARM cluster

• Fujitsu A64FX CPU
• NUMA architecture, 48 cores (4CPUs x 12cores)

Results for INT, input size was 2e9 (2 billions):

Algorithm	Random	Ascending	Descending	Rotated	OrganPipe	Heap	Total	Rank
PPQSort C++	5.84s	1.84s	4.55s	1.38s	2.96s	5.58s	22.15s	1
GCC BQS	13.72s	4.18s	19.11s	49.89s	8.24s	13.78s	108.92s	6
oneTBB	43.66s	0.09s	8.62s	13.84s	8.12s	43.9s	118.23s	9
poolSTL	34.63s	5.61s	7.23s	14.78s	7.81s	46.88s	116.94s	7
MPQsort	13.35s	5.74s	5.77s	4.67s	7.71s	12.87s	50.11s	5
cpp11sort	9.58s	2.47s	2.66s	5.47s	3.42s	9.9s	33.5s	3
AQsort	24.72s	3.66s	23.14s	21.83s	22.6s	25.31s	121.26s	8
Boost	8.2s	3.0s	4.26s	13.96s	6.97s	7.92s	44.31s	4
IPS$^4$o	4.8s	0.19s	5.97s	5.21s	5.59s	4.91s	26.67s	2

Summary

Extended benchmarks (detailed in forthcoming paper) shows that IPS4o (https://github.com/ips4o) often surpasses PPQSort in raw speed. However, IPS4o relies on the external library oneTBB (https://github.com/oneapi-src/oneTBB) introducing integration complexities. PPQSort steps up as a compelling alternative due to its:

• Competitive Speed: Delivers performance comparable to IPS4o on most machines.
• Hardware Agnostic: Maintains strong performance across various hardware, potentially surpassing IPS4o on specific systems, especially ARM platforms.
• Dependency-Free: No external libraries are required, simplifying integration. For applications demanding a fast, dependency-free parallel sorting solution, PPQSort is an excellent choice.

Running Tests and Benchmarks

Bash script for running or building specific components:

$ scripts/build.sh all
...
$ scripts/run.sh standalone
...

Note that the benchmark's CMake file will by default download sparse matrices (around 26GB).

Implementation

A detailed research paper exploring PPQSort's design, implementation, and performance evaluation will be available soon.