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

[Andreas Politz]

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 ?

> 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.