The cost of dynamic vs. static dispatch in C++ • Hacker News Board

Re: The cost of dynamic vs. static dispatch in C++

#51

Post by kevingadd » Thu, Dec 05, 2013, 9:50 PM UTC

MichaelGG wrote: post #42

kevingadd wrote: post #29

Earlier quoted context omitted.

The .NET and Java VMs are in fact able to do some inlining on virtual/interface calls and do other sorts of smart dispatch. So the cost of a virtual method in .NET and Java is not necessarily equivalent to the cost in C++.

I tried a simple example[1] in C#, .NET 4.5, both 32 and 64-bit, just looping and calling an Add method. The adding the keyword virtual increased runtimes > 200%. JVMs might do this, but the CLR's codegen doesn't. An old blog post by one of the CLR engineers[1] states: "We don't inline across virtual calls. The reason for not doing this is that we don't know the final target of the call. We could potentially do bette…

The CLR's inlining for virtual calls is constrained specifically to interfaces, not to all uses of 'virtual', IIRC. (Interfaces are still very much virtual calls, they just don't use the 'virtual' keyword.)

See [1] for an example where the CLR fully inlines a virtual call (through an interface, specifically)

The call is most definitely virtual (or dynamic if you prefer that term), not statically-dispatched. It just happens to be performed through an interface. I suspect the CLR optimizes this because interfaces are incredibly common (IEnumerable, etc.)

[1] http://msdn.microsoft.com/en-us/library/ms973852.aspx

Re: The cost of dynamic vs. static dispatch in C++

#52

Post by namuol » Thu, Dec 05, 2013, 9:50 PM UTC

Observation: the intricacies of our technologies are growing to such complexity that analysis of the things we once had a direct hand in the design of plays out much like the analysis of some sort of mysterious natural phenomenon.

Re: The cost of dynamic vs. static dispatch in C++

#53

Post by emn13 » Thu, Dec 05, 2013, 10:31 PM UTC

mjn wrote: post #41

adamtj wrote: post #39

Earlier quoted context omitted.

My understanding is that good virtual machines basically do this sort of profiling and optimization at runtime and JIT compile specializations as necessary. Does anybody know why JIT isn't done in classically AOT compilers? Is JIT overhead generally higher than cost savings of the optimizations?

> Does anybody know why JIT isn't done in classically AOT compilers? One (admittedly incomplete) answer is that AOT compilers try to replicate many of the wins that JIT compilers get from runtime specialization by including a profile-guided optimization pass instead, which specializes ahead of time, using data logged from what you hope is a representative example of runtime. Good JIT compilers can do things like opti…

I think something that's often overlooked in this discussion is the language semantics differences. So we're not just comparing AOT with JIT (or why not JIT an AOT compiled app...) We're almost always also comparing C++ to the JVM/CLR worlds.

And then the point is that most optimizations a JIT can do that an AOT cannot are particulaly important where the language semantics are "too" flexible. If your code has lots and lot of virtual calls; lots of exceptions with unpredictable code flow - well, sure, it's really important to elide that flexibility where it's not actually used. That's kind of like JS Vm's nowadays speculatively type their untyped objects - it's a huge win, and not possible statically.

But the point is - these optimizations are critical because the languages don't allow (or encourage) code to disable these dynamic features. In C++ this can be helpful; but how often is dynamic devirtualization really going to matter? I mean, you can statically devirtualize certain instances (e.g. whole-program optimization reveals only two implementations and replaces a virtual call with an if), but the real code-could by any subtype but actually isn't scenario just isn't one that comes up often.

The consequence is that C++ gets most of the benefits of a JIT simply because the JIT is solving problems C++ compilers don't need to solve. The cost is that the compiler wastes inordinate amounts of time compiling your entire program as optimally as it can, even though it only has a few hotspots.

Re: The cost of dynamic vs. static dispatch in C++

#54

Post by kasey_junk » Thu, Dec 05, 2013, 10:32 PM UTC

army wrote: post #38

MichaelGG wrote: post #34

Earlier quoted context omitted.

