RBush feedback about nettopologysuite.sandbox HOT 8 CLOSED

Was there a .sln file that got missed?

from nettopologysuite.sandbox.

Yes, but that has some projects in it that are not ready.

from nettopologysuite.sandbox.

Recursive iterators tend to perform poorly, in my experience; I usually wind up rewriting them using a heap-allocated Stack<T> like this:

private static IEnumerable<T> GetAll(Node node)
{
    var stack = new Stack<IBoundable<Envelope, T>>(node.Children);
    while (stack.Count != 0)
    {
        var child = stack.Pop();
        if (child is Node nodeChild)
        {
            foreach (var childChild in nodeChild.Children)
            {
                stack.Push(childChild);
            }
        }
        else
        {
            yield return child.Item;
        }
    }
}

from nettopologysuite.sandbox.

Right now, the callers of this method always (ultimately) get a List<T> that we created ourselves, so I'd tend to favor using List<T> in the method signatures here (and in SelectStep + Swap) to help the JIT emit better code for this.

In fact, I probably would have have made it T[] since its length never changes after it's built.

Thinking about it even more, we do recursively reference the System.Memory package, so this could be Span<T> and we could use its own .Slice method to get zero-copy, zero-allocation slices of the data instead of this:

from nettopologysuite.sandbox.

FWIW, as I understand it, flatbush is an even faster R-tree implementation (uses less memory too), for cases where the index is completely static after the initial build (deletions are forbidden too, not just additions).

Those improvements come from having a very densely packed data layout, so if you're interested in writing an ISpatialIndex<T> interface on top of it, I suggest starting from this MIT-licensed port. I've used this port before, and I was unable to come up with anything significant that could be improved about it in my last audit of the code.

from nettopologysuite.sandbox.

IIRC the HPRtree (Hilbert-Packed-Rtree) in JTS/NTS is not faster than STRtree.

from nettopologysuite.sandbox.

Thanks for the feedback @airbreather. Flatbush<T> is indeed faster, the index tester suggests that it takes less than half of the query time of Rbush<T>. Rbush<T> itself is faster than STRtree<T>

------------------------------------------------------
Real run
------------------------------------------------------
# items = 100000
Rbush[M8]           Avg query size = 269.43
  Load Time = 162  Query Time = 5469
Flatbush[M8]           Avg query size = 269.43
  Load Time = 41  Query Time = 2756
Rbush[M10]           Avg query size = 269.43
  Load Time = 135  Query Time = 5721
Flatbush[M10]           Avg query size = 269.43
  Load Time = 32  Query Time = 2524
Rbush[M12]           Avg query size = 269.43
  Load Time = 129  Query Time = 6178
Flatbush[M12]           Avg query size = 269.43
  Load Time = 32  Query Time = 2461
Rbush[M14]           Avg query size = 269.43
  Load Time = 137  Query Time = 5678
Flatbush[M14]           Avg query size = 269.43
  Load Time = 34  Query Time = 2531
Rbush[M16]           Avg query size = 269.43
  Load Time = 128  Query Time = 6108
Flatbush[M16]           Avg query size = 269.43
  Load Time = 34  Query Time = 2602
STR[M=6]           Avg query size = 269.43
  Load Time = 240  Query Time = 8751
STR[M=10]           Avg query size = 269.43
  Load Time = 200  Query Time = 8294
STR[M=14]           Avg query size = 269.43
  Load Time = 186  Query Time = 7660

from nettopologysuite.sandbox.

For reference include HPRtree<T>:

HPR[M=16]           Avg query size = 243,35092
  Load Time = 212  Query Time = 4272
Rbush[M16]           Avg query size = 243,35092
  Load Time = 175  Query Time = 7400
Flatbush[M16]           Avg query size = 243,35092
  Load Time = 38  Query Time = 2758
STR[M=16]           Avg query size = 243,35092
  Load Time = 192  Query Time = 9813

So for query time the order is

1. Flatbush<T>
2. HPRtree<T>
3. Rbush<T>
4. STRtree<T>

from nettopologysuite.sandbox.