> Even if that were the case, sorting a list that's already sorted is basically free. Any reasonable sort method (like the builtin one in a JS runtime) will check for that before doing anything to the list.
That’s n−1 pairs of elements that have to be compared with a a JS callback each time. (JavaScript’s combined language misfeatures that allow the array to be modified in many odd/indirect ways while it’s being sorted might add unusually high overhead to all sorting too – I’m not sure how much of a fast path there is.) Anyway, the code in question does include functionality to add new elements to the priority queue while it’s being processed.
> The overhead of creating a heap structure out of JS objects will dwarf any possible benefit of avoiding a couple of calls to Array.sort().
Not true even in general and with an unoptimized heap implementation, and in this case, there’s an array of JS objects involved either way. In fact, there’s no number of elements small enough for sorting to be faster in this benchmark in my environment (I have no idea whether it reflects realistic conditions in VS Code, but it addresses the point): https://gist.github.com/minitech/7ff89dbf0c6394ce4861903a232...
That’s n−1 pairs of elements that have to be compared with a a JS callback each time. (JavaScript’s combined language misfeatures that allow the array to be modified in many odd/indirect ways while it’s being sorted might add unusually high overhead to all sorting too – I’m not sure how much of a fast path there is.) Anyway, the code in question does include functionality to add new elements to the priority queue while it’s being processed.
> The overhead of creating a heap structure out of JS objects will dwarf any possible benefit of avoiding a couple of calls to Array.sort().
Not true even in general and with an unoptimized heap implementation, and in this case, there’s an array of JS objects involved either way. In fact, there’s no number of elements small enough for sorting to be faster in this benchmark in my environment (I have no idea whether it reflects realistic conditions in VS Code, but it addresses the point): https://gist.github.com/minitech/7ff89dbf0c6394ce4861903a232...