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

51–60 of 109 posts

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

#51

Post by pmarreck »

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 purely functional:

https://github.com/pmarreck/ruby-snippets/blob/master/functi...

(I actually regret using currying here because it hurts the portability of the algorithm)

While it may be difficult (if possible) to convert all conditional logic to functional logic in a given algorithm, perhaps a compiler could do the work, if certain patterns emerged.

I'm not a C guy, but I have to wonder if such an algorithm would run faster on Intel or ARM chips by avoiding all branching and branch prediction. Can someone chime in on this?

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

#52

Post by lmilcin »

dylan604 wrote: post #32
lmilcin wrote: post #31

Earlier quoted context omitted.

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

won't we need quantum computing for that first?

You don't need that.

The branch predictor can select a random branch, so it doesn't even need to actually predict anything. It should use quantum noise so that it has chance of selecting different branches in different copies of the universe. There is noting to compute, quantum or otherwise.

The bomb to destroy the universe will take care of all universes where it made wrong predictions, so that is where we should concentrate our development resources.

It has more utility than just branch prediction. Imagine the bomb going off automatically whenever there starts a war.

Any copy of the universe that starts a war is automatically eliminated and this guarantees that you, as an observer, will never observe any wars.

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

#53

Post by initplus »

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 comparison (item myItem) in equal proportion to each other, so the branch predictor is stuck at a 50% guess for that branch. There is a great talk on this but I can’t remember what it’s called...

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

#54

Post by brigade »

jonny_eh wrote: post #47

Why don't processors fetch and decode both branches?

That would get exponential real quick. But Intel’s Tremont does have an instruction decoder that’s 6-wide only when decoding a taken branch, since it also starts decoding the branch target in the same cycle.

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

#55

Post by Denvercoder9 »

majke wrote: post #8
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";

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?

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

#56

Post by [deleted] »

majke wrote: post #8
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";

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

[deleted]

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

#57

Post by JoeAltmaier »

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?

It does nothing, so its a noop of sorts. I wonder if its a branch-delay tactic of some kind? Surely the algorithm is unchanged if it were removed.

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

#58

Post by colejohnson66 »

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?

It’s just a two byte NOP. IIRC, it’s Intel’s recommended form for one of that length. Windows uses it for hot patching,[0], but I can’t imagine that’s the reason here.

[0]: https://devblogs.microsoft.com/oldnewthing/20110921-00/?p=95...

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

#59

Post by flakiness »

In old days people used #ifdef to compile things out so that the "production code" doesn't have any unnecessary branches. I was shocked when I first saw these living if()s in the server-side C++ code but then realized it was vital for debugging in production.

People also used to prefer table based jump over long if-else-if chain for anecdotal performance reasons. That has gradually changed over the evolution of CPUs with various optimizations like the branch prediction. Now some JIT impls like tracing JIT replace virtual function calls with if-elses.

By the way, I'm glad that the article is so thoughtfully written that it doesn't include any ambiguous "best practices" at the end. It could have created yet another myth. The three top tips in the article is more about stating facts. I admire the author taking that stance.

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

#60

Post by majke »

jfrunyon wrote: post #39

> This code is in a performance critical loop and it looks like a waste - we never run with the "debug" flag enabled[1]. 1. One historical solution to this specific 'if debug' problem is called "runtime nop'ing". You know what another historical solution is called? Use a compile-time constant and let the damn optimizer optimize. (Virtually) no modern, widely used compiler would fail to optimize out `if (0) { ... }`.…

We do run aarch64. We are very interested if M1 is faster than the ARM's we have.

https://blog.cloudflare.com/arms-race-ampere-altra-takes-on-...

https://blog.cloudflare.com/porting-our-software-to-arm64/

Post reply on HN