[Fwd: [Boost-users] [boost] Formal Review: Boost.Polygon
starts today August 24, 2009]
Barend.Gehrels at geodan.nl
Tue Sep 1 19:31:57 EDT 2009
Martin Davis wrote:
> Ok, I can see that. So in other words, GEOS uses a dynamic coordinate
> access paradigm, which gives flexibility to access different data
> structures, but can't be optimized by the compiler?
It is not only the compiler. Dynamic memory allocations are relatively
slow. Allocating 1000 times a point is slower than allocating once 1000
> Is this the reason for the performance difference for *all* the other
> libraries which beat it in peformance? Or maybe some of them *don't*
> provide the dynamic data structure wrapper, and hence also can be
> optimized by the compiler (but thus they are less adaptable for use
> with external data structures).
I don't know this for sure but I think most allocate for the whole
polygon or linestring at once. GPC is e.g. C, not C++.
> I presume it would be a big job to convert GEOS to a template-based
Probably. What would be possible and feasable is adapting GEOS's
datastructures (polygon) to GGL's concepts and then call e.g. GGL's
intersection. It would at least be a nice experiment. You still have the
dynamic memory then, but you can see which part is the algorithm and
which part is the memory access
> It's somewhat annoying that the problem of efficient memory access and
> compiler optimization is quite orthogonal to the actual geometric
> algorithms, and yet it seems difficult to express the algorithms in a
> sufficiently abstract way to allow optimizations to take place.
I don't see this. Using the std-library, both access to a vector and
(temporary) storage using a vector or deque are usually quite fast.
More information about the geos-devel