3 ms·

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

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.

cautious_int 11y ago
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.
- twoodfin 11y ago
  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?
  - cautious_int 11y ago
    Well a branch will fetch the incorrect cache line if it mispredicts, but a conditional move will fetch both cache lines every time.
    - rrrlasse 11y ago
      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.
      - cautious_int 11y ago
        The conditional move still depends on both values taken from the array, via other variables.

cautious_int 11y ago

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.

twoodfin 11y ago
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?
- cautious_int 11y ago
  Well a branch will fetch the incorrect cache line if it mispredicts, but a conditional move will fetch both cache lines every time.
  - rrrlasse 11y ago
    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.
    - cautious_int 11y ago
      The conditional move still depends on both values taken from the array, via other variables.