[geos-devel] Performance of GEOS compared to JTS

[Norman Vine]

Martin Daviswrites:
>
> JTS actually exhibits *sub-linear* performance for this test.  

I expected linear time, this is even better !
The task now is to discover  what is different between the 'C' code
and the Jave version.
> 
>My suspicion is that the poor performance is due to memory allocation - 

This could easily be the case.
BUT we should profile the code and stop guessing.

Cygwin has a 'poor' gprof implementtion so maybe one of the 
Linux users could configure GEOS with 

% CXXFLAGS="-O2 -g -pg" ./configure
make clean
make

run a 10000 pt test 
then run gprof so we had some REAL timings to look at

> 
>(since Linux may have a better - or worse! - memory allocator).

Cygwin and Linux actually use the same malloc subsystem
This is worth trying with MSVC too

 
> 
> 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

Ah this is MUCH better
It almost makes me think that somehow the
C code is missing an early reject somewhere
in the translation and turning this into a O(N**2)
instead of an O(N) operation

A profiling test should point to the offending loop

Norman