4 ms·

> Real-world impact: With 50+ view parts (text, cursors, minimap, scrollbar, widgets, decorations, etc.), this wastes 1-2ms per frame Good thing to find...

blharr 11mo ago
How does it possibly take 1-2ms to sort... 50 items? I'd expect that to happen in an order of microseconds
- klodolph 11mo ago
  It’s being sorted not once per frame, but once per item. If you have 50 items in the list, then the list gets sorted 50 times. If you have 200 items in the list, the list is sorted 200 times. This is unnecessary. The obvious alternative is a binary heap… which is what the fix does. Although it would also be obvious to reuse an existing binary heap implementation, rather than inventing your own.
  - duskwuff 11mo ago
    > It’s being sorted not once per frame, but once per item. 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. > The obvious alternative is a binary heap… which is what the fix does. 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().
    - minitech 11mo ago
      > 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/7ff89dbf0c6394ce4861903a2325c43c https://gist.github.com/minitech/7ff89dbf0c6394ce4861903a232...
  - anticensor 11mo ago
    > Although it would also be obvious to reuse an existing binary heap implementation, rather than inventing your own. Yes, that's indeed the approach I'd take.
- hdjfjkremmr 11mo ago
  it's sorting 50 times a list going from 50 to 0 items.
  - blharr 11mo ago
    49 of those times, it's hitting the best case of sorting an already sorted list, so I still can't imagine that huge of a performance penalty
    - hyperhello 11mo ago
      There are sort algorithms that don’t do any work except scanning if the list is unsorted, but there are more efficient ones to use if they are.
- retsibsi 11mo ago
  The issue seems to be a direct copy-paste from an LLM response, so I suspect "this wastes 1-2ms per frame" is estimated/made up.

blharr 11mo ago

How does it possibly take 1-2ms to sort... 50 items? I'd expect that to happen in an order of microseconds

klodolph 11mo ago
It’s being sorted not once per frame, but once per item. If you have 50 items in the list, then the list gets sorted 50 times. If you have 200 items in the list, the list is sorted 200 times. This is unnecessary. The obvious alternative is a binary heap… which is what the fix does. Although it would also be obvious to reuse an existing binary heap implementation, rather than inventing your own.
- duskwuff 11mo ago
  > It’s being sorted not once per frame, but once per item. 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. > The obvious alternative is a binary heap… which is what the fix does. 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().
  - minitech 11mo ago
    > 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/7ff89dbf0c6394ce4861903a2325c43c https://gist.github.com/minitech/7ff89dbf0c6394ce4861903a232...
- anticensor 11mo ago
  > Although it would also be obvious to reuse an existing binary heap implementation, rather than inventing your own. Yes, that's indeed the approach I'd take.
hdjfjkremmr 11mo ago
it's sorting 50 times a list going from 50 to 0 items.
- blharr 11mo ago
  49 of those times, it's hitting the best case of sorting an already sorted list, so I still can't imagine that huge of a performance penalty
  - hyperhello 11mo ago
    There are sort algorithms that don’t do any work except scanning if the list is unsorted, but there are more efficient ones to use if they are.
retsibsi 11mo ago
The issue seems to be a direct copy-paste from an LLM response, so I suspect "this wastes 1-2ms per frame" is estimated/made up.