Compiler hint for unlikely/likely for if branches

Quoting unlikely in std::intrinsics - Rust

This is a nightly-only experimental API. (core_intrinsics)
This intrinsic does not have a stable counterpart.

Question: is there a way in Rust to signal to compiler that a given if branch is likely/unlikely without using intrinsics, so we can use it in stable, or is the above the only way ?

2 Likes

You can use the cold attribute on functions. Then any branch containing that function call will be marked unlikely

4 Likes

What precisely does LLVM do with that information? I'm guessing the net result is that the probability goes up that a #[cold] branch is thrown out of the cpu cache, but how is this accomplished?

Here is how hashbrown does to implement likely and unlikely on stable:

#[inline]
#[cold]
fn cold() {}

#[inline]
fn likely(b: bool) -> bool {
    if !b { cold() }
    b
}

#[inline]
fn unlikely(b: bool) -> bool {
    if b { cold() }
    b
}
13 Likes

This reminds me of Schrodinger's cat -- I simultaneously understand and do not understand how this code works.

One argument (for it working):

  1. fn cold() {} optimizes to no-op
  2. if b { cold() } and if !b {cold() } both optimizes to no-op
  3. the cold() gives the LLVM a hint that one particular branch if expensive to inline, so it inlines he other branch instead (and does a jmp for the cold() branch)

Argument (for it not working):
This looks like lots of black magic relying on the precise order of compiler/optimization phases and what is optimized away / kept at which phase.

1 Like

Can somebody explain to me what this is about?

I mean, as far as I can tell most modern processors have branch predictors and speculative execution. They execute everything and anything until they can determine which result is actually required.

The optimal flow is found at run time.

How could any likely/unlikely hint help?

The hint affects code ordering. The code for the hot path is placed right after the branch, so it is more likely to be in the CPU cache already. The cold path is placed after the hot path, where it is more likely to cause a cache miss.

The hint also affects inlining. The LLVM optimizer adjusts its inlining threshold so that “cold” functions are inlined less often. This reduces instruction bloat without slowing down the hot path, and it can further improve cache locality.

11 Likes

Another thing worth considering is PGO. One of the things PGO exposes to the optimizer is exactly what likely/unlikely are communicating: the relative frequency of taking various brach targets.

Personally, I think #[cold] is a useful attribute for telling the optimizer to keep some function call out of the hot path, but that explicit likely/unlikely hints are much harder to use correctly and much easier to use detrimentally.

Any optimization hinting should be done only when improvement is measured by benchmarking, and not on a whim or by gut feeling, because performance at that level is hard to predict, and the compiler is almost surely better at it than you are. And then, when hinting is shown to be beneficial, you use the simplest tool available -- and here, I'd argue that PGO is actually better than un/likely hinting, because it lets the compiler discover the execution profile, rather than the programmer divining it.

2 Likes

Ah ha. Thanks.

I only use #[cold] on functions that are called infrequently or only once. To me this makes sense -- if I'm only going to call a function a few times per execution of my program, or only once during my programs entire lifetime, it makes sense to ensure that the optimizer doesn't waist all its time trying to optimize that function too much.

Does this technique generalize to either:

if let Some(_) = ... 

or tagging a single arm of a match statement ?

It does. Just put a call to cold() on all match branches you want to be unlikely, or all branches except the one you want to be likely.

See https://llvm.org/docs/LangRef.html#function-attributes:

cold
This attribute indicates that this function is rarely called. When computing edge weights, basic blocks post-dominated by a cold function call are also considered to be cold; and, thus, given low weight.

3 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.