Closed paulmach closed 2 years ago
I implement an "internal" maxHeap vs using the std lib one. This makes it twice as fast AND returns sorted results. Allocations are now ~K vs. "nodes seen".
If you were doing this 1000s of times for the same quadtree you could implement something to reuse the maxHeap memory. Some sort of KNearestContainer
and create one per goroutine/thread. That would put you down to 2-4 allocations per KNearest search.
benchmark old ns/op new ns/op delta
BenchmarkRandomKNearest10-12 3650 2094 -42.63%
BenchmarkRandomKNearest100-12 32616 15957 -51.08%
benchmark old allocs new allocs delta
BenchmarkRandomKNearest10-12 34 14 -58.82%
BenchmarkRandomKNearest100-12 269 104 -61.34%
benchmark old bytes new bytes delta
BenchmarkRandomKNearest10-12 1457 472 -67.60%
BenchmarkRandomKNearest100-12 12081 3432 -71.59%
as requested here https://github.com/paulmach/orb/issues/67
The results of the
quadtree.KNearest
were just the "heap" order. Now they are sorted closest first.It is slower however, would probably need to implement a custom heap to get rid of the allocs. I did that for the visvalingam simplification here. Hopefully generics will allow this to be simple and performant.