Hacker News Reader

Comment by yturijea | Hacker News Reader

I like how we have pretty much established how branchless coding is superior to branched coding. However I wonder if the compiler itself could recognize these patterns and turn branches into branchless instead, rather than making the code harder to read? as removing if conditions of course have a readability impact on the code.

View on HN

Branchless coding is superior to branched coding whenever the branches are more or less random, which happens frequently when checking some properties of input numbers, like their sign or whether they fall inside certain intervals, or when sorting an array that comes in random order.

When a branch alternative will be taken much more frequently than the other, then branched coding with an "if" becomes superior.

So neither is better in general than the other, whenever the program must choose between alternatives, you must think about whether one is more likely than the other, or if both have similar probabilities.

For instance, when sorting an array, the optimal algorithm is not the same when you expect the input array to have a random order and when you expect it to be already almost sorted.

This is true, but the example given yesterday showed that even if branches can be very well predicted (e.g. processing UTF-8 text which is 99.9999% ASCII), branchless code can result in speedup by making autovectorisation possible.

If the branchless code didn't transform to vector instructions, it would be strictly slower. But if it does, it allows the CPU to work on 16 bytes at a time instead of 1 at a time.

https://github.blog/engineering/architecture-optimization/do...

For sorting, conveniently we always definitely need to look at all the elements at least once anyway, so although even the early introspective sorts from the end of last century aren't designed this way both the Timsort and a modern sort like a PDQ sort will end up making that decision early.

"Oh, this was mostly already sorted, done"

If you meant exactly rather than almost then you can still squeak a small win from having an algorithm which is optimised for this case but the vast bulk of your runtime is eaten by the unavoidable work of checking. "Don't check" is faster but then you're not a sort algorithm at all.

Reply on news.ycombinator.com