1[/=========================================================================== 2 Copyright (c) 2017 Steven Ross, Francisco Tapia, Orson Peters 3 4 5 Distributed under the Boost Software License, Version 1.0 6 See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt 8=============================================================================/] 9 10[section:pdqsort 2.2.- pdqsort] 11 12[def __std_sort [@http://en.cppreference.com/w/cpp/algorithm/sort std::sort]] 13[def __std_stable_sort [@http://en.cppreference.com/w/cpp/algorithm/stable_sort std::stable_sort]] 14[def __std_less [@http://en.cppreference.com/w/cpp/utility/functional/less std::less]] 15[def __std_greater [@http://en.cppreference.com/w/cpp/utility/functional/greater std::greater]] 16 17[def __pdqsort_github [@https://github.com/orlp/pdqsort pdqsort]] 18[def __pdqsort [^[funcref boost::sort::pdqsort pdqsort]]] 19[def __pdqsort_branchless [^[funcref boost::sort::pdqsort_branchless pdqsort_branchless]]] 20 21[section:pdqsort_intro Introduction] 22 23Pattern-defeating quicksort (__pdqsort_github) is a novel sorting algorithm that combines the fast 24average case of randomized quicksort with the fast worst case of heapsort, while achieving linear 25time on inputs with certain patterns. pdqsort is an extension and improvement of David Mussers 26introsort. It is identical in usage to __std_sort. 27 28[endsect] [/section:pdqsort_intro Introduction] 29 30 31[section:pdqsort_usage Usage] 32 33Pattern-defeating quicksort is available through two calls, __pdqsort and __pdqsort_branchless. Both 34have identical guarantees, behavior and overloads as __std_sort, with the exception of the C++17 35parallel execution policy argument. Thus you can simply replace a call to __std_sort with __pdqsort, 36it is simply a faster implementation. It is almost always appropriate to simply call __pdqsort and 37ignore __pdqsort_branchless. 38 39__pdqsort_branchless runs significantly faster than __pdqsort for comparison functions that are 40branchless (for an explanation why see 'The Average Case' below), such as simple integer or float 41comparison, and slightly slower when the comparison function contains branches. When using 42an arithmetic type and a default comparison function (__std_less or __std_greater) __pdqsort 43automatically delegates to __pdqsort_branchless. If you know that your custom comparison function is 44branchless and wish to make use of this speedup call __pdqsort_branchless explicitly. 45 46[endsect] [/section:pdqsort_usage Usage] 47 48 49[section:pdqsort_benchmark Benchmark] 50 51A comparison of __pdqsort and GCC's __std_sort and __std_stable_sort with various input distributions: 52 53[$../images/pdqsort.png] 54 55Compiled with `g++ -std=c++11 -O2 -m64 -march=native`. 56 57[endsect] [/section:pdqsort_benchmark Benchmark] 58 59 60[section:pdqsort_best The Best Case] 61 62__pdqsort is designed to run in linear time for a couple of best-case patterns. Linear time is 63achieved for inputs that are in strictly ascending or descending order, only contain equal elements, 64or are strictly in ascending order followed by one out-of-place element. There are two seperate 65mechanisms at play to achieve this. 66 67For equal elements a smart partitioning scheme is used that always puts equal elements in the 68partition containing elements greater than the pivot. When a new pivot is chosen it's compared to 69the greatest element in the partition before it. If they compare equal we can derive that there are 70no elements smaller than the chosen pivot. When this happens we switch strategy for this partition, 71and filter out all elements equal to the pivot. 72 73To get linear time for the other patterns we check after every partition if any swaps were made. If 74no swaps were made and the partition was decently balanced we will optimistically attempt to use 75insertion sort. This insertion sort aborts if more than a constant amount of moves are required to 76sort. 77 78[endsect] [/section:pdqsort_best The Best Case] 79 80 81[section:pdqsort_avg The Average Case] 82 83On average case data where no patterns are detected __pdqsort is effectively a quicksort that uses 84median-of-3 pivot selection, switching to insertion sort if the number of elements to be 85(recursively) sorted is small. The overhead associated with detecting the patterns for the best case 86is so small it lies within the error of measurement. 87 88__pdqsort gets a great speedup over the traditional way of implementing quicksort when sorting large 89arrays (1000+ elements). This is due to a new technique described in "BlockQuicksort: How Branch 90Mispredictions don't affect Quicksort" by Stefan Edelkamp and Armin Weiss. In short, we bypass the 91branch predictor by using small buffers (entirely in L1 cache) of the indices of elements that need 92to be swapped. We fill these buffers in a branch-free way that's quite elegant (in pseudocode): 93 94 buffer_num = 0; buffer_max_size = 64; 95 for (int i = 0; i < buffer_max_size; ++i) { 96 // With branch: 97 if (elements[i] < pivot) { buffer[buffer_num] = i; buffer_num++; } 98 // Without: 99 buffer[buffer_num] = i; buffer_num += (elements[i] < pivot); 100 } 101 102[endsect] [/section:pdqsort_avg The Average Case] 103 104 105[section:pdqsort_worst The Worst Case] 106 107Quicksort naturally performs bad on inputs that form patterns, due to it being a partition-based 108sort. Choosing a bad pivot will result in many comparisons that give little to no progress in the 109sorting process. If the pattern does not get broken up, this can happen many times in a row. Worse, 110real world data is filled with these patterns. 111 112Traditionally the solution to this is to randomize the pivot selection of quicksort. While this 113technically still allows for a quadratic worst case, the chances of it happening are astronomically 114small. Later, in introsort, pivot selection is kept deterministic, instead switching to the 115guaranteed O(n log n) heapsort if the recursion depth becomes too big. In __pdqsort we adopt a hybrid 116approach, (deterministically) shuffling some elements to break up patterns when we encounter a "bad" 117partition. If we encounter too many "bad" partitions we switch to heapsort. 118 119[endsect] [/section:pdqsort_worst The Worst Case] 120 121 122[section:pdqsort_bad_partitions Bad Partitions] 123 124A bad partition occurs when the position of the pivot after partitioning is under 12.5% (1/8th) 125percentile or over 87,5% percentile - the partition is highly unbalanced. When this happens we will 126shuffle four elements at fixed locations for both partitions. This effectively breaks up many 127patterns. If we encounter more than log(n) bad partitions we will switch to heapsort. 128 129The 1/8th percentile is not chosen arbitrarily. An upper bound of quicksorts worst case runtime can 130be approximated within a constant factor by the following recurrence: 131 132 T(n, p) = n + T(p(n-1), p) + T((1-p)(n-1), p) 133 134Where n is the number of elements, and p is the percentile of the pivot after partitioning. 135`T(n, 1/2)` is the best case for quicksort. On modern systems heapsort is profiled to be 136approximately 1.8 to 2 times as slow as quicksort. Choosing p such that `T(n, 1/2) / T(n, p) ~= 1.9` 137as n gets big will ensure that we will only switch to heapsort if it would speed up the sorting. 138p = 1/8 is a reasonably close value and is cheap to compute on every platform using a bitshift. 139 140[endsect] [/section:pdqsort_bad_partitions Bad Partitions] 141 142[endsect] [/section:pdqsort 2.2.- pdqsort] 143
