Static polymorphism

Part 3 gave you one way to say “these types share an interface”: a base class with virtual functions. The call goes through a pointer stored in the object, and which function runs is decided while the program is running.

Templates give you another way. The interface is checked at compile time, the call goes straight to the function, and there is no base class in the object at all. This chapter is about when each is right — and the answer is not “always the fast one”.

#include <iostream>

struct Dynamic {
    virtual ~Dynamic() = default;
    virtual int scale(int x) const = 0;
};

struct DynamicDouble : Dynamic {
    int scale(int x) const override { return x * 2; }
};

struct StaticDouble {
    int scale(int x) const { return x * 2; }
};

template <class T>
int apply(const T& op, int x) { return op.scale(x); }

int main() {
    DynamicDouble d;
    const Dynamic& base = d;
    StaticDouble s;

    std::cout << apply(base, 21) << ' ' << apply(s, 21) << '\n';
}

Both print 42, and — press Assembly — both compile to movl $42. Neither call survives at all.

That is worth pausing on, because it contradicts the usual story. base refers to a DynamicDouble that was constructed three lines earlier and never left main, so the compiler knows its dynamic type exactly. Knowing that, it replaces the virtual call with a direct one and inlines it, the same as for StaticDouble. A vtable is not a cost the compiler is obliged to pay.

It becomes one as soon as the compiler loses sight of the dynamic type — which happens the moment the reference crosses a function boundary the optimiser cannot see through.

The cost of a virtual call, examined

“Virtual calls are slow” is folklore worth pinning down. The direct cost is one extra load and an indirect branch, which a modern branch predictor usually gets right. The real cost is that the compiler cannot inline through it — and everything the inliner would have done next does not happen either.

#include <iostream>
#include <memory>

struct Op {
    virtual ~Op() = default;
    virtual int apply(int x) const = 0;
};
struct AddOne : Op {
    int apply(int x) const override { return x + 1; }
};

struct StaticAddOne {
    int apply(int x) const { return x + 1; }
};

template <class F>
long long sum_applied(const F& op, int rounds) {
    long long total = 0;
    for (int i = 0; i < rounds; ++i) total += op.apply(i);
    return total;
}

long long virtual_total(const Op& op)          { return sum_applied(op, 1000); }
long long direct_total(const StaticAddOne& op) { return sum_applied(op, 1000); }

int main() {
    std::unique_ptr<Op> dynamic_op = std::make_unique<AddOne>();
    StaticAddOne static_op;
    std::cout << virtual_total(*dynamic_op) << ' ' << direct_total(static_op) << '\n';
}

Both print 500500. Press Assembly and find the two functions. On GCC at -O2, direct_total is two instructions:

movl  $500500, %eax
ret

The loop is gone. apply was inlined, the body became total += i + 1, and a thousand iterations of a known recurrence folded into one constant at compile time.

virtual_total is thirty-odd instructions with a real loop in the middle. GCC does something clever there — it loads the address of AddOne::apply, compares the vtable entry against it, and runs an inlined fast path when they match. That is speculative devirtualization, and it is the compiler guessing. It still has to keep the loop, and it still has to keep the indirect call for the case where the guess is wrong, because a const Op& could refer to anything.

CRTP: a base class that knows its derived type

The interesting case is when you want what inheritance gives you — shared code in a base, customised in a derived — without the indirection. The trick is to tell the base which derived class it belongs to, as a template argument.

#include <iostream>
#include <sstream>
#include <string>

template <class Derived>
class Formattable {
public:
    // Written once, in terms of a `write` the derived class supplies.
    // The call is direct: no virtual, no vtable.
    std::string to_string() const {
        std::ostringstream out;
        self().write(out);
        return out.str();
    }

    std::string boxed() const {
        std::string body = to_string();
        return "[" + body + "]";
    }

private:
    const Derived& self() const { return static_cast<const Derived&>(*this); }
};

class Version : public Formattable<Version> {
public:
    Version(int major, int minor) : major_(major), minor_(minor) {}
    void write(std::ostream& os) const { os << major_ << '.' << minor_; }

private:
    int major_, minor_;
};

class Celsius : public Formattable<Celsius> {
public:
    explicit Celsius(double degrees) : degrees_(degrees) {}
    void write(std::ostream& os) const { os << degrees_ << " \u00b0C"; }

private:
    double degrees_;
};

