[geos-devel] Extent-limited graph building ?

[Sandro Santilli]

On Fri, Sep 19, 2014 at 05:54:10PM +0200, Sandro Santilli wrote:

> So, to recap, we go from ~15 seconds to ~2.8 seconds with my
> specific case (polygon with ~250k holes, intersected with small
> box).
> 
> Some nice debugging output:
> 
>   Copied 467 nodes out of 10711 for geom 0
>   Copied 0 nodes out of 1 for geom 1
>   (computeSelfNodes) Self edges reduced from 10711 to 470
>   (computeSelfNodes) Self edges reduced from 1 to 1
>   Self edges reduced from 10711 to 470
>   Other edges reduced from 1 to 1
> 
> It looks like the majority of the time is still spent after
> the last output line. Now profiling that one.

Interesting, the profiler shows the same number of calls to 
index::strtree::STRtree::STRIntersectsOp::intersects(void const*, void const*)
with and without the envelope restriction optimization.

Calls to that function represent the 32% of total time with optimization
activated, and 18% without.

We're talking about 124380300 calls, all coming from 338673 calls to
index::strtree::AbstractSTRtree::query, in turn all coming from the
FastNodingValidator. This means 30% of those ~3 seconds are spent
validating the output, doesn't it ? Is that step still needed ?
That's one of the steps that a "loose" (visualization-oriented)
function would not spend time on.

--strk;

> Whole testsuite still succeed, and latest code is pushed to github:
> https://github.com/strk/libgeos/tree/ext-limited-graph