4 ms·

>gcc has __builtin_expect_with_probability(cond, 0, 0.5) but it does nothing (tested v10). ↩ I wonder what could possibly be the use of this builtin. Branch pr

by foldr 3y ago

>gcc has __builtin_expect_with_probability(cond, 0, 0.5) but it does nothing (tested v10). ↩ I wonder what could possibly be the use of this builtin. Branch prediction varies enough between different processors that it seems unlikely that anything useful could be done with a fine-grained probability estimate.

twoodfin 3y ago
Presumably it’s not about matching the dynamic branch prediction estimate but rather exploiting static (or profile-provided) information to assist other optimizations. Inlining seems like a natural application: Inlining is perhaps the most critical optimization to get right, and getting it right is a complex balance of frequency of use vs. added code bloat and associated further optimization cost. Having more than one bit of branch-likelihood as input to these decisions could easily be helpful.
- foldr 3y ago
  Good point. That's the only plausible explanation in this thread, I think. However, if you're at the level of performance tuning where you want to optimize inlining beyond the compiler defaults, I would have thought that it would make more sense to just experiment with forcing certain functions to be inlined or not.
gpderetta 3y ago
I think it is used for code layout: typically you want to make the most often taken branch as fallthrough as it can be slightly faster even when perfectly predicted. I also tried (and failed) to use expect with probability to generate a cmov, but in retrospect it is obvious: the parameter is not the prediction probability, but the taken/not-taken probability, and even a branch that goes either way with 50% probability can still be predicted perfectly (for example a branch that switches every other iteration), so the parameter can't be used to decide between predication and prediction. edit: what we really need is an [[unpredictable]] attribute.
- twoodfin 3y ago
  Indeed: A branch taken 50% of the time can be readily predicted 100% of the time if it follows a pattern the CPU can infer. Why you have to be careful choosing realistic input data if you are microbenchmarking at this level for a real purpose.
- pixelesque 3y ago
  clang has one: https://clang.llvm.org/docs/LanguageExtensions.html#builtin-unpredictable https://clang.llvm.org/docs/LanguageExtensions.html#builtin-...
  - ot 3y ago
    Which also does not affect cmov conversion. Every time this comes up I bring up this long-standing LLVM bug: https://bugs.llvm.org/show_bug.cgi?id=40027 https://bugs.llvm.org/show_bug.cgi?id=40027
    - dzaima 3y ago
      __builtin_unpredictable is gonna be fixed in LLVM/clang 17: https://github.com/llvm/llvm-project/commit/09515f2c20111628ce81ad5f40e12e5f6af5ed2f https://github.com/llvm/llvm-project/commit/09515f2c20111628... (also, bugs.llvm.org is old; the more up-to-date (but still open) issue is https://github.com/llvm/llvm-project/issues/39374 https://github.com/llvm/llvm-project/issues/39374)
      - ot 3y ago
        Amazing, finally!!!
- foldr 3y ago
  >typically you want to make the most often taken branch as fallthrough as it can be slightly faster even when perfectly predicted. Sure, but that application doesn't require a fine-grained probability estimate.
wongarsu 3y ago
At least when I last read it a couple years ago, Intel's optimization manual recommends certain code layouts. For example in the absence of better information a conditional jump backwards would be predicted as true (because that's what loops look like) while a jump forward is seen as less likely to happen (error conditions and else branches look like that). Not sure how consistent this is across architectures, and how useful it still is. But at least it used to be a thing
- kragen 3y ago
  pretty common but not, as i thought, universal since stretch https://en.wikipedia.org/wiki/Branch_predictor#Static_branch_prediction https://en.wikipedia.org/wiki/Branch_predictor#Static_branch... but the only simpler approach is 'predict not taken' which in a sense is what a cortex-m0 does
Pannoniae 3y ago
Read https://en.algorithmica.org/hpc/pipelining/branching/ https://en.algorithmica.org/hpc/pipelining/branching/ and the following chapter. TL;DR: you can generate different, and more efficient code if you know how much it is going to be mispredicted.
- gpderetta 3y ago
  The built-in doesn't provide misprediction information to the compiler.
- foldr 3y ago
  Nothing in that link shows how a compiler could make use of a fine-grained probability estimate in a practical way to guide optimizations. I'm perfectly aware of the general concept of branch prediction and the annotations that certain architectures have in their instruction sets.
