Hacker News Reader

gerbenston Hoare’s Rebuttal and Bubble Sort’s Comeback

The key point of this article (I'm the author) is that even if cmov would be like 50 cycle latency instruction and the penalty of a mispredicted branch is 0 (ie. after the cpu sees a branch is mispredicted it would immediately start executing the instructions from the correct branch), than cmov would still be faster on modern CPU's.

Because in branchless quicksort, no matter how long it takes to figure out where the element has to go relative to the pivot it doesn't obstruct the CPU's ability in this algorithm to start working on the next element the next cycle.

gerbenston Hoare’s Rebuttal and Bubble Sort’s Comeback

https://godbolt.org/z/zPWr73qjc

Here is an implementation. This should work with all types. Unfortunate I had to annotate with restrict, but a small price to pay.

gerbenston Hoare’s Rebuttal and Bubble Sort’s Comeback

it's not difficult to swap the pivot with the last element and have the compiler figure out it can keep pivot in register most of the time.

gerbenston Hoare’s Rebuttal and Bubble Sort’s Comeback

No you are not missing something. This is, I think, correct. I haven't tried it but it seems possible and possibly very effective.

gerbenston Hoare’s Rebuttal and Bubble Sort’s Comeback

Yes that is very much possible. In general you won't get 4 equal length ranges though. For instance in an already sorted array the median results in (n/2,0) and a (0,n/2) division. But the average case should be two sets of merge intervals both of size (n/4, n/4). In reality I think you will quickly run into other limits. You need quite a bit of registers, that shouldn't spill to stack.

gerbenston Hoare’s Rebuttal and Bubble Sort’s Comeback

A very interesting suggestion indeed. Shell sort is an insertion sort though. It owes its better complexity from being able to breaking out of loop early. But these are difficult to predict branches that bubble sort avoids.

Certainly this is worth an experiment

gerbenston Hoare’s Rebuttal and Bubble Sort’s Comeback

The "hybrid" as used in this article referred to a partition scheme that combines a "Lomuto partitioning like algorithm" together with a "Hoare partitioning like algorithm".

This amplifies the the strength of each scheme and mitigates the weakness. Ie. Lomuto does too many swaps, but naturally fits a branchfree implementation. Hoare is frugal with swaps, but is rather branchy. The "hybrid" here inherits the frugality of swaps from Hoare's scheme, while benefits from the branchfree implementation of Lomuto scheme.

What you seem to describe here is the classical and well-known hybridization of divide and conquer algorithms. This is also used and implicitly implied when branchless bubble sort is discussed. But the "hybrid" as used in the article wasn't meant to refer to this.

gerbenston Hoare’s Rebuttal and Bubble Sort’s Comeback

That was just hand analysis of the data flow together with Google Diagrams.

As I mention in the article, dependency analysis has, IMO, not received the widespread attention it should. I like Fabian Giesen's article if you want an introduction.

https://fgiesen.wordpress.com/2018/03/05/a-whirlwind-introdu...

gerbenston Hoare’s Rebuttal and Bubble Sort’s Comeback

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

gerbenston Hoare’s Rebuttal and Bubble Sort’s Comeback

No and I suspect that there is room for significant improvement here.