[geos-devel] JTS/GEOS performance

[strk at refractions.net]

On Wed, Feb 02, 2005 at 09:17:35AM -0800, Martin Davis wrote:
> > My proposal is to make GEOS interfaces closer to JTS in using 
> > vectors of Coordinates wherever JTS uses Coordinate[]. 
> 
> In actual fact, the use of CoordinateSequence in GEOS was completely
> deliberate, and I intend to migrate JTS to use that pattern as well.
> The reason was to encapsulate the representation of coordinate values,
> to easily allow using alternative coordinates and coordinate list
> implementations with JTS/GEOS.

Yes, I recognize my own acts there.

> 
> There may be a performance penalty to be paid for this flexibility, but
> I (and others) think that the increased versatility and cleaner
> architecture.  In fact, I would expect that with C++'s much better
> optimization and richer language model the penalty (if any) should be
> much less than in Java.  
> 
> Since CoordinateSequence::getAt() returns a reference, I don't see why
> that would be much slower than simply dereferencing an array.

That's a virtual call, so cannot be statically bound.
A simple coordlist[4] on the other hand is usually inlined.
(C++ gurus correct me if I'm wrong)

> 
> > I'd consider using vector<Coordinate>, which can returned 
> > with no copy involved by the DefaultCoordinateSequence using 
> > the toVector() method.
> 
> Could this be the source of the problem?  JTS uses getCoordinates all
> over the place.  This is NOT going to be efficient under the new
> CoordinateSequence pattern, since it requires converting a
> CoordinateSequence into a Coordinate[].  Instead, the JTS code will have
> to be rewritten to use a getCoordinate(int, Coordinate) method, which
> will extract the coordinate value into a provided Coordinate object.

I'm doing tests with the latest JTS code handy.
Geometry#getCoordinates() returns Coordinate[], not CoordinateSequence.
Note that for DefaultCoordinateSequence, the #toVector() method
doesn't involve any copy. Any different implementation will probably
require a copy but the assumption of a "fast" implementation has
always been in JTS, see the toInternalCoordinate() method.

> This lets the caller manage the memory (and in most cases, very few
> actual Coordinate objects have to be allocated).  I suspect that GEOS,
> although partially implemented using the CoordinateSequence pattern, was
> not fully converted to this pattern (fair enough, since this is a major
> change to the code and a major departure from alignment with JTS).
> Strk, can you confirm this assumption?

Nope. GEOS actually dropped CoordinateArrays and CoordinateList classes
merging all into CoordinateSequence. In no case direct vector<Coordinate>
is used.

--strk;

> So there's 2 choices - alter GEOS now, or wait until JTS moves and then
> mirror it.  
> 
> 
> Martin Davis, Senior Technical Architect
> Vivid Solutions Inc.      www.vividsolutions.com
> Suite #1A-2328 Government Street Victoria, B.C. V8T 5G5
> Phone: (250) 385 6040 - Local 308 Fax: (250) 385 6046
> 
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net
> http://geos.refractions.net/mailman/listinfo/geos-devel