C++: Polymorphism - CRTP

The virtual dispatch post covered the runtime branch, templates Pt 1 the compile-time one. CRTP is what Pt 1 left in its out-of-scope box:

                         POLYMORPHISM
                (same interface, many behaviors)
                              |
              +---------------+---------------+
              |                               |
        COMPILE TIME                      RUNTIME
     (type known statically)      (type known only at runtime)
              |                               |
      +-------+-------+              +--------+--------+
      |       |       |              |        |        |
  function  operator  templates   virtual  variant   manual fn
 overloading overloading (incl.   dispatch  + visit   pointers /
                        CRTP)    (open set) (closed   type erasure
                      ^^^^^^^^                set)
                      this post

Motivation

Virtual functions cost you a vtable pointer in every object, an indirect call at every invocation, and no inlining across that call. Worth paying when the dynamic type is only known at runtime and the compiler can’t tell which override runs.

Plenty of code that reaches for virtual doesn’t need that. The concrete type is known at compile time and you only wanted to write the shared logic once. CRTP gets the reuse without the dispatch.

The Mechanism

A base class template takes its own derived class as a template parameter:

template <typename Derived>
class Animal {
public:
    void speak() {
        static_cast<Derived*>(this)->speakImpl();
    }
};

class Dog : public Animal<Dog> {
public:
    void speakImpl() { /* bark */ }
};

class Cat : public Animal<Cat> {
public:
    void speakImpl() { /* meow */ }
};

Dog passes itself as the template argument to its own base. That’s the curiously recurring part.

Dog d; d.speak(); instantiates Animal<Dog>, fixing Derived as Dog. The cast in speak() is then static_cast<Dog*>(this), resolved at compile time. No vtable, no indirect call, and speakImpl() can inline into speak().

With a body simple enough to see through, the whole call collapses:

template <class D> struct Animal { int speak() { return static_cast<D*>(this)->speakImpl(); } };
struct Dog : Animal<Dog> { int speakImpl() { return 42; } };
int crtp_call(Dog& d) { return d.speak(); }

struct VAnimal { virtual int speak() = 0; };
struct VDog : VAnimal { int speak() override { return 42; } };
int virt_call(VAnimal& a) { return a.speak(); }

crtp_call(Dog&):              virt_call(VAnimal&):
  mov  $42, %eax                mov  (%rdi), %rax     # load vptr
  ret                           jmp  *(%rax)          # indirect call

Nothing to fold on the virtual side, since the target isn’t known until runtime. Sizes follow:

sizeof(Dog)   CRTP     1     empty base, no vptr
sizeof(VDog)  virtual  8     the vptr

What the Cast Costs

static_cast is free of checks, never free of work, but under single inheritance the work is also nothing:

Dog object in memory, single inheritance
addr 0x1000
  +-------------------------+
  | Animal<Dog> subobject   |  <- 0x1000
  |  (empty, no members)    |
  +-------------------------+
  | Dog's own members       |  <- 0x1000
  +-------------------------+

static_cast<Dog*>(this):
  this   = 0x1000   (type Animal<Dog>*)
  result = 0x1000   (type Dog*)

instructions emitted: NONE

Base subobject and derived object share an address, so only the static type changes.

Put the base at a nonzero offset and the cast becomes one fixed subtraction, the offset taken from the class layout:

struct Big { int a, b; };                                  // 8 bytes, sits first
template <typename D> struct Base {
    int tag;
    int get() { return static_cast<D*>(this)->impl(); }     // Base at offset 8
};
struct Derived : Big, Base<Derived> { int y; int impl(); };

callit(Base<Derived>&):
  sub  $8, %rdi                 # the whole cast
  jmp  Derived::impl()

Still no lookup, no branch. Casting a raw pointer adds a null test, since static_cast maps null to null: lea -8(%rdi) plus testq/cmovne. Casting this doesn’t, because this is never null.

dynamic_cast reads the vtable pointer out of the object, walks RTTI, then works out the offset or returns null. Memory-dependent and branchy. That’s the difference that matters on a hot path.

What You Give Up

Animal<Dog> and Animal<Cat> are unrelated types, the same way vector<int> and vector<string> are:

std::vector<Animal<Dog>*> v;
v.push_back(new Dog);
v.push_back(new Cat);

error: no matching function for call to
       'std::vector<Animal<Dog>*>::push_back(Cat*)'

There’s no common base to point at. CRTP buys speed by giving up runtime polymorphism, so a heterogeneous container still needs virtual, a variant, or type erasure.

Naming the Wrong Base

The base is spelled with the derived type inside it, so a copy-paste gets you this:

class Dog : public Animal<Dog> { public: void speakImpl() { std::puts("bark"); } };
class Cat : public Animal<Dog> { public: void speakImpl() { std::puts("meow"); } };
//                       ^^^ should be Cat

Cat::speak() casts a Cat* to Dog* and calls Dog::speakImpl on it. A Cat barks:

$ g++ -std=c++17 -Wall -Wextra footgun.cpp && ./a.out
bark

No error, no warning. It’s the same unchecked cast as before, and at runtime there’s nothing left to check against.

Check

Dog forgets to define speakImpl() entirely:

template <typename Derived>
class Animal {
public:
    void speak() { static_cast<Derived*>(this)->speakImpl(); }
};
class Dog : public Animal<Dog> { };   // no speakImpl

int main() { Dog d; }

Does that compile?

error: 'class Dog' has no member named 'speakImpl'

error: cannot declare variable 'd' to be of abstract type 'Dog'

template <typename D> struct Animal {
    static_assert(sizeof(D) > 0);       // D is Dog, mid-definition
};
class Dog : public Animal<Dog> { public: void speakImpl() {} };

error: invalid application of 'sizeof' to incomplete type 'Dog'

class Mute : public Animal<Mute> { };   // forgot speakImpl
static_assert(Speaker<Mute>, "Mute is missing speakImpl()");

error: static assertion failed: Mute is missing speakImpl()