Re: [boost] new library (space partitioning)

Subject: Re: [boost] new library (space partitioning)
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-07-30 18:57:29

Adam Wulkiewicz wrote:
> But the most important thing is that if you want to make building of
> arbitrary kd-tree possible boost::geometry::point should provide a
> method returning given coordinate not in compile-time.

This did come up in design discussions and I recall someone stating the need citing specifically nD spatial query as a place where they need it.  The desire to make the interface minimal means that as a practical matter the designer of the interface needs to choose either runtime or compile time.  Boost.Geometry chose compile time, I chose run time.  The argument against runtime is that it may cause access to be slow due to unfortunate things like:

struct pt { double x, y, z; };

double get_coord(const pt& p, unsigned int axis) {
        if(axis == 0)
                return p.x;
        if(axis == 1)
                return p.y;
        return p.z;
}

double coord = get_coord(pt, 0); //does the if statement compile away?

I argue that the accessor should inline and constant propigation will cause the if statement to dissolve away resulting in zero runtime overhead.

Sadly, this if tree type thing is what you have to write to use the compile time accessor with a runtime parameter, which the compiler can't compile away, in general if the runtime parameter is not a constant.  

double get_coord(const pt& p, unsigned int axis) {
        if(axis == 0)
                return get<0>(p);
        if(axis == 1)
                return get<1>(p);
        return get<2>(p);
}

Even though point may be defined as:

typedef boost_array<double, 3> pt;

and provide an operator[] you end up paying for branch or jump table access to its coordinates in addition to the array lookup for no good reason.  Thinking through what the compiler would have to do to optimize away the logic tree or switch statement I find it pretty unlikely.

I don't think it is too late for Boost.Geometry to change their interface, but I do recognize that it entails a lot of work.  I encapsulate the use of the adaptor in a free function so that I can change the interface and don't need to change every place where I use it, but I don't know if Boost.Geometry uses the adaptor directly everywhere or not.

Regards,
Luke