diff --git a/libcxx/benchmarks/algorithms.bench.cpp b/libcxx/benchmarks/algorithms.bench.cpp --- a/libcxx/benchmarks/algorithms.bench.cpp +++ b/libcxx/benchmarks/algorithms.bench.cpp @@ -38,18 +38,65 @@ Descending, SingleElement, PipeOrgan, - Heap + Heap, + QuickSortAdversary, }; -struct AllOrders : EnumValuesAsTuple { +struct AllOrders : EnumValuesAsTuple { static constexpr const char* Names[] = {"Random", "Ascending", "Descending", "SingleElement", - "PipeOrgan", "Heap"}; + "PipeOrgan", "Heap", + "QuickSortAdversary"}; }; +// fillAdversarialQuickSortInput fills the input vector with N int-like values. +// These values are arranged in such a way that they would invoke O(N^2) +// behavior on any quick sort implementation that satisifies certain conditions. +// Details are available in the following paper: +// "A Killer Adversary for Quicksort", M. D. McIlroy, Software—Practice & +// ExperienceVolume 29 Issue 4 April 10, 1999 pp 341–344. +// https://dl.acm.org/doi/10.5555/311868.311871. +template +void fillAdversarialQuickSortInput(T& V, size_t N) { + assert(N > 0); + // If an element is equal to gas, it indicates that the value of the element + // is still to be decided and may change over the course of time. + const int gas = N - 1; + V.resize(N); + for (int i = 0; i < N; ++i) { + V[i] = gas; + } + // Candidate for the pivot position. + int candidate = 0; + int nsolid = 0; + // Populate all positions in the generated input to gas. + std::vector ascVals(V.size()); + // Fill up with ascending values from 0 to V.size()-1. These will act as + // indices into V. + std::iota(ascVals.begin(), ascVals.end(), 0); + std::sort(ascVals.begin(), ascVals.end(), [&](int x, int y) { + if (V[x] == gas && V[y] == gas) { + // We are comparing two inputs whose value is still to be decided. + if (x == candidate) { + V[x] = nsolid++; + } else { + V[y] = nsolid++; + } + } + if (V[x] == gas) { + candidate = x; + } else if (V[y] == gas) { + candidate = y; + } + return V[x] < V[y]; + }); +} + template void fillValues(std::vector& V, size_t N, Order O) { if (O == Order::SingleElement) { V.resize(N, 0); + } else if (O == Order::QuickSortAdversary) { + fillAdversarialQuickSortInput(V, N); } else { while (V.size() < N) V.push_back(V.size()); @@ -128,6 +175,9 @@ case Order::Heap: std::make_heap(V.begin(), V.end()); break; + case Order::QuickSortAdversary: + // Nothing to do + break; } } diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -263,12 +263,14 @@ template void -__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) +__introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, + typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type __depth) { typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; const difference_type __limit = is_trivially_copy_constructible::value && is_trivially_copy_assignable::value ? 30 : 6; + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; while (true) { __restart: @@ -298,6 +300,13 @@ return; } // __len > 5 + if (__depth == 0) + { + // Fallback to heap sort as Introsort suggests. + _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp)); + return; + } + --__depth; _RandomAccessIterator __m = __first; _RandomAccessIterator __lm1 = __last; --__lm1; @@ -440,19 +449,34 @@ // sort smaller range with recursive call and larger with tail recursion elimination if (__i - __first < __last - __i) { - _VSTD::__sort<_Compare>(__first, __i, __comp); - // _VSTD::__sort<_Compare>(__i+1, __last, __comp); - __first = ++__i; + _VSTD::__introsort<_Compare>(__first, __i, __comp, __depth); + __first = ++__i; } else { - _VSTD::__sort<_Compare>(__i+1, __last, __comp); - // _VSTD::__sort<_Compare>(__first, __i, __comp); - __last = __i; + _VSTD::__introsort<_Compare>(__i + 1, __last, __comp, __depth); + __last = __i; } } } +template +inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) { + _Number __log2 = 0; + while (__n > 1) { + __log2++; + __n >>= 1; + } + return __log2; +} + +template +void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; + difference_type __depth_limit = 2 * __log2i(__last - __first); + __introsort(__first, __last, __comp, __depth_limit); +} + template inline _LIBCPP_INLINE_VISIBILITY void diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort.pass.cpp --- a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort.pass.cpp @@ -147,6 +147,63 @@ assert(*pv[array_size - 1] == v[array_size - 1]); } +// test_adversarial_quicksort generates a vector with values arranged in such a +// way that they would invoke O(N^2) behavior on any quick sort implementation +// that satisifies certain conditions. Details are available in the following +// paper: +// "A Killer Adversary for Quicksort", M. D. McIlroy, Software—Practice & +// ExperienceVolume 29 Issue 4 April 10, 1999 pp 341–344. +// https://dl.acm.org/doi/10.5555/311868.311871. +struct AdversaryComparator { + AdversaryComparator(int N, std::vector& input) : gas(N - 1), V(input) { + V.resize(N); + // Populate all positions in the generated input to gas to indicate that + // none of the values have been fixed yet. + for (int i = 0; i < N; ++i) + V[i] = gas; + } + + bool operator()(int x, int y) { + if (V[x] == gas && V[y] == gas) { + // We are comparing two inputs whose value is still to be decided. + if (x == candidate) { + V[x] = nsolid++; + } else { + V[y] = nsolid++; + } + } + if (V[x] == gas) { + candidate = x; + } else if (V[y] == gas) { + candidate = y; + } + return V[x] < V[y]; + } + +private: + // If an element is equal to gas, it indicates that the value of the element + // is still to be decided and may change over the course of time. + const int gas; + // This is a reference so that we can manipulate the input vector later. + std::vector& V; + // Candidate for the pivot position. + int candidate = 0; + int nsolid = 0; +}; + +void test_adversarial_quicksort(int N) { + assert(N > 0); + std::vector ascVals(N); + // Fill up with ascending values from 0 to N-1. These will act as indices + // into V. + std::iota(ascVals.begin(), ascVals.end(), 0); + std::vector V; + AdversaryComparator comp(N, V); + std::sort(ascVals.begin(), ascVals.end(), comp); + std::sort(V.begin(), V.end()); + assert(std::is_sorted(V.begin(), V.end())); +} + int main(int, char**) { // test null range @@ -171,6 +228,7 @@ test_larger_sorts(1009); test_pointer_sort(); + test_adversarial_quicksort(1 << 20); - return 0; + return 0; }