Table of Contents

Runtime polymorphism usually connects with v-tables and virtual functions. However, in this blog post, I’ll show you a modern C++ technique that leverages std::variant and std::visit. This C++17 technique might offer not only better performance and value semantics but also interesting design patterns.

Last Update: 2nd Nov 2020 (Passing arguments, Build time benchmark, fixes).

Virtual Functions  

I bet that in many cases when you hear runtime polymorphism, you immediately imagine virtual functions.

You declare a virtual function in a base class and then you override it in derived classes. When you call such a function on a reference or a pointer to the base class, then the compiler will invoke the correct overload. In most of the cases, compilers implement this technique with virtual tables (v-tables). Each class that has a virtual method contains an extra table that points to the addresses of the member functions. Before each call to a virtual method the compiler needs to look at v-table and resolve the address of a derived function.

A canonical example:

class Base {
public:
    virtual ~Base() = default;
    
    virtual void PrintName() const { 
        std::cout << "calling Bases!\n"
    }
};

class Derived : public Base {
public:
    void PrintName() const override { 
        std::cout << "calling Derived!\n"
    }
};

class ExtraDerived : public Base {
public:
    void PrintName() const override { 
        std::cout << "calling ExtraDerived!\n"
    }
};

std::unique_ptr<Base> pObject = std::make_unique<Derived>();
pObject->PrintName();

What are the advantages of this technique? Let’s name a few:

  • The syntax is built inside the language, so it’s a very natural and convenient way to write code.
  • If you want to add a new type then you just write a new class, no need to change the Base class.
  • Object Oriented - allows deep hierarchies.
  • You can store heterogeneous types in a single container, just store pointers to the Base class.
  • Passing parameters to functions is easy.

I’d like to draw your attention to the “extensibility” part. For example, thanks to this feature, you can implement a plugin system. You expose the interface through some base class, but you don’t know the final number of plugins. They might be even loaded dynamically. Virtual dispatch is a crucial; part in this system.

And what are the drawbacks?

  • Virtual method must be resolved before the call, so there’s extra performance overhead (compilers try hard to devirtualize calls as much as possible, but in most cases, this is not possible).
  • Since you need a pointer to call the method, usually it also means dynamic allocation, which might add even more performance cost.
  • If you want to add a new virtual method, then you need to run across the base class and derived classes and add that new function

However, in C++17 (and also before thanks to the boost libraries) we also got another way of doing dynamic polymorphism! Let’s have a look.

Runtime Polymorphism with std::variant and std::visit  

With std::variant, which is available since C++17, you can now use safe type unions and store many different types in a single object. Instead of a pointer to a base class, std::variant can store all “derived” classes.

Let’s convert our first example with Base class into this new technique:

First, the classes:

class Derived {
public:
    void PrintName() const { 
        std::cout << "calling Derived!\n"
    }
};

class ExtraDerived {
public:
    void PrintName() const { 
        std::cout << "calling ExtraDerived!\n"
    }
};

As you can see, there’s no Base class now! We can have a bunch of unrelated types now.

And now the core part:

std::variant<Derived, ExtraDerived> var;

var defines an object that can be Derived or ExtraDerived. By default, it’s initialised with the default value of the first alternative. You can read more about variants in my separate and large blog post: Everything You Need to Know About std::variant from C++17.

Calling Functions  

How can we call PrintName() depending on the type that is currently active inside var?

We need two things: a callable object and std::visit.

struct CallPrintName {
    void operator()(const Derived& d) { d.PrintName(); }    
    void operator()(const ExtraDerived& ed) { ed.PrintName(); }    
};

std::visit(CallPrintName{}, var);

In the above example, I created a struct that implements two overloads for the call operator. Then std::visit takes the variant object and calls the correct overload.

If our variant subtypes have a common interface, we can also express the visitor with a generic lambda:

auto caller = [](const auto& obj) { obj.PrintName(); }
std::visit(caller, var);

Passing Arguments  

Our “printing” functions don’t take any arguments… but what if you need some?

With regular functions it’s easy, just write:

void PrintName(std::string_view intro) const { 
    std::cout << intro << " calling Derived!\n;
}

