[geos-devel] [Fwd: [Boost-users] [boost] Formal Review: Boost.Polygon starts today August 24, 2009]

[Barend Gehrels]

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 
points.
>
> 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 
> paradigm?  
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.

Regards, Barend