geos icon indicating copy to clipboard operation
geos copied to clipboard

Improve STRtree memory layout

Open dbaston opened this issue 3 years ago • 1 comments

The GEOS STRtree stores its nodes in a single contiguous block of memory, which is nice. But that block isn't organized very well:

  • The branch nodes are at the right end of the block (a consequence of the construction order), with the root at the very end. So traversing the tree means moving from right-to-left in memory, which may not (?) be smart cache-wise.
  • Leaf nodes are not shifted in memory when their parent branch nodes are sorted, so the order of leaves in memory does not correspond to a depth-first traversal. We should get better query performance if the layout in memory matches the query order.

dbaston avatar Dec 07 '22 02:12 dbaston

The internet seems to think that modern CPU's don't particularly care about scan direction WRT prefect.

pramsey avatar May 15 '23 21:05 pramsey