C++ legacy inheritance vs CRTP + std::variant

cpp_legacy_inheritance_vs_std_variant.md

C++ : Polymorphic inheritance without vtable

In this article, we will see how to use CRTP, std::variant and std::visit to increase our code performances.

Table of content

1. Introduction
2. What's wrong with vTables ?
3. A way out ?
   1. CRTP
   2. std::variant + std::visit
4. Benchmark
5. Pros & cons

Motivation :

Inheritance and vTable were used for many years to create interface in C++ polymorphic class
What if ... there were another way to do this ?
easier, cleaner, faster and more reliable

Introduction

Inheritance is a mechanism that allows developers to create a hierarchy between classes, using "is-a" relationships. The class being inherited from is called the parent class (or base class), and the class inheriting is called the child class (or derived class).

This is useful for many purposes, such like :

• Code reusability.
  A child class will inherit datas and functions, so there's no need to duplicate code. Thus, the code base is faster to create, and easier to read & maintain.

• Make the code more "human friendly"
  An "Is-a" relationship is meaningful for anyone who is familiar with OOP. It allows to create a classe hierarchy that best reflects the way we mentally organize informations. A cat is a feline, a feline is an animal, and animal is a life-form, etc.

class life_form{};
class animal : public life_form{};
class feline : public animal{};
class cat    : public feline{};

void func()
{
    cat my_cat;
}

• Static polymorphism

Static polymorphism is a polymorphism resolved at compile time.

In the previous code snippet, my_cat is variable of cat type.
my_cat is also a feline, an animal, and a life_form.

void feed(animal & any_animal)
{
    // feed `any_animal`
}

void func()
{
    cat my_cat;

    feed(my_cat);
}

• Runtime polymorhpsim & vTable
  Ah, here's the big thing.

Runtime polymorphism is a polymorphism resolved at runtime. How ? Using vTables. Virtual tables (vTable) is a lookup table of functions pointers used to resolve function calls in a dynamic (late) binding way. When compiling a class, the compiler (at compile time thus) creates a static array that contains one entry for each virtual function that the class can call.

struct animal
{
    virtual void move_forward() = 0;
};
struct fish : public animal
{
    void move_forward() override
    {
        // swim using fins
    }
};
struct snake : public animal
{
    void move_forward() override
    {
        // use serpentine method
    }
};
struct feline : public animal
{
    void move_forward() override
    {
        // walk using paws
    }
};

void func()
{
    using pointer_type = std::unique_ptr<animal>;

    pointer_type my_animal(new snake());

    my_animal->move_forward(); // use serpentine method
}

What's wrong with vTables ?

As mentionned in the previous section, a virtual function call typically means a call via a function pointer stored in a vTable.

• Pros : Allows runtime polymorphism
• Cons : Bad performance impact

Why ?

When called, a virtual function require first to read the adress of the function. Thus, while the function instruction are loaded into the memory, the CPU will idle, waiting.

A way out ?

Great ! We now can summarize our list of requierement, and dive into code experiments !

Requierements :

• Interface
• Polymorphism
• Minimal amount of easy-to-read code
• Better performances than vtables

Let's use the following use-case :

• An actor that can receive, queue, and reacts to messages, and update itself as well.

Actor scenario :

1. Receives and queues 3 messages, one after another
2. Updates itself
3. Handles queued messages

Additionaly, we want actors to be polymorphic, in order to handle a collection or them.
And we want to be able to add or remove them dynamically from the collection.

For example purpose, we will use interger (int) as message type, just like :

using message_type = int;

Using inheritance, our abstract class may looks like this :

struct actor
{
    virtual ~actor() = default;

    virtual void update() = 0;

    void handle_queued_messages() { /* handle queued message one after another */ }
    void receive_message(message_type && msg)
    {   // queue `msg` into `pending_messages`
        pending_messages.emplace(std::forward<message_type>(msg));
    }

private:
    std::queue<message_type> pending_messages;
    virtual void handle_one_message(message_type && msg) = 0;
};

