gerbenst

6 ms·

1.
by gerbenst 5y ago
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 ex
2.
by gerbenst 5y ago
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.
3.
by gerbenst 5y ago
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.
4.
by gerbenst 6y ago
No you are not missing something. This is, I think, correct. I haven't tried it but it seems possible and possibly very effective.
5.
by gerbenst 6y ago
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 m
6.
by gerbenst 6y ago
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 i
7.
by gerbenst 6y ago
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 e
8.
by gerbenst 6y ago
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 intro
9.
by 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 po
10.
by gerbenst 6y ago
No and I suspect that there is room for significant improvement here.