Hoare’s Rebuttal and Bubble Sort’s Comeback

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by tialaramex on Sunday January 30, 2022 @04:24AM (#30135315)

CMOV is a win if the speculation won't work. HN regular Nathan Myers (ncmncm) wrote a proposal for C++ saying the compilers should offer a way to, in effect, signal that yeah, you really can't guess this one (thus, try CMOV).

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by gerbenst on Sunday January 30, 2022 @01:29PM (#30139689)

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.

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by masklinn on Sunday January 30, 2022 @04:50AM (#30135432)

> Many vulnerabilities stem from accessing/modifying memory that should not be accessed/modified.

So a complement to the likely/unlikely annotations?

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by bobthebuilders on Sunday January 30, 2022 @05:25AM (#30135613)

Got a link?

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by ncmncm on Sunday January 30, 2022 @08:34AM (#30137034)

https://cantrip.org/swap_if.pdf

It probably depends on a core language accommodation because bitwise-swapping objects, or even primitive elements of objects, with constructors is UB.

Arthur O'Dwyer's P1144 https://wg21.link/p1144 explores that territory too.

Gcc has weird limits on generating CMOV instructions to implement this sort of optimization.

[ Parent | on HN ]