[geos-devel] Re: isOnLine optimizations + ABI compatibility

[strk at refractions.net]

On Fri, Jun 24, 2005 at 12:03:59PM -0700, Martin Davis wrote:
> > I've been profiling Union operations.
> > It seems the most time-spending function
> > is Envelope::intersects() called by 
> > LineIntersector::computeIntersection()
> > called by CGAlgorithms::isOnLine for every segment of a given 
> > CoordinateSequence.
> 
> Strk, I've come up with a fix for this problem which should avoid any
> isCovered tests at all, for cases where it's not required (e.g. for the
> union of polygons).
> 
> I've commited this to JTS.  (I assume you can determine the changes from
> via diff, right?)  Can you retry your performance tests and let me know
> if this makes a difference?

Yes, a BIG difference. New timings are comparable between buffer(0)
and incremental Union() implementations:

Envelope::intersects calls reduce from
430875985 to
 10010718

Now the problem is understand whether it is possible to use the
patch in geos-2.1 without breaking ABI. I'll research on this
and in postgis connector before going back to GEOS/JTS profiling.

Thanks! (timings follow)

Timings:
------------------------------------------------------------------------

        Classic geomunion (geos-2.1)
                real    2m25.230s
                user    2m20.337s
                sys     0m0.527s

        Classic geomunion, Martin JTS patches (geos-2.1)
                real    0m58.692s
                user    0m56.113s
                sys     0m0.392s

------------------------------------------------------------------------

        Classic geomunion (geos-head)
                real    1m40.458s
                user    1m36.724s
                sys     0m0.454s

        Classic geomunion, Martin JTS patches (geos-head)
                real    0m43.015s
                user    0m41.207s
                sys     0m0.352s

        Buffer(0) geomunion (geos-head)
                real    0m43.845s
                user    0m41.906s
                sys     0m0.358s

------------------------------------------------------------------------