struct A : actor
{
    void update() override { /* impl ... */ }
    void handle_one_message(message_type && msg) override { /* impl ... */ }
};
struct B : actor
{
    void update() override { /* impl ... */ }
    void handle_one_message(message_type && msg) override { /* impl ... */ }
};

using container_type = std::vector<std::unique_ptr<using_inheritance::actor>>;

container_type actors;
// fill `actors` with A-s and B-s

for (auto & active_actor : actors)
{   // broadcast messages ...
    active_actor->receive_message(41);
    active_actor->receive_message(42);
    active_actor->receive_message(43);
}

for (auto & active_actor : actors)
{
    active_actor->update();
    active_actor->handle_all_messages();
}

In the code snippet above, we can see two issues :

• Pointers indirection when dereferencing active_actor for each member function call.
• VTable usage with pure virtual functions calls : update() and handle_one_message(msg).

CRTP to the rescue ?

Curiously recurring template pattern (CRTP), is a C++ idiom in which a class derive from a template class instanciation that use the first one as template argument.
It allows safe, static downcasting, from the base class into the derived one.

If you want more informations about CRTP, please consider reading this blog serie, from fluentcpp.com.

template <typename T>
class base{};

class derived : public base<derived>
{};

The main advantage of doing such thing is that from the base class perspective, the derived object is itself but downcasted.
Thus, by design, because the base is always inherited from by its template parameter, we can use static_cast instead of dynamic_cast.

In summary, using static_cast, the base class can access the derived class by downcasting itself into the derived class.

template <typename T>
struct base
{
    void do_stuff()
    {
        T & as_derived = static_cast<T&>(*this);
        // do stuffs with `as_derived`
    }
};

Also, we need to use two CRTP best-practices :

• Base class has private constructor
• Base class is friend with its derived class

This way, we ensure that the template base class will always be instanciated by the class it is derived from.

This is legal (compiling) code. Check it on godbolt.

template <typename T>
struct base
{};

struct impl_1 : public base<impl_1>
{};

struct impl_2 : public base<impl_1> // oops ! Shoud be base<impl_2>
{};

But if we use the tricks mentioned above, impl_2 does not compile anymore.

template <typename T>
class base
{
    base() = default;
    friend T;
};

Looks good so far. Let's see our current implementation progress (collapsible, click to expand) :

Interface

template <typename T>
struct actor
{
    void update()
    {
        as_underlying().update();
    }

    void handle_all_messages()
    {
        while (!pending_messages.empty())
        {
            auto message = std::move(pending_messages.front());
            pending_messages.pop();
            handle_one_message(std::move(message));
        }
    }

    void receive_message(message_type && msg)
    {
        pending_messages.emplace(std::forward<message_type>(msg));
    }

private:
    friend T;
    actor() = default;

    std::queue<message_type> pending_messages;

    inline T & as_underlying()
    {
        return static_cast<T&>(*this);
    }

    void handle_one_message(message_type && msg)
    {
        as_underlying().handle_one_message(std::forward<message_type>(msg));
    }
};

Derived classes

struct A : actor<A>
{
    using actor::actor;

    void update(){ /* impl ...*/ }

private:
    friend struct actor<A>;

    void handle_one_message(message_type && msg){ /* impl ...*/ }
};

struct B : actor<B>
{
    using actor::actor;

    void update(){ /* impl ...*/ }

private:
    friend struct actor<B>;

    void handle_one_message(message_type && msg){ /* impl ...*/ }
};

Let's have a look to our checklist of requierements :

• Interface
• Polymorphism
• Minimal amount of easy-to-read code
• Better performances than vtables

What about polymorphism ?

CRTP looks great, but in opposition to inheritance, we lost polymorphism.
Remember, we need to get multiple implementation of actor into a container.

using container_type = std::vector<std::unique_ptr<actor</* ? */>>>;

Also, what if we could avoid the usage of pointers as container's value_type ?

std::variant to the rescue

