Performance improvements to HPRtree

[msbarry]

Hello! While profiling performance of planetiler I noticed that STRtree in MCIndexNoder was one of the bottlenecks. I looked into HPRtree and saw there were a few opportunities to improve performance using some ideas from the flatbush library:

• compute hilbert indexes only once for each item while sorting
• limit the sort so it just sorts items into the correct node, but doesn't bother sorting within the node
• extract item bounds and values into arrays for faster lookups during query

This version performs faster in some of the microbenchmarks (especially when result sets are large) but when I swap out STRtree with this improved HPRtree planetiler spends about 30% less time in MCIndexNoder.computeNodes, isValid checks, and about 10% less time in the most expensive operations planetiler uses: GeometryPrecisionReducer.reduce and bufferUnionUnbuffer.

Here's a preview of what I've got: https://github.com/locationtech/jts/compare/master...msbarry:jts:hprtree?expand=1 - what do you think about incorporating this change into JTS @dr-jts ? One concern is that sortItemsIntoNodes method was ported directly from flatbush. I could either cite that or do a clean-slate implementation?

Thanks!

[dr-jts]

This is quite exciting - thanks, @msbarry . I'll look at it in more detail in the coming days.

It would be great if you can do a reasonably clean implementation of sortItemsIntoNodes. I guess that is a custom implementation of a sorting algorithm? Quicksort or Heapsort? Any idea why they are doing a custom sort? (Perhaps because they are sorting two arrays in synch, instead of just one?)

Additional ideas to look at:

• Turn HPRtree into a template class. Probably no performance boost, but nicer to code with
• Use a two different index sorting strategies. The HPRtree can be used to index rings, but rings can be indexed using some variant of VertexSequencePackedRtree. This could be built on Monotone chains as well, which are contiguous. The new tg library uses this idea - see https://github.com/tidwall/tg/blob/main/docs/POLYGON_INDEXING.md#natural.

[msbarry]

Thanks! I opened up #1012 for this.

The modified quicksort is so that it can stop sorting elements within the same node because queryItems just searches through them sequentially. I updated with it to use "textbook" quicksort with hoare partitioning.

Turn HPRtree into a template class

I took a stab at this in the PR, which required updating SpatialIndex and a few other classes to use generics, so any code that uses these will get compile warnings now (but not errors).

Use a two different index sorting strategies

That sounds interesting! Although probably good to in a separate PR from the HPRtree improvements.

[dr-jts]

Use a two different index sorting strategies

That sounds interesting! Although probably good to in a separate PR from the HPRtree improvements.

Agreed, that should be a separate PR.

[msbarry]

Use a two different index sorting strategies. The HPRtree can be used to index rings, but rings can be indexed using some variant of VertexSequencePackedRtree. This could be built on Monotone chains as well, which are contiguous. The new tg library uses this idea - see https://github.com/tidwall/tg/blob/main/docs/POLYGON_INDEXING.md#natural.

I'm trying to understand this approach a bit better... From what I can tell MCIndexNoder.computeNodes takes a list of SegmentString where each of them is a ring (?) then MCIndexNoder.add extracts the monotone chains from each ring and indexes them by their bounds, then intersectChains iterates over each chain and intersects with others with overlapping bounds from the index?

So the difference here would be that we'd use VertexSequencePackedRtree to index the nodes (or monotone chains?) of each segment string, then HPRtree to index those VertexSequencePackedRtree's by the ring bounds? I can't quite picture how intersectChains would use the result.

It also looks like VertexSequencePackedRtree indexes the points, not segments between them, so are you talking about a modified MonotoneChainSequencePackedRtree (or a generic BoundableSequencePackedRtree) that holds continuous monotone chains and indexes them by their bounds?

[msbarry]

OK I think I get it... intersectChains would become something like:

  private void intersectChains()
  {
    MonotoneChainOverlapAction overlapAction = new SegmentOverlapAction(segInt);

    for (MonotoneChain queryChain : monoChains) {
      Envelope queryEnv = queryChain.getEnvelope(overlapTolerance);
      for (MonotoneChainSequencePackedRtree ringIndex : index.query(queryEnv)) {
        for (MonotoneChain testChain : ringIndex.query(queryEnv)) {
          if (testChain.getId() > queryChain.getId()) {
            queryChain.computeOverlaps(testChain, overlapTolerance, overlapAction);
            nOverlaps++;
          }
          // short-circuit if possible
          if (segInt.isDone())
            return;
        }
      }
    }
  }

?

[dr-jts]

It also looks like VertexSequencePackedRtree indexes the points, not segments between them

Yes, a SegmentSequencePackedRtree is needed. That would provide an index for the rings, and then the rings would be indexed using the HPRtree.

Alternatively, as you suggest there could be a MonotoneChainSequencePackedRtree to index individual rings (with the rings indexed by HPRtree. Hard to say a priori how this would perform, and whether adding in the complexity of Monotone Chains would be worth it.

There could even be an implementation which merges the Monotone Chain idea with the Sequence Packed Ring idea, to avoid creating separate MonotoneChain objects.

This is obviously a lot of coding and testing to determine which is best (and "best" may be data-specific).