search

lemire / FastPriorityQueue.js

a fast heap-based priority queue in JavaScript
Apache License 2.0
357 stars 57 forks source link

Improve kSmallest and clone performance #29

Closed Barbarrosa closed 3 years ago

Barbarrosa commented 3 years ago

I was trying to improve performance of JITDB, and I noticed some calls to this library that could be improved.

The kSmallest method seemed to be running unusually slowly compared with other methods in this library. While the overall algorithm looked sound, it didn't seem to stand up to empirical testing & I found more success by simply cloning the inner array and dequeuing elements from it. I calculated an upper bound on how many elements to clone based on how deep kSmallest may need to look in the heap for results.

I updated clone while I was at it. The change from push to slice should take better advantage of JS engine optimizations for the initial copy, though I can't speak to whether the resulting array will be considered "packed" or "holey".

lemire commented 3 years ago

Nice code simplification. I am merging and re-releasing.