Well, we know our implementation types at compile time.
So, an all designated solution might be to use std::variant. Let's try this :

template <typename ... Ts>
using poly_T = std::variant<Ts...>;

using container_type = std::vector
<
    poly_T<A, B>
>;

So we can get the following usage : (Test it on Godbolot)

container_type actors
{
    A{},
    B{},
    A{}
    /* etc ... */
};

actors.emplace_back(A{});
actors.emplace_back(B{});

Before we can check our "polymorphism" from our list of requierement,
we need to find a synthax to call member functions.

Once again, the STL provides an all designated solution, using std::variant's std::visit.

template <class R, class Visitor, class... Variants>
constexpr R visit(Visitor&& my_visitor, Variants&&... my_var);

std::visit applies the visitor my_visitor to the std::variant my_var
The Visitor is any callable that covers every possible alternatives of Variants

Thus, in order to interact with our std::variant, we can define visitors in many ways.
In our specific case, we just need generic lambdas that were introduce with C++14.

Implementing our use case, we can write the following code :

container_type actors; /* contains many A-s and B-s */

for (auto & active_actor : actors)
{   // broadcast messages ...
    std::visit([](auto & act)
    {
        act.receive_message(41);
        act.receive_message(42);
        act.receive_message(43);
    }, active_actor);
}

for (auto & active_actor : actors)
{   // update, then handle pending messages
    std::visit([](auto & act)
    {
        act.update();
        act.handle_all_messages();
    }, active_actor);
}

Another great advantage of this design is that we can handle std::variant's template parameters differently (here, A and B),
without using dynamic_cast.

What about specific cases ?

Sometimes, you may want to have additional code for a specific type.

In legacy code (using inheritance), we would do the following ugly thing :

struct base
{
    virtual ~base() = default;
};
struct A : public base{};
struct B : public base{};

void handle_base_value(base * value)
{
    if (A * value_as_A_ptr = dynamic_cast<A*>(value))
        // deal with value_as_A_ptr
        ;
    else if (B * value_as_B_ptr = dynamic_cast<B*>(value))
        // deal with value_as_B_ptr
        ;
    else
        // other types
        ;
}
void func()
{
    base * my_value = new A();

    handle_base_value(my_value);
}

Using std::variant and std::visit we don't need dynamic_cast and pointers anymore, because types are known at compile time.

for (auto & active_actor : actors)
{
    std::visit([](auto & act)
    {
        using T = std::decay_t<decltype(arg)>;

        if constexpr (std::is_same_v<T, A>)
            // `act` is an `A`
            ;
        else if constexpr (std::is_same_v<T,B>)
            // `act` is a `B`
        else
        {   // other types
            static_assert(always_false<T>::value, "non-exhaustive visitor!");
            // or handle deal with act in another way
        }

    }, active_actor);
}

Alternatively, we still can define visitor types the old way, defining all operator() overloads so it is exhaustive.

using visitor_type = struct
{
    void operator()(using_CRTP_and_variants::A &){}
    void operator()(using_CRTP_and_variants::B &){}
};

for (auto & active_actor : actors)
{
    std::visit(visitor_type{}, active_actor);
}

In order to avoid if-constexpr and reduce the amount of code, another alternative is to use the convinient overloaded lambas trick :

template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;

for (auto & active_actor : actors)
{
    std::visit(overloaded
    {
        [](A & arg){ /* `arg` is an A */ },
        [](B & arg){ /* `arg` is a  B */ },
        [](auto & ){ /* other types   */ }
    }, active_actor);
}

The shorter the better, right ?

Let's have a look to our checklist :

• Interface
• Polymorphism
• Minimal amount of easy-to-read code
• Better performances than inheritance

Performances

Let's try the snippet (see below) on quick-bench.com, using C++20 standard and O3 optimization level.

Compiler	STL	CTRP + variants	vtable	how much faster?	link
Clang 7.0	Libc++ (LLVM)	345	502	1.5 times	test it !
GCC 8.2	libstdC++ (GNU)	281	667	2.4 times faster	test it !

