Konda.eu

C++ - Optimizing away vtable with metaprogramming

No comments

C++ - Optimizing away vtable with metaprogramming


Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /www/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /www/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /www/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /www/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /www/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /www/wp-content/plugins/latex/latex.php on line 49

In every object oriented language class inheritance is a life saver when it comes to program architecture. A rather nasty side effect that comes with it is usually performance degradation. And in C++ that penalty can be quite noticeable. When working with virtual methods in derived classes compiler generates vtable (Virtual Method Table), where address for each overridden method is specified. Vtable is then used every time virtual method is called to lookup that address, jump to it and execute code at that location. That penalty can quickly increase execution time by \(\). There is a neat trick that allows us to resolve those addresses compile-time allowing compiler to optimize vtable away using metaprogramming.

Using vtable

I used the following example for benchmarking with regular inheritance and virtual method:

class IRandom 
{	
    public:
        virtual float next() = 0;
};

class UniformRandom : public IRandom 
{
    public:
        float next() override
        {
            return 1;
        }
};

It's pretty dummy, but it should do the trick. IRandom *r = new UniformRandom(); was used to initialize and afterwards next() was called one billion times (\(\)). Average execution time after one thousand runs was 8.52 seconds. Pretty slow for only one billion returns.

Using metaprogramming

In second example base class is used as a wrapper which receives derived class type as a template parameter:

template<typename T>
class IMetaRandom
{
    public:
        float next()
        {
            return static_cast<Derived *>(this)->next();
        };
};


class MetaRandom : public IMetaRandom<MetaRandom>
{
    public:
        float next()
        {
            return 1;
        };
};

During compile time compiler will know which type is being used therefore it will completely remove vtable and optimize code as much as possible.  The upper code resulted after one thousand runs with one billion repetitions 3.82 seconds which is quite a speed up.

Conclusion

Even thought the speed up is enormous, by the factor of almost \(\) in the example above, it comes at a cost of code organization. There will be no compiler warnings if derived class doesn't implement necessary methods. Program will run in an endless loop making it a debugging nightmare. In most cases the usual way with vtable should be used. Use metaprogramming only in programs where speed is crucial.

Leave a Reply

Your email address will not be published.

Time limit is exhausted. Please reload CAPTCHA.