ppqsort::impl namespace

Namespaces

namespace cpp
namespace openmp

Classes

template<class T>
struct is_default_comparator
template<class T>
struct is_default_comparator<std::greater<T>>
template<class T>
struct is_default_comparator<std::less<T>>
template<>
struct is_default_comparator<std::less<>>
template<>
struct is_default_comparator<std::ranges::greater>
template<>
struct is_default_comparator<std::ranges::less>

Enums

enum side { left, right }

Typedefs

template<typename T, class Compare>
using use_branchless = std::integral_constant<bool, std::is_arithmetic_v<T>&& is_default_comparator<std::decay_t<Compare>>::value>

Functions

template<bool Force_branchless = false, typename RandomIt, typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>, bool Branchless = use_branchless<typename std::iterator_traits<RandomIt>::value_type, Compare>::value>
auto seq_ppqsort(RandomIt begin, RandomIt end, Compare comp = Compare()) -> void
template<typename ExecutionPolicy, typename... T>
auto call_sort(ExecutionPolicy&&, T... args) -> constexpr void
template<typename RandomIt, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto deterministic_shuffle(RandomIt begin, RandomIt end, const diff_t l_size, const diff_t r_size, RandomIt pivot_pos, const int insertion_threshold) -> void
template<bool branchless, typename RandomIt, class Compare, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto median_of_three_medians(const RandomIt& begin, const RandomIt& end, const diff_t& size, Compare comp) -> void
template<typename RandomIt, class Compare, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto median_of_five_medians(const RandomIt& begin, const RandomIt& end, const diff_t& size, Compare comp) -> void
template<bool branchless, typename RandomIt, class Compare, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto choose_pivot(const RandomIt& begin, const RandomIt& end, const diff_t& size, Compare comp) -> void
template<typename RandomIt, typename Compare, bool branchless, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto seq_loop(RandomIt begin, RandomIt end, Compare comp, diff_t bad_allowed, bool leftmost = true) -> void
template<bool Force_branchless = false, typename RandomIt, typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>, bool Branchless = use_branchless<typename std::iterator_traits<RandomIt>::value_type, Compare>::value>
auto par_ppqsort(RandomIt begin, RandomIt end, Compare comp = Compare(), int threads = static_cast<int>(std::jthread::hardware_concurrency())) -> void
template<bool Force_branchless = false, typename RandomIt, typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>>
auto par_ppqsort(RandomIt begin, RandomIt end, int threads) -> void
auto log2(const unsigned long long value) -> int
template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
auto partition_to_left(RandomIt begin, RandomIt end, Compare comp) -> RandomIt
template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
auto partition_to_right(RandomIt begin, RandomIt end, Compare comp) -> std::pair<RandomIt, bool>
template<bool branchless, typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto seq_cleanup(const RandomIt& g_begin, const T& pivot, const Compare& comp, const diff_t& g_first_offset, const diff_t& g_last_offset, bool g_already_partitioned) -> std::pair<RandomIt, bool>
template<class RandomIt, typename Offset, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto swap_offsets_core(RandomIt first, RandomIt last, Offset* offsets_l, Offset* offsets_r, diff_t& num, bool swap) -> void
template<class RandomIt, typename Offset, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto swap_offsets(RandomIt first, RandomIt last, Offset* offsets_l, Offset* offsets_r, diff_t& num_l, diff_t& num_r) -> diff_t
template<class RandomIt, typename Offset, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto swap_offsets(RandomIt first, RandomIt last, Offset* offsets_l, Offset* offsets_r, diff_t& num_l, diff_t& num_r, bool& t_already_partitioned) -> diff_t
template<side s, typename RandomIt, typename Offset, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto populate_block(RandomIt& begin, diff_t& offset, T pivot, Offset* offsets, diff_t& count, Compare comp, const int& block_size) -> void
template<side s, typename RandomIt, typename Offset, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto populate_block(RandomIt& it, T& pivot, Offset* offsets, diff_t& count, Compare comp, const int& block_size) -> void
template<class RandomIt, typename Offset, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto solve_left_block(const RandomIt& g_begin, diff_t& t_left, diff_t& t_left_start, diff_t& t_left_end, Offset* t_offsets_l, diff_t& t_count_l, const T& g_pivot, Compare comp) -> void
template<class RandomIt, typename Offset, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto solve_right_block(const RandomIt& g_begin, diff_t& t_right, diff_t& t_right_start, diff_t& t_right_end, Offset* t_offsets_r, diff_t& t_count_r, const T& g_pivot, Compare comp) -> void
template<typename RandomIt, typename Offset, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto partition_branchless_cleanup(RandomIt& first, RandomIt& last, RandomIt& block_l, RandomIt& block_r, Offset* offsets_l, Offset* offsets_r, diff_t& start_l, diff_t& start_r, diff_t& count_l, diff_t& count_r, T& pivot, Compare comp, const int& block_size) -> void
template<typename RandomIt, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto partition_branchless_core(RandomIt& first, RandomIt& last, T& pivot, Compare comp) -> void
template<class RandomIt, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
auto partition_right_branchless(RandomIt begin, RandomIt end, Compare comp) -> std::pair<RandomIt, bool>
template<class RandomIt, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
auto sort_2_branchless(RandomIt a, RandomIt b, Compare comp) -> void
template<class RandomIt, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
auto sort_3_partial_branchless(RandomIt a, RandomIt b, RandomIt c, Compare comp) -> void
template<class RandomIt, class Compare>
auto sort_3_branchless(RandomIt a, RandomIt b, RandomIt c, Compare comp) -> void
template<class RandomIt, class Compare>
auto sort_5_branchless(RandomIt x1, RandomIt x2, RandomIt x3, RandomIt x4, RandomIt x5, Compare comp) -> void
template<class RandomIt, class Compare>
auto sort_3(RandomIt a, RandomIt b, RandomIt c, Compare comp) -> void
template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
auto insertion_sort(RandomIt begin, RandomIt end, Compare comp) -> void
template<class RandomIt, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
auto insertion_sort_unguarded(RandomIt begin, RandomIt end, Compare comp) -> void
template<class RandomIt, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
auto partial_insertion_sort(RandomIt begin, RandomIt end, Compare comp) -> bool
template<class RandomIt, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
auto partial_insertion_sort_unguarded(RandomIt begin, RandomIt end, Compare comp) -> bool

