3 ms·

Towards the end of the article, Gerben makes the point that the comparison is not on the critical path of his variant of QuickSort, so even if the comparison in

Towards the end of the article, Gerben makes the point that the comparison is not on the critical path of his variant of QuickSort, so even if the comparison involves indirection, that comparison can still proceed in parallel with the main loop of the algorithm: > Combining these two tricks could lead to merge sort on par with the simple partition loop of QuickSort. However it’s just a mitigation. If instead of sorting a simple primitive value we would sort pointers to a struct. The comparison operator would have an extra load which immediately adds to the critical path. QuickSort is immune to this, even rather costly comparisons do not influence the ability to make progress. Of course if the comparison itself suffers from frequent branch misses, then that will limit the ability to overlap different stages of the iteration in the CPU pipeline. In the benchmark code for the blog, he includes a benchmark that has indirection to illustrate this, though these results were not included in the article itself. On my machine I get: $ CC=clang bazel build -c opt :all $ bazel-bin/bench_sort --benchmark_filter=BM_IndirectionSort ------------------------------------------------------------------------------------- Benchmark Time CPU Iterations ------------------------------------------------------------------------------------- BM_IndirectionSort<1, std_sort> 64 ns 64 ns 10900000 BM_IndirectionSort<1, std_stable_sort> 89 ns 89 ns 7900000 BM_IndirectionSort<1, std_heap_sort> 112 ns 112 ns 6300000 BM_IndirectionSort<1, exp_gerbens::QuickSort> 26 ns 26 ns 27000000 BM_IndirectionSort<1, HeapSort> 96 ns 96 ns 7300000 BM_IndirectionMergeSort<1> 45 ns 45 ns 15500000

gerbenst 6y ago
For more clarification. The number 0, 1 in these benchmarks mean the level of indirection. IndirectionSort<0, xxx> is sorting pointers on their address. While IndirectionSort<1, xxx> is sorting pointers on the value it's pointing to. Notice how MergeSort regresses much more then the QuickSort. Without an indirection MergeSort is competitive with an indirection QuickSort becomes relatively much better. As you point out sorting pointers to structs is much more important use case. This property becomes even more important as L1 cache is typically kind of small O(32kb), while L2/L3 cache is large O(1mb). So when sorting pointers it's not unreasonable to hit L2/L3 cache but miss L1. With L2/L3 typically being 10-20 cycles latency (vs 5 cycle for L1) QuickSort is largely insensitive to the L1 cache misses. BM_IndirectionSort<1, std_sort> 93 ns 93 ns 7700000 BM_IndirectionSort<1, std_stable_sort> 126 ns 125 ns 5600000 BM_IndirectionSort<1, std_heap_sort> 172 ns 172 ns 4200000 BM_IndirectionSort<1, exp_gerbens::QuickSort> 34 ns 34 ns 19000000 BM_IndirectionSort<1, HeapSort> 157 ns 157 ns 4700000 BM_IndirectionMergeSort<1> 68 ns 68 ns 10400000 BM_IndirectionSort<0, std_sort> 74 ns 74 ns 9500000 BM_IndirectionSort<0, std_stable_sort> 91 ns 91 ns 7800000 BM_IndirectionSort<0, std_heap_sort> 125 ns 125 ns 5800000 BM_IndirectionSort<0, exp_gerbens::QuickSort> 26 ns 26 ns 27200000 BM_IndirectionSort<0, HeapSort> 77 ns 77 ns 9300000 BM_IndirectionMergeSort<0> 36 ns 36 ns 19400000

gerbenst 6y ago

For more clarification. The number 0, 1 in these benchmarks mean the level of indirection. IndirectionSort<0, xxx> is sorting pointers on their address. While IndirectionSort<1, xxx> is sorting pointers on the value it's pointing to. Notice how MergeSort regresses much more then the QuickSort. Without an indirection MergeSort is competitive with an indirection QuickSort becomes relatively much better. As you point out sorting pointers to structs is much more important use case. This property becomes even more important as L1 cache is typically kind of small O(32kb), while L2/L3 cache is large O(1mb). So when sorting pointers it's not unreasonable to hit L2/L3 cache but miss L1. With L2/L3 typically being 10-20 cycles latency (vs 5 cycle for L1) QuickSort is largely insensitive to the L1 cache misses. BM_IndirectionSort<1, std_sort> 93 ns 93 ns 7700000 BM_IndirectionSort<1, std_stable_sort> 126 ns 125 ns 5600000 BM_IndirectionSort<1, std_heap_sort> 172 ns 172 ns 4200000 BM_IndirectionSort<1, exp_gerbens::QuickSort> 34 ns 34 ns 19000000 BM_IndirectionSort<1, HeapSort> 157 ns 157 ns 4700000 BM_IndirectionMergeSort<1> 68 ns 68 ns 10400000 BM_IndirectionSort<0, std_sort> 74 ns 74 ns 9500000 BM_IndirectionSort<0, std_stable_sort> 91 ns 91 ns 7800000 BM_IndirectionSort<0, std_heap_sort> 125 ns 125 ns 5800000 BM_IndirectionSort<0, exp_gerbens::QuickSort> 26 ns 26 ns 27200000 BM_IndirectionSort<0, HeapSort> 77 ns 77 ns 9300000 BM_IndirectionMergeSort<0> 36 ns 36 ns 19400000