Re: Virtual classes and run-time performance
Rune Allnor wrote:
Hi all.
I have a large set of (x,y,z) point that I want to manipulate. Most of
the data (millions) are "regular" while exactly three points are
"special".
The points are well separated in the list of points, points 0,..,N-1
are "regular", any points at indexes >= N are "special".
If the points, both special and normal, are already in a list, doesn't
that mean
that they share a common base class? Or is this more of a notional
list?
...
So I have a couple of options when implementing this.
The naive way is to test, on every call of the function, whether
any points are "special", and if so, invoke the relevant functions.
The test is simple enough -- test index agains N -- but finding out
exactly which of the points are special, and respond to that, might
generate some more overhead. This would amount to some
overhead at every single call to the function.
The other strategy is to implement this as a class hierarchy
like this (very sketchy, no C++ docs available, general ideas
only are interesting, so please don't get hung up on syntax
details!):
One doesn't want to prematurely optimize, but at the same time one
doesn't want to prematurely pessimize. When dealing with a huge number
of (I assume) small objects, using virtual functions will add (in most
known compiler interpolations) a pointer to a virtual table for each
point. Furthermore, if the operation in the 'all normal' case is
simple, like a cross-ratio or something, using virtual functions might
incur a relatively large per-call overhead. It might also destroy any
opportunities for inlining.
Whether or not the per-call overhead will exist depends on how you call
f(). If p is a pointer or reference to a Point, then p->f() or p.f()
will invoke the virtual dispatch mechanism. On the other hand, if rp is
an instance of a RegularPoint, then the compiler should realize that
rp.f() can be called directly.
class Point{
virtual void f(point,point,point)=0;
};
class RegularPoint : public Point{
virtual void f(RegularPoint,RegularPoint,RegularPoint);
virtual void f(SpecialPoint,RegularPoint,RegularPoint);
:
virtual void f(SpecialPoint,SpecialPoint,SpecialPoint);
// All 8 variants of type matches here. Most will be
// inetrfaces to generic functions for one and two special
// points, respectively. Maybe some extra overhead,
// maybe the compiler optimizes it away. But it will
// not affect the majority of operations.
};
class SpecialPoint{
virtual f(point,point,point){};
// This function will only be called from RegularPoint objects.
// That's THE distinction between regular and special points.
};
First - I'm not sure that this will do exactly what you want - the f()
overloads in the
RegularPoint subclasses do not override the pure virtual
f(point,point,point) - they hide it
(see the FAQ:
http://www.parashift.com/c++-faq-lite/strange-inheritance.html#faq-23.9)
Second, given the memory and possible runtime overheads, I don't see
any advantage to this over just defining a set of overloaded f()s:
void f(RegularPoint&, RegularPoint,RegularPoint,RegularPoint);
void f(RegularPoint&, SpecialPoint,RegularPoint,RegularPoint);
....
template <class P1,class P2, class P3>
void f(SpecialPoint&, P1, P2, P3);
(assuming RegularPoint and SpecialPoint have the required interface for
this function)
(I'm assuming that the first point is affected by f(), and must be a
non-const reference)
This would still only require 9 overloads, same as your inheritance
based method, but will avoid any time/space overhead as the compiler
will do all the work for you. This, of course, relies on the fact that
the callers of f() specify the concrete types, but from the way you
posed the question, I'm assuming they do (correct me if I am wrong!)
-matt
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]