Re:Hoare’s Rebuttal and Bubble Sort’s Comeback
by gerbenst on Saturday May 30, 2020 @08:06PM
(#23365995)
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
> 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: