[geos-devel] Performance of GEOS compared to JTS

[Martin Davis]

JTS actually exhibits *sub-linear* performance for this test.  (See test output below).  The reason for this is is that the indexing used in intersection detection drastically reduces the number of attempts to only check for intersections close to where the geometrys actually interact.  So, while the number of segments in one of the geometrys increases, the number of actual intersections is relatively constant.  

Not sure why the GEOS code doesn't do the same thing, though.  The metrics for the segment intersection test counts look ok - they hardly change, which is what you'd expect, since the number of locations where the geometries intersect doesn't change.  My suspicion is that the poor performance is due to memory allocation - there are quite a few places where small objects are allocated, in proportion to the total number of segments.  I think there's two ways of improving this: (a) use value objects instead of allocating memory in some cases (e.g. in the sweep line index) and (b) allocate memory in larger chunks and use sub-allocation.

One thing that might prove whether memory allocation is causing this symptom is to run the code on Linux and see whether the performance is different (since Linux may have a better - or worse! - memory allocator).

Metrics from JTS test:

# overlapping MCs: 34
# segment intersection tests: 38
n Pts: 10   Executed in 20 ms

# overlapping MCs: 40
# segment intersection tests: 26
n Pts: 100   Executed in 20 ms

# overlapping MCs: 44
# segment intersection tests: 7
n Pts: 1000   Executed in 80 ms

# overlapping MCs: 44
# segment intersection tests: 5
n Pts: 10000   Executed in 180 ms


Martin Davis, Senior Technical Specialist
Vivid Solutions Inc.
Suite #1A-2328 Government Street   Victoria, B.C.   V8T 5G5
Phone: (250) 385 6040    Fax: (250) 385 6046
EMail: mbdavis at vividsolutions.com  Web: www.vividsolutions.com


> -----Original Message-----
> From: Paul Ramsey [mailto:pramsey at refractions.net]
> Sent: Wednesday, November 06, 2002 9:25 AM
> To: geos-devel at geos.refractions.net
> Subject: Re: [geos-devel] Performance of GEOS
> 
> 
> I dunno, a factor of two in the worst case isn't *so* bad. Martin, 
> should the times be increasing exponentially as the vertices increase 
> linearly (is that what JTS does too)?
> 
> Norman Vine wrote:
> > Martin Davis writes:
> > 
> > 
> >>Ok, let us know what you find out.
> > 
> > 
> > A little better - but not what I was hoping for
> > 
> > This is on a 733mhz PIII
> > Cygwin gcc 3.2
> > 
> > Norman
> > 
> > Code as in CVS
> > 
> > n Pts: 1000   Executed in 1000
> > # overlapping MCs: 44
> > # segment intersection tests: 4
> > n Pts: 2000   Executed in 4000
> > # overlapping MCs: 44
> > # segment intersection tests: 7
> > n Pts: 3000   Executed in 10000
> > # overlapping MCs: 44
> > # segment intersection tests: 4
> > n Pts: 4000   Executed in 22000
> > # overlapping MCs: 44
> > # segment intersection tests: 5
> > n Pts: 5000   Executed in 92000
> > # overlapping MCs: 44
> > # segment intersection tests: 7
> > n Pts: 6000   Executed in 156000
> > # overlapping MCs: 44
> > # segment intersection tests: 6
> > n Pts: 7000   Executed in 224000
> > # overlapping MCs: 44
> > # segment intersection tests: 4
> > n Pts: 8000   Executed in 315000
> > 
> > < manually stopped test before completion >
> > 
> > 
> > My test  code with no pure virtuals and inlined code
> > 
> > n Pts: 1000   Executed in 0
> > # overlapping MCs: 44
> > # segment intersection tests: 4
> > n Pts: 2000   Executed in 2000
> > # overlapping MCs: 44
> > # segment intersection tests: 7
> > n Pts: 3000   Executed in 4000
> > # overlapping MCs: 44
> > # segment intersection tests: 4
> > n Pts: 4000   Executed in 8000
> > # overlapping MCs: 44
> > # segment intersection tests: 5
> > n Pts: 5000   Executed in 16000
> > # overlapping MCs: 44
> > # segment intersection tests: 7
> > n Pts: 6000   Executed in 64000
> > # overlapping MCs: 44
> > # segment intersection tests: 6
> > n Pts: 7000   Executed in 110000
> > # overlapping MCs: 44
> > # segment intersection tests: 4
> > n Pts: 8000   Executed in 148000
> > # overlapping MCs: 44
> > # segment intersection tests: 5
> > n Pts: 9000   Executed in 194000
> > # overlapping MCs: 44
> > # segment intersection tests: 5
> > n Pts: 10000   Executed in 255000
> > 
> > 
> > 
> > _______________________________________________
> > geos-devel mailing list
> > geos-devel at geos.refractions.net
> > http://geos.refractions.net/mailman/listinfo/geos-devel
> > 
> 
> 
> -- 
>        __
>       /
>       | Paul Ramsey
>       | Refractions Research
>       | Email: pramsey at refractions.net
>       | Phone: (250) 885-0632
>       \_
> 
> 
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net
> http://geos.refractions.net/mailman/listinfo/geos-devel
>