int main() {
    Version v{1, 10};
    Celsius t{21.5};

    std::cout << v.boxed() << ' ' << t.boxed() << '\n';
    std::cout << "sizeof(Version): " << sizeof(Version) << " bytes\n";
}

class Version : public Formattable<Version> is the curious recurrence: the base is parameterised on the class that derives from it. That is legal because the base only needs Version to be complete when its members are instantiated — which happens when they are called, long after the class is finished.

boxed() is the payoff. It is written once, calls to_string(), which calls self().write(out), which is Version::write — resolved at compile time and inlinable all the way down. A virtual write would have stopped the inliner at the first step.

Look at the size. Version is 8 bytes: two ints and nothing else. An empty base class contributes no storage, and there is no vtable pointer because there are no virtual functions. The same interface built with a virtual compare would be 16 bytes on a 64-bit machine — a vtable pointer, two ints, and padding.

#include <iostream>

template <class Derived>
class Counted {
public:
    static int live() { return live_; }
    int id() const { return id_; }

private:
    friend Derived;                 // only Derived may construct the base
    Counted() : id_(++next_) { ++live_; }
    ~Counted() { --live_; }

    int id_;
    static inline int next_ = 0;
    static inline int live_ = 0;
};

class Session : public Counted<Session> {};
class Job     : public Counted<Job> {};

int main() {
    Session a, b;
    Job j;
    std::cout << "sessions live: " << Session::live() << '\n';
    std::cout << "jobs live:     " << Job::live() << '\n';
    std::cout << "second session id: " << b.id() << ", first job id: " << j.id() << '\n';
    (void)a;
}

The private constructor plus friend Derived is the standard belt-and-braces CRTP guard. It also demonstrates the second thing CRTP is used for: each instantiation of Counted<T> has its own statics, so Session and Job get independent counters from one piece of code.

Concepts do the interface checking

CRTP’s weakness used to be error messages: pass the wrong type and you got a failure deep inside the base. Concepts fix that, and they also let you write static polymorphism with no base class at all.

#include <concepts>
#include <iostream>
#include <string>

template <class T>
concept Shape = requires(const T& s) {
    { s.area() } -> std::convertible_to<double>;
    { s.name() } -> std::convertible_to<std::string>;
};

struct Circle {
    double r;
    double area() const { return 3.14159265 * r * r; }
    std::string name() const { return "circle"; }
};

struct Square {
    double side;
    double area() const { return side * side; }
    std::string name() const { return "square"; }
};

void report(const Shape auto& s) {
    std::cout << s.name() << " has area " << s.area() << '\n';
}

int main() {
    report(Circle{1.0});
    report(Square{2.0});
}

Circle and Square share no base class, no header, and no knowledge of each other. They satisfy Shape by having the right members, which is what people mean by duck typing — except that it is checked, and the check happens before the program runs.

So when is virtual still right?

Every time the set of types is not known when the code is compiled.

#include <iostream>
#include <memory>
#include <string>
#include <vector>

struct Widget {
    virtual ~Widget() = default;
    virtual std::string render() const = 0;
};

struct Button : Widget { std::string render() const override { return "[button]"; } };
struct Label  : Widget { std::string render() const override { return "label"; } };
struct Spacer : Widget { std::string render() const override { return "   "; } };

int main() {
    // One container, three different types, chosen at run time.
    std::vector<std::unique_ptr<Widget>> layout;
    layout.push_back(std::make_unique<Label>());
    layout.push_back(std::make_unique<Spacer>());
    layout.push_back(std::make_unique<Button>());

    for (const auto& w : layout) std::cout << w->render();
    std::cout << '\n';
}

A std::vector<T> holds one type. This vector holds three, and which three is decided by code that runs — read from a config file, chosen by a user, loaded from a plugin. No amount of if constexpr gets you there, because the decision is not available to the compiler.

The dividing line, then:

That last row is the cost nobody mentions. A template instantiates a fresh copy of its code for every type it is used with. Ten types means ten copies in the binary and ten times the compilation work. Virtual dispatch compiles once and links once, and there is a size at which that stops being a fair trade.

Check yourself

Practice