10
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ 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). $\endgroup$
    – kaya3
    Commented May 25, 2023 at 20:48
  • $\begingroup$ A likely/unlikely annotation on the type doesn't make sense: likeliness is about the branch, not about the condition. Cc @kaya3 $\endgroup$ Commented May 25, 2023 at 21:08
  • $\begingroup$ @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. $\endgroup$
    – kaya3
    Commented May 25, 2023 at 21:10
  • $\begingroup$ 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? $\endgroup$ Commented May 25, 2023 at 21:14
  • $\begingroup$ Swift has _fastPath and _slowPath but they can only be called from within the standard library. $\endgroup$
    – Bbrk24
    Commented May 25, 2023 at 21:23

1 Answer 1

4
$\begingroup$

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.

  1. (if|for|while) () [[ likelihood ]] statement
  2. else [[ likelihood ]] statement
  3. [[ likelihood ]] (case … | default) : statement

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

  1. (if|for|while) () { [[ likelihood ]] statement statements }
  2. else { [[ likelihood ]] statement statements }
  3. if () {return; } [[ likelihood ]] statement
  4. 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .