Hacker News Reader

Comment by twoodfin | Hacker News Reader

Great link.

The most educational bit for me was the careful structuring and eventual elimination of the if/else to shake out a conditional move rather than an unpredictable branch.

Modern optimizers and CPU scheduling engines are so powerful, a lot of received wisdom on how to code for speed is outdated; manual loop unrolling, for example, is rarely very beneficial. It's nice to see that there's still some room for craftsmanship in the most critical of paths. Structuring loops for autovectorization is another useful habit to get into.

View on HN

Wouldn't a conditional move transfer the cost from branch mispredict to the cache miss.

I wonder how realistic their test were, and if the same results would be achieved with some cache trashing.

If you're going to miss when you go back to the array, you're going to pay that cost regardless. But without the mispredict, you'll be able to issue the load that much sooner.

I'm not familiar enough with Intel's architecture to know one way or the other, but it wouldn't surprise me if not mispredicting the next memory access saves you more than just some pipeline flushing: The CPU could speculatively issue the load you don't actually need, wasting resources that could be used to service the correct addresses.

Or did you mean something else?

Well a branch will fetch the incorrect cache line if it mispredicts, but a conditional move will fetch both cache lines every time.

The conditional move is the statement `low = v >= value ? low : other_low;` which either assigns `other_low` to `low` or does nothing.

And other_low is a variable, and not an arbitrary element of the list (which is a big difference with respect to cache), and it can also be seen from the assembly that it's stored in register. So there there is no "both cache lines" to fetch anything from.

The conditional move still depends on both values taken from the array, via other variables.

Reply on news.ycombinator.com