PPQSort

PPQSort, short for Parallel Pattern Quicksort, is an efficient implementation of the parallel quicksort algorithm developed exclusively using C++20 features, without relying on third-party libraries such as Intel TBB. This project combines insights from notable sorting algorithms like pdqsort, BlockQuicksort, and cpp11sort, integrating additional optimizations for enhanced performance.

Key Features

• Ease of Use: The header-only implementation utilizes only C++20 features, allowing for a user-friendly API.
• Comprehensive Testing: A rigorous test suite validates the accuracy and robustness of the sorting algorithm.
• High Performance: Benchmarks indicate that PPQSort achieves superior sorting speeds across a variety of machines.

Simple Integration

PPQSort is designed as a header-only library. The complete source files are located in the include directory. Users can incorporate PPQSort into existing CMake projects effortlessly using CPM.cmake like so:

include(cmake/CPM.cmake)
CPMAddPackage(
    NAME PPQSort
    GITHUB_REPOSITORY GabTux/PPQSort
    VERSION 1.0.4
)
target_link_libraries(YOUR_TARGET PPQSort::PPQSort)

Alternatively, FetchContent can be used, or developers can simply clone the repository and add the include directory to their linker flags.

Usage Example

PPQSort offers an API similar to std::sort, where execution policies can be specified:

// Run sorting in parallel
ppqsort::sort(ppqsort::execution::par, input.begin(), input.end());

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

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

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

By default, PPQSort utilizes C++ threads. For those who prefer, it can also be linked with OpenMP as a parallel backend while still enforcing the use of C++ threads by defining FORCE_CPP before including the header:

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

Performance Benchmarks

Performance evaluations reveal that PPQSort ranks as one of the swiftest parallel sorting algorithms across diverse datasets and systems. The results showcase the algorithm's efficiency and robustness:

ARM Cluster Support

PPQSort has demonstrated impressive performance on ARM architecture, such as the Fujitsu A64FX CPU with a NUMA setup. For example, benchmarks with an input size of 2 billion integers have shown:

Advantages

• Competitive Speed: PPQSort's performance is on par with advanced algorithms like IPS4o, particularly across various hardware.
• Hardware Agnostic: Maintains efficient performance on different systems, excelling on ARM platforms.
• No Dependency Issues: A seamless integration experience without the hassle of external library management.

PPQSort also plays a role in the Tracy project as a reliable sorting solution.

Additional Resources

Further details on implementation and benchmarks can be found through the following links:

• IT SPY Poster
• Master Thesis
• Conference Paper presented at PPAM.

For applications necessitating a high-speed, dependency-free parallel sorting solution, PPQSort is a strong candidate.