[geos-devel] Performance of GEOS compared to JTS (Report, Nov. 8)

[Norman Vine]

Martin Davis writes:

> For comparison purposes, here's the timings for JTS on the same numbers.  JTS now looks linear, just like GEOS. (I think we just
didn't go quite large enough last time).  It's still (a bit) faster than GEOS, though - and I'm running on a 1.1 GHz machine, not a
1.9 GHz box.  Maybe Java's just bettah...  8^)
>
> n Pts: 1000   Executed in 3014 ms
> n Pts: 2000   Executed in 91 ms
> n Pts: 4000   Executed in 50 ms
> n Pts: 8000   Executed in 110 ms
> n Pts: 16000   Executed in 210 ms
> n Pts: 32000   Executed in 411 ms
> n Pts: 64000   Executed in 801 ms
> n Pts: 128000   Executed in 2032 ms
> n Pts: 256000   Executed in 3545 ms

I did some major hacking on the code
machine: PIII 733 Cygwin gcc 3.2 -O3

n Pts: 1000  Executed in     10 ms.
n Pts: 2000  Executed in     30 ms.
n Pts: 4000  Executed in     60 ms.
n Pts: 8000  Executed in    140 ms.
n Pts: 16000  Executed in    330 ms.
n Pts: 32000  Executed in    680 ms.
n Pts: 64000  Executed in   1321 ms.
n Pts: 128000  Executed in   2834 ms.
n Pts: 256000  Executed in   5639 ms.


And here is the profiling result

Notice that the signOfDet2x2() is dominating like we would expect  :-)

I'll clean up what I did 'a little' and post a tarball somewhere tomorrow
so others can play.

Norman


Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 79.17      0.95     0.95  4543842     0.00     0.00  RobustDeterminant::signOfDet2x2(double, double, double, double)
  5.83      1.02     0.07        2     0.04     0.04  Geometry::hasNullElements(CoordinateList)
  5.00      1.08     0.06        2     0.03     0.03  LineString::computeEnvelopeInternal()
  4.17      1.13     0.05  1327961     0.00     0.00  SegmentIntersector::addIntersections(Edge*, int, Edge*, int)
  3.33      1.17     0.04   511968     0.00     0.00  SegmentIntersector::isTrivialIntersection(Edge*, int, Edge*, int)
  2.50      1.20     0.03        1     0.03     0.03  GeometryTestFactory::createSineStar(double, double, double, double, int, int)
  0.00      1.20     0.00  1327965     0.00     0.00  LineIntersector::hasIntersection()
  0.00      1.20     0.00  1071957     0.00     0.00  LineIntersector::computeIntersection(CoordinateList*, int, CoordinateList*,
int)
  0.00      1.20     0.00  1071957     0.00     0.00  RobustLineIntersector::computeIntersect(Coordinate, Coordinate, Coordinate,
Coordinate)
  0.00      1.20     0.00   511981     0.00     0.00  LineIntersector::getIntersectionNum()
  0.00      1.20     0.00   256100     0.00     0.00  Quadrant::quadrant(double, double)
  0.00      1.20     0.00   256088     0.00     0.00  Quadrant::quadrant(Coordinate, Coordinate)
  0.00      1.20     0.00   256006     0.00     0.00  Coordinate::getNull()
  0.00      1.20     0.00   256000     0.00     0.00  RobustLineIntersector::computeIntersection(Coordinate, Coordinate, Coordinate)
  0.00      1.20     0.00     1242     0.00     0.00  sleLessThan(SweepLineEvent*, SweepLineEvent*)
  0.00      1.20     0.00     1242     0.00     0.00  SweepLineEvent::compareTo(SweepLineEvent*)