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…
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.
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.
No you are not missing something. This is, I think, correct. I haven't tried it but it seems possible and possibly very effective.
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…
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…
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…
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…
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…
No and I suspect that there is room for significant improvement here.
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…
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.
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.
No you are not missing something. This is, I think, correct. I haven't tried it but it seems possible and possibly very effective.
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…
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…
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…
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…
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…
No and I suspect that there is room for significant improvement here.