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

11–20 of 72 posts

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

#11

Post by eliben »

tomp wrote: post #6

Instead of devirtualization, a simpler optimization, which would additionally also help in the dynamic case, is simple loop hoisting of the method pointer fetch. Instead of doing while(...) { (obj->vtable[0])(...) } we could have void(*fn)(...) = obj->vtable[0] while(...) { fn(...) } which would avoid two redirections per inner loop! Actually, I'm almost sure that is what LuaJIT would do, and many other high-level pr…

That would save the indirection, but I hope the article shows that by far the biggest cost comes from the lack of inlining. The latter would not be solved by your function pointer.

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

#12

Post by jamesaguilar »

nly wrote: post #2

When you think you can use CRTP instead of virtual dispatch in your program, you didn't need virtual dispatch to begin with... you needed a generic algorithm to operate over your object classes. That's exactly what run_crtp() is, the CRTPInterface class is completely redundant except that it provides some degree of compile-time concept checking (which we'll hopefully get in C++17) Virtual dispatch is useful for type…

Unit testing is my #1 use for virtual functions. "somebody else's code" a.k.a. standard ML modules is a distant second.

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

#14

Post by jheriko »

tomp wrote: post #6

Instead of devirtualization, a simpler optimization, which would additionally also help in the dynamic case, is simple loop hoisting of the method pointer fetch. Instead of doing while(...) { (obj->vtable[0])(...) } we could have void(*fn)(...) = obj->vtable[0] while(...) { fn(...) } which would avoid two redirections per inner loop! Actually, I'm almost sure that is what LuaJIT would do, and many other high-level pr…

this is not about C... C++ certainly. C has no such thing as a virtual function or dynamic dispatch (unless you implement it yourself).

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

#15

Post by jheriko »

its interesting to see a break down of this - especially using modern compilers on the intel platform.

did you try the intel compiler? for raw low level optimisation it sometimes massively out performs the ms, gcc or clang versions...

i'd imagine these problems are worse on ARM chips, and dynamic dispatch is even less effective there - certainly on PPC architectures I've seen much worse performance than on similarly powered Intels in precisely this situation. the caches are less and slower...

i'm not 100% but i think i've seen virtual calls 'devirtualised' by the MS compiler a couple of years ago... I might be thinking of something else though, it was a while back now. I was unpicking some CRTP mess in something that /was not performance critical in anyway/...

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

#16

Post by blt »

berkut wrote: post #8

I've done benchmarks on this fairly recently, and with the functions actually doing a lot of work (ray intersection for a raytracer), I saw practically no difference between CRTP and Virtual Functions: http://imagine-rt.blogspot.co.uk/2013/08/c-virtual-function-... And this was with billions of calls to the functions...

Yes, the penalty is most glaring for calls that do a tiny amount of work. Imagine if

  String.charAt(int index)
was a virtual call inside of strlen().

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

#17

Post by pslam »

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, which is about 8-16 cycles on modern architectures.

2) The function call itself is dependent on the final address loaded above. None of that can proceed until the branch address is known. If cached, all is good and the core correctly predicts execution of a large number of instructions. 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.

In any case, nearly all of this is dwarfed by the cost to the compiled code itself: in most cases you can't inline, so simple transformations which could eliminate the function call altogether can't happen.

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

#18

Post by kbutler »

"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 are ashamed of—this history—because it's apparent that people did things like this: When they got a number that was too high above Millikan's, they thought something must be wrong—and they would look for and find a reason why something might be wrong. When they got a number close to Millikan's value they didn't look so hard. And so they eliminated the numbers that were too far off, and did other things like that..."

http://neurotheory.columbia.edu/~ken/cargo_cult.html

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

#20

Post by pmjordan »

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.

Presumably this needs to be done at link-time? (And you'd have to disable it if you're planning to load code dynamically)
Post reply on HN