Portable branch prediction hints

Question

Is there any portable way of doing branch prediction hints? Consider the following example:

  if (unlikely_condition) {
    /* ..A.. */
  } else {
    /* ..B.. */
  }

Is this any different than doing:

  if (!unlikely_condition) {
    /* ..B.. */
  } else {
    /* ..A.. */
  }

Or is the only way to use compiler specific hints? (e.g. __builtin_expect on GCC)

Will compilers treat the if conditions any differently based on the ordering of the conditions?

I wonder whether this could be something C++0x attributes to stick on conditions for `if`? Like `if([[unlikely]] unlikely_condition) { ... }`? Currently the syntax does not allow it. It *does* however allow `if([[unlikely]] bool b = ...) { }`. Maybe one could abuse that :) — Johannes Schaub - litb, Sep 13 '10 at 17:41
GNU code contains a ridiculous amount of `if(likely(...))` junk in completely non-performance-critical code, and IMO this is really bad. For one thing, it doesn't read naturally in English - it sounds like "if this condition is likely to be true" instead of "if this condition is true, which it likely is". And for another, it's just clutter. Unless you have lots of performance-critical conditionals that won't compile to `cmov` or similar already, just ignore branch prediction hinting. — R.. GitHub STOP HELPING ICE, Sep 13 '10 at 18:04
@R.. I think I understand why the Linux kernel is littered with `if(unlikely(...))`. They prefer early exits that make code flow easier to follow. If they did not do this then the static branch prediction would always fail. — Oskar N., Sep 13 '10 at 21:53
And it would make Linux 0.00001% slower. Not measurable. If it is, simply put this crap in the few conditionals where it is measurable, not everywhere. — R.. GitHub STOP HELPING ICE, Sep 13 '10 at 23:24
It's also a kind of documental hint. I use it often to distinguish between active work code and exceptional error handling code. This said on the architecture I work on, it's a quite useful mechaism as the ISA has hint bits in the branch instruction (SPARC). — Patrick Schlüter, Sep 14 '10 at 09:56
Oskar: I think @R.. was referring to glibc, which is, err... let's say not as nice to read as the Linux Kernel. But maybe it's just me, you know, everyone has different tastes. — ninjalj, Oct 01 '11 at 09:54
@tristopia: MIPS also has something similar: branch likely instructions. — ninjalj, Oct 01 '11 at 09:56

score 32 · Accepted Answer · answered Sep 13 '10 at 17:44

The canonical way to do static branch prediction is that if is predicted not-branched (i.e. every if clause is executed, not else), and loops and backward-gotos are taken. So, don't put the common case in else if you expect static prediction to be significant. Getting around an untaken loop isn't as easy; I've never tried but I suppose putting it an an else clause should work pretty portably.

Many compilers support some form of #pragma unroll, but it will still be necessary to guard it with some kind of #if to protect other compilers.

Branch prediction hints can theoretically express a complete description of how to transform a program's flow-control graph and arrange the basic blocks in executable memory… so there are a variety of things to express, and most won't be very portable.

As GNU recommends in the documentation for __builtin_expect, profile-guided optimization is superior to hints, and with less effort.

And VS has PGO too, so it's a win-win. :) – GManNickG Sep 13 '10 at 17:48 — GManNickG, Sep 13 '10 at 17:48

Lior Kogan · Answer 2 · 2011-10-01T09:36:05.403

21

In most cases, the following code

if (a)
{
   ...
}
else
{
    ...
}

is actually

evaluate(A)

if (!A)
{
   jmp p1
}

... code A

   jmp p2

p1:

... code !A

p2:

Note that if A is true, "code A" is already in the pipeline. The processor will see the "jmp p2" command ahead, and will load p2 code to the pipeline.

If A is false, the "code !A" may not be in the pipleline, therefore it may be slower.

Conclusions:

do If(X) if X is more likely than !X
try to evaluate A as early as possible, so that the CPU can dynmically optimize the pipeline.

:

evaluate(A)

do more stuff

if (A)
   ...

edited Oct 01 '11 at 09:36

answered Sep 13 '10 at 17:55

Lior Kogan

19,919
6
53
85

