<div dir="ltr"><div>Wov 15 sec to 2 sec is a very nice speed up !<br></div>Cheers,<br>Rémi-C<br></div><div class="gmail_extra"><br><div class="gmail_quote">2014-09-23 10:21 GMT+02:00 Sandro Santilli <span dir="ltr"><<a href="mailto:strk@keybit.net" target="_blank">strk@keybit.net</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">On Fri, Sep 19, 2014 at 06:17:33PM +0200, Sandro Santilli wrote:<br>
> On Fri, Sep 19, 2014 at 06:05:09PM +0200, Sandro Santilli wrote:<br>
> > On Fri, Sep 19, 2014 at 05:54:10PM +0200, Sandro Santilli wrote:<br>
> ><br>
> > > So, to recap, we go from ~15 seconds to ~2.8 seconds with my<br>
> > > specific case (polygon with ~250k holes, intersected with small<br>
> > > box).<br>
> > ><br>
> > > Some nice debugging output:<br>
> > ><br>
> > >   Copied 467 nodes out of 10711 for geom 0<br>
> > >   Copied 0 nodes out of 1 for geom 1<br>
> > >   (computeSelfNodes) Self edges reduced from 10711 to 470<br>
> > >   (computeSelfNodes) Self edges reduced from 1 to 1<br>
> > >   Self edges reduced from 10711 to 470<br>
> > >   Other edges reduced from 1 to 1<br>
> > ><br>
> > > It looks like the majority of the time is still spent after<br>
> > > the last output line. Now profiling that one.<br>
> ><br>
> > Interesting, the profiler shows the same number of calls to<br>
> > index::strtree::STRtree::STRIntersectsOp::intersects(void const*, void const*)<br>
> > with and without the envelope restriction optimization.<br>
> ><br>
> > Calls to that function represent the 32% of total time with optimization<br>
> > activated, and 18% without.<br>
> ><br>
> > We're talking about 124380300 calls, all coming from 338673 calls to<br>
> > index::strtree::AbstractSTRtree::query, in turn all coming from the<br>
> > FastNodingValidator. This means 30% of those ~3 seconds are spent<br>
> > validating the output, doesn't it ? Is that step still needed ?<br>
> > That's one of the steps that a "loose" (visualization-oriented)<br>
> > function would not spend time on.<br>
><br>
> Removing the noding validator step results in current trunk<br>
> taking ~13 seconds instead of ~15 and the envelope-filtering version<br>
> taking ~0.9 seconds instead of ~3 seconds<br>
<br>
</div></div>Good news, I further reduced the time spent in noding validator<br>
by NOT adding in the OverlayOp edgeList those edges whose envelope does<br>
not overlap the target one. This brings the total time down to 2 seconds<br>
(from the original 15 seconds).<br>
<br>
I've committed all of this already, but I guess it could be further<br>
optimized by completely avoiding to push the input geometries components<br>
at the very start, so we'd save having to filter them out later (or deleting<br>
them once right after construction, which currently does not allow passing<br>
a "target extent").<br>
<div class="HOEnZb"><div class="h5"><br>
--strk;<br>
<br>
 ()  ASCII ribbon campaign  --  Keep it simple !<br>
 /\  <a href="http://strk.keybit.net/rants/ascii_mails.txt" target="_blank">http://strk.keybit.net/rants/ascii_mails.txt</a><br>
_______________________________________________<br>
geos-devel mailing list<br>
<a href="mailto:geos-devel@lists.osgeo.org">geos-devel@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/geos-devel" target="_blank">http://lists.osgeo.org/mailman/listinfo/geos-devel</a><br>
</div></div></blockquote></div><br></div>