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

61–70 of 72 posts

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

#61

Post by seanmcdirmid »

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.

Note you've just described inline caching [1]. A big research topic in the 90s, I'm sure this is pretty much a non-issue these days.

[1] http://en.wikipedia.org/wiki/Inline_caching

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

#62

Post by AndrewBissell »

MichaelGG wrote: post #43
army wrote: post #38

Earlier quoted context omitted.

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.

Not having to think about the question "should I make this method virtual?" makes the Java language simpler, yes.

In the vast majority of cases where a virtual function call is actually monomorphic or bimorphic at runtime, the JVM JIT can observe that and potentially inline the method (with an if statement in the bimorphic case). It puts guards around the inlined method and deoptimizes in the event that a newly loaded class renders the optimization incorrect.

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

#63

Post by MichaelGG »

kevingadd wrote: post #51
MichaelGG wrote: post #42

Earlier quoted context omitted.

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

I get even worse results using an interface for the Add function. That is, if I do "new X() as InterfaceType" then call the function, the performance is 5x worse than if I don't cast to the interface. This is in a tight loop doing an add.

Do you have any actual examples of making an interface call that gets inlined? This post[1], dated 2004 (later than the MSDN article you referenced) from Eric Gunnerson says:

"all the compiler knows is that it has an IProcessor reference, which could be pointing to any instance of an type that implementes IProcessor. There is therefore no way for the JIT to inline this call - the fact that there is a level of indirection in interfaces prevents it. That's the source of the slowdown."

He goes on to say that Sun does do something since Java makes everything virtual, and the CLR could do it in theory, but doesn't.

I skimmed through the linked article you provided but didn't find any mention of inlining interface method calls. On the excellent performance of virtual/interface calls, it says:

"the combination of caching the virtual method and interface method dispatch mechanisms (the method table and interface map pointers and entries) and spectacularly provident branch prediction enables the processor to do an unrealistically effective job"

1: http://blogs.msdn.com/b/ericgu/archive/2004/03/19/92911.aspx...

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

#64

Post by MichaelGG »

malkia wrote: post #55
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?

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?).

With C# generics on non-struct types, the emitted code is the same regardless of the type. On struct-types, it's necessarily different because there's no object header and the size of the objects can differ.

But, I can't think of a way to get an unknown struct type into a generic function without boxing (which makes it no longer a struct type). So for an AOT compiler it shouldn't be an issue. And there's probably some clever way to emit generic code for structs, too.

But generics have their own implementation difficulties and Mono didn't support them for a while in AOT.

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

#65

Post by MichaelGG »

AndrewBissell wrote: post #62
MichaelGG wrote: post #43

Earlier quoted context omitted.

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

Not having to think about the question "should I make this method virtual?" makes the Java language simpler, yes. In the vast majority of cases where a virtual function call is actually monomorphic or bimorphic at runtime, the JVM JIT can observe that and potentially inline the method (with an if statement in the bimorphic case). It puts guards around the inlined method and deoptimizes in the event that a newly loade…

It just flips it for "should I make this method final?" So at best it's a wash. In the majority of cases, a function shouldn't be virtual so users need to mark it final to accurately represent their design.

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

#66

Post by kevingadd »

MichaelGG wrote: post #63
kevingadd wrote: post #51

Earlier quoted context omitted.

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

I get even worse results using an interface for the Add function. That is, if I do "new X() as InterfaceType" then call the function, the performance is 5x worse than if I don't cast to the interface. This is in a tight loop doing an add. Do you have any actual examples of making an interface call that gets inlined? This post[1], dated 2004 (later than the MSDN article you referenced) from Eric Gunnerson says: "all t…

I've seen interface calls be inlined in action on the modern CLR when looking at disassembly. I don't understand why you would have expected the interface call to be faster than a normal non-virtual call? The interface call always needs a type check before the inlined call body in case of polymorphism; it can't be as fast as a normal call.

Or are you saying the interface call is 5x slower than a virtual call? That definitely isn't right.

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