Enum documentation

enum ppqsort::impl::side
#include <ppqsort/parameters.h>

Typedef documentation

#include <ppqsort/mainloop.h>
template<typename T, class Compare>
using ppqsort::impl::use_branchless = std::integral_constant<bool, std::is_arithmetic_v<T>&& is_default_comparator<std::decay_t<Compare>>::value>

Function documentation

#include <ppqsort.h>
template<bool Force_branchless = false, typename RandomIt, typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>, bool Branchless = use_branchless<typename std::iterator_traits<RandomIt>::value_type, Compare>::value>
void ppqsort::impl::seq_ppqsort(RandomIt begin, RandomIt end, Compare comp = Compare())

#include <ppqsort.h>
template<typename ExecutionPolicy, typename... T>
constexpr void ppqsort::impl::call_sort(ExecutionPolicy&&, T... args)

#include <ppqsort/mainloop.h>
template<typename RandomIt, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::deterministic_shuffle(RandomIt begin, RandomIt end, const diff_t l_size, const diff_t r_size, RandomIt pivot_pos, const int insertion_threshold)

#include <ppqsort/mainloop.h>
template<bool branchless, typename RandomIt, class Compare, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::median_of_three_medians(const RandomIt& begin, const RandomIt& end, const diff_t& size, Compare comp)

#include <ppqsort/mainloop.h>
template<typename RandomIt, class Compare, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::median_of_five_medians(const RandomIt& begin, const RandomIt& end, const diff_t& size, Compare comp)

#include <ppqsort/mainloop.h>
template<bool branchless, typename RandomIt, class Compare, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::choose_pivot(const RandomIt& begin, const RandomIt& end, const diff_t& size, Compare comp)

