Request For a feature - Templated virtual functions
Hi All, As you all know, there are situations, wherein the virtual function usage can be replaced with templates. But virtual functions can never be used with templates, since all the instantiations have to be tracked to form the virtual function table. But we can ask the user to provide a typelist of classes, that would probably be used with the virtual template function. I think this would solve this issue for most of the cases. Analyzing the instances where this would be useful - a) Any virtual function, which might need different types of arguments (not related to the inheritance hierarchy) b) I have a multi-method design pattern, where in i need more than one run-time resolution through the virtual functions. But sometimes, i might know one of the actual derived classes involved, with which i can avoid one virtual function call. I am not an expert in C++, but one way of achieving this would be to manually have a hash table with all the necessary function pointers for each class in the base class hierarchy and one such set for each of the classes mentioned in the typelist. Waiting for your feedback. Thanks in advance, Gokul.
On Wednesday 11 February 2009 13:27:46 Gokulakannan Somasundaram wrote:
As you all know, there are situations, wherein the virtual function usage can be replaced with templates. But virtual functions can never be used with templates, since all the instantiations have to be tracked to form the virtual function table. But we can ask the user to provide a typelist of classes, that would probably be used with the virtual template function. I think this would solve this issue for most of the cases.
If the list of arguments/return types is known at compile time, is this not the same as overloaded virtual functions? Here's an example: #include <iostream> using namespace std; struct Base { virtual void func( int ) { cout << "Base::int overload" << endl; } virtual void func( double ) { cout << "Base::double overload" << endl; } template <typename T> void virtfunc( T x ) { func( x ); } // "virtual" virtual ~Base() {} }; struct Derived : Base { virtual void func( int ) { cout << "Derived::int overload" << endl; } virtual void func( double ) { cout << "Derived::double overload" << endl; } virtual ~Derived() {} }; int main( int, char *[] ) { Base *p = new Derived; p->virtfunc( 3 ); p->virtfunc( 3.14 ); } $ g++ -o out -Wall tempvirt.cc $ ./out Derived::int overload Derived::double overload Regards, Ravi
On Thu, Feb 12, 2009 at 3:56 AM, Ravi <lists_ravi@lavabit.com> wrote:
On Wednesday 11 February 2009 13:27:46 Gokulakannan Somasundaram wrote:
As you all know, there are situations, wherein the virtual function usage can be replaced with templates. But virtual functions can never be used with templates, since all the instantiations have to be tracked to form the virtual function table. But we can ask the user to provide a typelist of classes, that would probably be used with the
virtual
template function. I think this would solve this issue for most of the cases.
If the list of arguments/return types is known at compile time, is this not the same as overloaded virtual functions? Here's an example:
#include <iostream> using namespace std; struct Base { virtual void func( int ) { cout << "Base::int overload" << endl; } virtual void func( double ) { cout << "Base::double overload" << endl; } template <typename T> void virtfunc( T x ) { func( x ); } // "virtual" virtual ~Base() {} }; struct Derived : Base { virtual void func( int ) { cout << "Derived::int overload" << endl; } virtual void func( double ) { cout << "Derived::double overload" << endl; } virtual ~Derived() {} };
int main( int, char *[] ) { Base *p = new Derived; p->virtfunc( 3 ); p->virtfunc( 3.14 ); }
$ g++ -o out -Wall tempvirt.cc $ ./out Derived::int overload Derived::double overload
Regards, Ravi
I think, i am trying to accomplish, what you have done through overloading through templates. Say if you have 10 such functions, with each implementation being different in the inheritance hierarchy, then you will write the same piece of code again and again, with different types. In your example you have written the functions twice, which is redundant. (same piece of code repeated twice). More overhead on maintenance,as the number of overloads increase. Hope i am able convey my point. Thanks, Gokul.
Gokulakannan Somasundaram wrote:
virtual functions can never be used with templates, since all the instantiations have to be tracked to form the virtual function table. But we can ask the user to provide a typelist of classes, that would probably be used with the virtual template function. I think this would solve this issue for most of the cases.
If you know all types before hand, just use Boost.Variant.
b) I have a multi-method design pattern, where in i need more than one run-time resolution through the virtual functions.
Boost.Variant supports that.
b) I have a multi-method design pattern, where in i need more than one
run-time resolution through the virtual functions.
Boost.Variant supports that.
Thanks for pointing me to Boost.Variant. But let me just try to clarify my
understanding on Boost Variant. It is a kind of union data type, where we store the data and its type together. Whenever we retrieve the data, it does a switch-case lookup and type-casts the data to that type. In my opinion, the switch-case is equivalent to a virtual table lookup. They should be having more or less the same runtime penalty. Infact if we have more virtual functions, it is better to go with the virtual table lookup. So for avoiding a virtual function call, we are introducing a virtual function call like penalty. I would just like to write some code to explain my case in more detail. Class Base1 { public: virtual void run1(int context) { std::cout << "Base1 Run1"<< context; } virtual void run2(int context) { std::cout << "Base1 Run2"<< context; } }; Class Derived1 : public Base1 { public: virtual void run1(int context) { std::cout << "Derived1 Run1"<< context; } virtual void run2(int context) { std::cout << "Derived1 Run2"<< context; } }; class Base2 { public: virtual void run(Base1* base1, int context) { base1->run1(context); } }; Class Derived2 : public Base2 { public: virtual void run(Base1* base1, int context) { base1->run2(context); } }; int main() { Base2* a = new Base2; Derived1* b = new Derived1; int context =2; a->run(b, context); }; Here even though, i know the type information of b, i am losing it. I can maintain it by function overloading, where in, i would repeat the same code for each overload. It would be much more elegant to achieve it with templates. Thanks, Gokul.
Gokulakannan Somasundaram wrote:
Thanks for pointing me to Boost.Variant. But let me just try to clarify my understanding on Boost Variant. It is a kind of union data type, where we store the data and its type together. Whenever we retrieve the data, it does a switch-case lookup and type-casts the data to that type. In my opinion, the switch-case is equivalent to a virtual table lookup. They should be having more or less the same runtime penalty.
Indeed. A switch-case is actually faster than a virtual table lookup, however.
Mathias Gaunard wrote:
A switch-case is actually faster than a virtual table lookup, however.
Is that independent of the number of cases? Thanks in advance, Niels -- Niels Dekker http://www.xs4all.nl/~nd/dekkerware Scientific programmer at LKEB, Leiden University Medical Center
Niels Dekker - mail address until 2010-10-10 wrote:
Mathias Gaunard wrote:
A switch-case is actually faster than a virtual table lookup, however.
Is that independent of the number of cases?
Both are constant-time. Nothing prevents a compiler to implement a switch/case with virtual functions, (well actually scope might be an issue, but circumventable), but typically it will do smarter things that do not prevent inlining for example.
Mathias Gaunard wrote:
Niels Dekker - mail address until 2010-10-10 wrote:
Mathias Gaunard wrote:
A switch-case is actually faster than a virtual table lookup, however.
Is that independent of the number of cases?
Both are constant-time. Nothing prevents a compiler to implement a switch/case with virtual functions, (well actually scope might be an issue, but circumventable), but typically it will do smarter things that do not prevent inlining for example.
Older versions of gcc actually create a jump table to compiler generated out-of-line functions, which show up as weak symbols. This could cause performance problems and the fix was generally to rewrite the code with if statements. To my imperfect knowledge, newer versions of gcc often compile switch/case to a conditional branch tree if the number of cases is small. branch_cost * log(num_cases) is constant if you bound num_cases to a constant. I'm not sure exactly what the compiler does when the number of cases is large, it is very rare. In any case, if you are using virual functions at all you've got much bigger performance penalties than vtable lookup itself or switch/case overhead. Virtual functions usually can't be inlined and out-of-line function calls make it impossible for the compiler to make assumptions that allow it to optimize code following the function call based upon information it gathered before the function call. This leads directly to the misconception that C++ is slower than C, and that Java is as fast as C++, since C++ written in a Java style effectively ties the compiler's hands. Regards, Luke
Simonson, Lucanus J wrote:
Mathias Gaunard wrote:
Niels Dekker - mail address until 2010-10-10 wrote:
Mathias Gaunard wrote:
A switch-case is actually faster than a virtual table lookup, however. Is that independent of the number of cases? Both are constant-time. Nothing prevents a compiler to implement a switch/case with virtual functions, (well actually scope might be an issue, but circumventable), but typically it will do smarter things that do not prevent inlining for example.
Older versions of gcc actually create a jump table to compiler generated out-of-line functions, which show up as weak symbols. This could cause performance problems and the fix was generally to rewrite the code with if statements. To my imperfect knowledge, newer versions of gcc often compile switch/case to a conditional branch tree if the number of cases is small. branch_cost * log(num_cases) is constant if you bound num_cases to a constant. I'm not sure exactly what the compiler does when the number of cases is large, it is very rare. In any case, if you are using virual functions at all you've got much bigger performance penalties than vtable lookup itself or switch/case overhead. Virtual functions usually can't be inlined and out-of-line function calls make it impossible for the compiler to make assumptions that allow it to optimize code following the function call based upon information it gathered before the function call. This leads directly to the misconception that C++ is slower than C, and that Java is as fast as C++, since C++ written in a Java style effectively ties the compiler's hands.
This reminds me of a discussion that came up when Steven Watanabe's Switch library was reviewed. http://lists.boost.org/Archives/boost/2004/08/69787.php -- Michael Marcin
AMDG Michael Marcin wrote:
This reminds me of a discussion that came up when Steven Watanabe's Switch library was reviewed.
That's quite different. The comparison there is between a control construct (switch statement) and using some bit twiddling to look up data in an array. Naturally, the straight line code is faster. If you store an array of function pointers to call, the functionality being compared would be more equivalent, but, that, of course, introduces the possibility of branch mispredictions, forfeiting all the gains of using a perfect hash. The test case there is also somewhat unrealistic in that it takes a different branch each time. In Christ, Steven Watanabe
On Fri, Feb 13, 2009 at 12:07 AM, Simonson, Lucanus J < lucanus.j.simonson@intel.com> wrote:
Mathias Gaunard wrote:
Niels Dekker - mail address until 2010-10-10 wrote:
Mathias Gaunard wrote:
A switch-case is actually faster than a virtual table lookup, however.
Is that independent of the number of cases?
Both are constant-time. Nothing prevents a compiler to implement a switch/case with virtual functions, (well actually scope might be an issue, but circumventable), but typically it will do smarter things that do not prevent inlining for example.
Older versions of gcc actually create a jump table to compiler generated out-of-line functions, which show up as weak symbols. This could cause performance problems and the fix was generally to rewrite the code with if statements. To my imperfect knowledge, newer versions of gcc often compile switch/case to a conditional branch tree if the number of cases is small. branch_cost * log(num_cases) is constant if you bound num_cases to a constant. I'm not sure exactly what the compiler does when the number of cases is large, it is very rare. In any case, if you are using virual functions at all you've got much bigger performance penalties than vtable lookup itself or switch/case overhead. Virtual functions usually can't be inlined and out-of-line function calls make it impossible for the compiler to make assumptions that allow it to optimize code following the function call based upon information it gathered before the function call. This leads directly to the misconception that C++ is slower than C, and that Java is as fast as C++, since C++ written in a Java style effectively ties the compiler's hands.
Regards, Luke
Thanks for the nice explanation. After your argument, i tried the code in Visual Studio and the Boost Variant was commandingly fast. I reran the code in g++ and it was equal. But what we are working with is the latest version of g++. I am planning to try this out in Sun Studio compiler and i will get back with the results. Please have a look at the code and i think it can't be more simpler.
Thanks, Gokul.
Gokulakannan Somasundaram wrote:
Thanks for pointing me to Boost.Variant. But let me just try to clarify my
understanding on Boost Variant. It is a kind of union data type, where we store the data and its type together. Whenever we retrieve the data, it does a switch-case lookup and type-casts the data to that type. In my opinion, the switch-case is equivalent to a virtual table lookup. They should be having more or less the same runtime penalty.
Indeed. A switch-case is actually faster than a virtual table lookup, however.
I did a small test in my system and the virtual function method proved to be slightly better than using boost::variant. The difference can be ignored, but then there is no use in switching to boost::variant. The method i suggest is simple, it just replaces the virtual function overloading with templates and hence it would provide better performance and better
On Thu, Feb 12, 2009 at 4:00 PM, Mathias Gaunard < mathias.gaunard@ens-lyon.org> wrote: maintenance. Thanks, Gokul.
----- Original Message ----- From: "Gokulakannan Somasundaram" <gokul007@gmail.com> To: <boost@lists.boost.org> Sent: Thursday, February 12, 2009 1:33 PM Subject: Re: [boost] Request For a feature - Templated virtual functions
On Thu, Feb 12, 2009 at 4:00 PM, Mathias Gaunard < mathias.gaunard@ens-lyon.org> wrote:
Gokulakannan Somasundaram wrote:
Thanks for pointing me to Boost.Variant. But let me just try to clarify my
understanding on Boost Variant. It is a kind of union data type, where we store the data and its type together. Whenever we retrieve the data, it does a switch-case lookup and type-casts the data to that type. In my opinion, the switch-case is equivalent to a virtual table lookup. They should be having more or less the same runtime penalty.
Indeed. A switch-case is actually faster than a virtual table lookup, however.
I did a small test in my system and the virtual function method proved to be slightly better than using boost::variant. The difference can be ignored, but then there is no use in switching to boost::variant. The method i suggest is simple, it just replaces the virtual function overloading with templates and hence it would provide better performance and better maintenance.
Hi, I'm interested. Could you show more :) Best, Vicente
On Thu, Feb 12, 2009 at 6:13 PM, vicente.botet <vicente.botet@wanadoo.fr>wrote:
----- Original Message ----- From: "Gokulakannan Somasundaram" <gokul007@gmail.com> To: <boost@lists.boost.org> Sent: Thursday, February 12, 2009 1:33 PM Subject: Re: [boost] Request For a feature - Templated virtual functions
On Thu, Feb 12, 2009 at 4:00 PM, Mathias Gaunard < mathias.gaunard@ens-lyon.org> wrote:
Gokulakannan Somasundaram wrote:
Thanks for pointing me to Boost.Variant. But let me just try to clarify
my
understanding on Boost Variant. It is a kind of union data type, where we store the data and its type together. Whenever we retrieve the data, it does a switch-case lookup and type-casts the data to that type. In my opinion, the switch-case is equivalent to a virtual table lookup. They should be having more or less the same runtime penalty.
Indeed. A switch-case is actually faster than a virtual table lookup, however.
I did a small test in my system and the virtual function method proved to be slightly better than using boost::variant. The difference can be ignored, but then there is no use in switching to boost::variant. The method i suggest is simple, it just replaces the virtual function overloading with templates and hence it would provide better performance and better maintenance.
Hi,
I'm interested.
Could you show more :) Best, Vicente
Hi, Sorry! I don't get you. i have just made a feature request, to allow templates in virtual functions, if the knowledge of the classes involved is known at Compile time and waiting for someone to take up my request :) Thanks, Gokul.
----- Original Message ----- From: "Gokulakannan Somasundaram" <gokul007@gmail.com> To: <boost@lists.boost.org> Sent: Thursday, February 12, 2009 1:56 PM Subject: Re: [boost] Request For a feature - Templated virtual functions
Hi,
I'm interested.
Could you show more :) Best, Vicente
Hi, Sorry! I don't get you. i have just made a feature request, to allow templates in virtual functions, if the knowledge of the classes involved is known at Compile time and waiting for someone to take up my request :)
Oops! I need to read more carefully the posts :( Vicente
On Thu, Feb 12, 2009 at 8:29 PM, Mathias Gaunard < mathias.gaunard@ens-lyon.org> wrote:
Gokulakannan Somasundaram wrote:
I did a small test in my system and the virtual function method proved to
be slightly better than using boost::variant.
I'd be interested in seeing such a test.
Attaching the files.. Thanks, Gokul.
Gokulakannan Somasundaram wrote:
Attaching the files..
Testing with GCC 4.3.2, -O3 -march=native -fomit-frame-pointer on an Intel Core 2 Duo. My results are: Time elapsed: 2621 mu.s 11000000 Time elapsed: 3136 mu.s 22000000 Time elapsed: 2250 mu.s 5000000 Hence, switch is slightly faster. Why do you test two times for the variant by the way?
Hence, switch is slightly faster.
I got even better results for switch with Visual Studio, but on Linux gcc 4.3.2, i am getting almost equal values for both. But we can say for sure that Boost Variant is not as fast as the direct function call. . That's why i am requesting a feature to allow limited functionality of templates inside the virtual functions.
Why do you test two times for the variant by the way?
There's no special reason for that. I just wanted to see, whether there
would be any difference.. Thanks, Gokul.
Gokulakannan Somasundaram wrote:
I got even better results for switch with Visual Studio, but on Linux gcc 4.3.2, i am getting almost equal values for both. But we can say for sure that Boost Variant is not as fast as the direct function call. . That's why i am requesting a feature to allow limited functionality of templates inside the virtual functions.
Well you can't do dynamic dispatch any faster than with a switch.
On Fri, Feb 13, 2009 at 4:19 PM, Mathias Gaunard < mathias.gaunard@ens-lyon.org> wrote:
Gokulakannan Somasundaram wrote:
I got even better results for switch with Visual Studio, but on Linux gcc
4.3.2, i am getting almost equal values for both. But we can say for sure that Boost Variant is not as fast as the direct function call. . That's why i am requesting a feature to allow limited functionality of templates inside the virtual functions.
Well you can't do dynamic dispatch any faster than with a switch.
Ok! i think i am not able to put forward my point. My request is to replace switch / dynamic dispatch with a compile time optimization with templates.
participants (8)
-
Gokulakannan Somasundaram -
Mathias Gaunard -
Michael Marcin -
Niels Dekker - mail address until 2010-10-10 -
Ravi -
Simonson, Lucanus J -
Steven Watanabe -
vicente.botet