But it’s not straightforward with our function object. The main issue is that std::visit() doesn’t have a way to pass arguments into the callable object. It only takes a function object and a list of std::variant objects (or a single one in our case).

One way to solve this inconvenience is to create extra data members to store the parameters and manually pass them into the call operators.

struct CallPrintName {
    void operator()(const Derived& d) { d.PrintName(intro); }    
    void operator()(const ExtraDerived& ed) { ed.PrintName(intro); } 
    
    std::string_view intro;
};

std::visit(CallPrintName{"intro text"}, var);

If your visitor is a lambda, then you can capture an argument and then forward it to the member functions:

auto caller = [&intro](const auto& obj) { obj.PrintName(intro); }
std::visit(caller, var);

Let’s now consider the pros and cons of such an approach. Can you see differences compared with virtual dispatch?

Advantages of std::variant polymoprhism  

  • Value semantics, no dynamic allocation
  • Easy to add a new “method”, you have to implement a new callable structure. No need to change the implementation of classes
  • There’s no need for a base class, classes can be unrelated
  • Duck typing: while virtual functions need to have the same signatures, it’s not the case when you call functions from the visitor. They might have a different number of argument, return types, etc. So that gives extra flexibility.

Disadvantages of std::variant polymorphism  

  • You need to know all the types upfront, at compile time. This forbids designs such as plugin system. It’s also hard to add new types, as that means changing the type of the variant and all the visitors.
  • Might waste memory, as std::variant has the size which is the max size of the supported types. So if one type is 10 bytes, and another is 100 bytes, then each variant is at least 100 bytes. So potentially you lose 90 bytes.
  • Duck typing: it’s an advantage and also disadvantage, depending on the rules you need to enforce the functions and types.
  • Each operation requires to write a separate visitor. Organising them might sometimes be an issue.
  • Passing parameters is not as easy as with regular functions as std::visit doesn’t have any interface for it.

Example  

Previously I showed you some basic and artificial example, but let’s try something more useful and realistic.

Imagine a set of classes that represent a Label in UI. We can have SimpleLabel with just some text, then DateLabel that can nicely show a date value and then IconLabel that also renders some icon next to the text.

For each label we need a method that will build an HTML syntax so that it can be rendered later:

class ILabel {
public:
    virtual ~ILabel() = default;
    
    [[nodiscard]] virtual std::string BuildHTML() const = 0;
};

class SimpleLabel : public ILabel {
public:
    SimpleLabel(std::string str) : _str(std::move(str)) { }
    
    [[nodiscard]] std::string BuildHTML() const override {
        return "<p>" + _str + "</p>";
    }
    
private:
    std::string _str;    
};

class DateLabel : public ILabel {
public:
    DateLabel(std::string dateStr) : _str(std::move(dateStr)) { }
    
    [[nodiscard]] std::string BuildHTML() const override {
        return "<p class=\"date\">Date: " + _str + "</p>";
    }
    
private:
    std::string _str;    
};

class IconLabel : public ILabel {
public:
    IconLabel(std::string str, std::string iconSrc) : 
         _str(std::move(str)), _iconSrc(std::move(iconSrc)) { }
    
    [[nodiscard]] std::string BuildHTML() const override {
        return "<p><img src=\"" + _iconSrc + "\"/>" + _str + "</p>";
    }
    
private:
    std::string _str;    
    std::string _iconSrc;
};

The example above shows ILabel interface and then several derived classes which implements BuildHTML member function.

And here we have the use case, where we have a vector with pointers to ILabel and then we call the virtual function to generate the final HTML output:

std::vector<std::unique_ptr<ILabel>> vecLabels;
vecLabels.emplace_back(std::make_unique<SimpleLabel>("Hello World"));
vecLabels.emplace_back(std::make_unique<DateLabel>("10th August 2020"));
vecLabels.emplace_back(std::make_unique<IconLabel>("Error", "error.png"));

std::string finalHTML;
for (auto &label : vecLabels)
    finalHTML += label->BuildHTML() + '\n';

std::cout << finalHTML;

Nothing fancy above, the calls to BuildHTML are virtual so at the end we’ll get the expected output:

<p>Hello World</p>
<p class="date">Date: 10th August 2020</p>
<p><img src="error.png"/>Error</p>

