 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Chris Theis
Guest
|
 Posted: Fri Jan 16, 2004 5:53 pm Post subject: Callbacks - Inheritance vs. templates |
 |
|
Hi all,
I've been thinking recently about some subtle optimization problem which is
quite common in scientific computing. Implementing for exampling integration
(or more complex problems) was formerly done using function pointers. A
common C++ way is to use inheritance for this:
class CIntegrator {
public
double Integrate(double a, double b, int NrOfPoints) {
...
for (int i=0; i < NrOfPoints; ++i)
m_Sum += Func(a + i*delta);
...
}
virtual double Func(double x) = 0;
};
class CMyIntegrator: public CIntegrator { .... }; // implement the
function that is to be integrated
Of course this introduces the overhead due to the use of virtual. Having
large & complex functions this overhead might be negligible but with simple
functions it is certainly not. Due to the use of virtual no direct function
calls can be created by the compiler. Although I'm not exactly sure, whether
this is really true. Generally virtual functions are not or cannot be
inlined, though in the light of things I've read recently (there was an
excellent CUJ article by Herb Sutter regarding inlining - even at runtime)
I'm not so sure anymore. IMHO performing points-to analysis or runtime
analysis inlining might be (theoretically) possible, although todays common
compilers won't perform this, or do they? If anybody can shed some more
light on this I'd be happy.
Another, possibility would be the use of templates:
double Func(double x) {
return sqrt(x);
}
template
double Integrate(double a, double b, int NrOfPoints)
{
...
for (int i=0; i < NrOfPoints; ++i)
Sum += TFunc(a + i*delta);
...
}
IMHO this is the way to go, as it should result in maximum the same amount
of CPU time required as the inheritance approach, if it is not even less due
to possible inlining. Any opinions of people more experienced in the details
of compiler technology are very welcome.
I'd really appreciate to hear other opinions which is the way to go.
Cheers
Chris
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Hyman Rosen
Guest
|
| Posted: Sat Jan 17, 2004 3:16 am Post subject: Re: Callbacks - Inheritance vs. templates |
|
|
Chris Theis wrote:
| Quote: | I'd really appreciate to hear other opinions which is the way to go.
|
You could even use a combination of the two techniques:
template <class Derived>
struct Integrator
{
double Integrate(double a, double b, int N)
{
... m_sum += static_cast<Derived *>(this)->Func(a + i*delta);
}
};
struct MyIntegrator : Integrator<MyIntegrator>
{
static double Func(double x) { return sqrt(x); }
};
Now your derived classes are free to make Func static, ordinary, or virtual
as they need, and the compiler should find it simple to inline the non-virtual
cases.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Ben Hutchings
Guest
|
| Posted: Sat Jan 17, 2004 10:55 am Post subject: Re: Callbacks - Inheritance vs. templates |
|
|
Chris Theis wrote:
| Quote: | I've been thinking recently about some subtle optimization problem which is
quite common in scientific computing. Implementing for exampling integration
(or more complex problems) was formerly done using function pointers. A
common C++ way is to use inheritance for this:
snip
Another, possibility would be the use of templates:
double Func(double x) {
return sqrt(x);
}
template<double TFunc(double)
double Integrate(double a, double b, int NrOfPoints)
{
...
for (int i=0; i < NrOfPoints; ++i)
Sum += TFunc(a + i*delta);
...
}
IMHO this is the way to go, as it should result in maximum the same amount
of CPU time required as the inheritance approach, if it is not even less due
to possible inlining. Any opinions of people more experienced in the details
of compiler technology are very welcome.
I'd really appreciate to hear other opinions which is the way to go.
|
Templates are definitely the way to go if you're concerned about speed.
You can also make them more generic:
struct Functor
{
double operator()(double x) const {
return sqrt(x);
}
};
template
double Integrate(TFunc f, double a, double b, int NrOfPoints)
{
...
for (int i=0; i < NrOfPoints; ++i)
Sum += f(a + i*delta);
...
}
This allows you to pass in some data along with the function.
Unfortunately it's slower if you use a function instead of a functor.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Ulrich Eckhardt
Guest
|
| Posted: Sat Jan 17, 2004 10:58 am Post subject: Re: Callbacks - Inheritance vs. templates |
|
|
Chris Theis wrote:
| Quote: | class CIntegrator {
public
double Integrate(double a, double b, int NrOfPoints) {
...
for (int i=0; i < NrOfPoints; ++i)
m_Sum += Func(a + i*delta);
...
}
virtual double Func(double x) = 0;
};
|
IMHO that is Javaish[1] ugly. The reason is that an algorithm is not so much
an object. So, make that rather:
// the function
struct function
{
float operator()(float x) const
{ do_compute_y(x); }
private:
virtual float do_compute_y(float x) const = 0;
};
// the algorithm
float integrate( float x1, float x2, unsigned n, function const& f)
{
for(...)
...
return sum;
}
| Quote: | double Func(double x) {
return sqrt(x);
}
template
double Integrate(double a, double b, int NrOfPoints)
{
...
for (int i=0; i < NrOfPoints; ++i)
Sum += TFunc(a + i*delta);
...
}
|
Hmm, here too above solution would be more in the spirit of C++, just
switching from runtime polymorphism to compile time polymorphism:
template
float integrate( float x1, float x2, unsigned n, FunctionType const& f)
{
for(...)
...
return sum;
}
The function type only needs to be callable like 'f(some_float)' to suit
this algorithm.
| Quote: | IMHO this is the way to go, as it should result in maximum the same amount
of CPU time required as the inheritance approach, if it is not even less
due to possible inlining. Any opinions of people more experienced in the
details of compiler technology are very welcome.
|
Let's look at three cases:
1. When calling integrate( 0.0f, 3.14f, 0.01f, sin), the compiler can see
all the way down to the call of sin(), possibly inlining everything in
between.
2. When calling integrate() with a struct implementing operator() in a
simple way, it still can easily see all calls, possibly inlining them. This
also applies if you call 'integrate( ...., derived_from_function());'.
Reason is, that when it knows that the static type is the dynamic type, it
can inline virtual calls.
3. All you have is a 'struct function* fn', not knowing what particular
function it points to. Now, when you call 'integrate(...., *fn)', all the
compiler will be able to do is call the generic version
'integrate<function>()' and dispatch all calls dynamically. Yes,
perfomance-wise this is the worst case, but being able to switch the
function to integrate at runtime might have other advantages.
Summary: when using a templatized algorithm that gets something that can be
called, the compiler has the widest range of freedom for
optimization/inlining but it still compiles from the same code even when it
has to use dynamic dispatch.
Uli
[1]: as far as I know, Java has no free functions and thus enforces a
certain style (in the name of OO) even when it is against the nature of the
problem at hand.
Somebody please correct me if that is not the case.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Jonathan Turkanis
Guest
|
| Posted: Sat Jan 17, 2004 10:58 am Post subject: Re: Callbacks - Inheritance vs. templates |
|
|
"Chris Theis" <Christian.Theis (AT) nospam (DOT) cern.ch> wrote
| Quote: | Hi all,
I've been thinking recently about some subtle optimization problem
which is
quite common in scientific computing. Implementing for exampling
integration
(or more complex problems) was formerly done using function
pointers. A
common C++ way is to use inheritance for this:
class CIntegrator {
public
double Integrate(double a, double b, int NrOfPoints) {
...
for (int i=0; i < NrOfPoints; ++i)
m_Sum += Func(a + i*delta);
...
}
virtual double Func(double x) = 0;
};
class CMyIntegrator: public CIntegrator { .... }; // implement
the
function that is to be integrated
|
Why not:
template
class CIntegrator {
public:
double Integrate(double a, double b, int NrOfPoints) {
...
for (int i=0; i < NrOfPoints; ++i)
m_Sum += fn(a + i*delta);
...
}
/* ... */
Fn fn;
};
?
typedef CIntegrator
You could also change Intergrate' to 'operator()' (and get rid of the
C's  )
Jonathan
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Allan Odgaard
Guest
|
| Posted: Sat Jan 17, 2004 11:06 am Post subject: Re: Callbacks - Inheritance vs. templates |
|
|
"Chris Theis" <Christian.Theis (AT) nospam (DOT) cern.ch> wrote
| Quote: | [...] IMHO performing points-to analysis or runtime analysis
inlining might be (theoretically) possible, although todays common
compilers won't perform this, or do they?
|
Logic dictates that inlining virtual functions are possible only when
the compiler knows the actual type of the object.
So when does it know the type?
if we write:
void work_on (foo* obj)
{
obj->action();
}
Assuming that this function is not in an anonymous namespace, there is
no way that the compiler can know that 'obj' is actually an instance
of foo, because when translating the function, it does not know of all
the possible contexts from which it will be called, nor which classes
will have foo as baseclass at run-time.
So this analysis can only be done when linking -- and I am not aware
of any linkers which does this sort of analysis.
The alternative is when the instantiation of the object is visible,
e.g.:
foo* obj = new foo;
...
obj->action();
If the compiler can prove that "..." will not assign to "obj" (which
may require alias analysis) then it could inline "action", but I
assume that this situation is rare, so no-one would bother with this
optimization (since the user can get the same result either by not
making "action" virtual, or prefix the member function call with
"foo::" to explicitly get foo's implementation).
| Quote: | Another, possibility would be the use of templates: [...]
IMHO this is the way to go, as it should result in maximum the same amount
of CPU time required as the inheritance approach, if it is not even less due
to possible inlining. Any opinions of people more experienced in the details
of compiler technology are very welcome.
|
Yes, I think there is consensus on referring to templates as
compile-time polymorphism and virtual member functions as run-time
polymorphishm.
The first allow for more efficient code, but all types must be known
at compile time, and since the code is "unfolded" (to handle each type
seperately), the code most likely will be bigger.
You may want to read Eric Nieblers article at:
http://www.cuj.com/documents/s=8230/cuj0301niebler/
Basically he combines the two by using virtual member functions, but
let some of the "algorithms" be templated on the object type, so that
for a subset of the "algorithms", the compiler will be able to inline
the member function call.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Jeff Schwab
Guest
|
| Posted: Sat Jan 17, 2004 11:52 pm Post subject: Re: Callbacks - Inheritance vs. templates |
|
|
Ulrich Eckhardt wrote:
| Quote: | Chris Theis wrote:
class CIntegrator {
public
double Integrate(double a, double b, int NrOfPoints) {
...
for (int i=0; i < NrOfPoints; ++i)
m_Sum += Func(a + i*delta);
...
}
virtual double Func(double x) = 0;
};
IMHO that is Javaish[1] ugly. The reason is that an algorithm is not so much
an object.
|
.....
| Quote: | [1]: as far as I know, Java has no free functions and thus enforces a
certain style (in the name of OO) even when it is against the nature of the
problem at hand.
Somebody please correct me if that is not the case.
|
There aren't free-standing functions, but it's easy enough to create a
class representing something like a functor. There just needs to be a
generally agreed-upon method name, like "run". The C++ syntax certainly
is prettier, but the concept is available in Java. In particular,
implementation inheritance for a single method is not as common as you
might think, since multiple inheritance is not allowed.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Frank Birbacher
Guest
|
| Posted: Mon Jan 19, 2004 12:30 am Post subject: Re: Callbacks - Inheritance vs. templates |
|
|
Hi!
Jeff Schwab wrote:
| Quote: | There aren't free-standing functions, but it's easy enough to create a
class representing something like a functor. There just needs to be a
generally agreed-upon method name, like "run". The C++ syntax certainly
is prettier, but the concept is available in Java. In particular,
implementation inheritance for a single method is not as common as you
might think, since multiple inheritance is not allowed.
|
But you can make it an interface in Java. I figured whenever I would use
a function pointer in C++, I would need an interface in Java. (For
non-Java folks: an interface is basically a struct with pure virtual
methods only, any class can inherit from multiple interfaces)
Frank
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Chris Theis
Guest
|
| Posted: Mon Jan 19, 2004 12:32 am Post subject: Re: Callbacks - Inheritance vs. templates |
|
|
"Jonathan Turkanis" <technews (AT) kangaroologic (DOT) com> wrote
[SNIP]>
| Quote: | Why not:
template<typename Fn
class CIntegrator {
public:
double Integrate(double a, double b, int NrOfPoints) {
...
for (int i=0; i < NrOfPoints; ++i)
m_Sum += fn(a + i*delta);
...
}
/* ... */
Fn fn;
|
Shouldn't that come before the for loop?
This approach is perfectly fine although free-standing functions are not
possible anymore, which might be a requirement. However, this depends very
much on the actual design of the whole thing and this here is just a purely
academic example.
| Quote: |
typedef CIntegrator
You could also change Intergrate' to 'operator()' (and get rid of the
C's )
Jonathan
|
Well to C or not to C is a question of style (which very often is determined
by the company/project you're working for).
Cheers
Chris
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Jonathan Turkanis
Guest
|
| Posted: Mon Jan 19, 2004 7:35 am Post subject: Re: Callbacks - Inheritance vs. templates |
|
|
"Chris Theis" <Christian.Theis (AT) nospam (DOT) cern.ch> wrote
| Quote: | "Jonathan Turkanis" <technews (AT) kangaroologic (DOT) com> wrote in message
template
class CIntegrator {
public:
double Integrate(double a, double b, int NrOfPoints) {
...
for (int i=0; i < NrOfPoints; ++i)
m_Sum += fn(a + i*delta);
...
}
/* ... */
Fn fn;
Shouldn't that come before the for loop?
};
?
|
It doesn't make any difference with data members.
| Quote: |
This approach is perfectly fine although free-standing functions are
not
possible anymore, which might be a requirement. However, this
depends very
much on the actual design of the whole thing and this here is just a
purely
academic example.
|
I was trying to preserve your original design as much as possible,
while switching from virtual functions to functors. The free function
approach may be fine sometimes, too.
| Quote: |
You could also change Intergrate' to 'operator()' (and get rid of
the
C's )
Jonathan
Well to C or not to C is a question of style (which very often is
determined
by the company/project you're working for).
|
Naturally.
Jonathan
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Jeff Schwab
Guest
|
| Posted: Mon Jan 19, 2004 7:38 am Post subject: [OT] Re: Callbacks - Inheritance vs. templates |
|
|
Frank Birbacher wrote:
| Quote: | Hi!
Jeff Schwab wrote:
There aren't free-standing functions, but it's easy enough to create a
class representing something like a functor. There just needs to be a
generally agreed-upon method name, like "run". The C++ syntax certainly
is prettier, but the concept is available in Java. In particular,
implementation inheritance for a single method is not as common as you
might think, since multiple inheritance is not allowed.
But you can make it an interface in Java. I figured whenever I would use
a function pointer in C++, I would need an interface in Java. (For
non-Java folks: an interface is basically a struct with pure virtual
methods only, any class can inherit from multiple interfaces)
Frank
|
You can declare the method name(s) in an interface, but you don't have
to do do; JavaBeans, for example, rely on reflection instead. Upcoming
support for generic programming may provide another way, too.
If you meant that interfaces can be used as a direct replacement for
multiple implementation inheritance, I'm afraid it's not true.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Uwe Schnitker
Guest
|
| Posted: Mon Jan 19, 2004 5:26 pm Post subject: Re: Callbacks - Inheritance vs. templates |
|
|
Frank Birbacher <bloodymir.crap (AT) gmx (DOT) net> wrote
| Quote: | Hi!
Jeff Schwab wrote:
There aren't free-standing functions, but it's easy enough to create a
class representing something like a functor. There just needs to be a
generally agreed-upon method name, like "run". The C++ syntax certainly
is prettier, but the concept is available in Java. In particular,
implementation inheritance for a single method is not as common as you
might think, since multiple inheritance is not allowed.
But you can make it an interface in Java. I figured whenever I would use
a function pointer in C++, I would need an interface in Java. (For
non-Java folks: an interface is basically a struct with pure virtual
methods only, any class can inherit from multiple interfaces)
Frank
|
So here we have one of those cases where the general concept (it's even
a Design Pattern - "Functor") is common to several languages, but the
idiomatic expression is different. Function pointers in C, callback
interfaces in Java, functor classes - templates or abstract base classes -
in C++. BTW, this list could go on: There are delegates in C#, blocks in
Ruby, ... ...
Interestingly, in C++ you can use the C and the Java idioms as well as the
unique C++ ones. But doing may be a bad idea. In general, native C++ idioms
should be preferred, literally translating Java style can look very bad
in C++.
Quod licet bovi, non licet Jovi! (The juxtaposition is of course intentional.)
Have fun,
Uwe
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Chris Theis
Guest
|
| Posted: Mon Jan 19, 2004 5:29 pm Post subject: Re: Callbacks - Inheritance vs. templates |
|
|
"Jonathan Turkanis" <technews (AT) kangaroologic (DOT) com> wrote
| Quote: |
"Chris Theis" <Christian.Theis (AT) nospam (DOT) cern.ch> wrote in message
news:budrc4$iil$1 (AT) sunnews (DOT) cern.ch...
"Jonathan Turkanis" <technews (AT) kangaroologic (DOT) com> wrote in message
template
class CIntegrator {
public:
double Integrate(double a, double b, int NrOfPoints) {
...
for (int i=0; i < NrOfPoints; ++i)
m_Sum += fn(a + i*delta);
...
}
/* ... */
Fn fn;
Shouldn't that come before the for loop?
};
?
It doesn't make any difference with data members.
|
Sorry, I was too fast and overlooked the second closing curly bracket!
[SNIP]
Chris
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
kanze@gabi-soft.fr
Guest
|
| Posted: Mon Jan 19, 2004 6:02 pm Post subject: Re: Callbacks - Inheritance vs. templates |
|
|
"Chris Theis" <Christian.Theis (AT) nospam (DOT) cern.ch> wrote
| Quote: | I've been thinking recently about some subtle optimization problem
which is quite common in scientific computing. Implementing for
exampling integration (or more complex problems) was formerly done
using function pointers. A common C++ way is to use inheritance for
this:
class CIntegrator {
public
double Integrate(double a, double b, int NrOfPoints) {
...
for (int i=0; i < NrOfPoints; ++i)
m_Sum += Func(a + i*delta);
...
}
virtual double Func(double x) = 0;
};
class CMyIntegrator: public CIntegrator { .... }; // implement the
function that is to be integrated
|
IMHO, this is a typical misuse of the template pattern. For something
like Integrate, some form of a call-back object would be more
appropriate:
class Function
{
public:
virtual ~Function() {}
virtual double operator()( double op ) const = 0 ;
}
double
integrate( double a, double b, int nrOfPoints, Function const& f )
The client code only derives from Function.
| Quote: | Of course this introduces the overhead due to the use of
virtual. Having large & complex functions this overhead might be
negligible but with simple functions it is certainly not.
|
In a case like integration, it is like often to be an issue.
In theory, it is possible for a compiler to do intermodule flow
analysis and optimize the virtual function out. But this is very
definitly something at the leading edge of compiler technology, and not
very common.
| Quote: | Due to the use of virtual no direct function calls can be created by
the compiler. Although I'm not exactly sure, whether this is really
true. Generally virtual functions are not or cannot be inlined,
though in the light of things I've read recently (there was an
excellent CUJ article by Herb Sutter regarding inlining - even at
runtime) I'm not so sure anymore. IMHO performing points-to analysis
or runtime analysis inlining might be (theoretically) possible,
although todays common compilers won't perform this, or do they? If
anybody can shed some more light on this I'd be happy.
|
There is often a big difference between what compilers can theoretically
do, using all of the most advanced and recently developed technologies,
and what the compiler you are actually using will do. You should be
aware that such optimization technologies exist, since if you count on
the compiler not doing it today, you can be sure that tomorrow, they
will install one for you that does. On the other hand, if profiling
shows that the virtual function calls are eating up more time than you
have, the fact that it is theoretically possible for a compiler to
optimize them out isn't of much pratical value.
| Quote: | Another, possibility would be the use of templates:
double Func(double x) {
return sqrt(x);
}
template
double Integrate(double a, double b, int NrOfPoints)
{
...
for (int i=0; i < NrOfPoints; ++i)
Sum += TFunc(a + i*delta);
...
}
IMHO this is the way to go, as it should result in maximum the same
amount of CPU time required as the inheritance approach, if it is not
even less due to possible inlining. Any opinions of people more
experienced in the details of compiler technology are very welcome.
|
The problem with the template version is that the polymorphism must be
resolved at compile time. If this function is to be called by another
function, which also takes a pointer to a function, then that function
must also become a template. And so on up the line. Carried too far,
you could end up with the entire application a template. (Think of the
consequences if the iostream classes used a template on a streambuf
conformant class, rather than delegation through an abstract base.)
Intuitively, I wouldn't think that this would be a problem with
integrate, and I would go for the template solution. But it is
something that I would keep in mind.
Note that you can provide both the template solution and the virtual
function. Write the function as a template, and provide the Function
class above. When the user needs the performance, he provides his own
functional object. When he needs the flexibility, he derives from your
Functional object, and ensures that it is what is passed, and not his
derived class. (If his code passes the derived class, then it obviously
doesn't need the flexibility.) And when he needs both the performance
and the flexibility, he buys a more powerful machine.
--
James Kanze GABI Software mailto:kanze (AT) gabi-soft (DOT) fr
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Frank Birbacher
Guest
|
| Posted: Thu Jan 22, 2004 8:53 am Post subject: Re: [OT] Re: Callbacks - Inheritance vs. templates |
|
|
Hi!
Jeff Schwab wrote:
| Quote: | JavaBeans, for example, rely on reflection instead.
|
I considered reflection, but I figured it to be slow. I never looked
into JavaBeans, though.
| Quote: | If you meant that interfaces can be used as a direct replacement for
multiple implementation inheritance, I'm afraid it's not true.
|
No, I was just thinking about function pointers.
Frank
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