got it! Please keep the 'if' code in braces pls -even though its single line. It's a bit confusing otherwise! – Ayyappa Oct 01 '11 at 08:26
1

"try to evaluate A as early as possible, so that the CPU can dynmically optimize the pipeline." - Can you please provide some pointers for this statement? I want to know how it will do it. – Ayyappa Oct 01 '11 at 08:30
A lot of information here: http://download.intel.com/design/pentiumii/manuals/24281603.pdf – Lior Kogan Oct 01 '11 at 09:34
@LiorKogan link is dead now. Any way to find it again? – Carlos Mar 15 '21 at 10:42
1

@Carlos: yes. Google "Intel 24281603". – Lior Kogan Mar 15 '21 at 11:17

score 7 · Answer 3 · answered Sep 13 '10 at 17:38

7

Optimization is inherently a compiler thing, so you have to use compiler functionality to help it. The language itself doesn't care about (or mandate) optimizations.

So the best you can do without compiler-specific extensions is organize your code in such a way where your compilers will "do the right thing" without help. But if you want to be sure, tap in to compiler extensions. (You might try abstracting them behind the preprocessor, so your code remains portable.)

answered Sep 13 '10 at 17:38

GManNickG

494,350
52
494
543

6

There's plenty of precedent for the language providing optimisation hints, though (`inline`, `restrict`, `register`). Some are more pointful than others on modern compilers. It doesn't matter whether a particular implementation actually does anything with them: if there's a reasonable chance of some doing something useful, then it would be a nice feature. I reckon static branch prediction in the main doesn't meet that criterion, so I don't think it's a bad call to leave it out. It is a judgement on the merits of the case, though, not quite "we don't care about optimisation, ever". – Steve Jessop Sep 13 '10 at 17:55
@Steve: Yeah, I guess I automatically ignore those so I forget about them. You're right. – GManNickG Sep 13 '10 at 18:33
2

I think `restrict` is probably worthwhile as a premature optimisation. It's not going to do any harm, it might do significant good by preventing horrible store/load dependencies, and where it applies it's presumably a documented requirement (as in `memcpy`) whether that's reflected in the source or not. The others (and in C++03), I agree with your resounding "meh" :-) – Steve Jessop Sep 13 '10 at 21:34
@Steve: I agree, I was ignoring `restrict` since it's not part of the current standard. :) – GManNickG Sep 13 '10 at 21:47
Ah, but this is one of those tagged-C-and-C++ questions, where even the simplest answer can disappear in a blizzard of caveats. – Steve Jessop Sep 13 '10 at 22:12
@Steve: Oh, I didn't even see that. :x – GManNickG Sep 13 '10 at 22:32

score 7 · Answer 4 · answered Jan 30 '20 at 18:37

7

C++20 offers likely and unlikely attributes

Allow the compiler to optimize for the case where paths of execution including that statement are more or less likely than any alternative path of execution that does not include such a statement

answered Jan 30 '20 at 18:37

Tony Tannous

14,154
10
50
86

This feature is [not yet available in Clang](https://clang.llvm.org/cxx_status.html#cxx20), unfortunately. – Franklin Yu Apr 15 '20 at 03:15
1

@FranklinYu it seems Clang 12 supports this as per https://en.cppreference.com/w/cpp/compiler_support. – Tony Tannous Dec 04 '20 at 14:09
That’s a good news! Thanks for the update. – Franklin Yu Dec 04 '20 at 19:19

score 1 · Answer 5 · answered Sep 13 '10 at 17:37

1

Just be consistant with what you do. I like to use

if (!(someExpression))

But the compiler should treat this equally.

answered Sep 13 '10 at 17:37

JonH

32,732
12
87
145

score 1 · Answer 6 · answered Sep 13 '10 at 18:06

1

What's wrong with checking for a specific compiler via #ifdef and hiding these things behind a custom macro? You can #define it to expand to the plain expression in cases you don't have a compiler that supports these optimization hints. I recently did something similar with explicit cache prefetches which GCC supports via an intrinsic function.

answered Sep 13 '10 at 18:06

sellibitze

27,611
3
75
95

I've done that. With more than two or three compilers it can become a real mess, if different compilers use different syntax. – David Thornley Sep 13 '10 at 18:29

Portable branch prediction hints

6 Answers6

Linked