Mass decoration registration and disposable is slow

[Tyriar]

VS Code issue: microsoft/vscode#199593

Lots of GC happening when registering and disposing many decorations. Here's an example showing and hiding a command guide in VS Code which creates and then disposed ~16k decorations:

https://github.com/Tyriar/xterm.js/blob/1943636f023b0496c2b95aeb31f2d08d7c0e4dce/src/common/services/DecorationService.ts#L41-L60

Some ideas to speed up:

• Don't use splice(!) in SortedList
  • Doing something more clever here would probably vastly improve registration
• Use an object pool
• Defer clean up to idle callback

[jerch]

My guess also goes to the splice needs here, SortedList basically implements the insert sort idea, which is nice for insertion/removal at the end with O(1), but soon saturates to O(n²) for average (I guess this happens alot here, when lines drop off the scroll buffer at the top).

Edit: For reference - I've done an RB tree impl back during the buffer rewrite (which never made it into the core code), maybe this comes handy at some point: https://github.com/jerch/xterm.js/blob/AttributeStorage/src/AttributeStorage.ts
(sidenote - the code is not nicely abstracted but highly optimized for the attribute task back then 😅 )

Edit2: A balanced tree based impl will perform alot worse for typical insertion/removal at the end. Maybe partitioning of the list (like a skiplist) will already do the job here?

[Tyriar]

Yes RB or AVL is probably the fix. I've done both before but it looks like I never bothered porting the RB tree from js to ts yet. https://github.com/gwtw/ts-avl-tree, https://github.com/gwtw/js-data-structures/blob/master/lib/red-black-tree.js

A balanced tree based impl will perform alot worse for typical insertion/removal at the end. Maybe partitioning of the list (like a skiplist) will already do the job here?

It's still just log n though, the main thing that matters is that it scales well imo

[tisilent]

I see if there is anything I can do on the demo to facilitate subsequent verification. 😀

[jerch]

@Tyriar How would an easy repro look like? Is it enough to spam tons of decorations all over the lines, or do they need to follow a certain pattern?

Which action triggered the toxic removals? Was that just from scrolling off at the top? Because if thats the case, we could prolly lift some burden here by batching the removals with interim "dead keys" on the sorted list and doing a final cleanup copy. Difference would be O(n + m log n) vs. currently O(m*n + m log n) for m elements to be removed from n elements (the m multiplier comes from the splice copy overhead for every single removal in our current bisearch&splice approach, which we have only once with dead keys).

[Tyriar]

There's a lot of decorations in vscode now with shell integration, especially when you're hovering the terminal as there's a "command guide" as well:

I think my repro above was something like running tree and then scrolling up with smooth scroll on. Doing a find will make it more intense

[Tyriar]

Example with the decoration stress test button I made: