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

71–80 of 109 posts

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

#71

Post by knorker »

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".

You can hint the compiler: https://en.cppreference.com/w/cpp/language/attributes/likely

Or you can use profile directed optimization, as others mentioned.

In my test recently it reduced branches as a whole by 30%, according to perf stat ./a.out

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

#72

Post by MaxBarraclough »

andromeduck wrote: post #26
MaxBarraclough wrote: post #15

Earlier quoted context omitted.

Following that line, it's never exactly been syntactic sugar. When initializing a const local, you can use the ternary operator on the right hand side of the assignment, but you can't get the same effect using if (short of writing a new function). Similarly, C++ lets you use the ternary operator for the left hand side of an assignment, (a ? b : c) = 42; although you could use an if for this pretty easily.

Wow I had no idea you could use it on the LHS. TIL.

A TIL of my own: it seems not to be allowed in C.

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

#73

Post by astrange »

bob1029 wrote: post #43
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".

I might be off base here, but you would probably do best to not overthink this and let the compiler do its job. Attempting to pre-optimize if statements relative to a branch predictor (a very hardware-specific thing) is probably a massive fool's errand.

The compiler doesn't know how the CPU branch predictor works either. It's not especially good at optimizing this, or guessing if a branch is predictable or not, so you might as well do it yourself.

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

#74

Post by astrange »

the_duke wrote: post #37
xenadu02 wrote: post #27

Earlier quoted context omitted.

You can easily verify this in your specific code base but I believe the compiler prefers not-taken jumps for paths it predicts to be less frequently taken. You can provide hints that the path is a cold one to ensure the compiler uses the most efficient conditional branch layout. On some architectures the compiler will also provide this hint to the CPU (with a prefix, the instruction it selects, or a flag bit in the i…

C++ 20 introduces standard likely/unlikely attributes: https://en.cppreference.com/w/cpp/language/attributes/likely

clang also has `__builtin_unpredictable` which is at least as useful as likely/unlikely.

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

#75

Post by mateo411 »

andrepd wrote: post #68
lmilcin wrote: post #29

Earlier quoted context omitted.

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.

I disagree with that. Production doesn't mean that the code runs fast, but that it is stable and reliable.

There are use cases where you need a performant system that uses CPU really efficiently, in these cases Python is probably not the right tool.

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

#76

Post by acidbaseextract »

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…

As you point out, the exact properties that make binary search algorithmically fast can slow it down on real computer hardware.

Branch predictors like low entropy (unsurprising) branches, but binary search is algorithmically fast because it maximizes the entropy (information gained) from the few branch checks that it does make.

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

#77

Post by PaulDavisThe1st »

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…

Not that this at all answers your question, and I'm guessing you know this already, but for a language with a preprocessor, that should be something more like:

  #ifndef NDEBUG
  #define DEBUG(msg) if (debug) { log (msg); }
  #else
  #define DEBUG(msg) 
  #endif
this eliminates any question of branch cost from an NDEBUG ("production" or "optimized") build, and you don't have to wonder.

Obviously there are more sophisticated methods too.

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

#78

Post by im3w1l »

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…

My takeaway was the opposite. You have a fairly generous budget of if's and code size if you use a low level language. But if you use a higher level language you could run into the limits.

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

#79

Post by cmeacham98 »

pmarreck wrote: post #51

Couple of thoughts here: > if (debug) The language Elixir, during its compilation phase, actually automatically removes these in the production environment. That is to say, it is a macro which behaves as expected in every environment but "prod", in which case it removes itself. > conditionals A number of years ago I used Ruby to experiment with writing a version of fizzbuzz that avoided conditionals entirely, and was…

> The language Elixir, during its compilation phase, actually automatically removes these in the production environment. That is to say, it is a macro which behaves as expected in every environment but "prod", in which case it removes itself.

I mean, you can do this in C too. Make "debug" an #ifdef, and when it is defined to "false" the compiler will obviously optimize that out.

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

#80

Post by Dylan16807 »

andrepd wrote: post #68
lmilcin wrote: post #29

Earlier quoted context omitted.

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.

Lots of code doesn't run so often that it needs to be optimal. If you use proper data structures and algorithms then you'll avoid the real problems. The constant factor slowdown you get from language choice won't matter for the vast majority of lines of code.
Post reply on HN