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

[Matt Armstrong]

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.