And here’s the case with std::variant:

struct VSimpleLabel {
    std::string _str;    
};

struct VDateLabel {
    std::string _str;    
};

struct VIconLabel {
    std::string _str;    
    std::string _iconSrc;
};

struct HTMLLabelBuilder {
    [[nodiscard]] std::string operator()(const VSimpleLabel& label) {
        return "<p>" + label._str + "</p>";
    }
    [[nodiscard]] std::string operator()(const VDateLabel& label) {
        return "<p class=\"date\">Date: " + label._str + "</p>";
    }
    [[nodiscard]] std::string operator()(const VIconLabel& label) {
        return "<p><img src=\"" + label._iconSrc + "\"/>" + label._str + "</p>";
    }
};

In the previous code sample, I simplified the interface for the Label classes. Now, they store only the data and the HTML operations are moved to HTMLLabelBuilder.

And the use case:

using LabelVariant = std::variant<VSimpleLabel, VDateLabel, VIconLabel>;
std::vector<LabelVariant> vecLabels;
vecLabels.emplace_back(VSimpleLabel { "Hello World"});
vecLabels.emplace_back(VDateLabel { "10th August 2020"});
vecLabels.emplace_back(VIconLabel { "Error", "error.png"});

std::string finalHTML;
for (auto &label : vecLabels)
    finalHTML += std::visit(HTMLLabelBuilder{}, label) + '\n';

std::cout << finalHTML;

The example is available at Coliru

Alternatives  

HTMLLabelBuilder is only one option that we can use. Alternatively, we can also write a generic lambda that calls the member function from the derived classes:

struct VSimpleLabel {
    [[nodiscard]] std::string BuildHTML() const {
        return "<p class=\"date\">Date: " + _str + "</p>";
    }
    
    std::string _str;    
};

struct VDateLabel {
    [[nodiscard]] std::string BuildHTML() const {
        return "<p class=\"date\">Date: " + _str + "</p>";
    }

    std::string _str;    
};

struct VIconLabel {
    [[nodiscard]] std::string BuildHTML() const {
        return "<p><img src=\"" + _iconSrc + "\"/>" + _str + "</p>";
    }

    std::string _str;    
    std::string _iconSrc;
};

auto callBuildHTML = [](auto& label) { return label.BuildHTML(); };
for (auto &label : vecLabels)
    finalHTML += std::visit(callBuildHTML, label) + '\n'

This time we’re using a generic lambda, which gives a benefit of having the call in one place.

Adding Concepts to Generic Lambdas  

In the disadvantage section for std::variant/std::visit I mentioned that Duck typing might sometimes be an issue. If you like, you can enforce the interface on the types and functions. For example, with C++20, we can write a concept that allows us to call generic lambda only on types that expose the required interface.

(Thanks to Mariusz J for this idea!)

template <typename T>
concept ILabel = requires(const T v)
{
    {v.buildHtml()} -> std::convertible_to<std::string>;
};

The concept is satisfied by all types that have buildHtml() const member function that returns types convertible to std::string.

Now we can use it to enforce the generic lambda (thanks to the constrained auto terse syntax):

auto callBuildHTML = [](ILabel auto& label) -> std::string { return label.buildHtml(); };
for (auto &label : vecLabels)
    finalHTML += std::visit(callBuildHTML, label) + '\n';

See the example at @Wandbox

More Examples  

I also have one other blog post where I experimented with my old project and replaced a bunch of derived classes into std::variant approach.

Have a look:

Replacing unique_ptr with C++17’s std::variant a Practical Experiment

Performance  

Another critical question you may want to ask is about the performance of this new technique.

Is std::visit faster than virtual dispatch?

Let’s find out.

When I created a simple benchmark for my ILabel example, I got no difference.

You can see the benchmark here @QuickBench

I guess the string handling has high cost over the whole code execution; also there are not many types in the variant, so this makes the actual call very similar.

But, I have another benchmark that uses a particle system.

using ABC = std::variant<AParticle, BParticle, CParticle>;
std::vector<ABC> particles(PARTICLE_COUNT);

for (std::size_t i = 0; auto& p : particles) {
  switch (i%3) {
    case 0: p = AParticle(); break;
    case 1: p = BParticle(); break;
    case 2: p = CParticle(); break;
  }
  ++i;
}

