Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Branch predictor: How many “if”s are too many?

blog.cloudflare.com

Post reply on HN
Print view View original

61–70 of 109 posts

Re: Branch predictor: How many “if”s are too many?

#61

Post by lttlrck »

I feel like I'm missing something in the conclusion.

The initial question is:

  if (debug) {
    log("...");
  }
> Is it ok to have if clauses that will basically never be run?

And the summary is:

> If it's never-taken, it's probably ok. I found no evidence that such branches incur any extra cost. But do avoid always-taken branches and function calls.

However, if debug is false in the initial example, the branch is always taken, it's jumping over the call to log. Such code incurs a penalty - correct?

https://www.godbolt.org/z/o1Yd7oWYa

Re: Branch predictor: How many “if”s are too many?

#62

Post by Scaevolus »

lttlrck wrote: post #61

I feel like I'm missing something in the conclusion. The initial question is: if (debug) { log("..."); } > Is it ok to have if clauses that will basically never be run? And the summary is: > If it's never-taken, it's probably ok. I found no evidence that such branches incur any extra cost. But do avoid always-taken branches and function calls. However, if debug is false in the initial example, the branch is always ta…

Given appropriate likeliness annotations or profile-guided optimization, it's possible for the compiler to _invert_ the conditional and move the log statement to a "cold" section of code outside of the main flow, making it a never-taken branch.

Re: Branch predictor: How many “if”s are too many?

#63

Post by parhaml »

hinkley wrote: post #30
jugg1es wrote: post #21

This is a pretty amazing analysis that answers questions we probably all had as newbie programmers before realizing that code readability mattered more than efficiency 99.9% of the time.

The goalposts are constantly changing, but there are refactorings that achieve both. As a student, real world performance analysis was one of the ways I kept myself engaged in otherwise sometimes tedious curricula. After college I landed a job far away from home only to discover their software was so slow I was embarrassed to be associated with it, so I got a quick self-directed study in practical optimization. On an…

I appreciate this comment. We can develop these little ingrained patterns that keep things 'optimal' and at the same time think about future us having to read the code again.

I know that even 1 week future me appreciates readable code at the expense of a _little_ bit of performance.

Re: Branch predictor: How many “if”s are too many?

#64

Post by lttlrck »

Scaevolus wrote: post #62
lttlrck wrote: post #61

I feel like I'm missing something in the conclusion. The initial question is: if (debug) { log("..."); } > Is it ok to have if clauses that will basically never be run? And the summary is: > If it's never-taken, it's probably ok. I found no evidence that such branches incur any extra cost. But do avoid always-taken branches and function calls. However, if debug is false in the initial example, the branch is always ta…

Given appropriate likeliness annotations or profile-guided optimization, it's possible for the compiler to _invert_ the conditional and move the log statement to a "cold" section of code outside of the main flow, making it a never-taken branch.

Yes. I guess that's covered by "it's probably ok"... I'm going to play in godbolt now.

Re: Branch predictor: How many “if”s are too many?

#65

Post by Scaevolus »

lttlrck wrote: post #64
Scaevolus wrote: post #62

Earlier quoted context omitted.

Given appropriate likeliness annotations or profile-guided optimization, it's possible for the compiler to _invert_ the conditional and move the log statement to a "cold" section of code outside of the main flow, making it a never-taken branch.

Yes. I guess that's covered by "it's probably ok"... I'm going to play in godbolt now.

-O2 turns it into a "jump if nonzero" without any extra annotations: https://www.godbolt.org/z/j9dfrbosv

Re: Branch predictor: How many “if”s are too many?

#66

Post by sischoel »

initplus wrote: post #53
omginternets wrote: post #42

Are there any rules-of-thumb for avoiding branch mispredictions, other than reducing the number of conditional branches? For example (not that I expect this to be true), something of the same sort as "your if block should contain the rare condition".

