[geos-devel] Current project status

[Yury A. Bychkov]

1. RobustLineIntersector has been updated.
2. MonotoneChainIndexer::getChainStartIndices was a biggest single contributor
to Coordinate() calls (~20% of total calls). I've replaced instances
CoordinateList with references to gauge performance increase (See results
below).
3. Currently I am redoing the CoordinateList (and calls to its methods) with
respect to the suggestions on the list.

Here are the performance results (P4-2.53):
No modifications:
 # overlapping MCs: 406
 # segment intersection tests: 226
 n Pts: 1000  Executed in     30 ms.
 # overlapping MCs: 406
 # segment intersection tests: 278
 n Pts: 2000  Executed in     50 ms.
 # overlapping MCs: 406
 # segment intersection tests: 248
 n Pts: 4000  Executed in    100 ms.
 # overlapping MCs: 406
 # segment intersection tests: 250
 n Pts: 8000  Executed in    150 ms.
 # overlapping MCs: 406
 # segment intersection tests: 272
 n Pts: 16000  Executed in    391 ms.
 # overlapping MCs: 406
 # segment intersection tests: 264
 n Pts: 32000  Executed in    751 ms.
 # overlapping MCs: 406
 # segment intersection tests: 236
 n Pts: 64000  Executed in   1513 ms.
 # overlapping MCs: 406
 # segment intersection tests: 264
 n Pts: 128000  Executed in   3395 ms.
 # overlapping MCs: 406
 # segment intersection tests: 238
 n Pts: 256000  Executed in   7120 ms.
 # overlapping MCs: 406
 # segment intersection tests: 232
 n Pts: 512000  Executed in  12788 ms.
 # overlapping MCs: 406
 # segment intersection tests: 232
 n Pts: 1024000  Executed in  25296 ms.

New RobustLineIntersector:
 # overlapping MCs: 406
 # segment intersection tests: 226
 n Pts: 1000  Executed in     20 ms.
 # overlapping MCs: 406
 # segment intersection tests: 278
 n Pts: 2000  Executed in     40 ms.
 # overlapping MCs: 406
 # segment intersection tests: 248
 n Pts: 4000  Executed in     90 ms.
 # overlapping MCs: 406
 # segment intersection tests: 250
 n Pts: 8000  Executed in    130 ms.
 # overlapping MCs: 406
 # segment intersection tests: 272
 n Pts: 16000  Executed in    311 ms.
 # overlapping MCs: 406
 # segment intersection tests: 264
 n Pts: 32000  Executed in    621 ms.
 # overlapping MCs: 406
 # segment intersection tests: 236
 n Pts: 64000  Executed in   1252 ms.
 # overlapping MCs: 406
 # segment intersection tests: 264
 n Pts: 128000  Executed in   2754 ms.
 # overlapping MCs: 406
 # segment intersection tests: 238
 n Pts: 256000  Executed in   5688 ms.
 # overlapping MCs: 406
 # segment intersection tests: 232
 n Pts: 512000  Executed in  10895 ms.
 # overlapping MCs: 406
 # segment intersection tests: 232
 n Pts: 1024000  Executed in  22042 ms.

CoordinateList instances replaced with references in MonotoneChainIndexer; some
tweaking of CoordinateList:
 # overlapping MCs: 406
 # segment intersection tests: 226
 n Pts: 1000  Executed in     20 ms.
 # overlapping MCs: 406
 # segment intersection tests: 278
 n Pts: 2000  Executed in     30 ms.
 # overlapping MCs: 406
 # segment intersection tests: 248
 n Pts: 4000  Executed in     70 ms.
 # overlapping MCs: 406
 # segment intersection tests: 250
 n Pts: 8000  Executed in    120 ms.
 # overlapping MCs: 406
 # segment intersection tests: 272
 n Pts: 16000  Executed in    270 ms.
 # overlapping MCs: 406
 # segment intersection tests: 264
 n Pts: 32000  Executed in    500 ms.
 # overlapping MCs: 406
 # segment intersection tests: 236
 n Pts: 64000  Executed in    991 ms.
 # overlapping MCs: 406
 # segment intersection tests: 264
 n Pts: 128000  Executed in   2023 ms.
 # overlapping MCs: 406
 # segment intersection tests: 238
 n Pts: 256000  Executed in   4276 ms.
 # overlapping MCs: 406
 # segment intersection tests: 232
 n Pts: 512000  Executed in   7861 ms.
 # overlapping MCs: 406
 # segment intersection tests: 232
 n Pts: 1024000  Executed in  15993 ms.


Yury