3 ms·

Modern compilers and branch predictors means this doesn't matter 99.9% of the time. If you take the same branch every time 100 times in a row, the processor wi

by wyager 3y ago

Modern compilers and branch predictors means this doesn't matter 99.9% of the time. If you take the same branch every time 100 times in a row, the processor will optimize the cost of the branch away almost entirely. If the branch condition is not volatile, compilers will usually lift it.

bhuber 3y ago
This is mostly true, but sometimes the cost of evaluating the condition itself is non-trivial. For example, if a and b are complex objects, even something as trivial as `if (a.equals(b)) ...` might take a relatively long time if the compiler/runtime can't prove a and b won't be modified between calls. In the worst case, a and b only differ in the last field checked by the equality method, and contain giant collections of some sort that must be iterated recursively to check equality.
- wyager 3y ago
  "If the branch condition is not volatile, compilers will usually lift it" Usually in any program with well-defined semantics (e.g. not using janky multithreaded mutability), this will be true
titzer 3y ago
It's not just the direct cost of a branch, it's the downstream costs as well. Removing (or automatically folding branches in a compiler) can lead to optimizations after the branch. E.g. if (foo > 0) { x = 3; } else { x = 7; } return x * 9; If the compiler (or programmer) knows foo is greater than zero (even if we don't know what it actually is), then the whole thing folds into: return 27; That also means that foo is not even used, so it might get dead-code eliminated. If that gets inlined, then the optimizations just keep stacking up. (not that the article was about that, it's just one implication of removing branches: downstream code can be optimized knowing more). So, in summary, compilers matter.
- RenThraysk 3y ago
  That code shouldn't generate any branching (unless on an odd cpu). A serious compiler should recognise it can be done with a conditional move.
  - titzer 3y ago
    A conditional move is not guaranteed to be faster than a predictable branch. It varies a lot by microarchitecture. It was just an example. Imagine if you had a store in the else branch. Now optimizing away a store means that load elimination may kick in. Folding branches in the compiler unlocks tons of downstream benefits.
- wyager 3y ago
  "If the branch condition is not volatile, compilers will usually lift it."
  - titzer 3y ago
    Lift it where?

by wyager 3y ago

bhuber 3y ago

This is mostly true, but sometimes the cost of evaluating the condition itself is non-trivial. For example, if a and b are complex objects, even something as trivial as `if (a.equals(b)) ...` might take a relatively long time if the compiler/runtime can't prove a and b won't be modified between calls. In the worst case, a and b only differ in the last field checked by the equality method, and contain giant collections of some sort that must be iterated recursively to check equality.

wyager 3y ago
"If the branch condition is not volatile, compilers will usually lift it" Usually in any program with well-defined semantics (e.g. not using janky multithreaded mutability), this will be true

titzer 3y ago

It's not just the direct cost of a branch, it's the downstream costs as well. Removing (or automatically folding branches in a compiler) can lead to optimizations after the branch. E.g. if (foo > 0) { x = 3; } else { x = 7; } return x * 9; If the compiler (or programmer) knows foo is greater than zero (even if we don't know what it actually is), then the whole thing folds into: return 27; That also means that foo is not even used, so it might get dead-code eliminated. If that gets inlined, then the optimizations just keep stacking up. (not that the article was about that, it's just one implication of removing branches: downstream code can be optimized knowing more). So, in summary, compilers matter.

RenThraysk 3y ago
That code shouldn't generate any branching (unless on an odd cpu). A serious compiler should recognise it can be done with a conditional move.
- titzer 3y ago
  A conditional move is not guaranteed to be faster than a predictable branch. It varies a lot by microarchitecture. It was just an example. Imagine if you had a store in the else branch. Now optimizing away a store means that load elimination may kick in. Folding branches in the compiler unlocks tons of downstream benefits.
wyager 3y ago
"If the branch condition is not volatile, compilers will usually lift it."
- titzer 3y ago
  Lift it where?