3 ms·
Sorting is going to be more expensive than mis-predicting every item in the array (since sorting inherently involves multiple rounds of conditional swaps, getti
by wyager 9y ago
Sorting is going to be more expensive than mis-predicting every item in the array (since sorting inherently involves multiple rounds of conditional swaps, getting it wrong a lot of the time on random data). The trick in the SO post is that they use the same sorted data tens of thousands of times.
- repsilat 9y agoYou can partition the list with zero branches (aside from the loop test.) You don't need to sort it. (Though, of course, the original algorithm can be written in a one-pass branchless fashion anyway, so the point is kinda moot.)