[geos-devel] Performance of GEOS compared to JTS

[Paul Ramsey]

Here are the results from Linux. Processor is AMD Athlon 1900+ (1666.785Mz)

# overlapping MCs: 36
# segment intersection tests: 39
n Pts: 10   Executed in 0
# overlapping MCs: 40
# segment intersection tests: 26
n Pts: 100   Executed in 0
# overlapping MCs: 44
# segment intersection tests: 7
n Pts: 1000   Executed in 1000
# overlapping MCs: 44
# segment intersection tests: 4
n Pts: 2000   Executed in 3000
# 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 17000
# overlapping MCs: 44
# segment intersection tests: 5
n Pts: 5000   Executed in 82000
# overlapping MCs: 44
# segment intersection tests: 7
n Pts: 6000   Executed in 127000
# overlapping MCs: 44
# segment intersection tests: 6
n Pts: 7000   Executed in 174000


Martin Davis wrote:
 > 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
 >>>
 >>>

-- 
       __
      /
      | Paul Ramsey
      | Refractions Research
      | Email: pramsey at refractions.net
      | Phone: (250) 885-0632
      \_