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".

The manipulations deal with quadruples of points. If all points
are "regular", then one set of operations take place. If any of
the points are "special", then another set of operations are
invoked. There could be 1, 2, or 3 "special" points involved in
each manipulation, but always at least one "regular" point.
The points are passed to the relevant functions in arbitrary
order, one does never know in advance if any points are
special, and if so, how many or where they appear in the
list of points that are involved in the manipulation.

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!):

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.
};

This way, the test about what method to call is done by
run-time type matching. Of course, this will be optimized
in the end, so one might be optimistic about performance.

Is there reason to expect the latter implementation to
perform particularly worse than the first approach, what
run-time is concerned? Have anybody tested the relative
run-time performance of these sorts of things?

I have used this trick in the past in applications where
run-time was not a concern. It surely makes the source
code a lot easier to maintain... 

Rune


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

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! ]

Rune Allnor <allnor@tele.ntnu.no> 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".
> 
> The manipulations deal with quadruples of points. If all points
> are "regular", then one set of operations take place. If any of
> the points are "special", then another set of operations are
> invoked. There could be 1, 2, or 3 "special" points involved in
> each manipulation, but always at least one "regular" point.
> The points are passed to the relevant functions in arbitrary
> order, one does never know in advance if any points are
> special, and if so, how many or where they appear in the
> list of points that are involved in the manipulation.
> 
  Depends on what the properties are of Special and Regular and is there
any symmetry between arguments,  Perhaps this is a 'multimethod' a
pseudo virtual function dispatched on 4 arguments instead of one.

15 overloads is a possiblity if this is the way the only thing virtual
provides is storing the points in a wrapper in a container.

Determine what f needs to know about a point type and these are the
functions to make virtual in Point.  4 virt.functions takes less space
than 15. :)   If this is done one free function f(Point &,Point &,Point
&,Point &) is needed, provided the properties are obtained by virtual
calls.

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

allnor@tele.ntnu.no (Rune Allnor) wrote (abridged):
> This way, the test about what method to call is done by
> run-time type matching. Of course, this will be optimized
> in the end, so one might be optimistic about performance.
> 
> Is there reason to expect the latter implementation to
> perform particularly worse than the first approach, what
> run-time is concerned? Have anybody tested the relative
> run-time performance of these sorts of things?

Although you don't show it, I think you must be talking about a quadruple 
dispatch. You'd call a virtual function on each of the 4 points, which 
would effectively determine the type of that point, and you'd chain them 
together so that the final function implementation knew the types of all 4 
of them. It's quite a lot of infrastructure. (If you have a lot of 
different functions, it would be worth considering a Visitor instead of 
multiple dispatch - it would simplify the implementation at the cost of 
another virtual call.)

In addition you'd effectively add the overhead of a vtable pointer to each 
point, although you might be able to avoid that by using the Flyweight 
Pattern.

In general I'd expect a virtual function call to be slower than a normal 
function call, but faster than a normal call plus a (large) switch 
statement. In this case we don't need a switch; there are only two classes 
of point so a simple if statement will do. I think you would need to 
measure this on your target machine.

My intuition says that the if-statement would win. It sounds like you have 
something like:

    inline bool is_special( int index ) { return index > N; }
    
    inline bool any_are_special( int i0, int i1, int i2, int i3 ) {
        return is_special( i0 ) || is_special( i1 ) ||
                is_special( i2 ) || is_special( i3 );
    }
    
    void f( Point points[], int i0, int i1, int i2, int i3 ) {
        if (any_are_special( i0, i1, i2, i3 ))
            slow_f( points, i0, i1, i2, i3 );
        else
            fast_f( points, i0, i1, i2, i3 );
    }

I would expect this to be faster than anything based on virtual functions, 
because if statements are fast, we have no vtable indirection (which can 
be slow because it brings in more memory, and can be hard for the CPU to 
branch-predict), and we avoid some function calls.

It doesn't strike me as hard to maintain, either. If you have lots of 
functions, I'd consider encapsulating it and using a visitor or callback. 
Here's another version:

    void dispatch( Func *f, Point points[],
            int i0, int i1, int i2, int i3 ) {
        if (is_special(i0))
            if (is_special(i1))
                if (is_special(i2)
                    if (is_special(i3))
                         f->do_ssss( points, i0, i1, i2, i3 );
                    else
                         f->do_sssn( points, i0, i1, i2, i3 );
                 else
                    if (is_special(i3))
                         f->do_ssns( points, i0, i1, i2, i3 );
                    else
                         f->do_ssnn( points, i0, i1, i2, i3 );
         // ... etc...
    }

where Func is a class with 16 virtual functions. With or without Func we 
can encapsulate the dispatching into a single function, separate to the 
functions that do the work.

It doesn't seem like it would be hard to write several versions and time 
them to see which is quicker.

-- Dave Harris, Nottingham, UK.

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]