C++ devirtualization at runtime?

Question

Are there techniques/libraries that allow the flexibility of having a class hierarchy (that has virtual functions) yet, once the objects types have been determined at runtime, allows devirtualization of the function calls?

For a simple example, suppose I have a program that reads shape types (circle, rectangle, triangle, etc.) from some configuration file to construct a some data structure of said shapes (e.g., vector<shape*>):

class shape {
public:
    virtual void draw() const = 0;
    // ...
};

class circle : public shape {
public:
    void draw() const;
    // ...
};

// ...
vector<shape*> shapes;

Obviously, if I want to draw all the shapes, I can do:

for ( auto&& s : shapes )
    s->draw();

Every time such an iteration over shapes is done, a virtual function call is made to call draw() for every shape.

But suppose once shapes is created, it's never going to change again for the lifetime of the program; and further suppose that draw() is going to be called many times. It would be nice if, once the actual shapes are known, there were a way to "devirtualize" the calls to draw() at runtime.

I know about optimization techniques to devirtualize virtual function calls at compile time, but I am not asking about that.

I'd be very surprised if there were a clever hack to do this in C++ directly since one way of doing this would be to modify the in-memory machine code at runtime. But is there some C++ library out there that enables such a thing?

I imagine something like this might be possible via LLVM since that allows generation of machine code at runtime. Has anybody used LLVM for this? Perhaps a framework layered on top of LLVM?

NOTE: the solution has to be cross platform, i.e., at least using gcc/clang and VC++.

Answer 1

I'm fairly certain that there's no such thing as a magic, "Here compiler, there are no more subclasses I'm going to define and this list is not going to change, so eliminate the virtual function call overhead" kind of thing.

One thing you can do that can help with virtual calls in extremely performance-critical situations is to sort your list of shapes by their subtypes. For example, instead of a sporadic pattern of subtypes like circle, rectangle, triangle, rectangle, triangle, square, etc., you want to rearrange those types to form like: circle, circle, circle, circle, ..., square, square, square, ..., etc. This is effectively optimizing for branch prediction. I don't know if this method is still applicable or yields much mileage with the latest architectures and optimizers, but there was at least a time not too long ago when I was alive where it was very useful.

About JITs, I've been exploring that area a bit. I wouldn't necessarily recommend trying to find a JIT solution to magically make your C++ code faster.

Instead, I've been exploring it since my software already has a domain-specific language, a visual kind of nodal GUI programming language where you draw connections between nodes (functions) instead of writing code to make new things like shaders and image filters (similar to Unreal Engine 4's BluePrint). It's currently nowhere near as fast as handwritten native code which is why I was interested in exploring a code-generation/JIT route. It currently works more like an interpreter.

I've tried Tiny C and LCC for these but one thing I found rather disappointing about them is that their optimizers aren't quite as sophisticated as your commercial production compilers. I often got results averaging 3 to 4 times slower than MSVC or GCC. They're otherwise wonderful since they're so featherweight and easy to embed.

LLVM seems like a wonderful match except that it's enormous. We have this kind of old school aesthetic in our core-level area where the code that is meant to be maximally reused should reuse as little as possible (to avoid sporadic dependencies to external packages). I've had a difficult time reducing that down to something featherweight enough to pass those standards, but I'm still looking into it.