RecTree

[Sandro Santilli]

On Thu, Mar 14, 2024 at 11:12:44AM -0700, Paul Ramsey wrote:
> Sandro,
> I don’t know if you’re still poking around distance, but I have been too, and here’s a few notes.

I settled with the GEOS DistanceIndexed so no, I'm not poking anymore.

> - Firstly, with respect to distance vs distance_sqr [...]
>   I would have thought I’d see something measurable,

Your test gives me a ~18% speed increase by dropping the sqrt(), go figure!
4.5 vs 5.5 secs with -O0 and 2e9 iterations.

> - Secondly, I have dusted off the old RecTree code
> 
> So you can manually turn on the functionality, see if/how much better it is than the existing functions for your workloads.

Loading geometries in https://trac.osgeo.org/postgis/attachment/ticket/3587/test10input_singlepoly.sql.gz
with TopoGeo_AddLinestring in path order (shell first) gives these numbers:

	GEOSDistanceIndexed: Time: 222501.482 ms (03:42.501)
	   LWGEOM_Rect_Tree: Time: 161353.258 ms (02:41.353)

Times reported by loading all-worst-cases
topology/test/perf/TopoGeo_addLinestring_concentricCircles.sql:

	GEOSDistanceIndexed: 3062.23ms on average
	   LWGEOM_Rect_Tree: 1653.98ms on average

Times reported by loading always-intersecting
topology/test/perf/TopoGeo_addLinestring.sql:

	GEOSDistanceIndexed: 32453.30ms on average
	   LWGEOM_Rect_Tree: 20617.80ms on average

Using the liblwgeom one we're saving conversion which is good too!
It looks like a clear win to switch over.

Can you see any reason to postpone such switch or should I push it ?

> I am going to look at trying to make the build a little more memory
> friendly which should also increase the locality of the tree nodes,
> which might speed up the scan phase a little (this kind of rework make
> the point-in-poly code about 15% faster, but no guarantees.)

Great work !

--strk;
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 659 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20240314/3c772014/attachment.sig>