bug#58361: 29.0.50; noverlay branch is O(N) for important calls

[Stefan Monnier]

> I think, a straightforward way   to use 2 trees, one for begin and one for
> end, could be to create another abstraction above those trees, while for the
> most part  duplicating the existing  interface.  This abstraction would then
> either delegate to one or both trees, depending on the operation. The trick
> would be to kinda multiplying the end-tree by -1,  i.e. reverse begin and
> end and multiply with -1 all inputs and outputs of this tree.
>
> Would that work ?

Could be but I'm not sure we want to pay this memory&cpu price to try
and fix a performance bug that's still hypothetical.
For all we know, in those cases where this performance problem could
bite, other performance problems bite us harder anyway.


        Stefan


>> Am 07.10.2022 um 17:23 schrieb Matt Armstrong <matt@rfc20.org>:
>> 
>> To start, I don't think this issue should delay a merge to master.  I
>> don't think it is clear we need to fix anything here.
>> 
>> I would like a note or FIXME in code noting the potentially slow
>> algorithm (patch sent), because it is currently well hidden behind a
>> generator loop.
>> 
>> 
>> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> 
>>>> Here we traverse overlays in ASCENDING order of BEG positions.  The best
>>>> we can say is that this loop executes in O(K*log(N)) time, where K is
>>>> the MIN of number of overlays that overlap POS and the number of valid
>>> 
>>> The core operation in itree.c is the equivalent of `overlays-in/at`.
>> 
>> [...]
>> 
>> Yes, and for this O(K*log(N)) performance is a good result.  The key
>> insight is that previous and next overlay changes require examining a
>> large K (in worst case, extending all the way to the beginning or end of
>> the buffer) because there is no ordering by END positions.
>> 
>>> Realistic benchmarks would be most welcome.
>> 
>> I am working on polishing off
>> https://git.sr.ht/~matta/emacs-overlay-perftests.  Good news is that
>> redisplay is faster on the noverlay branch for the "realistic" case of
>> overlaping not overlapping eachother in pathalogical ways.
>> 
>> 
>>> [ Site note: `previous-overlay-change` is probably not very important in
>>>  practice, but `next-overlay-change` OTOH is indeed important because
>>>  it's used during redisplay.  So if someone comes up with a trick to
>>>  speed up only one direction, it should be good enough.  ]
>>> 
>>> Maybe one way to improve the behavior is to accept the worst-case
>>> bound but to try and avoid paying it over-and-over each time the
>>> redisplay needs the "next change".  IOW instead of a
>>> `next_overlay_change` function which takes a POS and returns the next
>>> change after that, the xdisp.c might benefit from having a
>>> `next_overlay_changes` *generator* which takes a starting POS and
>>> returns an iterator which will return (each time it's called) the
>>> successive positions where there's an overlay change.
>>> 
>>> Hopefully this way we'd pay the O(N) cost once per redisplayed window
>>> rather than once per "small step in the rendering engine" (i.e. per
>>> next_overlay_change).
>> 
>> At the moment I can't think of a reasonable way to implement such a
>> generator efficiently without, effectively, computing a temporary
>> ordered collection over overlay END positions.
>> 
>> This is why I keep coming back to the idea of storing both BEG and END
>> positions in ordered collections at all times.
>> 
>> 
>>> Another way to do basically the same is to let next_overlay_change
>>> fill up a cache of change-positions which would be flushed whenever
>>> some overlay is modified/added/removed (or the current_buffer is
>>> different from last time).  That might be easier to use with the
>>> current code since xdisp.c wouldn't need to pass around this iterator
>>> (which could require significant reworks).
>> 
>> ...possibly, but the problem with caching is the time spent filling the
>> cache back up.  I like the idea of storing both BEG and END positions in
>> an ordered collection because in that case the (potentially slow)
>> recomputation need not occur with every key press.  If we're not worried
>> about that kind per-key-press of delay, then I argue there is no need
>> for a cache either.