C++ 20: How about metaprogramming over inheritance?

Intro

This blog introduces the metaprogramming technique with C++ 20 and ways to elinminate the virtual table considering the trade-off, and how would you choose from when it comes to an engineering decision.

Also, Just wanna let you know! This passage is 100% hand-written!

Reference

• C++ Core Guide Line
• isocpp

Polymorphism

When we say polymorphism, we generally consider 2 cases: dynamic one and static one. You might be familiar with the former one where we use a base class pointer to access common fields and methods, with code provided below:

class UIWidget {
    public:
        virtual void onClick() = 0;
};

class MyWidget: public UIWidget{
    void onClick() override {
        // ...
    }
};

std::unique_ptr<UIWidget> w = std::make_unqiue<MyWidget>();

Notice that you use a UIWidget pointer to point to a MyWidget object because you are sure MyWidget must support the same interface as UIWidget.

However, such mechanism is driven by virtual table, and it's intuitive enough. Imagine when UIWidget has lots of implementations, e.g., MyWidget, YourWidget, HisWidget, etc, how would you ensure you are pointing to the corresponding ones? A virtual table is then used as a map that maps pointer to functions of its implementation classes.

Here the thing is, you use one pointer to point to multiple classes, which set you free from writing endless overrides, but it takes cost. You pay for the cost to look up the virtual table to find the implementation functions. See the graph below for a reference.

auto A = std::make_unique<AWidget>();
auto B= std::make_unique<BWidget>();

// A's vptr points to AWidget's vtable:
A -> A's vptr -> class AWidget's vtable -> class AWidget's func

// B's vptr points to BWidget's vtable:
B -> B's vptr -> class BWidget's vtable -> class BWidget's func

It's not only a matter of looking up your tables. When you call the functions that way, you make indirect branch which prevents from the branch prediction and inlining. In a hot path of a high-frequency system, you generally don't hope this happen.

And that's why you may want to use metaprogramming.

Meta Programming

The intutition is even more simple. If you don't want vtables and run-time polymorphism, just write hard code. This honestly works very well and in the early years people actually did a lot through thousands of function overrides.

The thing is, still quite simple, is there any way that we can write the "code" once, and generate the "inherited code" in a way like pay-as-you-go. Say, you called A and B, then compiler generates overrides for A and B, and insert the generated code directly into the source code during pre-processing. And that's how people implemented the template in C++.

We will have another blog talking more about the template metaprogramming techniques. Today we just discover it generally.

In pre-11 stage, people used various "black magics" upon the template, such as Curiously Recurring Template Tattern (CRTP), an old way to implement static polymorphism and actually still being mentioned til the Concept introduced by C++20. Concept is much more readable and intuitive, and I strongly recommend using it if you are writing libraries. Read some source codes like SObjectizer, which is developed in C++17 (No concepts) and you will find how weird the code is.

You may write a simple concept and use it like this:

// Define the concept:
// Must have a onClick() method
template <typename T>
concept Clickable = requires(T obj) {
    { obj.onClick() } -> std::same_as<void>;
};

// Require the concept on a function
template<typename T>
    requires Clickable<T>
void callClick(T& widget){
    widget.onClick;
};

And when you call function "callClick" with whatever class that implements concept "Clickable", the code after pre-processing will be:

class SomeWidget {public: void onClick() {std::cout << "Hey\n";}};
SomeWidget sw;

// Before preprocessing
callClick(someWidget); 

// After preprocessing:
sw.onClick();

Trade-Offs

Metaprogramming may cause an explosion of source code size. It might look alright before pre-processing but doubles a couple times when compiling. This would crash your instruction caches! In high-frequency scene, we generally want to make the full use of our cache since fetching from caches/memory is pretty much a high and unpredictable cost.

And you have also lost the ability to add polymorphism during the run time since you must re-compile your code to introudce new entrants. This would be annoying for almost every GUI applications.

My recommendation is, like I said, if you are writting a library then metaprogramming is definitely a good choice. And there are ways to combine vtable and concepts, but we are not gonna talk about it this time.

Beyond

This is not the only use of metaprogramming. There are much more to discover such as type erasure, weird requirements (e.g., a field of required name), etc. People may remeber the modules from C++ 20 and laugh on it for its not being fully supported, but concept is always a good reason to start a C++ 20 project.