[geos-devel] Extent-limited graph building ?

[Rémi Cura]

Wov 15 sec to 2 sec is a very nice speed up !
Cheers,
Rémi-C

2014-09-23 10:21 GMT+02:00 Sandro Santilli <strk at keybit.net>:

> 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
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/geos-devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20140923/76ae4a8b/attachment.html>