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 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 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