Interval Heap vs MinHeap

Jump to navigation Jump to search

Interval Heap vs MinHeap

I'm curious, why did you go with the MinHeap instead of the IntervalHeap for your path ordering? Surely IntervalHeap can be kept pruned and small, resulting in less overhead?

Skilgannon (talk)07:38, 20 July 2013

I hadn't actually thought to try that. The IntervalHeap is something I added specifically when I was thinking about implementing to search iterator, rather than optimizing the search steps themselves.

I just tried it right now. Turns out that the more complex procedure to maintain the IntervalHeap's ordering adds more cost than is saved by keeping the path ordering queue pruned, at least for this size of tree in the 'standard' data set.

I tried two seperate approaches of using the IntervalHeap to keep that queue pruned:

  1. Remove any paths which are now known to be too distant, whenever we finish processing a leaf node (aka, always keep it pruned as much as possible)
  2. When we're adding a new path to the queue, if the furthest path in the queue is too distant, replace it to avoid growing the heap (aka, don't actively prune it, merely don't grow it if we can avoid it)

Both approaches performed worse overall than the unpruned MinHeap. Even if I do a run with JIT warmup allowed to compensate for the IntervalHeap's more complex code, it still performs slightly worse on average. When the JIT warmup is allowed however, the "worst case" time appears to improve though, just not the average.

Rednaxela (talk)14:45, 20 July 2013

How about keeping a flag in your leaf node processing so that you only try pruning if you added a new item?

Skilgannon (talk)14:48, 20 July 2013

You do not have permission to edit this page, for the following reasons:

  • The action you have requested is limited to users in the group: Users.
  • You must confirm your email address before editing pages. Please set and validate your email address through your user preferences.

You can view and copy the source of this page.

Return to Thread:User talk:Rednaxela/kD-Tree/Interval Heap vs MinHeap/reply (3).

And how about if you just use the IntervalHeap, but don't try any pruning? I'm curious whether the pruning is slow, or the different heap.

Skilgannon (talk)15:26, 20 July 2013

I was thinking it was the different heap... but actually turns out the heaps are approximately the same performance, with the difference being the pruning:

 - #1 Rednaxela's kd-tree (3rd gen, Interval Heap) [0.0290]
 - #2 Rednaxela's kd-tree (3rd gen) [0.0290]
 - #3 Rednaxela's kd-tree (3rd gen, Interval Heap, Prune When Points Added) [0.0293]
 - #4 Rednaxela's kd-tree (3rd gen, Interval Heap, Avoid Growing Heap When Possible) [0.0294]
 - #5 Skilgannon's Cache-hit KDTree [0.0296]
Rednaxela (talk)16:26, 20 July 2013

So the incremental difference from a larger heap is less than the cost of removing the points.

Skilgannon (talk)19:54, 20 July 2013