C++ Tutorial: How to use CRTP to speed up your code

CRTP (curiously recurring template pattern) is a powerful C++ design. This video shows how to use it to speed up interface code.

Tools that I use:

In code:

[marcusmors]

Sick improvement. Can't wait to see my professor's face after applying this. Thank you so much.

[Paul-fnwb]

Hi Zen, great video! I searched for "crtp" in youtube and found this one. Thank you for a clear explanation of the topic. The benchmark times surprised me a lot.

[Bobbias]

I've come across crtp before but never really understood its value. Now I sure as hell do. That performance improvement is absolutely wild, especially for such a simple example.

[krzysztofdabrowski]

Than u very much it allowed me to understand this better!

[Dziaji]

omg, those eyes! Never seen anything like them.

[danwu]

thank you! please make more c++ videos.

[panjak]

Well, but it's really not polymorphic in the true sense of the word. Can't put different objects into vector and iterate over them whilst expecting polymorphism.

[smu]

have you checked if the benchmark was correct? I mean on assembly level. Is it not possible that there is more about that on optimization level and it optimizes the calculation also out. That is also a great step, but different reason.

[Gismo]

The new "deducing this" feature might be worth mentioning here, as it can essentially replace most CRTP use cases but with much less code

[peskyjellyfish]

Thanks for the clear explanation of CRTP. In your example you add up the loop index in the Count function. Clang knows this specific loop and usually replaces it with the closed sum formula N(N+1)/2. In this case, the CRTP might just help with inlining the Count function, so Clang can optimize the looping. I'm not sure you'd get such a dramatic performance boost just by avoiding the virtual function overhead. If you change the count function to a `counter += n % 10` do you still see increased performance?

[MaitreBart]

Subject well introduced.
I find crtp quite an interesting application of compile-time polymorphism.
But from what I can foresee, any possible implementation of the interface needs to be a template class, thus be coded in header files, thus in some way, "public". So I guess for companies that wish to make their libraries implementation hidden, this is a no-go, right?
Also, I'd would be interested to see a couple of examples where one can use this principle in a multiple inheritance context (e.g. vertical-only and fanned out).

[rvoros]

Let me challenge your intro to CRTP.
1) It'd need some explanation how come the template can refer to an undefined type when defining Derived?

2) RunCRTP has to be templated so Derived must be known by it and also must be known by the caller.
So then simply using T* obj as arg would do the job without the fuss of CRTP. Thus based on this example, CRTP doesn't offer anything. We need an example where it really shines. This isn't it. (and no others shine either that I have seen)

I want to show the power of giving a good example. Recursion is a nice idea but when books demonstrate it through the calculation of factorial you see it's pointless because a for loop would do the job much simpler and easier so you don't get it. What's the point? Because the example was not strong enough.
On the other hand if you introduce the concept of recursion through tree traversing, for example, then it's obvious. No questions asked.

[ДенисПручковский-ыф]

I believe it's a bad idea to write code avoiding normal inheritance in favor of CRTP. In most simple cases compiler can replace dynamic call to a simple static function call. And performance will be exactly the same (I've checked it)
I do not deny that there are situations where the compiler cannot (cannot yet) get rid of a virtual call, and the method invocation time is comparable to the running time of that method. But it happens very rarely (almost never)

[jthrush]

I see a big drawback of this is that (AFAIK) you can’t have an array of interfaces. Each element would need its own template type. You could probably make it work with tuples but i don’t see a way to make it work with arrays.

[ItsBaffledd]

Excuse my ignorance but how does this differ from just skipping the CRTP method and just having each child class implement their own "void DoSomething()" that is not virtual?

You are still defining the child class with RunCRPT so you could also just use the child class directly? This doesnt "Skip" inheritance because you cant have

Base* b = c; it needs to still define the type like so

Base<Child>* b = child

So why not just use
Child* cptr = c;

The template removes any kind of anonymity to the parent type and just says "This is your exact parent type". I dont see the use case in this example?

[dibyojyotibhattacherjee]

Will there be any c++ project series or advent of code in c++?

[RyanLynch]

can you do a video about why virtual methods are so slow and when they should be used?

[lucy-pero]

so static dispatch is faster than dynamic dispatch at runtime. Mind-blowing revelations in this video. Jesus.

[roykimor]

if you know the template type you're going to pass to RunCRPT then its just like accepting the generated Base_CRTPImplemented generated compiler name and you can't use it in containers of type interface really

[Dziaji]

This actually doesn't work. It completely removes the point of a virtual function to begin with. The problem is that all the derived types will now have different base types. Usually, the point of a virtual function is so you can have an array of base type pointers, and by calling the virtual function from the base type pointer, each object "knows" its derived type and calls the corresponding function.

Using the way he describes in this video, you can't make an array of base types, because each derived type has its own unique base type, so you have to make an array for each derived type, and if you have separate arrays for each type, you might as well make each array with its own derived type, so the concept of a virtual function becomes pointless. Using his example, you might as well make the template function take "(T* obj)" as a parameter instead of "(Base<T> *obj)".

The CRTP technique CAN be used to speed up virtual functions a bit, but you have to add another non-template base class that your crtp class inherits from so that all the cinstances can be casted to the same type to make an array, and you have to create a function pointer as a member, and in the constructor of the derived class, you set that pointer equal to a static function defined in the derived class. This means that the runtime will not have to do a lookup to figure out which dervied class type to use, the object will have the function pointer as one of its own data members. There are a couple points to take into consideration for this method:
- It will not be as fast as a non virtual function call, because of the fact that the location of the function is not known at compile time, so you have an indirection where the pointer needs to be accessed before the function is called, but since you are probably about to access other members of that object anyway, the value of the pointer is probably already cached (or was about to be cached) so it won't even add an additional RAM access, so it is super fast compared to doing a lookup for that function pointer by first accessing the virtual method table.
- if you only have 1 or 2 virtual functions using this method, you will save ram over the standard virtual function scheme, because each object will have 1 extra pointer, and that would be the case with a virtual function as well, but since this method has no virtual function table, you save on RAM. However, each additional pseudo-virtual function you create in this way will add another pointer to every instance, while virtual functions will continue to only add a single pointer to each instance, so it could end up wasting a lot of RAM, so in that case, you are trading RAM for speed.
- You have to be careful with the default assignment operator of the base class, because setting a base class instance equal to another will copy the pseudo virtual function pointer as well, and if you are setting a base type equal to a derived type casted to a base type, you will crash if you try to call this virtual method. So to deal with that, you need to explictly implement the assignment operator for your base class and set that pointer equal to the base class's version of the function, and to properly copy a dervied class, you have to use the standard "base *Dervied::Copy()" function, and you can use the pseudo-virtual scheme for that too.
- Your pseudo virtual member functions will now be static functions, so you have to call them with the "this" pointer as the first member like you would have to do with C, so to call them, you have to do obj.PseudoVirtualFn(obj, otherParams), but you can get around this by using an intermediate function that does this for you automatically.