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.
Branch predictor: How many “if”s are too many?
21–30 of 109 posts
Re: Branch predictor: How many “if”s are too many?
#22Earlier quoted context omitted.
Wouldn't the compiler optimize this to an array lookup? static const char* countries[257]; Or even: static const char countrycodes[514]; return countrycodes[i * 2];
Doesn't look like it. Each case is a compare and jump: https://godbolt.org/z/KWYEW3d9s
Turn the gcc version up to 11.
Re: Branch predictor: How many “if”s are too many?
#23Earlier quoted context omitted.
Wouldn't the compiler optimize this to an array lookup? static const char* countries[257]; Or even: static const char countrycodes[514]; return countrycodes[i * 2];
Doesn't look like it. Each case is a compare and jump: https://godbolt.org/z/KWYEW3d9s
Playing around a bit, it does seem that clang will do so: https://godbolt.org/z/1czW91bMM
A presentation on algorithm improvements popped up when looking into it (2015): https://llvm.org/devmtg/2015-10/slides/Wennborg-SwitchLoweri...
Re: Branch predictor: How many “if”s are too many?
#24Earlier quoted context omitted.
Wouldn't the compiler optimize this to an array lookup? static const char* countries[257]; Or even: static const char countrycodes[514]; return countrycodes[i * 2];
Doesn't look like it. Each case is a compare and jump: https://godbolt.org/z/KWYEW3d9s
[deleted]
Re: Branch predictor: How many “if”s are too many?
#25Earlier quoted context omitted.
You have an off-by-one error. The strings are 3 bytes long. 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 No need to hard code the length, and the cast is guaranteed to be within the bounds of an int o…
Well caught! I have two off by one errors :D seems they start from 1 instead of 0, and I didn't account for the null byte :D your solution is nicer and easier to read :)
This jives with the overall point of the article of keep it simple and readable. The semi fancy indexing caused 2 errors and the upside is negligible after the compiler gets done with it.
Re: Branch predictor: How many “if”s are too many?
#26Earlier quoted context omitted.
Until after C++11, ternary was the only way to use "if then" in constexpr functions. So it has slightly more use from a C++ point of view.
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.
Re: Branch predictor: How many “if”s are too many?
#27The “if (debug) log” example in the article is likely compiled to an always taken conditional jump past the logging call. And therefore not quite free. Nitpicking of course, I love such in-depth articles.
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 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)
Re: Branch predictor: How many “if”s are too many?
#28I'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";
I immediately wanted to rewrite it as an array, yep, since the countries are already indexed.
And to minimize the risk of errors such as the "Anguila" error above.
Re: Branch predictor: How many “if”s are too many?
#29This 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, 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.
Re: Branch predictor: How many “if”s are too many?
#30This 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.
The goalposts are constantly changing, but there are refactorings that achieve both.
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 yo me gets a little concerned about that level of enthusiasm.