<p>Branch prediction information can <a href="https://stackoverflow.com/a/11227902/16217248">affect performance</a>. Languages to provide programmers with ways to provide branch prediction hints to improve performance of code. One option is C++ <code>[[likely]]</code> and <code>[[unlikely]]</code> attributes:</p>
<pre class="lang-cpp prettyprint-override"><code>if (!(ptr = malloc(size))) {
    [[unlikely]];
    fputs(&quot;OUT OF MEMORY!1&quot;, stderr);
    halt_and_catch_fire();
}
</code></pre>
<p>Attributes are typically applied to types or variables, so having a standalone one is counter intuitive.</p>
<p>Another way is applying the hint directly to the conditional expression:</p>
<pre class="lang-cpp prettyprint-override"><code>if (__builtin_expect(!(ptr = malloc(size)), 0)) {
    // ...
}
</code></pre>
<p>Which in a more established language might be a <em>qualifier/modifier</em> to a <code>bool</code> type:</p>
<pre class="lang-cpp prettyprint-override"><code>if ((unlikely bool)!(ptr = malloc(size))) {
    // ...
}
</code></pre>
<p>Which syntax options would be the most suitable for a C-style language and why? What are there advantages and disadvantages?</p>

<syntax><optimization><branch-prediction><hints>
Syntax options for providing branch prediction information
CC BY-SA 4.0
2023-05-25T20:48:16.190Z
It's not clear what you mean by "semantic options" ─ branch prediction hints only affect performance, not program behaviour. Though I guess in some sense having probabilities be represented in the type system is sort of a semantic decision, particularly if it affects assignability (e.g. you are forbidden to assign a `likely bool` to an `unlikely bool`).
kaya3
CC BY-SA 4.0
2023-05-25T21:08:20.513Z
A likely/unlikely annotation on the type doesn't make sense: likeliness is about the branch, not about the condition. Cc @kaya3
Gilles 'SO- stop being evil'
CC BY-SA 4.0
2023-05-25T21:10:07.063Z
@Gilles'SO-stopbeingevil' It's one of the ideas from the question ─ a cast to type "unlikely bool". It's not obvious to me that such a type doesn't make sense.
kaya3
CC BY-SA 4.0
2023-05-25T21:14:20.320Z
Hmmm. I suppose a likeliness annotation does make sense on an expression, and in particular on a function result. For example `malloc` returns either a valid pointer (likely) or null (unlikely). But the likeliness information is finicky. It does flow through a wrapper function. But it stops being true after it's been tested or after something has happened. So maybe it's some form of linear type annotation?
Gilles 'SO- stop being evil'
CC BY-SA 4.0
2023-05-25T21:23:30.083Z
Swift has [`_fastPath` and `_slowPath`](https://github.com/apple/swift/blob/main/docs/StandardLibraryProgrammersManual.md#_fastpath-and-_slowpath) but they can only be called from within the standard library.
Bbrk24
<p>There are a couple separate concerns here.</p>
<p>First, what can we actually do with this information?</p>
<p>Second, how should we represent it in the syntax and/or type system?</p>
<p>I think <code>unlikely bool</code> makes sense for C and C++. Here’s my reasoning, a short elaboration of the feature, and a few ideas for alternatives.</p>
<h1>What can we do?</h1>
<h2>Deciding how to generate code</h2>
<p>If a path is unlikely, then we should move its code out of the main path of a function or the primary code paths in the executable, a.k.a. <em>outlining</em>. That way, code that is more likely to run is also more likely to be available in the instruction cache at the time it’s needed. For the same reason, we might optimise such code for small size, rather than speed. The probability of a loop condition also corresponds to the expected number of iterations of the loop, which may affect other choices, such as whether to unroll it.</p>
<p>This is basically how GCC uses <code>__builtin_expect(actual, expected)</code>. It assigns a high probability to a branch—by default, this is the same as <code>__builtin_expect_with_probability(actual, expected, probability)</code> with <code>probability</code> set to <code>0.90</code>, meaning 90%. If a code path contains a call to a function with the <code>hot</code> or <code>cold</code> attribute, then that path is considered more or less likely. (In principle, “unreachable” and “no-return” attributes could also be implemented using this mechanism, by assigning a probability of 0.)</p>
<h2>Deciding what code to generate</h2>
<p>If the target instruction set offers ops for prefetching, then we could emit them to begin fetching data and instructions for an upcoming code path, some suitable number of cycles ahead of time, depending on the target microarchitecture.</p>
<p>For instance, x86 has a <code>prefetch</code> instruction, which allows fetching <em>data</em> into a certain level of cache. Broadly speaking, Intel processors distinguish code from data only in cache level 1, but levels 2 and higher are “unified”. So this op can’t be used to control ifetch directly, but prefetching into L2 may reduce the latency of an ifetch. This might be useful for code paths that thwart the processor’s branch prediction <em>despite</em> being quite likely. I think it would be most directly useful for encoding a notion of “urgency” or “emergency”: <em>unlikely</em> code paths, which nevertheless must run <em>immediately</em> when they do run.</p>
<h1>The status quo</h1>
<p>The branch probability is a property of the code itself, not just the value of a condition, so in principle it <em>should</em> be attached to a statement. But for example, <code>__builtin_expect</code> is only meaningful in an <code>if</code> or loop condition, and Clang only uses <code>[[likely]]</code> and <code>[[unlikely]]</code> annotations in a few special cases.</p>
<ol>
<li><code>(<b>if</b>|<b>for</b>|<b>while</b>) <b>(</b> … <b>)</b> <b>[[</b> <i>likelihood</i> <b>]]</b> <i>statement</i></code></li>
<li><code><b>else</b> <b>[[</b> <i>likelihood</i> <b>]]</b> <i>statement</i></code></li>
<li><code><b>[[</b> <i>likelihood</i> <b>]]</b> (<b>case</b> … | <b>default</b>) <b>:</b> <i>statement</i></code></li>
</ol>
<p>Clang will ignore these annotations in many code patterns that you might expect to use this probability information.</p>
<ol>
<li><code>(<b>if</b>|<b>for</b>|<b>while</b>) <b>(</b> … <b>)</b> <b>{</b> <b>[[</b> <i>likelihood</i> <b>]]</b> <i>statement</i> <i>statements</i> <b>}</b></code></li>
<li><code><b>else</b> <b>{</b> <b>[[</b> <i>likelihood</i> <b>]]</b> <i>statement</i> <i>statements</i> <b>}</b></code></li>
<li><code><b>if</b> <b>(</b> … <b>)</b> <b>{</b> … <b>return</b> … <b>;</b> <b>}</b> <b>[[</b> <i>likelihood</i> <b>]]</b> <i>statement</i></code></li>
<li><code>f<b>(</b> … <b>)</b><b>;</b> <b>[[</b> <i>likelihood</i> <b>]]</b> <i>statement</i></code></li>
</ol>
<p>This could be considered just a limitation of these compilers, but I think it goes a little deeper than that. These languages have a deep distinction between statements and expressions, and statements aren’t first-class objects—they don’t have types, so there isn’t a natural place to put this information in the type system. As such, there’s no standard or other incentive to implement this consistently with another compiler. This is the kind of thing that leads to “butterfly programming”: a programmer tries to optimise their code through a vague understanding of profiling statistics and nebulous influence over compiler heuristics.</p>
<h1>C and C++</h1>
<p>Although a branch probability is a property of <em>code</em>—basic blocks—and not the <em>value</em> of the condition, because C and C++ <em>don’t</em> treat code as a first-class object, the condition is the natural place to consider it.</p>
<p>There’s a close analogy with the <code>volatile</code> qualifier: volatility is properly about <em>accesses</em> to a value, and not the data type itself; but the modifier sets the default <em>interpretation</em> of an access.</p>
<p>So, one possible interpretation closely follows the lines of <code>const</code> and <code>volatile</code>:</p>
<ul>
<li><code>likely bool b;</code> = <code>bool likely b;</code> declares a <code>bool</code> that is likely to be <code>true</code></li>
<li><code>likely int i;</code> declares an <code>int</code> likely to be nonzero (thus interpreted as true in a Boolean context)</li>
<li><code>T *likely p;</code> declares a pointer likely to be non-null</li>
<li><code>unlikely bool</code> (<code>unlikely int</code>, <code>T *unlikely</code>, &amp;c.) are likely to be <code>false</code> (zero, null, &amp;c.)</li>
<li><code>likely</code> &amp; <code>unlikely</code> modifiers can be safely added or removed by casting</li>
<li>The result of <code>&amp;&amp;</code> is <code>likely</code> just when <em>both</em> of its operands are <code>likely</code></li>
<li>The result of <code>||</code> is <code>likely</code> just when <em>either</em> of its operands is <code>likely</code></li>
</ul>
<p>These would guide the annotation of each statement and substatement with its likelihood, let’s say <code>warm</code> or <code>cool</code>, which is either specified on the statement or inferred from its enclosing statement. True branches and bodies of loops are warm by default when their conditions are <em>likely</em>; false branches and the statement after a loop or one-sided <code>if</code> are warm when <em>unlikely</em>.</p>
<p>This specification would provide a standard for computing this information, while still allowing compilers to choose (and, hopefully, <em>document</em>) their own methods of aggregating it and making optimisation decisions based on it. One compiler might use a simple weighted average, while another might use some form of <a href="https://www.evanmiller.org/how-not-to-sort-by-average-rating.html" rel="nofollow noreferrer">confidence sorting</a>.</p>
<h1>Alternatives</h1>
<p>More powerful methods are possible, of course, but also more complex. You could make statements first-class objects, whose types are monadic actions indexed with their probabilities. You could replace the binary “likely truthy or not” with a relation amongst possible values and their predicted weights:</p>
<pre><code>{
  (TREW, 90),  // likely to be truthy
  (FOLS,  9),  // unlikely to be falsy
  (&lt;0,    0),  // can’t be negative (unsafe!)
  (else,  1)   // unlikely to be anything else
}
</code></pre>
<p>And this would let you store the result of profile-guided optimisation in the source, making it versionable and reproducible. You could even encode the expected pattern of use of an object—e.g. an arbitrary integer vs. a monotonic counter.</p>
<p>However, this quickly runs into challenges. You need to carefully manage the size and complexity of propositions involved in a program analysis, or it may seriously impact compiler performance without meaningfully improving quality of results.</p>

CC BY-SA 4.0
2023-05-29T21:48:26.057Z
2023-06-05T01:14:14.100Z
2023-06-05T01:14:14.100Z
Jon Purdy
# Syntax options for providing branch prediction information
Posted by: username_0 on 2023-05-25
Branch prediction information can affect performance. Languages to provide programmers with ways to provide branch prediction hints to improve performance of code. One option is C++ [[likely]] and [[unlikely]] attributes:
if (!(ptr = malloc(size))) {
    [[unlikely]];
    fputs("OUT OF MEMORY!1", stderr);
    halt_and_catch_fire();
}

Attributes are typically applied to types or variables, so having a standalone one is counter intuitive.
Another way is applying the hint directly to the conditional expression:
if (__builtin_expect(!(ptr = malloc(size)), 0)) {
    // ...
}

Which in a more established language might be a qualifier/modifier to a bool type:
if ((unlikely bool)!(ptr = malloc(size))) {
    // ...
}

Which syntax options would be the most suitable for a C-style language and why? What are there advantages and disadvantages?
**Tags:** syntax optimization branch-prediction hints
> **Comments:**
> **username_1**: It's not clear what you mean by "semantic options" ─ branch prediction hints only affect performance, not program behaviour. Though I guess in some sense having probabilities be represented in the type system is sort of a semantic decision, particularly if it affects assignability (e.g. you are forbidden to assign a `likely bool` to an `unlikely bool`).  
> **username_2**: A likely/unlikely annotation on the type doesn't make sense: likeliness is about the branch, not about the condition. Cc @kaya3  
> **username_1**: @Gilles'SO-stopbeingevil' It's one of the ideas from the question ─ a cast to type "unlikely bool". It's not obvious to me that such a type doesn't make sense.  
> **username_2**: Hmmm. I suppose a likeliness annotation does make sense on an expression, and in particular on a function result. For example `malloc` returns either a valid pointer (likely) or null (unlikely). But the likeliness information is finicky. It does flow through a wrapper function. But it stops being true after it's been tested or after something has happened. So maybe it's some form of linear type annotation?  
> **username_3**: Swift has [`_fastPath` and `_slowPath`](https://github.com/apple/swift/blob/main/docs/StandardLibraryProgrammersManual.md#_fastpath-and-_slowpath) but they can only be called from within the standard library.  
---
## 1 answers
### Answer by username_4 on 2023-05-29. Score: 4 | Accepted answer
There are a couple separate concerns here.
First, what can we actually do with this information?
Second, how should we represent it in the syntax and/or type system?
I think unlikely bool makes sense for C and C++. Here’s my reasoning, a short elaboration of the feature, and a few ideas for alternatives.
What can we do?
Deciding how to generate code
If a path is unlikely, then we should move its code out of the main path of a function or the primary code paths in the executable, a.k.a. outlining. That way, code that is more likely to run is also more likely to be available in the instruction cache at the time it’s needed. For the same reason, we might optimise such code for small size, rather than speed. The probability of a loop condition also corresponds to the expected number of iterations of the loop, which may affect other choices, such as whether to unroll it.
This is basically how GCC uses __builtin_expect(actual, expected). It assigns a high probability to a branch—by default, this is the same as __builtin_expect_with_probability(actual, expected, probability) with probability set to 0.90, meaning 90%. If a code path contains a call to a function with the hot or cold attribute, then that path is considered more or less likely. (In principle, “unreachable” and “no-return” attributes could also be implemented using this mechanism, by assigning a probability of 0.)
Deciding what code to generate
If the target instruction set offers ops for prefetching, then we could emit them to begin fetching data and instructions for an upcoming code path, some suitable number of cycles ahead of time, depending on the target microarchitecture.
For instance, x86 has a prefetch instruction, which allows fetching data into a certain level of cache. Broadly speaking, Intel processors distinguish code from data only in cache level 1, but levels 2 and higher are “unified”. So this op can’t be used to control ifetch directly, but prefetching into L2 may reduce the latency of an ifetch. This might be useful for code paths that thwart the processor’s branch prediction despite being quite likely. I think it would be most directly useful for encoding a notion of “urgency” or “emergency”: unlikely code paths, which nevertheless must run immediately when they do run.
The status quo
The branch probability is a property of the code itself, not just the value of a condition, so in principle it should be attached to a statement. But for example, __builtin_expect is only meaningful in an if or loop condition, and Clang only uses [[likely]] and [[unlikely]] annotations in a few special cases.

(if|for|while) ( … ) [[ likelihood ]] statement
else [[ likelihood ]] statement
[[ likelihood ]] (case … | default) : statement

Clang will ignore these annotations in many code patterns that you might expect to use this probability information.

(if|for|while) ( … ) { [[ likelihood ]] statement statements }
else { [[ likelihood ]] statement statements }
if ( … ) { … return … ; } [[ likelihood ]] statement
f( … ); [[ likelihood ]] statement

This could be considered just a limitation of these compilers, but I think it goes a little deeper than that. These languages have a deep distinction between statements and expressions, and statements aren’t first-class objects—they don’t have types, so there isn’t a natural place to put this information in the type system. As such, there’s no standard or other incentive to implement this consistently with another compiler. This is the kind of thing that leads to “butterfly programming”: a programmer tries to optimise their code through a vague understanding of profiling statistics and nebulous influence over compiler heuristics.
C and C++
Although a branch probability is a property of code—basic blocks—and not the value of the condition, because C and C++ don’t treat code as a first-class object, the condition is the natural place to consider it.
There’s a close analogy with the volatile qualifier: volatility is properly about accesses to a value, and not the data type itself; but the modifier sets the default interpretation of an access.
So, one possible interpretation closely follows the lines of const and volatile:

likely bool b; = bool likely b; declares a bool that is likely to be true
likely int i; declares an int likely to be nonzero (thus interpreted as true in a Boolean context)
T *likely p; declares a pointer likely to be non-null
unlikely bool (unlikely int, T *unlikely, &c.) are likely to be false (zero, null, &c.)
likely & unlikely modifiers can be safely added or removed by casting
The result of && is likely just when both of its operands are likely
The result of || is likely just when either of its operands is likely

These would guide the annotation of each statement and substatement with its likelihood, let’s say warm or cool, which is either specified on the statement or inferred from its enclosing statement. True branches and bodies of loops are warm by default when their conditions are likely; false branches and the statement after a loop or one-sided if are warm when unlikely.
This specification would provide a standard for computing this information, while still allowing compilers to choose (and, hopefully, document) their own methods of aggregating it and making optimisation decisions based on it. One compiler might use a simple weighted average, while another might use some form of confidence sorting.
Alternatives
More powerful methods are possible, of course, but also more complex. You could make statements first-class objects, whose types are monadic actions indexed with their probabilities. You could replace the binary “likely truthy or not” with a relation amongst possible values and their predicted weights:
{
  (TREW, 90),  // likely to be truthy
  (FOLS,  9),  // unlikely to be falsy
  (<0,    0),  // can’t be negative (unsafe!)
  (else,  1)   // unlikely to be anything else
}

And this would let you store the result of profile-guided optimisation in the source, making it versionable and reproducible. You could even encode the expected pattern of use of an object—e.g. an arbitrary integer vs. a monotonic counter.
However, this quickly runs into challenges. You need to carefully manage the size and complexity of propositions involved in a program analysis, or it may seriously impact compiler performance without meaningfully improving quality of results.
---
