@Tyriar Is there a better way to determine, if a cell is decorated? This callback method runs several times for all matched decorations, while all I need is a.hasDecoration(x,y) boolean indicator here.

We can add ahasDecoration. A faster way currently would be usinggetDecorationsAtCell and break after the first one, that needs a generator created though.

Hmm indeed, the generator has worse runtime, even if I break out of the iteration early 😢

@Tyriar I was not able to find a faster access for ahasDecoration method. Tried different things like early exit fromforEachDecorationAtCell, using an iterable instead of a generator, even tried returning an array of decorations to save the second iteration. All beside the iterable perform slightly better if there are no decorations, but the difference is only ~20ms vs. ~1ms over 14s total runtime. The picture changes, if there are decorations - thenforEachDecorationAtCell beats them all being at least 20% faster. Thus I think it is good as it is atm.

The toxic runtime part is the binary search across lines, plus the a linear search within the line, some numbers from myls -lR /usr test (tested with DOM renderer):

• 0 highlighted matches: ~20 ms forforEachDecorationAtCell
• 100 matches: ~130 ms forforEachDecorationAtCell
• 1000 matches: ~500 ms forforEachDecorationAtCell

with ~80% spent in_search (binary search part) and the rest inforEachDecorationAtCell (linear search part). Which makes me wonder, if the binary search part could be omitted by another indirection on the list with O(1) access to the line values.

Btw I was not able to test higher matches, seems the highlighting is capped in the search addon.

Edit: On a sidenote - it might already help to reshape _search into a loop instead of recursive calls.
Edit2: Yeah - changing _search into a loop reduces runtime from 500 ms to 150 ms for 1000 matches (also v8 folds _search intoforEachDecorationAtCell, so I cant separate binary vs. linear search cost anymore)

Any perf improvements are welcome of course, but I wouldn't worry too much about squeezing a lot out of looking up decorations as they are normally not used at all or used sparingly. VS Code only uses it with find (which performs good enough with many results), highlighting things temporarily and adding decorations next to commands for shell integration.

Nice work if a_search refactor speeds things up that much!

The loop version shows these runtimes:

• 0 matches: ~1 ms
• 100 matches: ~40 ms
• 1000 matches: ~120 ms

Btw a linear scan withreturn this._array.map(el => this._getKey(el)).indexOf(key) is still the fastest up to 1000 matches (~90 ms), but certainly will degrade pretty fast after that. It also changes the return value, so I did not bother with it.

That would also allocate memory for the mapped arrays, but yeah we're after better scaling while should happen with the binary search