From 1.5 to 2.4 times faster. Now we can check our "Better performances" checkbox.

• Interface
• Polymorphism
• Minimal amount of easy-to-read code
• Better performances than inheritance

See the benchmark complete snippet

// gcc   : CRTP_and_variant is 2.5 times faster (libstdc++, GNU)
// clang : CRTP_and_variant is 1.4 times faster (libc++, LLVM)

#include <queue>
#include <variant>
#include <iostream>
#include <memory>

using message_type = int;

namespace using_CRTP_and_variants
{
    template <typename T>
    struct actor
    {
        void update()
        {
            as_underlying().update();
        }

        void handle_all_messages()
        {	// internal states only
            while (!pending_messages.empty())
            {
                auto message = std::move(pending_messages.front());
                pending_messages.pop();
                handle_one_message(std::move(message));
            }
        }

        void receive_message(message_type && msg)
        {
            pending_messages.emplace(std::forward<message_type>(msg));
        }

    private:
        friend T;
        actor() = default;

        std::queue<message_type> pending_messages;

        inline T & as_underlying()
        {
            return static_cast<T&>(*this);
        }
        inline T const & as_underlying() const
        {
            return static_cast<T const &>(*this);
        }

        void handle_one_message(message_type && msg)
        {
            as_underlying().handle_one_message(std::forward<message_type>(msg));
        }
    };

    struct A : actor<A>
    {
        using actor::actor;

        void update()
        {
            //std::cout << "A : update()\n";
        }

    private:
        friend struct actor<A>;

        void handle_one_message(message_type && msg)
        {
            //std::cout << "A : handle_one_message : " << msg << '\n';
        }
    };
    struct B : actor<B>
    {
        using actor::actor;

        void update()
        {
            //std::cout << "B : update()\n";
        }

    private:
        friend struct actor<B>;

        void handle_one_message(message_type && msg)
        {
            //std::cout << "B : handle_one_message : " << msg << '\n';
        }
    };
}

namespace using_inheritance
{
    struct actor
    {
        virtual ~actor() = default;
        virtual void update() = 0;

        void handle_all_messages()
        {	// internal states only
            while (!pending_messages.empty())
            {
                auto message = std::move(pending_messages.front());
                pending_messages.pop();
                handle_one_message(std::move(message));
            }
        }

        void receive_message(message_type && msg)
        {
            pending_messages.emplace(std::forward<message_type>(msg));
        }

    private:

        std::queue<message_type> pending_messages;

        virtual void handle_one_message(message_type && msg) = 0;
    };

    struct A : actor
    {
        void update() override
        {
            //std::cout << "A : update()\n";
        }
        void handle_one_message(message_type && msg) override
        {
            //std::cout << "A : handle_one_message : " << msg << '\n';
        }
    };
    struct B : actor
    {
        void update() override
        {
            //std::cout << "B : update()\n";
        }
        void handle_one_message(message_type && msg) override
        {
            //std::cout << "B : handle_one_message : " << msg << '\n';
        }
    };
}


template <typename ... Ts>
using poly_T = std::variant<Ts...>;

static void test_CRTP_and_variants(benchmark::State& state) {

    using container_type = std::vector<poly_T
    <
        using_CRTP_and_variants::A,
        using_CRTP_and_variants::B>
    >;

    container_type actors
    {
        using_CRTP_and_variants::A{},
        using_CRTP_and_variants::B{},
        using_CRTP_and_variants::A{},
        using_CRTP_and_variants::B{},
        using_CRTP_and_variants::A{},
        using_CRTP_and_variants::B{},
        using_CRTP_and_variants::A{},
        using_CRTP_and_variants::B{},
        using_CRTP_and_variants::A{},
        using_CRTP_and_variants::B{}
    };

    for (auto _ : state) {
        for (auto & active_actor : actors)
        {	// broadcast messages ...
            std::visit([](auto & act)
            {
                act.receive_message(41);
                act.receive_message(42);
                act.receive_message(43);
            }, active_actor);
        }

        for (auto & active_actor : actors)
        {
            std::visit([](auto & act)
            {
                act.update();
                act.handle_all_messages();
            }, active_actor);
        }
        benchmark::DoNotOptimize(actors);
    }
}
// Register the function as a benchmark
BENCHMARK(test_CRTP_and_variants);

