Silly micro-optimization: branching vs. dynamic dispatch
seeblog.seenet.ca/2020/08/silly-micro-optimiz...Posted Aug 5, 2020, 1:36 PM UTC
1023
seeblog.seenet.ca
Branches are indeed cheaper at run-time:
- Often times a branch is just transparent, if well-predicted.
- On the other hand, dynamic dispatch has a cost of about 5ns in C -- save the registers, call the function, restore the registers that need restoring.
This slight overhead is the least performance issue with dynamic calls, though.
Statically dispatched functions are very amenable to optimization:
- The optimizer can inline them, which enables many further optimizations: constant propagation, branch elimination, etc...
- Even if the optimizer cannot inline them, it can still perform inter-procedural optimizations; for example noting that the function is called with
"foo"as the 2nd argument, it can create a specialization of the function just for that case and call the specialization instead, or in the other direction, it can notice that the called function always returns a positive integer, never throws, etc...
Dynamically dispatched functions, on the other hand, are a significant obstacle:
- The call-site cannot be optimized based on information about the callee -- because nobody knows who the callee is.
- The callee cannot be specialized, in general, because of ABI constraints.
Optimizers will go to great lengths to "de-virtualize" dynamically dispatched functions. Actually, some even perform speculative devirtualization, turning the dynamic-call site into the equivalent of:
if (dynamic == candidate_a) { candidate_a(); }
else if (dynamic == candidate_b) { candidate_b(); }
else if (dynamic == candidate_c) { candidate_c(); }
else { dynamic(); }
And then optimize the (now) static calls as normal.
When the optimizer decides that a multi-level if-ladder is faster than just straight-up calling the dynamic function...
10
Branches are indeed cheaper at run-time:
I think you may have misinterpreted my measurements. Note that my results are given in operations per millisecond – higher numbers are better. In all cases except for some of the PHP ones, dynamic dispatch yielded noticeably better performance. That's why I was so surprised. Even if this is a very trivial example, well, so is the real-world use-case on which this writeup is based.
Optimizers will go to great lengths to "de-virtualize" dynamically dispatched functions.
Understandably so. In fact, it seems like they may go to such great lengths that the result can end up being faster than branch prediction. In particular, look at the Python case: I had to go out of my way to make the branching version operate in the same order of magnitude as dynamic dispatch.
2
I can't 100% speak to this but likely all function calls in python are dynamic dispatch, at least in user level code. The branch is likely just straight additional cost on top of function call.
2
I do worry when I see what appears to be hand rolled benchmarking boiler plate. Especially with languages like Java.
The take away; is that these rule's of thumb, "branching is slow", avoid "virtual" calls; are often repeated from history, when these things were always true. Now its better to write the code the way you want to read it, and the way that makes sense.
5
is it still silly if it can boost execution by a third? 🤔
4
I think, in most real-world situations, the difference would be largely drowned out by the amount of time spent in the inner function. It can be a big difference, but a big difference in something which only accounts for a small part of the overall compute time. Microbenchmarks like this do tend to overemphasize the importance of what they're measuring, I think.
But I was definitely surprised by the scale of some of the results.
2
Surprisingly illuminating on both the optimization itself, and the differences between languages.
If androids dream of anything other than electric sheep then they probably dream of keeping their processor pipelines full, and this should certainly do that.
Big JIT energy, I guess.
Er. A topic with ample potential for micro-optimization. Perhaps Java's NIH tendencies aren't bad all of the time.
2
The CL community "discovered" this and implemented it by extending their OOP system (all standards compliant): https://github.com/marcoheisig/fast-generic-functions
2
[deleted]
2
Why did you disable optimizations instead of marking the functions as noinline?
2
Because it didn't occur to me that of course there would be an annotation for that. Thank you for pointing it out. I've updated the C source in the post, and recompiled/rerun both versions, both with and without optimizations (-O2 and -Os) to show the difference. There's still a very slight difference with -O2, but basically negligible. I was surprised to see that indirection still wins out by ~3.5% with -Os.
1
You can also replace rand() with __asm__("") to keep the functions from being optimized as well, and then compile with -O3. For me this took the difference down to about 0.1%.
Keep in mind that I’m most interested in relative comparisons within the same language, so these numbers should still be relatively comparable.
If you're disabling optimization, you can't make any such assumptions about relative speed.
1
-O2 and -Os don't hoist the condition outside the loop while -O3 does. That probably explains why indirection wins out there. (Needed optimization flag: -funswitch-loops)
1
Indirection definitely has its place. There are reasons compilers generally compile switch-case to a jump table instead of a sequence of branches.
There might be an argument for using a branch if the alternative is chasing pointers through vtables, but I think the lunatics who avoid indirection in the name of performance would be more likely to try to architect their code in a way to avoid the branch/indirection altogether.
2
Giving all numbers with 6 digits after the decimal point makes me think this guy doesn't know what he's doing at all...
1
I trimmed the percentage comparisons. The other numbers are copy/pasted as output by the programs themselves. I thought after I posted it that I should've perhaps used a truncated formatting instead of just %f. But please, don't let formatting alone leave you thinking I don't know what I'm doing: that's why I provided the code, so you can see for yourself one way or the other.
2
If you can't be bothered by the basic formatting if your post why should anybody be bothered reading it?
-1
I've updated the code to round its output to one decimal place, and updated the tables. Thank you for the feedback.
1
I’ve observed upwards of 80% differences converting hot paths from dynamic dispatch to macros and branching instead. That’s just mine own little observations in writing a sort of C data structure library for myself. A better programmer in high performance situations (such as gaming) could very likely observe well over 100% increases in performance.
This example is far too trivial and favours a single hit use case while STILL showing pretty radical performance benefits. 5% is nothing to scoff at depending on your scale.
Edit:
Towards your conclusion, indirection is slow. If you measure the indirection of an int vs a copy, you’ll see two things:
The optimized build of the raw int will be much more inclined to inline
even if it doesn’t inline, the copy of an int will just be faster (you can mitigate this with little tricks like performing a copy prior to running a loop rather than running indirection in a loop, for example)
There are general rules of thumb (I think a struct of 4 ints or greater?) for when you should prefer indirection in your own code bases. Of course, there are reasons that you simply can’t avoid it as well.
And yet, that wasn't my conclusion. If you look again, you'll find that all of my results are given in operations per millisecond. A higher number is better – and in all cases except for some of the PHP ones, dynamic dispatch/indirection results in more work done in the same amount of time. As u/matthieum points out, there's a lot of behind-the-scenes effort put into optimizing dynamic dispatch. Yes, this is a trivial case where the work being done on the other side of the call is minimal; but that's also representative of the real-world situation which got me thinking about this (where the call being abstracted over was basically just
sprintf).There is indeed, but you shouldn’t rely on the compiler doing stuff for you.
Yeah you should. That's exactly what compilers are for.
Yikes. No. You 100% should not assume which optimizations the compiler will and will not be able to figure out.
The compiler will give you anywhere from a 1-1 representation of what you wrote to a complete rewrite and those rules change from compiler to compiler, version to version.
Compiler flags are requests that the compiler may decide to completely ignore, or a bad combination of flags may just cause you to screw up your own builds. For example, saying to optimize for binary size may just outright disable certain optimizations. Or maybe the compiler will decide that some thing too important of an optimization. Or maybe not.
How is operations per ms at all a sane measure of performance? 10 billion nops per ms won't do more work that you care about than 10 thousand adds.