Branch predictor: How many “if”s are too many?
blog.cloudflare.com
blog.cloudflare.com
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.
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.
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, performing I/O) that will be making any gains from this pretty insignificant.
Where this comes into picture is if you are really bent on improving performance of your code on a grand scale (when you develop algorithmic trading or maybe operating system), when you have a very dense, busy inner loop (for example video encoding) or when you develop compilers.
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.
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.
If you're saying the fastest method is O(n), then sure, no method can guarantee fast processing of the entire list. But that fact sure isn't python's fault!
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 any given day, you're much more likely to be amused by your own cleverness than anyone else is, so you either do it for your own reasons, stop doing it entirely, or find palatable forms of expression.
My most concrete example is probably the bizarre love triangle between locality of reference, lazy evaluation, and common subexpression elimination. There are several islands of sanity where reading comprehension is improved by refactoring in ways that happen to reduce or avoid calculations.
You clean up the code and it gets 5% faster. You use the same pattern in three places and you're comfortably into double digits.
As more evidence piled up for me about the dangers of confusing code, I spent more time thinking about the legibility and very little time thinking about the performance, but the fact is that I still do it intuitively. 25yo me would still be pretty happy with the performance of my code, even though <mumble>yo me gets a little concerned about that level of enthusiasm.
I know that even 1 week future me appreciates readable code at the expense of a _little_ bit of performance.
More generally I don't think we should consider that readability and efficiency are at opposing ends of the same axis. With a bit of care and good tools it's often possible to get the best of both worlds, or close enough.
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.
const char *getCountry(int cc) {
if(cc == 1) return "A1";
if(cc == 2) return "A2";
if(cc == 3) return "O1";
if(cc == 4) return "AD";
if(cc == 5) return "AE";
if(cc == 6) return "AF";
if(cc == 7) return "AG";
if(cc == 1) return "AI";
...
if(cc == 252) return "YT";
if(cc == 253) return "ZA";
if(cc == 254) return "ZM";
if(cc == 255) return "ZW";
if(cc == 256) return "XK";
if(cc == 257) return "T1";
return "UNKNOWN";
}
static const char* countries[257];
static const char countrycodes[514];
return countrycodes[i * 2];A presentation on algorithm improvements popped up when looking into it (2015): https://llvm.org/devmtg/2015-10/slides/Wennborg-SwitchLoweri...
static const char countrycodes[514];
return countrycodes[i * 2];
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) { ... }`.
Also, why does M1 performance matter to Cloudflare's software? I kinda doubt their servers are on Macbooks.
https://blog.cloudflare.com/arms-race-ampere-altra-takes-on-...
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 instruction) which avoids the perf hit on the first iteration.
Both Clang and GCC recognize __builtin_expect which can be wrapped in a macro easily:
#define unlikely(x) __builtin_expect(!!(x), 0)
The initial question is:
if (debug) {
log("...");
}
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?
#ifndef NDEBUG
#define DEBUG(msg) if (debug) { log (msg); }
#else
#define DEBUG(msg)
#endif
Obviously there are more sophisticated methods too.
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 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.
I'd write something similar, more or less; Probably the following, not for optimization, but more as a matter of style:
const char countries[][3] = {
"A1",
"A0",
// [...]
};
// [...]
int total_countries = (int) (sizeof(countries) / sizeof(countries[0]));
return cc < total_countries ? countries[cc] : "UNKNOWN";
Stylistically-wise I think the best solution would be to write the array like:
const char countries[][3] = {
[0] = "A1",
[1] = "A0",
};
Good call. It might have caught the off-by-one mistake I made (the codes start from 1 and not 0 in the blog post). Maybe even switch to using an enum as our index instead of an int.
getCountry:
mov eax, OFFSET FLAT:.LC0
cmp edi, 258
ja .L1
mov edi, edi
mov rax, QWORD PTR CSWTCH.1[0+rdi*8]
.L1:
retSo clang did this for a long time it seems.
Edited to add: I understand that it's a NOP, but why would the compiler emit one here?
[0]: https://devblogs.microsoft.com/oldnewthing/20110921-00/?p=95...
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.
mov eax, OFFSET FLAT:.LC0
cmp rdi, 258
ja .L1
mov rax, QWORD PTR CSWTCH.1[0+rdi*8]
And to minimize the risk of errors such as the "Anguila" error above.
Run it on infinite multiverse, construct a mechanism to destroy the Universe every time branch predictor did not predict every single conditional correctly.
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.
> 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?
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.
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.
For example (not that I expect this to be true), something of the same sort as "your if block should contain the rare condition".
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 to branches which have a high penalty and which are rarely or often taken, and see if it makes a difference.
> 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.
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.
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, 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...
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.
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.
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.
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
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.
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.
The chart shows funny alignment issues. It's unclear what they are caused by.
You mean 192K.
Are you suggesting that you believe that both the number and the unit were a typo?
> Oh, and because it's NOT 196 thousand. 3072*64 = 196608. Which rounds to... 197 thousand.
Truncation is a totally valid way of representing numbers when pinpoint accuracy isn't really necessary. "32K" is a very common way to refer to the number 32768, for example.
> or 192KiB if you prefer that sort of thing
I appreciate the caveat here as I very much do not and believe that the concept of kibibytes being distinct from kilobytes are a scam perpetuated by hard-drive and floppy disk manufacturers as a way to cut costs while still advertising the same storage space. It definitely makes sense to use the same definitions for the SI prefixes, but even two decades after that ISO was published no-one actually says "kibibytes", so clearly it's not much of a standard.
But that's another discussion entirely.
Except that you just said that "32768->32K" involves truncation. What is 32*1024? 32 KiB is exactly, no truncation involved, 32768.
(BTW, kibibytes are distinct from kilobytes because 1024 is distinct from 1000. Similarly, 1048576 is distinct from 1000000.)
> Truncation is a totally valid way of representing numbers [with lower precision]
No. Rounding is.
--
Once again. THEY, the authors of the post, use unit multipliers of 1024 in every other figure on the page. Except in this one particular figure where you claim they intentionally use 1000. I frankly don't care whether they define KB as 1000B or 1024B. Either way works. But they should, at the very least, be consistent within the space of a single blog post.
> This is visible with block size 64 breaking at 3072 mark 3072*64=196K, and for block 32 at 6144: 6144*32=196K.
You mean 192K.
In some cases the compiler may decide to evaluate both paths and then "undo" the path that was wrong. This is very common on VLIW architectures like Itanium which have hardware support for this (predicates), but it can also be done with other instruction sets.