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

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

  1. #16
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,196

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

    Quote Originally Posted by TSLexi
    The C++ standard should require compilers to support devirtualization in order to be compliant.
    The C++ standard does not require any particular scheme for the implementation of virtual functions, hence it cannot require any particular optimisation pertaining to such implementations. It could require compilers to implement virtual calls as non-virtual calls wherever possible, but that may well be too loose a requirement since "wherever possible" depends on how good the compiler is at the analysis required to determine that such an optimisation can be correctly applied. So, for compilers that lack the implementation of such optimisations, this is not a bug, but rather the lack of a feature.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  2. #17
    Join Date
    Dec 2013
    Posts
    75

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

    Why won't the committee require compilers to implement devirtualization in order to be compliant?

  3. #18
    Join Date
    Apr 1999
    Posts
    27,418

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

    Quote Originally Posted by TSLexi View Post
    Why won't the committee require compilers to implement devirtualization in order to be compliant?
    Because that is an implementation detail, and the C++ standard doesn't dictate implementation details.

    Give us a small sample of code that would result in "devirtualization".

    Regards,

    Paul McKenzie

  4. #19
    Join Date
    Dec 2013
    Posts
    75

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

    Code:
    class Functor
    {
      public:
    	Functor();
    	Functor(const Functor & rhs) = default;
       virtual ~Functor() =default; 
    	virtual float operator() (const FloatV  & input) const =0;
    	virtual int GetArgNum() const =0;
    };
    
    class Plane: public Functor
    {
      public:
    	Plane() = delete;
    	Plane(const FloatV& values);
    	Plane(const Plane & rhs) = default;
    	 virtual ~Plane() = default; 
    	virtual float operator() (const FloatV & input) const;
    	virtual int GetArgNum() const;
      private:
         const int argnum;
    	 const FloatV cf;
    };
    Code:
    class Trainer
    {
      public:
    	Trainer() = delete;
    	Trainer(const Functor& function);
    	void GenerateData();
    	  FloatV& GetData();
    	int GetAnswer() const;
      private:
    	const Functor& f;
    	mutable FloatV TrainingData;
    	mutable int answer;
    };
    Code:
    int main()
    {
    Plane f(coefficients)
    Trainer t(f);
    t.GenerateData();
    t.GetData();
    return 0;
    }
    Last edited by TSLexi; February 2nd, 2014 at 12:33 AM.

  5. #20
    Join Date
    Oct 2008
    Posts
    1,077

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

    that devirtualization case is trivial and has been implemented by compilers for ages. But, devirtualizing all possibly statically resolved virtual calls requires a lot of work from the compiler, especially with the c++ aliasing rules, object and compilation models. So, the best you can ask to a compiler is to being able of devirtualizing "typical" use cases to the extent of making OO the best choice to the avarage programmer ( so, as other said, you don't "need" generic programming techniques, and no I never opposed to OO methodology or any other silly allusion ruzzle claims ). But, if you need tight control on what can be statically resolved (eg. you're a library writer and you want your library components to be used by any programmer with nearly-arbitrary requirements ) then TMP is still the way to go.

    sorry if I repeat myself, but CRTP and OO inheritance serve diferent purposes, so it's like asking which is better between a car and a screwdriver; yes, they have a common point of implementing polymorphic behavior, but the list ends here.

    on the other hand, if your question is: should I bother with manually resolving polymorphic behavior at compile time ? obviously it depends on your/your potential users requirements (after proper profiling) and obviously most of the time ( and hence in prima facie ) it's not worth it ( furthermore, it depends in the overall design of the code you're working own: clearly, it's easier to find CRTP-like patterns in a generic programming library rather than in an OO design ).

    or, if your question is: there exists the theorical need of manually resolving polymorphic behavior at compile time ? IMO definitely yes, because the compiler cannot do everything a programmer can. The point has nothing to do with microoptimizations of virtual calls but it has to do with semantics, has to do with asking the compiler to do his work the best in almost all occasions.

    As a concrete example of a non-devirtualizable but statically resolvable code, consider this simple snippet ( off the top of my head, sorry if I missed something )

    Code:
    struct A{virtual void foo();};
    struct B:A{void foo();};
    struct C:A{void foo();};
    
    struct D
    {
    	void bar( A* pp ){ p = pp; } // D has the semantical property that bar <should> be called exactly once
    	void foo(){ p->foo(); }
    
    	A* p;
    };
    
    // ...
    
    D d;
    
    d.bar( new B{} );
    foobar( d ); // foobar being a semantically correct but dynamically resolved call
    d.foo();
    the compiler cannot prove that D:: p points to a B so devirtualization cannot occur; nonetheless, the <semantics> of D tells us that D:: p must be a B.
    Now, this is obviosuly not a realistic example, but situations like that can happen in more complex/real examples as well due to the relatively weak c++ rules laserlight alluded to.

    Moreover, the fact that the compiler could in principle prove what the dynamic object of a pointer is, does not imply that the compiler will succeed at proving it, due to time/memory constraints. For example, consider

    Code:
    A* p = foobar(c) ? new B{} : new C{};
    p->foo();
    where foobar is an algebraic expression E(c) depending, say, on an integer c provided by user input. Now, we could mathematically prove that E(c) always holds true for every possible c, but the compiler may not be able of proving it in a reasonable time due to intrisic limitations given by the algorithmic complexity it's using. In contrast, if foobar were augmented with domain specific compile time data we could suggest the compiler which algorithm to use to prove that foobar is true in a reasonable time.
    Last edited by superbonzo; February 2nd, 2014 at 08:40 AM. Reason: typos

  6. #21
    Join Date
    Dec 2013
    Posts
    75

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

    So we've moved from arguing execution speed to arguing compile speed...compile in the cloud for fast compilation, execute on multi-core chipsets for fast execution.

  7. #22
    Join Date
    Oct 2008
    Posts
    1,077

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

    Quote Originally Posted by TSLexi View Post
    So we've moved from arguing execution speed to arguing compile speed...compile in the cloud for fast compilation, execute on multi-core chipsets for fast execution.
    no, I never argued about compilation speed ( the compiler will simply give up an optimization route if it sees the time will explode; so, this has nothing to do with compilation speed, but with the result of compilation, hence execution speed as you call it ); please, reread carefully what I wrote or tell me where I expressed myself wrongly ...
    Last edited by superbonzo; February 2nd, 2014 at 04:56 AM.

  8. #23
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,643

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

    Quote Originally Posted by TSLexi View Post
    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.
    No, that's not the inherent reason why CRTP exists. CRTP exists to templatize class behaviour in a generic way.

    The other is a side effect that works well in a highly controlled environment (like the Java VM and .NET) where 'every' type has an associated runtime type. And makes not so much sense in a language that is less expectant of it's runtime environment.

    There are cases of CRTP where "virtual" isn't even at all used.


    Quote Originally Posted by TSLexi View Post
    When would *you* use CRTP over virtual functions? When your design says that the pointed to object can never be changed at runtime?
    Again, no, the "pointed to object" is irrelevant, unless you are using a "side effect" of CRTP in a specific way.

    When would I use it... When I have a need for generic class behaviour and there are sufficiently many (many dozens) of classes that the added confusion/complexity outweighs the fact you don't need to repeat the same bits of code in each class.
    And in that case, I would also add "it depends who the target audience of said classes are". THe higher end (more experience) the expectancy of your target audience, the easier it is to introduce such idioms.


    I understand CRTP, and that it allows smaller class memory representations
    NO.
    THe amount of generated code will be largely the same. Genericism via templates does not reduce amount of generated code, it only reduces amount of code writte (along with other benefits such as less likely to write errors, ...)

    and faster execution speed
    More likely than not... this isn't going to make a change.
    If you CRTP a virtual function it'll still be a virtual function. If you CRTP a non-virtual, the end result is the same non-virtual.

    There is a change devirtualization might make a change, but again... this won't matter much in C++


    And with modern compiler optimizations like devirtualization, virtual functions should be as fast as CRTP
    Mmmm... no. See next.


    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.
    1) Yes, compiler have become smarter in removing unnecessary calls to a virtual if the compiler can establish the precise type and can thus call the function directly rather than using the 'virtual mechanism' (not all compilers use vtables for this).

    2) The problem is worse on java where the code is interpreted by the VM (or runtime compiled), and the type is dynamic so there's a much bigger runtime cost than a simple "vtable lookup and call through pointer" of native C++ code running on actual hardware.
    So there has been less need to try and solve this for C++ because the difference between a direct call and a virtual call is immeasurable.

    The above is especially true with the "base address randomization" feature which basically changes all calls to indirect calls anyway, so the difference between a "regular" function call and a virtual function call is even less.


    If you really have a case where the difference between regular/virtual call would actually matter (as in a noticable part of the CPU time is going into the call itself), then the real issue is the call/return itselfr and not the regular/virtual nature of said call.
    Last edited by OReubens; February 3rd, 2014 at 07:46 AM.

  9. #24
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,643

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

    It would appear you don't quite understand CRTP just yet. Maybe just a particular sub-aspect of it when used in the specific case with virtual functions (a very narrow view at CRTP as a whole).
    CRTP is not only about virtuals. You can also make a CRTP template with regular member functions or static functions
    or... The purpose is genericism in class behaviour.
    The specific end-behaviour can be static, virtual, or can be derived from template specialization or a combination of multiple/all of these.

  10. #25
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,643

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

    Quote Originally Posted by OReubens View Post
    If you really have a case where the difference between regular/virtual call would actually matter (as in a noticable part of the CPU time is going into the call itself), then the real issue is the call/return itselfr and not the regular/virtual nature of said call.
    Just thought about this, but oddly enough... CRTP can be a way to actually solve this issue by avoiding the function call entirely (replacing it with a inline) at the cost of runtime code duplication (which would be the solution anyway) without the actual C++ code duplciation.

    consider:

    Code:
    class base
    {
    public:
    	virtual void Calc(int& x) = 0;
    
    	int func_using_Calc_many_times()
    	{
    		int x=0;
    		// more code here
    
    		for (int i=0; i<1000000000; ++i)
    		{
    			// more cod ehere
    			Calc(x);
    		}
    
    		// more code here, using x.
    		return x;
    	}
    };
    
    class derived : public base
    {
    	virtual void Calc(int& x)
    	{
    		x = (x+1) * x + 1;
    	}
    };
    
    int main()
    {
    	derived d;
    	int x = d.func_using_Calc_many_times();
    }
    The above generates 1 billion calls to a virtual function. Since the virtual function itself is small, the overhead of the actual call is significant.

    Now consider a CRTP approach where you templatize the func_using_Calc_many_times() and CRTP it so you can easily duplicate the entire function in all your classes, but instead of a virtual, since the call is now part of the class, it can be optimized to an inline. You will get a full implementation of the function in each class rather than 1 generic function calling to many virtuals. So this'll take more code, but be faster since it saves the virtual while conceptually still offering the same dynamicism.

    Code:
    template <typename T>
    class cbase
    {
    public:
    	int func_using_Calc_many_times()
    	{
    		int x=0;
    		// more code here
    
    		for (int i=0; i<1000000000; ++i)
    		{
    			// more cod ehere
    			T::Calc(x);
    		}
    
    		// more code here, using x.
    		return x;
    	}
    };
    
    class cderived : public cbase<cderived>
    {
    public:
    	static void Calc(int& x)
    	{
    		x = (x+1) * x + 1;
    	}
    };

    Trying the above on my PC.
    the virtual solutions runs in 6.5 sec
    the CRTP solution runs in 5 sec
    Which is a 23% improvement. For an even simpler Calc() this would be more prominent. 23% might be significant.
    But how many times is your virtual function called 1 billion times. Except for this "enforced" example, the 1.5sec difference will not be noticable.


    Or as a conclusion, CRTP can be a means to remain having generic code without the virtual call overhead.
    THat doesn't mean all cases of CRTP are doing exactly what's happening here. Again, this is 1 specific case where CRTP can be used to do something (in this case: automate code repetition/duplication in each derived class to get as sideeffect that you remove a call entirely by allowing the compiler to inline a static).

  11. #26
    Join Date
    Jul 2013
    Posts
    168

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

    Quote Originally Posted by Paul McKenzie View Post
    Because that is an implementation detail, and the C++ standard doesn't dictate implementation details.
    This is a flawed argument.

    If devirtualization were required by the standard then it would cease to be an implementation detail.

  12. #27
    Join Date
    Jul 2013
    Posts
    168

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

    Quote Originally Posted by superbonzo View Post
    sorry if I repeat myself, but CRTP and OO inheritance serve diferent purposes, so it's like asking which is better between a car and a screwdriver; yes, they have a common point of implementing polymorphic behavior, but the list ends here.
    No.

    Polymorphism is polymorphism and it serves the purpose of polymorphic behaviour regardless of when it's resolved, be it at compiletime or runtime.

    The only difference is that the CRTP (used to simulate OO inheritance) is resolved at compiletime since it's a template pattern, whereas ordinary OO inheritance (using virtual functions) is resolved at runtime. Unless, that is, devirtualization optimization can be applied to the latter. Then they're equivalent and you can replace CRTP with OO inheritance. It won't change the semantics or meaning of your code. The compiler output will be equivalent, even identical.

    I'm no stranger to making things faster by resolving things at compiletime by it's not a design issue. The C++ template system is a form of generics and that's not the same kind of polymorphism as OO inheritance. I know that but the difference is not when the polymorphisms get resolved.

    If you dropped this artificial rift between compiletime and runtime you wouldn't be so confuddled.
    Last edited by razzle; February 18th, 2014 at 07:15 AM.

  13. #28
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,643

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

    Quote Originally Posted by razzle View Post
    whereas ordinary OO inheritance is resolved at runtime.
    This is flat out wrong. It is resolved at compiletime just the same way. That's why C++ has strictly typed. it's the compiler that decides it will call a member through a v-table (or some other mechanism) or whether it can definitely decide that it can call the member directly.
    Runtime has nothing to do here.


    Again I fear the point about CRTP is lost somewhere. CRTP is not "an alternative solution to replace virtuals". It can sometimes be used as such, but that's not really what it's about.

    virtual members are an important part of (dynamic) polymorphism
    CRTP is a means to automate class genericism, this genericism may have nothing to do at all with polymorphism. Though admittedly static polymorphism is an obvious use of CRTP.

  14. #29
    Join Date
    Jul 2013
    Posts
    168

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

    Quote Originally Posted by OReubens View Post
    This is flat out wrong. It is resolved at compiletime just the same way. That's why C++ has strictly typed. it's the compiler that decides it will call a member through a v-table (or some other mechanism) or whether it can definitely decide that it can call the member directly.
    Runtime has nothing to do here.
    No you are wrong. The call of a virtual function is not resolved (or bound as it's also called) at compiletime. The type checking can be performed at compiletime unless a downcast is involved. But the call itself is resolved at runtime by way of a so called dynamic dispatch. That's why it takes a little longer than a non-virtual call.

    Again I fear the point about CRTP is lost somewhere. CRTP is not "an alternative solution to replace virtuals". It can sometimes be used as such, but that's not really what it's about.
    Nothing is lost. Have a look again at the title of the thread.

    virtual members are an important part of (dynamic) polymorphism
    CRTP is a means to automate class genericism, this genericism may have nothing to do at all with polymorphism. Though admittedly static polymorphism is an obvious use of CRTP.
    No.

    CRTP is a template pattern that can be used to simulate OO polymorphism (virtual functions) at compiletime. That's the usage we're talking about here.

    My point is that with devirtualization enabled, CRTP will be nothing but a premature optimization. The compiler will optimize your ordinary OO polymorphic code to do exactly what you thought you needed CRTP to accomplish.
    Last edited by razzle; February 18th, 2014 at 09:11 AM.

Page 2 of 2 FirstFirst 12

Posting Permissions

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


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center