If you have perf critical branches in your code, you should try and make them as predictable as possible. Sometimes that means using a different approach that is algorithmically worse, but has much more predictable branches. Classic example is linear search is faster than binary search for “small” lists. The item == myItem branch is only taken once at the end. Meanwhile binary search will take the branches of it’s co…

Although it is possible to create branchless binary search. Here is one article: https://schani.wordpress.com/2010/04/30/linear-vs-binary-sea..., there are probably other ways to do that.

Another interesting question where one could sink a lot of time is how do to binary search on GPU's using multiple threads. There branching in multiple threads at the same time is also bad, but for slightly different reasons.

Re: Branch predictor: How many “if”s are too many?

#67

Post by berkut »

Veedrac wrote: post #49
berkut wrote: post #46

Earlier quoted context omitted.

You can use the __builtin_expect keyword on GCC and clang. It does make a difference (HPC code uses it quite a bit because of this), but as it's done manually, results obviously vary depending on processor, and there's a limit to how far you can take it. Trying not to branch (not always possible) is best... Basically, it's like manually doing profile-guided optimisation - you look at perf or vtune, and add the above…

Note that this is not targeted to branch prediction, but compiler optimizations. It should be done carefully, because it tends to have a larger downside than its upside, and the changes the compiler makes based on it can be unpredictable, and unstable. > Trying not to branch (not always possible) is best... Branches are often faster than branch-free methods, since they can speculate certain data dependencies away.

> Branches are often faster than branch-free methods, since they can speculate certain data dependencies away.

And often they're slower, since predicting some branches is often impossible due to the data :) So the processor ends up miss-predicting most of the time, thinking it knows what happened last time.

It all depends on what you're doing.

Re: Branch predictor: How many “if”s are too many?

#68

Post by andrepd »

lmilcin wrote: post #29
jugg1es wrote: post #21

This is a pretty amazing analysis that answers questions we probably all had as newbie programmers before realizing that code readability mattered more than efficiency 99.9% of the time.

In most applications you will not be able to get to the level of performance when any of this is going to matter. For example, if you program Python then there is so much more conditionals in Python runtime itself than you will not see any difference from couple of your conditionals being predicted better or worse. You will also be doing a lot of other stuff (like spending time in framework code, calling libraries, p…

I think that's more of an indictment of how bad the concept of "production python" is.

Re: Branch predictor: How many “if”s are too many?

#69

Post by Narishma »

lmilcin wrote: post #31
dusted wrote: post #2

I'm wondering how you guys would optimize that code ? My naive approach would be something like this: const int numCountryIndicies = however many there are..; const char* countries = "A1\0A2\0..."; return (cc < numCountryIndicies)?countries[cc*2]:"UNKNOWN";

> I'm wondering how you guys would optimize that code ? Run it on infinite multiverse, construct a mechanism to destroy the Universe every time branch predictor did not predict every single conditional correctly.

It reaches out it reaches out it reaches out it reaches out— One hundred and thirteen times a second.

Re: Branch predictor: How many “if”s are too many?

#70

Post by Const-me »

Denvercoder9 wrote: post #55
majke wrote: post #8

Earlier quoted context omitted.

Modern freshest gcc 11 can optimize the if's nicely https://godbolt.org/z/771foExcG getCountry: mov eax, OFFSET FLAT:.LC0 cmp edi, 258 ja .L1 mov edi, edi mov rax, QWORD PTR CSWTCH.1[0+rdi*8] .L1: ret

Anyone know what the purpose of the mov edi, edi instruction there is? Edited to add: I understand that it's a NOP, but why would the compiler emit one here?

That instruction clears upper 4 bytes of the rdi register. Note the next instruction uses rdi in the address.

edi register is the lower 4 bytes of rdi. Instructions which write these smaller pieces zero out the unused higher bytes of the destination registers. This helps with performance because eliminates data dependencies on the old values in these higher bytes.

Post reply on HN