auto CallGenerate = [](auto& p) { p.generate(); };
for (auto _ : state) {
  for (auto& p : particles)
    std::visit(CallGenerate, p);
}

The Particle class (and their versions AParticle, BParticle, etc) uses 72 bytes of data, and they have the Generate() method that is “virtual”.

And this time I got 10% per improvement for the std::visit version!

So why the code might be faster? I think we might have several things here:

  • the variant version doesn’t use dynamic memory allocation, so all the particles are in the same memory block. CPUs can leverage this to get better performance.
  • Depending on the number of types it might be the case that runtime if that is used to check the currently active type in a variant is much faster and more predictable to the compiler than pointer chasing for v-table.

Here’s also another benchmark that shows that the variant version is 20% slower than a vector with just one type: std::vector<AParticle> particles(PARTICLE_COUNT);. See it at QuickBench

Other Performance Results  

My test was relatively simple and might not mean that std::visit is always faster. But to get a better perspective you might want to have a look at this excellent presentation from Mateusz Pusz who implemented a whole TCPIP state machine and got much better performance with std::visit. The execution times were also more stable and predictable than virtual calls.

CppCon 2018: Mateusz Pusz “Effective replacement of dynamic polymorphism with std::variant” - YouTube

Code Bloat And Build Times  

There are also concerns about the code bloat that you might get from std::visit. Since this feature is a pure library implementation without extra support from the language, we can expect that it will add extra bytes to your executable.

If you worry about this issue, then you might check the following links:

It’s also worth remembering that the library solution works with all mixtures of std::variant, even with many variants passed in, so you pay for that “generic” support. If you’re not satisfied with the performance of the library, and you have a limited set of use cases, you can roll your implementation and see if that improves your code.

Build Performance of std::visit and std::variant  

I showed you some numbers with runtime performance, but we also have a tool that allows us to test the compilation speed of those two approaches.

See here @BuildBench

And the results: GCC 10.1, C++17, O2:

Buils Times

So it’s almost the same! In terms of preprocessed lines, it’s even smaller for the variant version 39k vs 44k. Regarding assembler, it’s 2790 LOC for the variant version and 1945 LOC for virtual.

Sorry for an interruption in the flow :)
I've prepared a little bonus if you're interested in Modern C++, check it out here:

Summary  

In the article, we looked at a new technique to implement runtime polymorphism. With std::variant we can express an object that might have many different types - like a type-safe union, all with value semantics. And then with std::visit we can call a visitor object that will invoke an operation based on the active type in the variant. All makes it possible to have heterogeneous collections and call functions similarly to virtual functions.

But is std::variant-based polymorphism better than a regular “virtual” polymorphism? There’s no clear answer, as both have their strengths and weaknesses. For example with std::variant, you need to know all of the possible types upfront, which might not be the case when you write a generic library or some kind of a plugin system. But on the other hand std::variant offers value semantics which might improve the performance of the system and reduce the need to use dynamic allocation.

I also got a perfect summary from people who used that code in production. Here’s one great comment from Borys J (see his profile at Github):

Some time ago I used std::variant/std::visit to implement processing of different types of commands in an embedded system. Good thing about variants is that polymorphism works without indirection - you don’t need a pointer or reference like with virtual functions. This helps in cases when the object would need to be created in a function and then returned from it. I often code without using heap/dynamic memory at all so I cannot just create an object dynamically within a function and then pass the ownership upwards. With variant, I can just return it by value (assuming it’s reasonably small) without loosing polymorphism.

On the other hand, using them as a type-oriented branching technique I found that as you move them around (in common sense, I don’t mean move semantics) and you need to process them at different stages you end up writing a new type of visitor each time you need to do something with the variant. To make things worse, sometimes the way different types within the variant are processed differs only slightly. In the result, you end up with multiple visitors, some of them being kind of intermediate and unnatural, each with few separate member functions for each variant type. At the end of the day, you have the good old callback hell once again. Sure, you can utilise the lambda overload construct but it doesn’t change that much.

Back to you:

  • Have you played with std::variant and std::visit?
  • Did you use it in your production code or just small project?

Share your experience in comments below!

References