#include <ppqsort/mainloop.h>
template<typename RandomIt, typename Compare, bool branchless, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::seq_loop(RandomIt begin, RandomIt end, Compare comp, diff_t bad_allowed, bool leftmost = true)

#include <ppqsort/parallel/cpp/mainloop_par.h>
template<bool Force_branchless = false, typename RandomIt, typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>, bool Branchless = use_branchless<typename std::iterator_traits<RandomIt>::value_type, Compare>::value>
void ppqsort::impl::par_ppqsort(RandomIt begin, RandomIt end, Compare comp = Compare(), int threads = static_cast<int>(std::jthread::hardware_concurrency()))

#include <ppqsort/parallel/cpp/mainloop_par.h>
template<bool Force_branchless = false, typename RandomIt, typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>>
void ppqsort::impl::par_ppqsort(RandomIt begin, RandomIt end, int threads)

int ppqsort::impl::log2(const unsigned long long value)
#include <ppqsort/parameters.h>

#include <ppqsort/partition.h>
template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
RandomIt ppqsort::impl::partition_to_left(RandomIt begin, RandomIt end, Compare comp)

Template parameters
RandomIt
Compare
T
Parameters
begin
end
comp
Returns Iterator to pivot

Partition [__first, __last) using the comp Assumes that *begin has the chosen pivot Assumes that input range has at least 3 elements

#include <ppqsort/partition.h>
template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
std::pair<RandomIt, bool> ppqsort::impl::partition_to_right(RandomIt begin, RandomIt end, Compare comp)

#include <ppqsort/partition.h>
template<bool branchless, typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
std::pair<RandomIt, bool> ppqsort::impl::seq_cleanup(const RandomIt& g_begin, const T& pivot, const Compare& comp, const diff_t& g_first_offset, const diff_t& g_last_offset, bool g_already_partitioned)

#include <ppqsort/partition_branchless.h>
template<class RandomIt, typename Offset, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::swap_offsets_core(RandomIt first, RandomIt last, Offset* offsets_l, Offset* offsets_r, diff_t& num, bool swap)

#include <ppqsort/partition_branchless.h>
template<class RandomIt, typename Offset, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
diff_t ppqsort::impl::swap_offsets(RandomIt first, RandomIt last, Offset* offsets_l, Offset* offsets_r, diff_t& num_l, diff_t& num_r)

#include <ppqsort/partition_branchless.h>
template<class RandomIt, typename Offset, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
diff_t ppqsort::impl::swap_offsets(RandomIt first, RandomIt last, Offset* offsets_l, Offset* offsets_r, diff_t& num_l, diff_t& num_r, bool& t_already_partitioned)

#include <ppqsort/partition_branchless.h>
template<side s, typename RandomIt, typename Offset, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::populate_block(RandomIt& begin, diff_t& offset, T pivot, Offset* offsets, diff_t& count, Compare comp, const int& block_size)

Use offset --> used by parallel sort

#include <ppqsort/partition_branchless.h>
template<side s, typename RandomIt, typename Offset, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::populate_block(RandomIt& it, T& pivot, Offset* offsets, diff_t& count, Compare comp, const int& block_size)

Use iterator --> used by sequential sort

#include <ppqsort/partition_branchless.h>
template<class RandomIt, typename Offset, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::solve_left_block(const RandomIt& g_begin, diff_t& t_left, diff_t& t_left_start, diff_t& t_left_end, Offset* t_offsets_l, diff_t& t_count_l, const T& g_pivot, Compare comp)

solve_blocks are used by parallel sort

#include <ppqsort/partition_branchless.h>
template<class RandomIt, typename Offset, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::solve_right_block(const RandomIt& g_begin, diff_t& t_right, diff_t& t_right_start, diff_t& t_right_end, Offset* t_offsets_r, diff_t& t_count_r, const T& g_pivot, Compare comp)

#include <ppqsort/partition_branchless.h>
template<typename RandomIt, typename Offset, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::partition_branchless_cleanup(RandomIt& first, RandomIt& last, RandomIt& block_l, RandomIt& block_r, Offset* offsets_l, Offset* offsets_r, diff_t& start_l, diff_t& start_r, diff_t& count_l, diff_t& count_r, T& pivot, Compare comp, const int& block_size)

