Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

eli.thegreenplace.net

Post reply on HN
Print view View original

41–50 of 72 posts

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

#41

Post by mjn »

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?

> 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 optimizing fast paths, discovering latent static classes in highly dynamic languages, etc. These kinds of optimizations can also be done AOT, if you have good profile data and suitable analysis & optimization passes.

The pros/cons of each approach are not entirely resolved, and you will find varying opinions. Part of the problem with making a direct comparison is that there are large infrastructural inconveniences with switching from one approach to the other. A good JIT is a quite pervasive beast, not something you can just tack on as a nice-to-have. PGO is somewhat infrastructurally easier to add to an existing AOT compiler. Therefore, if you can do most of what JIT does via PGO, you would prefer to do that, were you the maintainer of an existing AOT compiler. Whether you really can is afaik a bit of an open question.

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

#42

Post by MichaelGG »

kevingadd wrote: post #29
rottyguy wrote: post #13

anything similar for higher level languages (c# or the likes)?

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 better here (for example, if 99% of calls end up in the same target, you can generate code that does a check on the method table of the object the virtual call is going to execute on, if it's not the 99% case, you do a call, else you just execute the inlined code), but unlike the J language, most of the calls in the primary languages we support, are not virtual, so we're not forced to be so aggressive about optimizing this case."

I guess things haven't changed. My testing with the CLR indicates that for best performance, you should make sure your IL is already inlined. The CLR does much better with huge function bodies.

1: http://pastebin.com/98c7Bt7f 2: http://blogs.msdn.com/b/davidnotario/archive/2004/11/01/2503...

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

#43

Post by MichaelGG »

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.

Simpler? The only case it matters is when a subclass has shadowed a non-virtual method. "Simpler" would be simply disallowing shadowing.

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

#44

Post by pslam »

nkurz wrote: post #37
pslam wrote: post #17

A big extra cost of virtual functions in the underlying CPU not mentioned in the article: they effectively create a branch target dependency on a pointer chase. Put another way: 1) The virtual function address lookup requires a load from an address which is itself loaded. If neither location is cached, this has the unavoidable latency of two uncached memory accesses. Even at best, this incurs two cached L1 accesses,…

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 have bigger issues with L1 thrashing at that point. The more subtle problem is even with prediction, there's a (quite high) limit to the number of unretired speculated instructions. Again, a micro-benchmark won't show that up - you'd need a large function in the inner loop.

I'm making it sound like there's no cost to virtual functions in real applications, but it's there, usually measurable and every little adds up. If anything, I think a better reason to not simply spray "virtual" everywhere is it demonstrates that the author didn't understand the data structures they created.

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

#45

Post by mappu »

Taniwha wrote: post #31

I worked on serious x86 clone once - we took a lot of real-world trace and ran it through our various microarchitectures to see how it would fly - dynamic C++ dispatch was interesting normally you expect something like mov r1, n(bp) ; get vtable mov r2, n(r2) ; get method pointer call (r2) ; call that's a really bad pipe break a double indirect load and a call - but branch prediction may be your friend ... However so…

I use push/ret idiom all the time to stdcall off the stack.. did not realise there was a return cache, that's very interesting.

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

#46

Post by zwieback »

cma wrote: post #7

I'd like to see a comparison of calling a dynamically linked function call vs a non-dynamically linked virtual call. Dynamic linking has more indirection than you might expect because the function addresses can't always just be put at the call site during the library load (the places where you would want to write the address can be in code that is read-only mmapped to aid in sharing memory between processes and to av…

In an ideal world the OS could still replace the call sites with straight calls to the loaded library, circumventing a jump table altogether. I don't remember what this is called, maybe something like a thunk, but I've seen it happen in the debugger where the first call causes a fault which rewrites the call site with the target address and subsequent calls are straight to the lib. This can work even if the chunk of code containing the call sites is shared and readonly, as long as the OS can override that.

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

#47

Post by ksk »

eliben wrote: post #10
alextingle wrote: post #5

for (unsigned i = 0; i tick(j); } } I wouldn't go quite so far as to say that benchmarks with tight inner loops like this are completely useless, but they are nearly so. The author is clearly aware that the real world of performance is much bigger & more complex than his simple Petri dish. Credit to him for mentioning that. It's also really refreshing to see him analysing the optimised assembly. The trouble with this…

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?

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

#48

Post by Taniwha »

mappu wrote: post #45
Taniwha wrote: post #31

I worked on serious x86 clone once - we took a lot of real-world trace and ran it through our various microarchitectures to see how it would fly - dynamic C++ dispatch was interesting normally you expect something like mov r1, n(bp) ; get vtable mov r2, n(r2) ; get method pointer call (r2) ; call that's a really bad pipe break a double indirect load and a call - but branch prediction may be your friend ... However so…

I use push/ret idiom all the time to stdcall off the stack.. did not realise there was a return cache, that's very interesting.

depends on the CPU - but it's relatively trivial thing to build (especially because unlike other caches it's a stack) on x86s return nominally is ALWAYS a bad pipe bubble: a pop followed by an indirect jump - the pop gets resolved at the end of its micro-op and the jump wants to be resolved early on so as to start decoding the next instruction

In the end it can't hurt to generate a bad jump prediction off of the return cache, it's no worse than being idle - the effect of messing with the cache though can cause it to always fail so as a result you get no advantage from it

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

#49

Post by Taniwha »

mappu wrote: post #45
Taniwha wrote: post #31

I worked on serious x86 clone once - we took a lot of real-world trace and ran it through our various microarchitectures to see how it would fly - dynamic C++ dispatch was interesting normally you expect something like mov r1, n(bp) ; get vtable mov r2, n(r2) ; get method pointer call (r2) ; call that's a really bad pipe break a double indirect load and a call - but branch prediction may be your friend ... However so…

I use push/ret idiom all the time to stdcall off the stack.. did not realise there was a return cache, that's very interesting.

(I should add - it's an x86, you're really register poor - sometimes you do have to do stuff like that - but if you have a register "mov reg, a;jmp (reg)" is better than "push a;ret")

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

#50

Post by banachtarski »

alextingle wrote: post #5

for (unsigned i = 0; i tick(j); } } I wouldn't go quite so far as to say that benchmarks with tight inner loops like this are completely useless, but they are nearly so. The author is clearly aware that the real world of performance is much bigger & more complex than his simple Petri dish. Credit to him for mentioning that. It's also really refreshing to see him analysing the optimised assembly. The trouble with this…

Also, CRTP prevents you from storing all derived objects in a single container, since the underlying types are now heterogeneous. There are also more restrictions present in terms of slicing, casting, among other things that render CRTP a poor choice in many situations.

In the end, it's just another tool which is the right one in particular circumstances, and the wrong one in all others.

Post reply on HN