But in cases of needless virtual calls (doesn't Java default to virtual for some strange reason?) it may be a quick and easy win. Additionally, it's not always so easy to drop to a low-level language. If your architecture is enormous and complicated, it might be totally unfeasible to change languages for hot parts.

In Java, all methods are virtual. You can often achieve a similar effect to non-virtual methods by declaring them final to prevent them being overridden in subclasses, but the same rules about which method is called apply. The reason to simplify the language (in comparison to C++) - the rules about which method are called are much simpler and easy to remember.

Also depending on the JVM and JIT settings over time those virtual methods get treated as non-virtual.

Re: The cost of dynamic vs. static dispatch in C++

#55

Post by malkia » Thu, Dec 05, 2013, 10:34 PM UTC

adamtj wrote: post #39

MichaelGG wrote: post #32

Earlier quoted context omitted.

Can profile-guided optimization realise that a certain virtual function almost always resolves to a specific implementation and have a conditional check to inline or optimize when needed? I'm not overly experienced with complicated OO systems, but sometimes it seems the OO is just an abstraction for convenience, but runtime will always take a particular path.

My understanding is that good virtual machines basically do this sort of profiling and optimization at runtime and JIT compile specializations as necessary. Does anybody know why JIT isn't done in classically AOT compilers? Is JIT overhead generally higher than cost savings of the optimizations?

I'm not an expert on the topic, but JIT is not allowed in certain places - like game consoles, ios, etc, to the point where even simpler trampoline (ffcall, libffi) are not allowed too. As such AOT helps there where JIT can't be used, but does not support absolutely everything (C# templates when comes to types that are not yet loaded I guess?).

Re: The cost of dynamic vs. static dispatch in C++

#56

Post by emn13 » Thu, Dec 05, 2013, 10:54 PM UTC

army wrote: post #23

eliben wrote: post #10

Earlier quoted context omitted.

And I have seen projects whose performance was crippled by layers upon layers of endless virtual calls. YMMV ;-)

Agreed, for almost all code it doesn't matter, but for the remaining small fraction it's worth thinking about these things. It sounds pretty insane to go with a blanket approach of removing virtual calls throughout an entire codebase without understanding which ones are the problematic ones. Especially since some ways of solving the problem could potentially lead to other problems like increased compiled code size. I…

Sure, it's a waste to optimize code that doesn't significantly contribute to execution time. And there are lots of cases that are I/O bound, memory bound, cache bound, cross-thread communication bound etc. But if you're doing actual calculations - so not lots of communication like I/O or threading, and not delegating the crunching to a library - and your calculations are not trivial bit-pushing (e.g. not just streaming with minor changes), then it's a good bet that any virtual function calls in that kind of code will be problematic; getting rid of the inner-loop dynamic dispatches will almost certainly help.

So it's situational, but IME it's pretty predictable where you'll see this kind of optimization help. By all means profile and use whatever tools at hand to help you along, and don't apply the optimization blindly - but despite the whole "black art" label optimization sometimes gets this kind of thing really is pretty straightforward.

Re: The cost of dynamic vs. static dispatch in C++

#57

Post by nkurz » Thu, Dec 05, 2013, 11:59 PM UTC

pslam wrote: post #44

nkurz wrote: post #37

Earlier quoted context omitted.

Best case, the core may still block predicted execution shortly after due to running out of non-dependent instructions, until it knows for sure the address it should have branched to. Worst case, the branch can't proceed until the two memory accesses access. You seem very familiar with these issues, but this doesn't sound right to me. Maybe I'm not understanding your terminology, but don't all modern processors suppo…

If the branch target is an address loaded from memory, and there is no cached result for the branch instruction, then there's no way it can predict which instruction to execute next. The target could be anywhere in valid memory. The reason the measurements don't show it is the micro-benchmark will be predicting very well. In fact it's quite difficult to defeat prediction even for giant codebases, and you probably hav…

On the other hand, having no cached result for the branch probably correlates strongly with not having the target in I-cache, which means you may be stalling out anyway. It also implies that the branch is not in the middle of a tight loop.

Regarding the size of the ROB, I was wondering about the size a while ago and found an interesting post from someone who measured it for modern Intel processors: Ivy Bridge (168), Sandy Bridge (168), Lynnfield (128), Northwood (126), Yorkfield (96), Palermo (72), and Coppermine (40). http://blog.stuffedcow.net/2013/05/measuring-rob-capacity/

I agree with you on the virtual part. I'm actually a C programmer more interested in how to implement efficient dispatch for interpreters. Eli (the original author) has some good posts on that as well: http://eli.thegreenplace.net/2012/07/12/computed-goto-for-ef...

Re: The cost of dynamic vs. static dispatch in C++

#58

Post by nkurz » Fri, Dec 06, 2013, 12:22 AM UTC

ksk wrote: post #47

eliben wrote: post #10

Earlier quoted context omitted.

And I have seen projects whose performance was crippled by layers upon layers of endless virtual calls. YMMV ;-)

I have never heard of any project where virtual calls are the dominant factor in performance. Are there any open source projects amongst your examples?

It's not necessarily done with explicit 'virtual' calls in C++, but speed of dispatch is very important to interpreters for dynamic languages. Here's an improvement to Python where the same general type of fixes make a significant difference: http://bugs.python.org/issue4753

Re: The cost of dynamic vs. static dispatch in C++

#59

Post by tezka » Fri, Dec 06, 2013, 12:22 AM UTC

kbutler wrote: post #18

"If anything doesn’t feel right, or just to make (3) more careful, use low-level counters to make sure that the amount of instructions executed and other such details makes sense given (2)." This is explicit support for confirmation bias. See Feynman's discussion of measuring the charge of the electron in Cargo Cult Science: "Why didn't they discover the new number was higher right away? It's a thing that scientists…

it was funny you felt the need to post your wisdom both here and under the actual post.

Re: The cost of dynamic vs. static dispatch in C++

#60

Post by nkurz » Fri, Dec 06, 2013, 12:32 AM UTC

vicaya wrote: post #19

This _could_ be another case of premature optimization, as gcc 4.9+ could automagically devirtualize non-overridden virtual functions. icc could do that for years.

That's not the way the phrase 'premature optimization' is usually used. Usually, it means spending time optimizing something that is not a limiting factor, or that otherwise will not make a difference in the final result. Keeping your code simple in the hope that eventually it will become fast is something else, probably falling closer to 'Sufficiently Smart Compiler' http://c2.com/cgi/wiki?SufficientlySmartCompiler.