#include <ppqsort/partition_branchless.h>
template<typename RandomIt, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::partition_branchless_core(RandomIt& first, RandomIt& last, T& pivot, Compare comp)

#include <ppqsort/partition_branchless.h>
template<class RandomIt, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
std::pair<RandomIt, bool> ppqsort::impl::partition_right_branchless(RandomIt begin, RandomIt end, Compare comp)

#include <ppqsort/sorts.h>
template<class RandomIt, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
void ppqsort::impl::sort_2_branchless(RandomIt a, RandomIt b, Compare comp)

Template parameters
RandomIt
Compare
T
Parameters
a
b
comp

@Brief Sort 2 elements, 1 compare, branchless @Note https://godbolt.org/z/o3sTjeGnv

#include <ppqsort/sorts.h>
template<class RandomIt, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
void ppqsort::impl::sort_3_partial_branchless(RandomIt a, RandomIt b, RandomIt c, Compare comp)

Template parameters
RandomIt
Compare
T
Parameters
a
b
c
comp

@Brief Sort 3 elements, 2 compares, branchless @Note Assumes that b and c are already sorted

#include <ppqsort/sorts.h>
template<class RandomIt, class Compare>
void ppqsort::impl::sort_3_branchless(RandomIt a, RandomIt b, RandomIt c, Compare comp)

Template parameters
RandomIt
Compare
Parameters
a
b
c
comp

@Brief Sort 3 elements, 3 compares, branchless, 17 instructions

#include <ppqsort/sorts.h>
template<class RandomIt, class Compare>
void ppqsort::impl::sort_5_branchless(RandomIt x1, RandomIt x2, RandomIt x3, RandomIt x4, RandomIt x5, Compare comp)

Template parameters
RandomIt
Compare
Parameters
x1
x2
x3
x4
x5
comp

@Brief Sort 5 elements, 9 compares, branchless, 43 instructions

#include <ppqsort/sorts.h>
template<class RandomIt, class Compare>
void ppqsort::impl::sort_3(RandomIt a, RandomIt b, RandomIt c, Compare comp)

Template parameters
RandomIt
Compare
Parameters
a
b
c
comp

@Brief Sort 2 elements, maximum 3 compares and 2 swaps, minimum 2 compares and 0 swap

#include <ppqsort/sorts.h>
template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
void ppqsort::impl::insertion_sort(RandomIt begin, RandomIt end, Compare comp)

Template parameters
RandomIt Random access iterator
Compare Comparator
T Value type of RandomIt
Parameters
begin Start of range
end End of range
comp Comparator

@Brief Sort range using insertion sort

#include <ppqsort/sorts.h>
template<class RandomIt, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
void ppqsort::impl::insertion_sort_unguarded(RandomIt begin, RandomIt end, Compare comp)

Template parameters
RandomIt Random access iterator
Compare Comparator
T Value type of RandomIt
Parameters
begin Start of range
end End of range
comp Comparator

@Brief Sort range using insertion sort @Note Assumes that element before begin is lower or equal to all elements in range

#include <ppqsort/sorts.h>
template<class RandomIt, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
bool ppqsort::impl::partial_insertion_sort(RandomIt begin, RandomIt end, Compare comp)

Template parameters
RandomIt Random access iterator
Compare Comparator
T Value type of RandomIt
Parameters
begin Start of range
end End of range
comp Comparator
Returns True if sorting was successful, false if aborted

@Brief Try to sort range using insertion sort with limit on swaps @Note Assumes begin < end

#include <ppqsort/sorts.h>
template<class RandomIt, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type>
bool ppqsort::impl::partial_insertion_sort_unguarded(RandomIt begin, RandomIt end, Compare comp)

Template parameters
RandomIt Random access iterator
Compare Comparator
T Value type of RandomIt
Parameters
begin Start of range
end End of range
comp Comparator
Returns True if sorting was successful, false if aborted

@Brief Try to sort range using insertion sort with limit on swaps @Note Assumes begin < end and that element before begin is lower or equal to all elements in range