Why is the CRTP used instead of virtual functions?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 29

Thread: Why is the CRTP used instead of virtual functions?

  1. #1
    Join Date
    Dec 2013
    Posts
    75

    Why is the CRTP used instead of virtual functions?

    I was reading about the CRTP, and I can't for the life of me understand it's advantages over virtual functions.

    Unless you're coding embedded systems, and can't afford the few extra bytes for the vptr, or coding something requiring high-performance, where every nanosecond counts, I just don't see why the CRTP is so attractive. It just adds more text and forces every user class that wants to use the CRTP'd hierarchy to become a template class.

    I tried implementing my Functor hierarchy with the CRTP instead of virtual functions...All it did was clutter my files with angle brackets and made the whole thing look very ugly.

    Please, enlighten this chick.

    Lexi

  2. #2
    Join Date
    Apr 1999
    Posts
    27,433

    Re: Why is the CRTP used instead of virtual functions?

    Quote Originally Posted by TSLexi View Post
    I was reading about the CRTP, and I can't for the life of me understand it's advantages over virtual functions.
    en.wikipedia.org/wiki/Template_metaprogramming
    http://en.wikipedia.org/wiki/Templat...c_polymorphism

    As to code being "ugly", that is the nature of template metaprograms. Unless you are an advanced user of C++ and are used to this paradigm, then of course it won't look "natural" or "pretty".

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; January 31st, 2014 at 05:06 AM.

  3. #3
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,967

    Re: Why is the CRTP used instead of virtual functions?

    Quote Originally Posted by TSLexi View Post
    I was reading about the CRTP, and I can't for the life of me understand it's advantages over virtual functions.
    THe good news... you don't need to understand.

    It's an unusual pattern, and it's an advanced concept. It doesn't have a whole lot of good uses.
    Unless you're deeply into generic programming and/or advanced library/framework design, you probably won't ever need it.
    Even in the cases where you COULD use it, it's often a good idea to not bother and just do a bit more code repetition because you could confuse yourself and others that need to work on the classes more than it's worth.

  4. #4
    Join Date
    Jul 2013
    Posts
    301

    Re: Why is the CRTP used instead of virtual functions?

    Quote Originally Posted by TSLexi View Post
    I just don't see why the CRTP is so attractive.
    I don't think very many finds it attractive in the sense they use it whenever they can. At least not among OO programmers. I think most view CRTP as a legacy idiom (to be pulled out of the trick bag when some low level magic is needed).

    And it's even less attractive now that devirtualization optimizations are coming of age for C++. The compiler simply removes dynamic dispatches whenever possible.

    What surprises me is that it took so long. Java has had it for ages. Either it's because old C++ programmers so desperately need slow virtual calls to substantiate their critical view of OO, or it's because competition between compiler suppliers isn't working so no one is willing to put money into improvements.
    Last edited by razzle; February 1st, 2014 at 01:30 AM.

  5. #5
    Join Date
    Oct 2008
    Posts
    1,146

    Re: Why is the CRTP used instead of virtual functions?

    Quote Originally Posted by TSLexi View Post
    I was reading about the CRTP, and I can't for the life of me understand it's advantages over virtual functions.
    first of all, you're confusing two different goals: one is to let the compiler generate code avoiding code repetition, this is the main goal of CRTP; the other one is to inject code at compile time into a type behavior avoiding any kind of dispatch mechanism, this is not related to CRTP per se and it's a commonly found theme in generic programming ( take a look at traits, policies, tag dispatching, etc... ).

    Now, regarding why one should use CRTP, as OReubens already said, it's your choice from a user POV and if you don't know templates well ( there's not only the "ugliness" issue, there are many things like name look up rules that one should be aware of ) code repetition may be the lesser evil choice after all. That said, if you're a library writer those complexities will be hidden to the final (non-template) users anyway so why not ?

    moreover, the boiler plate code you want to generate often needs to fulfill a set of requirements that are simple but error prone; CRTP allows you to implement only a minimal subset of function necessary to implement everything with guaranteed behavior at no cost ( for example, consider a type mimicking an integer and exposing all usual integer operators, you have to make sure that (!a==b)==(a!=b), (a<b)==!(a>=b), etc... BTW, this is exactly what the Boost.Operator library does for you; it's a lot of code spared, at no cost, guaranteed to be corrected, presented expressively ( compare "myclass: is_integer_like<myclass>" with my_class{...} operator< ...A LOT OF operators... ; which one does express the intent better ? ) ).

    Yes, you can do the same by defining an OO hierarchy but this will have its own problems ( ignoring runtime costs, there's still slicing, enforcing possibly unrelated types to a common base, difficulties with virtual disptach of binary operators, etc ... ).

    Regarding the runtime costs issue, the "few extra bytes" and virtual call overhead can be comparatively high for small classes or often invoked methods. For example, the vptr will increase the size of an int-like object of >100% ( consider a computationally oriented program with billions of them; as a further example, consider iterators: these often have the size of a single pointer and are meant to be called in possibly tight loops too; doubling the size and inhibiting inlining to simple pointer arithmetic for no reason is just premature pessimization; BTW, Boost.Iterators defines a CRTP iterator facade/adaptor for this purpose ... ).

    Moreover, injecting code dependencies at compile time does not only mean sparing size and runtime calls; it also gives you the opportunity of using all that compile time information to perform domain specific optimizatons that are simply impossible to obtain otherwise. For example, given an algebra expression "a=some_operation(b,c);" the compiler can select at compile time the best algorithm given the <types> (and hence the meaning) of a,b and c at no cost; no compiler technology will ever do this, because no compiler could ever read programmer minds ( or better, if it could, programmers would lose their jobs anyway ).

    As a further example also involving size optimizations, consider a statistical facility used to compute statistics of data; those statistics often will share common substatistics in order to be computed ( for example, a mean needs the count and the total, a standard deviation needs a count, a total and a total of squares ), now, with generic programming the compiler can detect that and compute/store those substatistics once at no added cost, in a still expressive and highly extensible way ( BTW, Boost.Accumulators does exactly this, among other things ).
    Last edited by superbonzo; February 1st, 2014 at 04:00 AM.

  6. #6
    Join Date
    Dec 2013
    Posts
    75

    Re: Why is the CRTP used instead of virtual functions?

    That was an awesome reply. When would *you* use CRTP over virtual functions? When your design says that the pointed to object can never be changed at runtime?

    I just "get" virtual functions. I understand CRTP, and that it allows smaller class memory representations, and faster execution speed, but I honestly see virtual functions as a much cleaner way of achieving polymorphism. And with modern compiler optimizations like devirtualization, virtual functions should be as fast as CRTP

  7. #7
    Join Date
    Jul 2013
    Posts
    301

    Re: Why is the CRTP used instead of virtual functions?

    Quote Originally Posted by superbonzo View Post
    Regarding the runtime costs issue, the "few extra bytes" and virtual call overhead can be comparatively high for small classes or often invoked methods.
    Well, with devirtualization the OO approach is as efficient as CRTP.

    Do you understand that?
    Last edited by razzle; February 1st, 2014 at 05:44 PM.

  8. #8
    Join Date
    Jul 2013
    Posts
    301

    Re: Why is the CRTP used instead of virtual functions?

    Quote Originally Posted by TSLexi View Post
    And with modern compiler optimizations like devirtualization, virtual functions should be as fast as CRTP
    Note that devirtualization optimization cannot make virtual functions calls static if they really need to be dynamic. So devirtualization doesn't remove the need for dynamic calls. It just avoids making them uneccessarily.

    And this applies to CRTP. If you use OO and virtual functions instead to accomplish the same as CRTP, the devirtualization optimization will be produce code as efficient as if you used CRTP.

    So there is a use for CRTP in template programming to make it neater, but it won't be more efficient than OO (with devirtualization).

  9. #9
    Join Date
    Dec 2013
    Posts
    75

    Re: Why is the CRTP used instead of virtual functions?

    Quote Originally Posted by razzle View Post
    Note that devirtualization optimization cannot make virtual functions calls static if they really need to be dynamic. So devirtualization doesn't remove the need for dynamic calls. It just avoids making them uneccessarily.

    And this applies to CRTP. If you use OO and virtual functions instead to accomplish the same as CRTP, the devirtualization optimization will be produce code as efficient as if you used CRTP.

    So there is a use for CRTP in template programming to make it neater, but it won't be more efficient than OO (with devirtualization).
    That's the point I was trying to make. CRTP is an idiom only needed if your compiler lacks the ability to devirtualize your virtual function calls after static code analysis determines dynamic dispatch isn't required.

  10. #10
    Join Date
    Jul 2013
    Posts
    301

    Re: Why is the CRTP used instead of virtual functions?

    Quote Originally Posted by TSLexi View Post
    That's the point I was trying to make. CRTP is an idiom only needed if your compiler lacks the ability to devirtualize your virtual function calls after static code analysis determines dynamic dispatch isn't required.
    That's right.

    Superbonzo is opposing OO as a design methology mainly for efficiency reasons and for them devirtualization is the worst nightmare because it renders the efficiency argument moot.

    I'm not against template programming to do at compile time whatever's possible but I'm not willing to trade in the considerable advantages of OO design and replace it with template programming for efficiency reasons. That would be premature optimization (and an evil according to Knuth who's the master of proper optimizations).
    Last edited by razzle; February 1st, 2014 at 05:39 PM.

  11. #11
    Join Date
    Dec 2013
    Posts
    75

    Re: Why is the CRTP used instead of virtual functions?

    If your design method is completely based on a compiler flaw, you shouldn't be programming. It's a recipe for unmaintainable code

  12. #12
    Join Date
    Jul 2013
    Posts
    301

    Re: Why is the CRTP used instead of virtual functions?

    Quote Originally Posted by TSLexi View Post
    If your design method is completely based on a compiler flaw, you shouldn't be programming. It's a recipe for unmaintainable code
    Could you please expand on that. It's complicated stuff you know.
    Last edited by razzle; February 1st, 2014 at 05:58 PM.

  13. #13
    Join Date
    Dec 2013
    Posts
    75

    Re: Why is the CRTP used instead of virtual functions?

    https://www.thc.org/root/phun/unmaintain.html

    Compiler Dependent CodeIf you discover a bug in your compiler or interpreter, be sure to make that behaviour essential for your code to work properly. After all you don't use another compiler, and neither should anyone else!

  14. #14
    Join Date
    Jul 2013
    Posts
    301

    Re: Why is the CRTP used instead of virtual functions?

    Quote Originally Posted by TSLexi View Post
    Well, the lack of a devirtualization optimization in most C++ compilers isn't a bug really.

    But it's a pity it's not there already though. And as I've said Java has had it for ages (at least ten years).

    In my view devirtualization tilts the balance even further in favour of OO on C++. It becomes harder to claim efficiency reasons to avoid OO. Template programming becomes more just a way to do the compiler's work.

    I wish Don Superbonzo good luck in his fight against the windmills.
    Last edited by razzle; February 1st, 2014 at 06:45 PM.

  15. #15
    Join Date
    Dec 2013
    Posts
    75

    Re: Why is the CRTP used instead of virtual functions?

    The C++ standard should require compilers to support devirtualization in order to be compliant.

    TMP is wonderful for automatic code-generation, but an exercise in psychosis for code-optimization. If only the language could let you do metaprogramming without templates.

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center