static void test_inheritance(benchmark::State& state) {

    using container_type = std::vector<std::unique_ptr<using_inheritance::actor>>;

    container_type actors;
    {
        actors.emplace_back(std::make_unique<using_inheritance::A>());
        actors.emplace_back(std::make_unique<using_inheritance::B>());
        actors.emplace_back(std::make_unique<using_inheritance::A>());
        actors.emplace_back(std::make_unique<using_inheritance::B>());
        actors.emplace_back(std::make_unique<using_inheritance::A>());
        actors.emplace_back(std::make_unique<using_inheritance::B>());
        actors.emplace_back(std::make_unique<using_inheritance::A>());
        actors.emplace_back(std::make_unique<using_inheritance::B>());
        actors.emplace_back(std::make_unique<using_inheritance::A>());
        actors.emplace_back(std::make_unique<using_inheritance::B>());
    }

    for (auto _ : state) {
        for (auto & active_actor : actors)
        {	// broadcast messages ...
            active_actor->receive_message(41);
            active_actor->receive_message(42);
            active_actor->receive_message(43);
        }

        for (auto & active_actor : actors)
        {
            active_actor->update();
            active_actor->handle_all_messages();
        }
    }
}
BENCHMARK(test_inheritance);

Pros & cons

Let's do a quick recap.
According to our design, we can define an interface, create many polymorphic implementations with a minimal amount of readable code.
As a result, we end with better performances than the old fashion way "inheritance with vtable".

However, is it worthy ?

Pros :

• no more vtable
• std::visit flexibility
• Better performances

Cons :

• sizeof(std::variant<...>)

We can already see an issue : std::variants<...>'s size on the stack. Indeed, the size of a std::variant is slightly greater than the type with the largest alignement it contains, as it must also store the information of which type it currently contains.

• CRTP can hide/shadow functions

CRTP can hide/shadow member functions, and thus lead to unexpected behaviors.
In order to avoid this, as saw previously, we used explicit base contructor call and friendship.

However, according to Herb Sutter's talks "Thoughts on a more powerful and simpler C++", we may find a way to solve this in the future using metaclasses. Maybe.

We still can do some static checks using SFINAE with std::void_t and std::experimental::is_detected

Thank you for reading

Wrote by Guillaume Dua.
Special thanks to O. Libre for reviewing this paper.

Want to read more ?
New articles incoming soon on gist.github.

@xNWDD I agree with you. that is the important point that CRTP is compiler friendly. vtables are not. it really does not matter using std::visit, variant or not.

@ArtBlnd I agree that our point of views differs,
because we both have different requirement for our code.
As mentioned before, my point was to test different shapes of codes for a similar functional need,
measuring performances for both.
After-what, picking one for my most recurring needs, from a performance, as well as ease-to-use perspective.

So far, the results I got on several plateforms/OS/compilers I daily work with are fine. It's about the same performance trends as shown on the snippet exposed on quick-bench.

About :

it doesn't matter its standard. the point is how useful is this on real-world.
Well, it does. In many companies, you cannot simply use your favorite tech environment, such as libraries, OS, compilers, archs, etc.
What's important here is to understand that the truth is not absolute, as you need to respect your companies/clients requirements.
Also, even standard is not safe here. Take embed development for instance : you may not be allowed to use exception, or bigger part of the STL (as well as C++ features) according to guidelines.

