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

81–90 of 109 posts

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

#81

Post by chrisweekly »

im3w1l wrote: post #78
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…

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.

Bit of a tangent but in the userland app space I'm increasingly interested in sidestepping the whole "conditionals" question with finite state machines, eg with a lib like XState.

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

#82

Post by throwaway823882 »

> Is it ok to have if clauses that will basically never be run?

Yep.

> But when I thought about it more: should it be improved?

Nope.

If you are an average programmer, you should write your code first to be legible and maintainable.

If you are a smart programmer, you should add performance tests to your test suite (since you need to do performance testing anyway for any production-critical code) and run your app on the appropriate-sized machine.

If you are a very smart programmer, you should rely on performance hacks when your application no longer meets performance requirements under heavy load.

If you are a freaking genius, you should think about optimizing your code.

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

#83

Post by sellyme »

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

Rule of thumb #1: don't. The compiler is probably smarter than you, it can handle things itself most of the time.

Rule of thumb #2: always test low-level performance improvements on real data. This is very similar to rule #1 - the compiler might already be implementing the optimisation you're changing to, so you might be making the code less readable for no benefit.

Rule of thumb #3: sort your arrays. Sorting algorithms are one of the most aggressively-optimised functions in modern computer science, it's a very small overhead compared to regular branch prediction failures. Make sure to keep rules #1 and #2 in mind, but this is probably the most common significant performance improvement to be gleaned from branch prediction.

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

#86

Post by singron »

sischoel wrote: post #66
initplus wrote: post #53

Earlier quoted context omitted.

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.

On a GPU you could do a parallel n-ary search. I.e. instead of making 1 test in the center, make n tests. E.g. 1 round of 32-ary search should be equivalent of 5 rounds of binary search. Not only do you avoid the branch predictor, but the memory access is also parallel, which isn't true in branchless binary search. If the width of the search is larger than a warp/wavefront (32/64), then you need to add synchronization and it might not be faster anymore.

GPUs aren't really built for latency though and this will waste a lot of accesses on speculation. You are probably better off with a good btree.

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

#87

Post by Retric »

flakiness wrote: post #59

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…

Jump tables can still be vastly faster than if-else-if though it really depends on the specifics such as the frequency of each option being correct. Best practices are always subservient to benchmarks when optimizing.

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

#88

Post by superdimwit »

flakiness wrote: post #59

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…

Big if/else lists will often get compiled into a jump table anyway.

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

#89

Post by asveikau »

flakiness wrote: post #59

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…

> Now some JIT impls like tracing JIT replace virtual function calls with if-elses.

I think it was about 2010ish when I first noticed a C compiler (Microsoft's) doing this optimization for function pointer calls. Might have been a link time optimization, because caller and callee were in different compilation units.

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

#90

Post by Agentlien »

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.

This kind of statement always makes me feel funny. It's true that algorithmic complexity is the most important part, you always have to measure, and micro optimisations are often not worthwhile. But this type of statement seems a lot stronger than that.

I'm a graphics programmer working in game development and most of my time is spent on our performance task force. I spend a lot of time thinking about the performance impact of things I write and revisiting things I've written to improve their performance.

My job would have been easier if more people spent a bit more time considering the performance impact of their solutions, as well.

Post reply on HN