[geos-devel] JTS/GEOS performance

[Chapman, Martin]

I studied the GEOS code and here is my opinion:

1.  GEOS makes multiple copies of the coordinates during many operations
rather than storing the points once and then passing pointers. 

2.  GEOS has a complicated object model that makes objects for
everything.  To calculate most spatial operations and relationships
requires the construction and destruction of many many objects.

3.  The DE9IM implementation makes mistakes like intersects = !disjoint.
That requires a full scan of all points in a poly, whereas a straight
intersect algorithm will return faster most of the time because it can
exit after it finds the first intersecting point.  In general, I think
there should be optimized algorithms for each spatial
operation/relationship rather than trying to calculate the full de9-im
matrix.  You can keep the matrix, just change the way it gets populated
behind the scenes.

4.  When doing operations on point arrays, make functions that takes
pointers to arrays and just pass the pointers in from the geometry
classes.  Currently, when you call a function like intersects GEOS makes
copies of points and a slew of objects for each geometry operation.  

For a comparison, we tried to use geos with postgresql and used the
POSTGIS intersect method.  We found it very slow so we wrote our own
user-defined intersect function.  Ours is 109 times faster on a million
plus geometries.  That means a one second query for us takes GEOS 109
seconds.

Martin



-----Original Message-----
From: Martin Davis [mailto:mbdavis at VividSolutions.com] 
Sent: Friday, January 28, 2005 10:12 AM
To: GEOS Development List
Subject: RE: [geos-devel] JTS/GEOS performance


Poor alloc performance would be my first guess for the performance
difference.  I would think Java is pretty optimized for memory
allocation, since it relies on it so heavily.  

I think one standard approach to handling slow malloc is to build a
sub-allocation layer.  This would be made a bit easier in GEOS, since
almost the allocation done inside geometry methods is released at the
end of the method.  You could probably even dispense with the free calls
as long as you were operating in the memory pool.  (One messiness that
would need to be thought out is how to support exposing the various
components such as tree indexes and noding while still allowing a custom
allocator to be supplied.  Or you could just forget about this and just
support access through geometry methods.  This is getting pretty far
from the philosophy of JTS though...).

I'm not enough of a C expert to know if this is the best route to pursue
- anyone have any other ideas?

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


> -----Original Message-----
> From: strk at refractions.net [mailto:strk at refractions.net]
> Sent: January 28, 2005 4:20 AM
> To: geos-devel at geos.refractions.net
> Subject: [geos-devel] JTS/GEOS performance
> 
> 
> Some time ago I've been researching about GEOS performance
> problems as related to JTS. Attached is a shapefile and an 
> .xml test you can use to compare the two.
> 
> JTS does not support buffers tests, so you'll need to use
> another method for that. I used JUMP, which reports computation time.
> 
> Well. The operation is a buffer(polygon, 2000).
> 
>  JTS:  18 seconds
> GEOS: 574 seconds (9 minutes, 34 secs)
> 
> GEOS computation keeps the CPU pretty busy (98.2-99.8%)
> and takes up to about 170 MB of ram
> 
> JTS seems to use 3 threads, the bigger using at most 80%
> of CPU, but most of the time far below that point.
> JUMP reports 104MB committed, but I'm not sure about the meaning.
> 
> For GEOS, valgrind reports (with buffer 500):
>  malloc/free: 2982697 allocs, 2982697 frees, 924407212 bytes
> allocated.
> 
> How much do you think this wild allocation negatively
> influence the poor performance of GEOS ?
> 
> --strk;
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net
> http://geos.refractions.net/mailman/listinfo/geos-devel
> 
_______________________________________________
geos-devel mailing list
geos-devel at geos.refractions.net
http://geos.refractions.net/mailman/listinfo/geos-devel