[libc++] Add introsort to avoid O(n^2) behavior
This commit adds a benchmark that tests std::sort on an adversarial inputs,
and uses introsort in std::sort to avoid O(n^2) behavior on adversarial
inputs.
Inputs where partitions are unbalanced even after 2 log(n) pivots have
been selected, the algorithm switches to heap sort to avoid the
possibility of spending O(n^2) time on sorting the input.
Benchmark results show that the intro sort implementation does
significantly better.
Benchmarking results before this change. Time represents the sorting
time required per element:
----------------------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations
----------------------------------------------------------------------------------------------------------
BM_Sort_uint32_QuickSortAdversary_1 3.75 ns 3.74 ns 187432960
BM_Sort_uint32_QuickSortAdversary_4 3.05 ns 3.05 ns 231211008
BM_Sort_uint32_QuickSortAdversary_16 2.45 ns 2.45 ns 288096256
BM_Sort_uint32_QuickSortAdversary_64 32.8 ns 32.8 ns 21495808
BM_Sort_uint32_QuickSortAdversary_256 132 ns 132 ns 5505024
BM_Sort_uint32_QuickSortAdversary_1024 498 ns 497 ns 1572864
BM_Sort_uint32_QuickSortAdversary_16384 3846 ns 3845 ns 262144
BM_Sort_uint32_QuickSortAdversary_262144 61431 ns 61400 ns 262144
BM_Sort_uint64_QuickSortAdversary_1 3.93 ns 3.92 ns 181141504
BM_Sort_uint64_QuickSortAdversary_4 3.10 ns 3.09 ns 222560256
BM_Sort_uint64_QuickSortAdversary_16 2.50 ns 2.50 ns 283639808
BM_Sort_uint64_QuickSortAdversary_64 33.2 ns 33.2 ns 21757952
BM_Sort_uint64_QuickSortAdversary_256 132 ns 132 ns 5505024
BM_Sort_uint64_QuickSortAdversary_1024 478 ns 477 ns 1572864
BM_Sort_uint64_QuickSortAdversary_16384 3932 ns 3930 ns 262144
BM_Sort_uint64_QuickSortAdversary_262144 61646 ns 61615 ns 262144
Benchmarking results after this change:
----------------------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations
----------------------------------------------------------------------------------------------------------
BM_Sort_uint32_QuickSortAdversary_1 6.31 ns 6.30 ns 107741184
BM_Sort_uint32_QuickSortAdversary_4 4.51 ns 4.50 ns 158859264
BM_Sort_uint32_QuickSortAdversary_16 3.00 ns 3.00 ns 223608832
BM_Sort_uint32_QuickSortAdversary_64 44.8 ns 44.8 ns 15990784
BM_Sort_uint32_QuickSortAdversary_256 69.0 ns 68.9 ns 9961472
BM_Sort_uint32_QuickSortAdversary_1024 118 ns 118 ns 6029312
BM_Sort_uint32_QuickSortAdversary_16384 175 ns 175 ns 4194304
BM_Sort_uint32_QuickSortAdversary_262144 210 ns 210 ns 3407872
BM_Sort_uint64_QuickSortAdversary_1 6.75 ns 6.73 ns 103809024
BM_Sort_uint64_QuickSortAdversary_4 4.53 ns 4.53 ns 160432128
BM_Sort_uint64_QuickSortAdversary_16 2.98 ns 2.97 ns 234356736
BM_Sort_uint64_QuickSortAdversary_64 44.3 ns 44.3 ns 15990784
BM_Sort_uint64_QuickSortAdversary_256 69.2 ns 69.2 ns 10223616
BM_Sort_uint64_QuickSortAdversary_1024 119 ns 119 ns 6029312
BM_Sort_uint64_QuickSortAdversary_16384 173 ns 173 ns 4194304
BM_Sort_uint64_QuickSortAdversary_262144 212 ns 212 ns 3407872
Differential Revision: https://reviews.llvm.org/D113413
GitOrigin-RevId: 7f287390d78d301956e8e925a84349fd4408a11e
3 files changed
