Change Details

There are two commits in this request. The first one adds a benchmark that tests std::sort on an adversarial inputs. The second commit adds intro sort to the std::sort. 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 15.0 ns 15.0 ns 45875200 BM_Sort_uint32_QuickSortAdversary_4 4.56 ns 4.55 ns 156237824 BM_Sort_uint32_QuickSortAdversary_16 3.04 ns 3.04 ns 233832448 BM_Sort_uint32_QuickSortAdversary_64 44.9 ns 44.9 ns 15728640 BM_Sort_uint32_QuickSortAdversary_256 69.8 ns 69.8 ns 10223616 BM_Sort_uint32_QuickSortAdversary_1024 119 ns 119 ns 6029312 BM_Sort_uint32_QuickSortAdversary_16384 174 ns 174 ns 4194304 BM_Sort_uint32_QuickSortAdversary_262144 212 ns 212 ns 3407872 BM_Sort_uint64_QuickSortAdversary_1 15.1 ns 15.1 ns 47448064 BM_Sort_uint64_QuickSortAdversary_4 4.54 ns 4.53 ns 149684224 BM_Sort_uint64_QuickSortAdversary_16 3.01 ns 3.01 ns 233832448 BM_Sort_uint64_QuickSortAdversary_64 44.9 ns 44.8 ns 15466496 BM_Sort_uint64_QuickSortAdversary_256 70.3 ns 70.2 ns 10223616 BM_Sort_uint64_QuickSortAdversary_1024 121 ns 121 ns 6029312 BM_Sort_uint64_QuickSortAdversary_16384 176 ns 176 ns 4194304 BM_Sort_uint64_QuickSortAdversary_262144 212 ns 212 ns 3145728

There are two commits in this request. The first one adds a benchmark that tests std::sort on an adversarial inputs. The second commit adds intro sort to the std::sort. 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

There are two commits in this request. The first one adds a benchmark that tests std::sort on an adversarial inputs. The second commit adds intro sort to the std::sort. 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 15.06.31 ns 15.6.30 ns 45875200107741184 BM_Sort_uint32_QuickSortAdversary_4 4.5651 ns 4.550 ns 1562378248859264 BM_Sort_uint32_QuickSortAdversary_16 3.0400 ns 3.040 ns 23383244823608832 BM_Sort_uint32_QuickSortAdversary_64 44.98 ns 44.98 ns 15728640990784 BM_Sort_uint32_QuickSortAdversary_256 69.80 ns 69.88.9 ns 10223616 9961472 BM_Sort_uint32_QuickSortAdversary_1024 1198 ns 1198 ns 6029312 BM_Sort_uint32_QuickSortAdversary_16384 1745 ns 1745 ns 4194304 BM_Sort_uint32_QuickSortAdversary_262144 2120 ns 2120 ns 3407872 BM_Sort_uint64_QuickSortAdversary_1 15.16.75 ns 15.16.73 ns 47448064103809024 BM_Sort_uint64_QuickSortAdversary_4 4.5453 ns 4.53 ns 14968422460432128 BM_Sort_uint64_QuickSortAdversary_16 3.012.98 ns 3.012.97 ns 2338324484356736 BM_Sort_uint64_QuickSortAdversary_64 44.93 ns 44.83 ns 15466496990784 BM_Sort_uint64_QuickSortAdversary_256 70.369.2 ns 7069.2 ns 10223616 BM_Sort_uint64_QuickSortAdversary_1024 12119 ns 12119 ns 6029312 BM_Sort_uint64_QuickSortAdversary_16384 1763 ns 1763 ns 4194304 BM_Sort_uint64_QuickSortAdversary_262144 212 ns 212 ns 31457283407872