bjourne 3y ago
There are ARM processors where bits in the branch instructions encode whether they should be predicted as taken or not. So on such architectures such hints can be useful. On x86-64, however, they are afaik completely useless (from an optimization perspective).

by foldr 3y ago

twoodfin 3y ago

Presumably it’s not about matching the dynamic branch prediction estimate but rather exploiting static (or profile-provided) information to assist other optimizations. Inlining seems like a natural application: Inlining is perhaps the most critical optimization to get right, and getting it right is a complex balance of frequency of use vs. added code bloat and associated further optimization cost. Having more than one bit of branch-likelihood as input to these decisions could easily be helpful.

foldr 3y ago
Good point. That's the only plausible explanation in this thread, I think. However, if you're at the level of performance tuning where you want to optimize inlining beyond the compiler defaults, I would have thought that it would make more sense to just experiment with forcing certain functions to be inlined or not.

gpderetta 3y ago

I think it is used for code layout: typically you want to make the most often taken branch as fallthrough as it can be slightly faster even when perfectly predicted. I also tried (and failed) to use expect with probability to generate a cmov, but in retrospect it is obvious: the parameter is not the prediction probability, but the taken/not-taken probability, and even a branch that goes either way with 50% probability can still be predicted perfectly (for example a branch that switches every other iteration), so the parameter can't be used to decide between predication and prediction. edit: what we really need is an [[unpredictable]] attribute.

twoodfin 3y ago
Indeed: A branch taken 50% of the time can be readily predicted 100% of the time if it follows a pattern the CPU can infer. Why you have to be careful choosing realistic input data if you are microbenchmarking at this level for a real purpose.
pixelesque 3y ago
clang has one: https://clang.llvm.org/docs/LanguageExtensions.html#builtin-unpredictable https://clang.llvm.org/docs/LanguageExtensions.html#builtin-...
- ot 3y ago
  Which also does not affect cmov conversion. Every time this comes up I bring up this long-standing LLVM bug: https://bugs.llvm.org/show_bug.cgi?id=40027 https://bugs.llvm.org/show_bug.cgi?id=40027
  - dzaima 3y ago
    __builtin_unpredictable is gonna be fixed in LLVM/clang 17: https://github.com/llvm/llvm-project/commit/09515f2c20111628ce81ad5f40e12e5f6af5ed2f https://github.com/llvm/llvm-project/commit/09515f2c20111628... (also, bugs.llvm.org is old; the more up-to-date (but still open) issue is https://github.com/llvm/llvm-project/issues/39374 https://github.com/llvm/llvm-project/issues/39374)
    - ot 3y ago
      Amazing, finally!!!
foldr 3y ago
>typically you want to make the most often taken branch as fallthrough as it can be slightly faster even when perfectly predicted. Sure, but that application doesn't require a fine-grained probability estimate.

wongarsu 3y ago

At least when I last read it a couple years ago, Intel's optimization manual recommends certain code layouts. For example in the absence of better information a conditional jump backwards would be predicted as true (because that's what loops look like) while a jump forward is seen as less likely to happen (error conditions and else branches look like that). Not sure how consistent this is across architectures, and how useful it still is. But at least it used to be a thing

kragen 3y ago
pretty common but not, as i thought, universal since stretch https://en.wikipedia.org/wiki/Branch_predictor#Static_branch_prediction https://en.wikipedia.org/wiki/Branch_predictor#Static_branch... but the only simpler approach is 'predict not taken' which in a sense is what a cortex-m0 does

Pannoniae 3y ago

Read https://en.algorithmica.org/hpc/pipelining/branching/ https://en.algorithmica.org/hpc/pipelining/branching/ and the following chapter. TL;DR: you can generate different, and more efficient code if you know how much it is going to be mispredicted.

gpderetta 3y ago
The built-in doesn't provide misprediction information to the compiler.
foldr 3y ago
Nothing in that link shows how a compiler could make use of a fine-grained probability estimate in a practical way to guide optimizations. I'm perfectly aware of the general concept of branch prediction and the annotations that certain architectures have in their instruction sets.

bjourne 3y ago

There are ARM processors where bits in the branch instructions encode whether they should be predicted as taken or not. So on such architectures such hints can be useful. On x86-64, however, they are afaik completely useless (from an optimization perspective).