[geos-devel] Extent-limited graph building ?

[Sandro Santilli]

On Fri, Sep 19, 2014 at 06:17:33PM +0200, Sandro Santilli wrote:
> On Fri, Sep 19, 2014 at 06:05:09PM +0200, Sandro Santilli wrote:
> > 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.
> 
> Removing the noding validator step results in current trunk
> taking ~13 seconds instead of ~15 and the envelope-filtering version
> taking ~0.9 seconds instead of ~3 seconds

Good news, I further reduced the time spent in noding validator
by NOT adding in the OverlayOp edgeList those edges whose envelope does
not overlap the target one. This brings the total time down to 2 seconds
(from the original 15 seconds).

I've committed all of this already, but I guess it could be further
optimized by completely avoiding to push the input geometries components
at the very start, so we'd save having to filter them out later (or deleting
them once right after construction, which currently does not allow passing
a "target extent").

--strk; 

 ()  ASCII ribbon campaign  --  Keep it simple !
 /\  http://strk.keybit.net/rants/ascii_mails.txt