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

31–40 of 72 posts

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

#31

Post by Taniwha »

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 some of the code we saw (I think it came from a Borland compiler)

   mov r1, n(bp) ; get vtable
   push n(r2)    ; get method pointer 
   ret           ; call
an extra memory write/read but always caught in L1 and on the register poor x86 it saves a register right> ... but on most CPUs of the time you're screwed for the branch prediction - CPUs had a return cache, a cheap way to predict the branch target of a return - by doing a return without a call you've popped the return cache leaving it in a bad state - EVERY return in an enclosing method is going to mispredict as well - the code will run, but slowly

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

#32

Post by MichaelGG »

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,…

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.

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

#33

Post by MichaelGG »

gjm11 wrote: post #30

So he found that dynamic dispatch was a lot more expensive. Fair enough and not very surprising. But let's quantify it a bit in absolute terms. The dynamic version of the code took 1.25s to run, during which time it performed approximately 8 x 10^8 virtual function calls. That translates to a cost per call of 1.5 nanoseconds . From which my takeaway would be: In inner-loopy code for which an extra nanosecond or so pe…

1.5 nanoseconds per call in the best case. In some huge monstrosity where you've got to go chase down object headers not in the cache, things may be quite different.

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

#34

Post by MichaelGG »

CmonDev wrote: post #21
rottyguy wrote: post #13

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

I think there is usually something else to optimize before this becomes a problem. And if it becomes a problem you need a low-level language anyway?

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.

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

#35

Post by nkurz »

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…

And as an alternative, would you suggest laboriously using low level counters to verify that every measurement you think is correct is indeed correct? Given finite resources, what's a better approach than concentrating on the apparent anomalous measurements? I'm not sure I see the parallel.

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

#36

Post by froydnj »

MichaelGG wrote: post #32
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,…

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.

Microsoft's PGO/LTCG implementation does just this. GCC can do something similar as well.

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

#37

Post by nkurz »

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 support speculative execution? All instructions (including dependent) are executed, but the results are held in the Reorder Buffer until the branch choice is confirmed. If this is still a large issue, why don't Eli's measurements show it to be?

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

#38

Post by army »

MichaelGG wrote: post #34
CmonDev wrote: post #21

Earlier quoted context omitted.

I think there is usually something else to optimize before this becomes a problem. And if it becomes a problem you need a low-level language anyway?

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.

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

#39

Post by adamtj »

MichaelGG wrote: post #32
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,…

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?

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

#40

Post by MrBuddyCasino »

pmjordan wrote: post #27
andor wrote: post #22

Earlier quoted context omitted.

The Java Hotspot VM can still optimize for this case, if the virtual call leads to only a few classes most of the time. Several virtual methods can be inlined, but of course there's still an extra step compared to static dispatch: the classes of the current object and the inlined methods have to be compared. If no matching method is inlined, control needs to be passed back to the VM.

A fascinating article on this type of optimisation: http://www.azulsystems.com/blog/cliff/2010-04-08-inline-cach...

Interesting read, I didn't know that making fields final in Java does nothing for performance. Any idea what those "Generic Popular Frameworks" are? I put my money on Hibernate.
Post reply on HN