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

[Mateusz Loskot]

Barend Gehrels wrote:
> 
>>> I just debugged the Geos area routine, what could then be the reason
>>> that it is relatively slow? It might be that it is accessed as a
>>> vector, indeed, but not as an iterator, so getting points using
>>> "return (*vect)[pos]" is not efficient as it could be using
>>> iterators. Besides that it is probably no problem to make the getAt
>>> function inline.
>>>     
>>
>> getAt is a virtual function, can't be inlined.
>>   
> Right, I debugged in CoordinateArraySequence, where it is not denoted
> virtual (the overloaded version is...), but I now saw that its parent
> indeed is virtual.
> 
> A (probably) working way to have less virtual calls (for area) then
> would be changing this:
>        double bx=ring->getAt(i).x;
>        double by=ring->getAt(i).y;
>        double cx=ring->getAt(i+1).x;
>        double cy=ring->getAt(i+1).y;

It would be not a bad idea to help compiler to optimise as much as
possible:

double const cx = ...

Most people think it's too trivial to influence generated code,
but it may really help.

> to this:
> Coordinate const& c = ring->getAt(i + 1 );
> double cx = c.x, cy = c.y;

Best option possible.

> and have a previous_coordinate (b) for the getAt(i). Would save 3
> virtual calls + 3 times non-iterator-based vector access... I didn't try
> it.

Anyway, all the small things that "seem" trivial, make a big difference
in fact.

>> Templates would make it a lot better, but far away from 1:1 mapping
>> with Java.
>>   
> Sure, though Java also have templates now
> 
>> Beside, how do you handle memory management in GGL ?
>>   
> 1) Using the std:: library. Where it is an optional template parameter,
> so you can have polygon<point> but also polygon<point, std::deque> for
> if you decide that you want a deque instead of a vector

Plus, you can use your own containers or you can use your own allocators
with standard containers. It's not uncommon situation when specialised
allocators are really a good idea.

> 2) Using concepts, actually a polygon or linestring can be anything as
> long as it fullfiles the concept. So having an iterator (for linestring
> that is enough), having traits te denote exterior/interior ring
> handling. In this way our library does not even now what is below the
> surface, it just uses it.

This is an important detail.

One of the major feature of GGL is that it's extensible and
applicable to user-defined types that conform to concepts and contracts
defined by GGL. It is realised with use of abstractions
like iterator, range, collection which are orthogonal to specific types.

This makes it possible to design set of geometry or geometry-like
types or managed with sophisticated allocators, memory pools, etc.
and use them with GGL.

For example, it would be possible to specialise ggl::polygon with
stxxl::vector [1] and apply GGL algorithms on such container capable to
store very large number of elements.

[1] http://stxxl.sourceforge.net/

There are much more powerful options available like use of
concept of views [2], iterator adaptors [3], etc.

[2] http://www.zib.de/weiser/vtl/
[3] http://www.boost.org/doc/libs/1_39_0/libs/iterator/doc/index.html

Imagine calculation of length or transformation of coordinate of N
linestrings, both of M points, in single-pass using zip_iterator :-)

Best regards,
-- 
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org