C++: what is the Curiously-Recurring-Template-Pattern? and can Curiously-Recurring-Template-Pattern replace virtual functions?

Question

I don't have a precise description of the problem so I'm just asking if this is possible (and if it is, some other information would be great).

A programmer told me you can avoid runtime overhead caused by virtual functions/polymorphism. He said to avoid the runtime overhead you can use templates in pattern called Curiously_recurring_template_pattern which looks something like this:

class Derived : public Base<Derived>
{
  // ... implementation here
};

How does this Curiously-Recurring-Template-Pattern work?

How can one use Curiously-Recurring-Template-Pattern to substitute normal virtual functions/polymorphism?

Did I get it wrong?

Gabi

One cannot. The two are totally different and solve different problems. However, it is commonly the case that people mistakenly use X when they should be using Y, and then the advice would be to "use Y rather than X". That doesn't mean that X and Y are related, just that people don't know what they're doing. – Cerf

Whoa, it is CRTP pattern. – Frond

Answer 1

Very specifically, the CRTP can be used instead of a base class with virtual functions to implement the template method pattern without virtual function call overhead.

With virtual functions, the TMP looks like this:

class ProvidesMethod {
protected:
  void Method() {
    // do something
    Part1();
    // do something else
    Part2();
    // do something final
  }

private:
  virtual void Part1() = 0;
  virtual void Part2() = 0;
};

class ExposesMethod : private ProvidesMethod {
public:
  using ProvidesMethod::Method;

private:
  void Part1() {
    // first part implementation
  }
  void Part2() {
    // second part implementation
  }
};

With the CRTP, it looks like this:

template <typename Derived>
class ProvidesMethod {
protected:
  void Method() {
    // do something
    self().Part1();
    // do something else
    self().Part2();
    // do something final
  }

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

class ExposesMethod : private ProvidesMethod<ExposesMethod> {
public:
  using ProvidesMethod<ExposesMethod>::Method;

private:
  friend class ProvidesMethod<ExposesMethod>;
  void Part1() {
    // first part implementation
  }
  void Part2() {
    // second part implementation
  }
};

Copilot

Why are the "self" methods required? Why not just call Part(); ? – Schoolmaster

Because that would use the type of this in the context of Method, which is ProvidesMethod, which doesn't have Part1 - as the compiler will be quick to point out if you just try this change. Alternatively, if your CRTP base has default implementations of the parts, the compiler will use those, with no chance for the derived class to override them, because they're not virtual calls. – Copilot

Answer 2

this is called CRTP (for Curiously Recurring Template Pattern) so you can look it up.

Although I don't really see how it could replace classic polymorphism...

On the other hand, one can in some cases replace complex hierarchical structure of classes by template, (see policy-based design for more info), but it's not always possible...

Cell

Answer 3

As Julien noted, this is CRTP. You should look it up. But the CRTP cannot replace virtual functions. If it does in a particular case for you, then you didn't actually need virtual functions in the first place. Look, templates provide compile-time polymorphism. Virtual functions provide run-time polymorphism. If you don't know what which override is going to be called at compile time, then a template based solution isn't going to work. If you always know what the real type of an object is going to be at runtime, then you don't need virtual functions.

Smackdab

Answer 4

I'm not sure how you would use templates to provide something like virtual functions - it seems strange to me - certainly without a bunch of trickery that eventually amounts to implementing your own version of virtual functions instead of using the compiler provideed ones, I find it very hard to see how you can make a way that the code calling the function don't know what type the object is, and call the correct function for that object type. Which is what virtual functions do.

Further, from personal experience, the ACTUAL overhead from virtual functions is very small, and only in very extreme cases does it make a difference (the main case where the non-virtual function becomes inlined, and is so trivial that the overhead of calling a function is a substantial part of the total execution time (which also means the function needs to be called many times for it to make any significant difference). There is MORE overhead if you have to "work out what to do" (using if-statements or something like that) in some other way [other than implementing your own variation on "virtual function", but that's just reinventing the wheel, and unless your new wheel is better than the existing one, that's not a good idea].

Donatus

I agree that CRTP likely adds obscurity for little real life performance gains much of time time. However the ability to inline code is a serious thing in short functions that have to run fast. It avoids function call overhead, stack usage, and can improve caching. The indirect lookup needed for virtual functions can be significant. – Secretarygeneral

I agree, but if you actually NEED to execute something different based on which class it is, there needs to be an if, switch, or function pointer type solution. Virtual is almost always the most efficient of those. The lookup is only significant if the vtable isn't in cache and the this pointer isn't in cache - and if you are using some member data, at least the this pointer needs to be loaded into cache anyway. – Donatus

@MatsPetersson There doesn't have to be any selection statement. CRTP "simulates" virtual dispatch like this: template <typename Derived> class Base { void foo() { ((Derived*)this)->pseudoVirtualBar(); } This will call different functions based on the template parameter (i.e. the derived class). – Refractive

Right, so it hides the typecast to the correct type, when doing a "manual" polymorphism. Which is great if you know at compile time what you want to choose. But then you can ALSO solve this case with a more obvious cast. Either way, unless we have extreme circumstances (e.g. returning one integer, or the sum of two integer members, or something similarly trivial), virtual functions have fairly low overhead. – Donatus

I believe CRTP is intended to 'look like' a polymorphic structure but all the bindings are made at compile time; hence no run time overhead. As @Mats states if you're having to do a lot of ifs, switches, etc. to simulate run time polymorphism you're better off using real virt calls. – Secretarygeneral