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

[Martin Davis]

One thing to make clear - GEOS does not alway require allocations to be 
done pointwise.  The CoordinateSequence interface and various subclasses 
provide the option of allocating all storage for a list of points in a 
single allocation.

I would certainly be curious to see how the algorithmic component of 
GEOS compares to GGL (or any other library).  The JTS/GEOS predicate and 
overlay algorithms were developed with the primary goal being first 
generality and then performance.  So no doubt there's better ways of 
doing things. 

In the GEOS algorithms at least I don't see any way of avoiding dynamic 
allocation, since there's no way to predict a priori how many line 
segment intersections will be found, or how what the structure of the 
output geometry is.  Does GGL avoid this problem in some way?

Barend Gehrels wrote:
>
>
> 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
>
>
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/geos-devel
>

-- 
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022