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 algorit…
Branch predictor: How many “if”s are too many?
91–100 of 109 posts
Re: Branch predictor: How many “if”s are too many?
#92Couple 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 easiest is using the preprocessor to hardcode values such that branches can be eliminated. This is nice and all but it can start to cause problems with things getting confusing.
---
The other common thing you can do is provide compiler attributes to hint at what the code is doing. For example, you can specify that a function is pure (doesn't affect the observable state of the program) or const (pure attribute with the addition that the function is not affected by changes to anything other than the inputs. i.e. same inputs always give you the same output). There are also cold/hot attributes for improving branch prediction.
Similarly there is the leaf attribute which restricts the control flow of a function largely to the current translation unit and allows the compiler to deduce significantly more information about what the code is intending to do.
---
Now on the more fancy/dangerous side is using strict aliasing, the restrict keyword, and array parameters in functions. Strict aliasing tells the compiler that types can only contain what they say they contain (i.e. any two pointers for the same location in memory must have the same type).
Likewise the restrict keyword states that any memory accessed by a restrict qualified pointer can only be accessed by that pointer or by pointers derived from said pointer (member accesses, array access, pointer sliding/offsets). This allows the compiler to know that memory isn't being touched by other accesses (which without restrict it could be). Realistically this allows you some small to large performance gains any time you are interacting with more than one pointer at a time as the alternative is that the compiler may have to recheck every cached value any time you write to another pointer. An example would be `f(char * restrict x, char * restrict y)`. Here you know that no value ever possibly accessed or written to in x will affect any value ever possibly accessed or written to in y and vice versa. Note that the restrict keyword is valid on variables, pointers, members, and arrays.
In a similar vein, you can leverage array arguments in functions to guarantee to the compiler that a pointer argument is non-null and contains some number of elements. For example the difference between the functions `f(char * x)`, `g(char y [5])`, and `h(char z [static 5]` is that the compiler can't necessarily know for sure that x is a valid address in memory or how many elements it contains. The compiler does however know that the variable y contains exactly 5 elements and that the variable z contains at minimum 5 elements. The compiler can now potentially elide null checks and bounds checks (say for null terminated strings). Since the function is aware of this, it may help a bit but it benefits more in that with inlined functions, macros, and LTO the compiler can optimise within the scope of said function trees to elide those checks/branches. Something to note because people don't always pick up on it, array arguments do in fact work with size 1 which allows you to specify that all your arguments are guaranteed valid pointers. Basically for any internal functions, you probably always want to use either an array argument over a pointer so you can elide null checks and the like.
---
Combining all of the above in a C project can sufficiently restrict the search space so that the compiler can elide most "unused" code sections, restructure a decent bit of branching code into branch free forms (since it can be deduced equivalent at compile time), and reasonably tag the branch weights for the remaining branches.
TLDR: Yes however some of the techniques come with the downside that if the code doesn't fit the requirements of the technique the optimisations can introduce bugs into the program. There are some levels of compiler warnings to help you when using these features but they only catch the obvious cases (since if they could catch all of them, they could implement the techniques automatically). It's C, it comes with its footguns but if you know how to use them, you'll probably only be burned a few times and hopefully not too badly.
Re: Branch predictor: How many “if”s are too many?
#93I'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";
it’s probably a switch on the index (or in this case you could actually have an array and use the index). I don’t know my compilers that well but if I had to guess I would say there is a good chance this will be optimized away by the compiler.
Re: Branch predictor: How many “if”s are too many?
#94Earlier quoted context omitted.
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.
Plus python has many problems besides performance.
Re: Branch predictor: How many “if”s are too many?
#95In 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?
#96Earlier quoted context omitted.
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.
This is given as an excuse to write sloppy code and then we get the bloated mess that is modern software and the modern web. Plus python has many problems besides performance.
If you write things with good big O performance, for almost all of your lines of code you're done. It will perform fine.
Bloated messes don't come from writing a bunch of business logic in python instead of C, not while processors are this many orders of magnitude faster than they used to be. They comes from layers and layers of abstractions, or doing things completely the wrong way.
Re: Branch predictor: How many “if”s are too many?
#97Re: Branch predictor: How many “if”s are too many?
#98Couple 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?
#99Earlier quoted context omitted.
it’s probably a switch on the index (or in this case you could actually have an array and use the index). I don’t know my compilers that well but if I had to guess I would say there is a good chance this will be optimized away by the compiler.
As pointed out above, gcc ≥11 optimises it to a switch / lookup table ( https://godbolt.org/z/PxvGKqGrd ).
Re: Branch predictor: How many “if”s are too many?
#100Earlier quoted context omitted.
This is given as an excuse to write sloppy code and then we get the bloated mess that is modern software and the modern web. Plus python has many problems besides performance.
Sloppy code would be using the wrong data structures and algorithms. Sloppy code would be optimizing nothing at all. If you write things with good big O performance, for almost all of your lines of code you're done. It will perform fine. Bloated messes don't come from writing a bunch of business logic in python instead of C, not while processors are this many orders of magnitude faster than they used to be. They come…