Serving the Quantitative Finance Community

 
User avatar
pcaspers
Topic Author
Posts: 30
Joined: June 6th, 2005, 9:49 am
Location: Germany

virtual calls overhead / crtp

August 1st, 2015, 5:03 pm

Is there evidence on how much overhead virtual function calls produce / what performance gain you can get from replacing them by a crtp in practice ? Any small examples that demonstrate that ? I am trying to compare this on some simple code snippets, but I literally do not see *any* difference w.r.t. timings.
Last edited by pcaspers on July 31st, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
lballabio
Posts: 0
Joined: January 19th, 2004, 12:34 pm

virtual calls overhead / crtp

August 1st, 2015, 5:33 pm

Hi Peter, I had huge gains when we moved trees in QuantLib from virtual methods to CRTP, but I don't have a simple example. I might try to retrieve the change from version control.It was quite a few years ago, though, and compilers might have improved in the meantime and made it less of a difference.
 
User avatar
pcaspers
Topic Author
Posts: 30
Joined: June 6th, 2005, 9:49 am
Location: Germany

virtual calls overhead / crtp

August 1st, 2015, 5:58 pm

Hello Luigi, thank you. It would surely be interesting to see if there is a similar speedup with current compilers. If it is not too involved to get the old version back and running.
 
User avatar
Polter
Posts: 1
Joined: April 29th, 2008, 4:55 pm

virtual calls overhead / crtp

August 1st, 2015, 8:50 pm

 
User avatar
pcaspers
Topic Author
Posts: 30
Joined: June 6th, 2005, 9:49 am
Location: Germany

virtual calls overhead / crtp

August 2nd, 2015, 7:11 am

Thanks, that seems to confirm what Luigi says. (Unfortunately wejgomi's links do not seem to be valid any more?)
 
User avatar
pcaspers
Topic Author
Posts: 30
Joined: June 6th, 2005, 9:49 am
Location: Germany

virtual calls overhead / crtp

August 2nd, 2015, 12:13 pm

Here is quite a nice analysis
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

virtual calls overhead / crtp

August 2nd, 2015, 3:41 pm

Of course, CRTP and subtype polymorphic are wrong design in many case. You need a new derived class for each specific overridden function ==> explosion in the number of classes..Instead, class B{std::function< void ()> ovverridable_fun;};1 class, many instances.Q. Has C+11 'override' any impact?// I remember: nested functions (Normal/Unif) CRTP was 10 times faster.
 
User avatar
pcaspers
Topic Author
Posts: 30
Joined: June 6th, 2005, 9:49 am
Location: Germany

virtual calls overhead / crtp

August 2nd, 2015, 4:25 pm

QuoteOf course, CRTP and subtype polymorphic are wrong design in many case.Yes. But not always :-)QuoteQ. Has C+11 'override' any impact?Don't think so, in my understanding this only is a compile time check to ensure that your implementation of a virtual function is actually matching, to avoid errors due to misspelling or different modifiers.
Last edited by pcaspers on August 1st, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
Polter
Posts: 1
Joined: April 29th, 2008, 4:55 pm

virtual calls overhead / crtp

August 2nd, 2015, 8:35 pm

`final` does, at least since GCC 4.9: "New type inheritance analysis module improving devirtualization. Devirtualization now takes into account anonymous name-spaces and the C++11 final keyword."Explanation: http://hubicka.blogspot.com/2014/08/dev ... ing.html// "In this post I will focus on C++11 final specifier and a way how compiler can aid user to annotate the code to improve code quality."There are even more powerful devirtualization features in GCC 5: http://hubicka.blogspot.com/2015/04/GCC ... ws.html"14% fewer calls remains without a speculation after the ipa-devirt pass. The number of speculative devirtualizations also improved by 16%. By removal of now useless polymorphic call targets, the number of functions drops from 221880 to 198467, 11%."Another nice summary: https://web.archive.org/web/20150201191 ... irtualize/
Last edited by Polter on August 1st, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
lballabio
Posts: 0
Joined: January 19th, 2004, 12:34 pm

virtual calls overhead / crtp

August 3rd, 2015, 3:25 pm

Peter, the change was in revision 27d8ae0. The previous revision was 84f3208. It's from 10 years ago, so I'm not sure that they will compile with a modern Boost version. Let me know if you get them working. For comparison, you can run the BermudanSwaption example before and after the change.(Also, after a while I realized that for most classes I didn't really need CRTP, templates were enough. Oh well.)
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

virtual calls overhead / crtp

August 3rd, 2015, 4:28 pm

QuoteOriginally posted by: Polter`final` does, at least since GCC 4.9: "New type inheritance analysis module improving devirtualization. Devirtualization now takes into account anonymous name-spaces and the C++11 final keyword."But final means you cannot create derived classes and/or overwrite methods. pcaspers,good point about inheritance.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

virtual calls overhead / crtp

August 3rd, 2015, 4:43 pm

Quote(Also, after a while I realized that for most classes I didn't really need CRTP, templates were enough. Oh well.)For good or bad, software styles are driven by developer preferences (and prejudices.) It is not Theology. The new templates in C++ make thing a lot more readable.
Last edited by Cuchulainn on August 2nd, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
pcaspers
Topic Author
Posts: 30
Joined: June 6th, 2005, 9:49 am
Location: Germany

virtual calls overhead / crtp

August 3rd, 2015, 5:32 pm

QuoteOriginally posted by: lballabioPeter, the change was in revision 27d8ae0. The previous revision was 84f3208. It's from 10 years ago, so I'm not sure that they will compile with a modern Boost version. Let me know if you get them working. For comparison, you can run the BermudanSwaption example before and after the change.(Also, after a while I realized that for most classes I didn't really need CRTP, templates were enough. Oh well.)QuantLib 0.3.10 :-) yes, it compiles with Boost 1.57.0 (after amending a few things: observable.hpp - insert a forward declaration of Observer, sobolrsg,hpp - delete the extra qualification before nextSequence, quote.hpp - include errors.hpp, BermudanSwaption.cpp - compile with -fpermissive). The Bermudan swaption example runs as well, it takes 1m10s on my machine. In the current master, after commenting out the fd pricing engines in the example which were not present back then and assuming the rest is doing the same as before (it seems so), 1m7s, so practically no difference.
 
User avatar
lballabio
Posts: 0
Joined: January 19th, 2004, 12:34 pm

virtual calls overhead / crtp

August 3rd, 2015, 8:08 pm

Not sure I've got it---which one is 1m10? Before or after the change? Do you see any difference between 27d8ae0 and 84f3208 if you compile them both?
 
User avatar
lballabio
Posts: 0
Joined: January 19th, 2004, 12:34 pm

virtual calls overhead / crtp

August 3rd, 2015, 8:17 pm

QuoteOriginally posted by: CuchulainnQuote(Also, after a while I realized that for most classes I didn't really need CRTP, templates were enough. Oh well.)For good or bad, software styles are driven by developer preferences (and prejudices.) It is not Theology. Yes, but there are constraints. Assuming you don't want virtual functions, if a method defined in the base class needs to call a method defined in the derived class (so basically, the Template Method pattern) you'll need CRTP. If not, ordinary templates are enough.What I meant with that quotation was that I thought I was in the first case, and only afterwards I realized I was in the second instead.