About @branchHint

Explain
1

Hi everyone!

I’ve seen lately that a lot of @branchHint(.unlikely) has been added to Zig’s source code, how does the compiler treat these? What kind of optimizations?

Thanks :slight_smile:

3 Likes
2

It avoids jumps for likely case => no cache invalidation.

1 Like
3

Assembly branch instructions, are conditional jumps. There are two paths to follow, the one that the condition holds and the opposite one.

  • CPU can predict the path with @branch(.none) or not a @branch hint at all.
  • @branch(.likely) means that this path is likely to be reached.
  • @branch(.unlikely) means that this path is unlikely to be reached.
  • @branch(.cold) means that this path is unlikely to ever be reached.
  • @branch(.unpredictable) means that it is difficult to predict if this path is reached or not.

For example:

    i = 1000;
    while (i > 0) {
        i -= 1;
        ...
    }

The statements inside while are .likely because they run 999 times, the other path (to skip while) is .unlikely because it runs only one time.

4 Likes
4

How does this work with the hardware? Is there an instruction that tells the gpu to set certain values in the branch predictor? I tried googling but didn’t find anything talking about the details.

5

For x86 it is a branch instruction prefix, since Pentium 4.
0x2e for branch not taken (weak hint) and 0x3e for branch taken (strong hint).

1 Like
6

While there are branch hint instructions, the compiler won’t actually emit these, since they just make the executable bigger with little benefit.

However, they can help the compiler decide between branchless code (with cmov) or actual branches. Or where to put the code of the branch, if it’s unlikely it may make sense to put the code of the branch further away from the hot path.
It can also impact whether the compiler unrolls a loop or not.

But all of these things are rather unpredictable/unreliable. So I’d suggest to always test this with godbolt before actually using this. Normally you are probably just best off with the default branch heuristics the compiler already employs.

9 Likes
7

Yep. I’ve remembered someone’s (quite old) experiment with Linux kernel. The author states that presence/absence of likely/unlikely does not affect performance.

8

There’s one more aspect here which I’m not sure how exactly it should be incorporated but I suspect will be relevant which is fuzz testing. These branch hints tell the fuzzer some metadata about code paths which could be relevant. Again, I’m not sure exactly how to exploit this data, and would welcome suggestions, but at least one thing that comes to mind is to calculate bug priority based on how much the control flow spends in likely vs cold branches.

Edit: already thought of one thing - if a fuzz input has explored a cold branch but not yet explored the non-cold branch of the condition, it should focus on trying to explore the non-cold branch, because probably all the inputs that are going into the cold branch are uninteresting failures - for example if you were fuzzing a programming language it would mostly generate syntax errors, and the syntax error function would be marked cold, so the fuzzer would at least know that when it hits a syntax error that’s less interesting than not making a syntax error.

2 Likes