Devirtualization in LLVM and Clang(blog.llvm.org)
blog.llvm.org
Devirtualization in LLVM and Clang
http://blog.llvm.org/2017/03/devirtualization-in-llvm-and-clang.html
26 comments
Impressive undergraduate work: Undergraduate student at University of Warsaw, currently working on C++ static analysis in IIIT.
On the Java side of things, devirtualization in the JVM's JIT compiler is discussed in articles like: http://insightfullogic.com/2014/May/12/fast-and-megamorphic-... ; https://shipilev.net/blog/2015/black-magic-method-dispatch/
I’m curious how helpful this is in practice. Often, if you’re going through the pain of using C++, you probably care a lot about performance, so you also try to make sure to minimize use of virtual calls.
You'd be surprised. WebKit, for example, uses a lot of virtual calls for simple things like "is this element a table".
Should it really be done that way though? I have to think that if virtual calls are used like that there is a huge amount of performance squandered by the general structure.
Right but are those call sites typically monomorphic (i.e. devirtualizable?)
const type field in the base class, non-virtual accessor (direct field access can be inlined). Memory vs CPU, the usual trade off.
It wouldn't cost memory though, because you free up a slot in the virtual table. No?
Often they become so after inlining.
[deleted]
I'm also curious about the real-world benefits. Generally speaking, if you are using a virtual function, it's because you need polymorphic behavior. Is there a lot of code that uses virtual functions where not needed?
Most polymorphism is actually statically determined, and most that isn't is static at compile time is static after program initialization. There is a lot of optimization you can do based on this knowledge.
A virtual call on a modern processor is typically not very costly. Too much inlining, OTOH, can be (if it generates bloated code that trashes your cache)
The call itself is not very expensive, but the effect of having to jump through vtables can prevent other optimizations in a way similar to calling a function in a DLL.
Not a huge issue for business logic bits or if your virtual functions are quite large, but using virtual functions for small often used calls such as specific getters or some mathematical function can cause a big performance hit.
Not a huge issue for business logic bits or if your virtual functions are quite large, but using virtual functions for small often used calls such as specific getters or some mathematical function can cause a big performance hit.
Exactly. The cost is not the overhead from the actual call - it's the fact that it inhibits other optimizations. The same applies to normal function calls when link time optimization is disabled.
This only becomes relevant in hot loops, but inlining can give big wins when combined with other optimizations.
This only becomes relevant in hot loops, but inlining can give big wins when combined with other optimizations.
Virtual function calls can be expensive, just compare the out-of-the-box performance between std::sort (c++, no virtual calls) and qsort (c, "virtual call" via function pointer). This can make a 10x difference when sorting something trivial (e.g. integer array). std::sort will compile to a single instruction for the comparison, qsort will typically have to do a full virtual function call, not expensive by itself but still significantly worse than single integer comparison instruction.
That's not a particularly meaningful comparison - qsort and std::sort aren't necessarily the same algorithm, moving elements is done differently, etc. So you're going to get very different results either way. If you wanted to compare you'd need to use an indirect function call with std::sort to compare - not hard to arrange...
I disagree, virtual function calls are somewhat costly. Removing a single virtual function call in any kind of hot code can result in measurable performance improvements.
Edit: it also depends a lot on if the virtual function can be predicted, e.g. which derived classes' method will actually end up being called. Mispredicted virtual functions are pretty slow.
Edit: it also depends a lot on if the virtual function can be predicted, e.g. which derived classes' method will actually end up being called. Mispredicted virtual functions are pretty slow.
It blocks other interprocedural optimization such inlining and interprocedural const prop.