Index: libcxx/benchmarks/CMakeLists.txt =================================================================== --- libcxx/benchmarks/CMakeLists.txt +++ libcxx/benchmarks/CMakeLists.txt @@ -162,6 +162,7 @@ algorithms/make_heap.bench.cpp algorithms/make_heap_then_sort_heap.bench.cpp algorithms/min_max_element.bench.cpp + algorithms/nth_element.bench.cpp algorithms/pop_heap.bench.cpp algorithms/push_heap.bench.cpp algorithms/ranges_make_heap.bench.cpp Index: libcxx/benchmarks/algorithms/common.h =================================================================== --- libcxx/benchmarks/algorithms/common.h +++ libcxx/benchmarks/algorithms/common.h @@ -37,12 +37,13 @@ PipeOrgan, Heap, QuickSortAdversary, + QuickSelectAdversary, }; -struct AllOrders : EnumValuesAsTuple { +struct AllOrders : EnumValuesAsTuple { static constexpr const char* Names[] = {"Random", "Ascending", "Descending", "SingleElement", "PipeOrgan", "Heap", - "QuickSortAdversary"}; + "QuickSortAdversary", "QuickSelectAdversary"}; }; // fillAdversarialQuickSortInput fills the input vector with N int-like values. @@ -88,12 +89,34 @@ }); } +// fillAdversarialQuickSelectInput fills the input vector with N int-like values. +// These values are arranged in such a way that they will make quickselect using median +// of 3 quadratic. +template +void fillAdversarialQuickSelectInput(T& V, size_t N) { + assert(N > 0); + + V.reserve(N); + size_t K = N / 2; + for (size_t i = 0; i < K; ++i) { + if (i & 1) { + V.push_back(K + i - 1); + } else { + V.push_back(i); + } + } + for (size_t i = 0; i < K; ++i) + V.push_back(2 * i); +} + 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 if (O == Order::QuickSelectAdversary) { + fillAdversarialQuickSelectInput(V, N); } else { while (V.size() < N) V.push_back(V.size()); @@ -172,6 +195,7 @@ std::make_heap(V.begin(), V.end()); break; case Order::QuickSortAdversary: + case Order::QuickSelectAdversary: // Nothing to do break; } Index: libcxx/benchmarks/algorithms/nth_element.bench.cpp =================================================================== --- /dev/null +++ libcxx/benchmarks/algorithms/nth_element.bench.cpp @@ -0,0 +1,43 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include +#include + +#include "common.h" + +namespace { +template +struct NthElement { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies( + state, Quantity, Order(), BatchSize::CountBatch, + [](auto& Copy) { + size_t k = Copy.size() / 2; + std::nth_element(Copy.begin(), Copy.begin() + k, Copy.end()); + }); + } + + bool skip() const { return Order() == ::Order::QuickSelectAdversary && Quantity == 1; } + + std::string name() const { + return "BM_NthElement" + ValueType::name() + Order::name() + "_" + + std::to_string(Quantity); + }; +}; +} // namespace + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + makeCartesianProductBenchmark(Quantities); + benchmark::RunSpecifiedBenchmarks(); +} Index: libcxx/include/__algorithm/nth_element.h =================================================================== --- libcxx/include/__algorithm/nth_element.h +++ libcxx/include/__algorithm/nth_element.h @@ -12,6 +12,8 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/iterator_operations.h> +#include <__algorithm/make_heap.h> +#include <__algorithm/sift_down.h> #include <__algorithm/sort.h> #include <__config> #include <__debug> @@ -41,6 +43,26 @@ } } +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void +__heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp) +{ + std::__make_heap<_AlgPolicy>(__first, __middle, __comp); + + typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first; + _RandomAccessIterator __i = __middle; + for (; __i != __last; ++__i) + { + if (__comp(*__i, *__first)) + { + _IterOps<_AlgPolicy>::iter_swap(__i, __first); + std::__sift_down<_AlgPolicy>(__first, __comp, __len, __first); + } + } + + _IterOps<_AlgPolicy>::iter_swap(__first, __middle); +} + template _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) @@ -50,6 +72,7 @@ // _Compare is known to be a reference type typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; const difference_type __limit = 7; + difference_type __depth = 2 * std::__log2i(__last - __first); while (true) { if (__nth == __last) @@ -76,6 +99,13 @@ std::__selection_sort<_AlgPolicy, _Compare>(__first, __last, __comp); return; } + if (__depth == 0) + { + // fall back to heap select. + std::__heap_select<_AlgPolicy, _Compare>(__first, __nth, __last, __comp); + return; + } + --__depth; // __len > __limit >= 3 _RandomAccessIterator __m = __first + __len/2; _RandomAccessIterator __lm1 = __last; Index: libcxx/include/__algorithm/sort.h =================================================================== --- libcxx/include/__algorithm/sort.h +++ libcxx/include/__algorithm/sort.h @@ -884,7 +884,7 @@ } template -inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) { +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Number __log2i(_Number __n) { if (__n == 0) return 0; if (sizeof(__n) <= sizeof(unsigned))