this approach is very beneficial if you can assume its type, and execute it as its original type which has static calls
Indeed ! That's the whole point. Create a statical, compiler-friendly design that is still convinient to use.
Take FSM implemented using std::visit and std::variant` for example. It's really convinient to use

@xNWDD Thanks for your long reply, I'll check it ASAP.
As we both teach C++, what I can suggest is that we collaborate about this paper.
May I suggest that you create a review and/or pull request ?

Same for you @ArtBlnd, what about "channeling" our discussion into a great Gist ? Feel free to help ;-)

Hello @GuillaumeDua I was looking for information about CRTP + std::variant and luckily found this page. I read it and have a question: Why should we write friend T in Base class and friend struct Base<A> or friend struct Base<B> in heritors?

Also thank you for article, I found it really useful! :)

@Hochheilige : Thanks for reading.

Short answer

This is not mandatory.
It depends on which data you are willing to share between base and derived class, and which way.

Long answer

Let's take this example :

template <typename T>
struct crtp{};

The purpose of CRTP is to create a context where you ensure that :

• The base class knows which is the derived one.

So in crtp, such instruction is legale :

static_cast<T&>(*this)

Why this is convinient is the lack of tight-coupling though, thus the ability to extends class using as CRTP as generic class features.

However, the CRTP, as a base class, cannot access private member of the derived one.

This is the same as :

class base { int i; };
class derived : public base {
    void usage() {
        const auto value = derived{}.i; // error
    }  
};

Which results in clang in the following error message:

error: 'i' is a private member of 'base'

But if you use the friend keywork :

class base
{
    friend class derived;
    int i;
};
class derived : public base
{
    void usage()
    {
        const auto value = derived{}.i; // OK
    }  
};

So you might be willing to use friendship the other way, in order to use CRTP as a class feature.
See live example on godbolt here

---

NB What's convinient is that CRTP might be extended with extra logic using if constexpr instructions or SFINAE using the detection idiom in general maners.
For instance :

template <typename T>
struct print_feature
{
   void print(std::ostream & os)
   {
       if constexpr (detect::has_shift_op_to_ostream_v<T>) // or maybe some `std::detect` impl, depending on standard release
          os << static_cast<T&>(*this);
       else
          os << "not implemented yet"; // or another default behavior : static_assert(false, ...), etc.
   }
};

@GuillaumeDua Thank you! I was confused because in my case I have no private fields in base class. But in your case can we use protected: int i ? I ask this just to make sure :)

And I have one more question about static_cast<T&>(*this) is that good to cast to T* or the better way is to cast to T& or it is all depends only on my vision on concrete task?

@Hochheilige Glad to help. I also teach C++ as a school mentor and professional trainer.

I see very little real cases where you'd like to use protected encapsulation.
As you can read in the CppCoreGuideline, rule C.133 :

C.133: Avoid protected data
Reason
protected data is a source of complexity and errors. protected data complicates the statement of invariants. protected data inherently violates the guidance against putting data in base classes, which usually leads to having to deal with virtual inheritance as well.

About static_cast<T&>(*this) , you should - almost - always avoid manipulating raw pointers.
Programming is all about writing a "story", so you'd better keep it as clear as possible, thus avoid multiples & costly indirections.

In general, i'd say Teach Yourself C++ in ∞ Days, using Godbolt and other tools

@Hochheilige

Reading code you produced, you also can use concepts for static polymorphism, if your compiler supports C++20.
https://en.cppreference.com/w/cpp/language/constraints

@GuillaumeDua Thank you for your explanation and for all links it is really useful and I feel like I've taken new look on C++ after each your comment!

I'm not sure that I'm ready to concepts and C++20 because I even don't know most of C++17 features, but found your advice about concepts interesting and going to try it.

Thank you again!

@Hochheilige Concepts are way easier that previous SFINAE + detection idiom boilerplates.
I'll write a paper about this very topic when I'll have enough time :)

Keep in mind that in a general manner, C++ tends to become easier, so I'd advise you to use latest standards as often as possible.
Also, I keep seeing students and professionals in my training that are currently learnin stuffs that already became deprecated - if not removed - in newest standards ! Like std::auto_ptr for instance.

@GuillaumeDua Thanks again, really waiting for your next article :)