[geos-devel] Performance of GEOS compared to JTS
Martin Davis
mbdavis at VividSolutions.com
Wed Nov 6 17:25:03 EST 2002
hmm, not looking too good. It's showing super-linear performance also.
I guess we're going to have to wait for Yury to report back on what he finds once he's had an in-depth look at what's going on.
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 2:22 PM
> To: geos-devel at geos.refractions.net
> Subject: Re: [geos-devel] Performance of GEOS compared to JTS
>
>
> 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
> \_
>
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net
> http://geos.refractions.net/mailman/listinfo/geos-devel
>
More information about the geos-devel
mailing list