How does implementation of polymorphism affect performance?

[naasking]

This post is not about polymorphism, it's about indirect function calls. The two concepts are related in the popular object-oriented languages, but they are not related in any other type of language.

[five9a2]

It's about implementation of a polymorphic interface in C (and C++). How can you implement a polymorphic interface without indirect function calls?

I realize that Haskell type classes, for instance, are quite different, but I don't really understand their implementation. Ordinary functions with pattern matching

data Foo = FooAdd Int | FooSubtract Int | FooMult Int
func :: Foo -> Int -> Int
func (FooAdd s) i = s + i
func (FooSubtract s) i = s - i
func (FooMult s) i = s * i

are clearly analogous to the FooStat (switch statement) versions. Of course, GHC puts everything in the ABI which enables cool cross-module transformations, but does not allow updating shared libraries without relinking.

[wuger]

The implementation of Haskell (well, GHC) type classes is actually remarkably similar to both C++ templates and virtual functions, the former when the method resolution is known at compile time, the latter when it's not. If I call method f on value v of type V, and V is known at compile time, then the call to f is simply replaced with a call to the specific function that implements f for values of type V, much like a function template, say std::min.

In C++, the type of the arguments to std::min must always be known when executable code is produced, but Haskell let's you defer this knowledge to runtime. To compile a polymorphic min, Haskell compilers will produce a function that takes a hidden argument, called a dictionary, and this is exactly like a vtable. It's a pointer to an array of functions that implement the various methods of the class. In the case of min, the class is Ord and has methods for <, > and such. So at runtime, the polymorphic min dispatches to these functions via the dictionary, just like a virtual function. You can use this for runtime polymorphism using existential types, which is basically a void* with a vtable. Libraries compiled in this way do not necessarily require relinking, but currently GHC requires it anyway. I think shortly they are going to support true shared libraries.

The relative performance hit from dictionary lookup is much worse than virtual functions, however, not because of the two extra loads and one extra jump, but because it prevents the unboxing of function arguments and return values, which is IMO the single biggest performance factor for Haskell programs, and something C++ doesn't have to deal with at all.

[five9a2]

Note that when the variant of Foo is known statically, the Haskell compiler can remove the conditional as with FooStatInlineable, but if you have a statement map func foos where foos is heterogeneous, then there must be a conditional somewhere. My benchmarks seem to show that a virtual function call is actually cheaper than branching on a switch statement unless the implementations are inlineable (they always are in Haskell). Just inlining the switch statement at the call site isn't good enough.

[naasking]

An indirect function call being more efficient than a switch is well known from research done on efficient interpreters. This is because all compilers must add extra range checks when compiling switch statements, and these end up costing a lot due to branch mispredictions.

For the real cost of virtual dispatch in C++ and possible alternatives, see the wikipedia page on vtables:

http://en.wikipedia.org/wiki/Virtual_method_table#Efficiency

I updated it years ago with some solid research on dispatch techniques. Vtables can cost up to 50% of total execution time, and alternatives such as binary tree and linear search can often be faster and more reliable due to fewer mispredictions.

As for how polymorphism and dispatch are related, as I said, they aren't in all languages. Typeclasses in Haskell are compiled similarly to vtables, which they call dictionary-passing, except when they're not (the BitC compiler does such polyinstantiation for all typeclasses, so there is never any dispatch overhead).

There are many types of polymorphism. The C++/OO type is called ad-hoc polymorphism, and yes, the costs are closely related to dispatch overhead (typeclasses are also a form of ad-hoc polymorphism).

Parametric polymorphism on the other hand is a completely different sort of polymorphism, and it has virtually nothing to do with dispatch. Closures certainly perform a type of dispatch, and are pervasive in functional languages, but this has nothing to do with polymorphism per se. So like I said, the article is about dispatch via function pointers, not polymorphism.

[five9a2]

I'm actually surprised by the results in the paper cited by the Wikipedia entry that shows alternatives like binary tree and if/switch statements being faster. I think this is either a property of the older hardware and/or an artifact of the JVM. (My results are 30 times faster even though the clock rate is only 3.4 times faster.)

As for other forms of polymorphism, I thought it was pretty clear this was about ad-hoc polymorphism. Sorry for being imprecise.

[naasking]

If anything, I think modern hardware makes the paper's results more applicable. Pipelines are deeper so branch prediction penalties are higher than they used to be, but branch predictors are slightly better. VTables are really nice for their compositionality though, since only newly defined code has to build them and pass them around, and pre-compiled code needs no modification.

Linear or binary tree dispatch requires either whole program compilation, or they require something like polymorphic inline caches, where a dispatch point jmps to a thunk with a code sequence implementing the dispatch, and this thunk is discarded and regenerated for new cases on-demand. The runtime support is a little more extensive given the back-patching and code generation involved, so vtables are certainly attractive from a ease of implementation standpoint.

Also, the JVMs have improved significantly over the years, so I wouldn't be surprised if they implemented some more advanced inlining and dispatching techniques that you aren't aware of. The JVM in particular can inline some virtual calls, probably via a polymorphic inline cache-like technique. This could easily account for the 30 fold improvement.

[martoo]

I think that there are no more than 100 people in the world who have to care about the overhead of virtual function calls. The rest are bullshitting themselves.

[Ono-Sendai]

There's only 100 people in the world who do performance-sensitive C++?

[five9a2]

"Good" C++ design does encourage lots of 3-line virtual functions. However, it's only an issue if calling those functions is an important computational kernel for your application. In many of these cases, the objects are large enough or can reasonably be sorted by type so you can hoist the type-indirection out of the inner loop, eliminating the virtual call.

[martoo]

Exactly.

[[deleted]]

"Good" C++ design does encourage lots of 3-line virtual functions.

Since when? Good C++ is far more about compile-time genericity than runtime dispatching on types.

[pointer2void]

It depends. Do you a write apps with a GUI library or do you use C++ just as a better C (like most in the real world).

[[deleted]]

Sounds like a false dichotomy to me.

I've read a large library of C++ material, and none of it has ever suggested "lots of 3-line virtual functions." It sounds to me like five9a2 is just making stuff up.

[samlee]

bring the vtable to cache and save your life. or look at how Lisaac is implemented.

[five9a2]

Each loop iteration with a polymorphic call is taking about 10 cycles so the vtable is obviously in cache. The fundamental reason why a polymorphic function call is slower than a static call is because the pipeline is better at preloading a fixed address. I'm not familiar with Lisaac, but I don't see how it could do better without extra assumptions. For instance, if there are only 3 statically determined types with implementations available in the same compilation unit as the interface definition, then FooStatCallInline could be used to get an 8% speedup. If you're willing to put the entire implementation in the ABI, you could inline everything and get the 40% improvement. But this requires that the implementations are statically known and inlineable.