#67

Post by AndrewBissell »

MichaelGG wrote: post #65
AndrewBissell wrote: post #62

Earlier quoted context omitted.

Not having to think about the question "should I make this method virtual?" makes the Java language simpler, yes. In the vast majority of cases where a virtual function call is actually monomorphic or bimorphic at runtime, the JVM JIT can observe that and potentially inline the method (with an if statement in the bimorphic case). It puts guards around the inlined method and deoptimizes in the event that a newly loade…

It just flips it for "should I make this method final?" So at best it's a wash. In the majority of cases, a function shouldn't be virtual so users need to mark it final to accurately represent their design.

Well, the answer to "should I make x final" is always "yes" in Java, so you don't really have to think too hard about that either. :-) `final` really should have been the default setting for all methods, classes, and local variables, but unfortunately inheritance was still in vogue when Java was created, and the benefits of immutable values weren't as well understood or appreciated either (or maybe they just figured the C & C++ programmers they were trying to win over would hate it).

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

#68

Post by MichaelGG »

kevingadd wrote: post #66
MichaelGG wrote: post #63

Earlier quoted context omitted.

I get even worse results using an interface for the Add function. That is, if I do "new X() as InterfaceType" then call the function, the performance is 5x worse than if I don't cast to the interface. This is in a tight loop doing an add. Do you have any actual examples of making an interface call that gets inlined? This post[1], dated 2004 (later than the MSDN article you referenced) from Eric Gunnerson says: "all t…

I've seen interface calls be inlined in action on the modern CLR when looking at disassembly. I don't understand why you would have expected the interface call to be faster than a normal non-virtual call? The interface call always needs a type check before the inlined call body in case of polymorphism; it can't be as fast as a normal call. Or are you saying the interface call is 5x slower than a virtual call? That de…

I expect an inlined interface or virtual call to be the same as an inlined non-virtual call. But since the CLR (4.5, Windows 7 x64, using 32 or 64-bit codegen) won't emit an inlined virtual/interface call for int Add(int, int) -- it's slower.

In my simple program doing a loop, calling an Add function on an interface, it is definitely making a function call each time. It unrolls 4 times, and loads the function pointer once per iteration - I'd have though it would only load it once overall. Loop is 89 bytes. There is no conditional inside the loop to check for the type.[1]

If I change it to not use the interface (don't cast to the interface type), it's unrolled and inlined. Loop is 34 bytes.[2]

It's the same on 32-bit, except there's no unrolling. The non-virtual loop body is 2 instructions (inc, add). The interface has a push, 3 movs and a call. The virtual one requires two extra movs (to load the function pointer - with an interface the address is embedded as a literal).

Shrug. Maybe it still doesn't work with value types? I started it without VS then broke in with the debugger to get the disassembly.

The loop is doing "y = x.Add(y, i)" where y is a local.

Edit: Aha! Using an interface method (not virtual) and strings, I was able to get inlining. I guess the CLR is still weak in dealing with value types.

1: Start of the loop using an interface:

  lea r8d,[rdi-1]
  mov rbx,qword ptr [FFEEFE60h]
  mov edx,eax
  mov rcx,rsi ; rsi is the object pointer
  lea r11,[FFEEFE60h] ; I am embarrassed to admit I don't know what r11 is doing
  call rbx ; just does lea eax[rdx+r8], ret
  ; similarly 3 more times then loop
2: Without using the interface, the loop body:

  lea eax,[r8-1] ; r8's the counter
  add ecx,eax   
  lea edx,[rcx+r8]
  lea ecx,[rdx+rax]
  lea eax,[r8+2]
  add ecx,eax
  ; then loop

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

#69

Post by ksk »

nkurz wrote: post #58
ksk wrote: post #47

Earlier quoted context omitted.

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

Good example.

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

#70

Post by CmonDev »

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.

There you go - something else to fix before other optimizations: "your architecture is enormous and complicated".
Post reply on HN