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

[Stefan Monnier]

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

I'll merge it soon, yes, thanks.

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

Excellent, thanks.

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

Indeed, the generator needs to build such a side table (I was thinking
of something like a heap datastructure).  I don't see it as a problem.

> This is why I keep coming back to the idea of storing both BEG and END
> positions in ordered collections at all times.

But that comes at a non-negligible constant-factor cost :-(

[ Maybe a "cheapish" (memory-wise) way to make it work is to add two
  fields `prev` and `next` used to link the nodes into a doubly-linked
  list ordered by `end` positions.  We should be able to find a given
  position in this list efficiently (i.e. not linear time) by relying on
  the `limit` field, thus making it unnecessary to maintain a second
  *tree*.  ]

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

I'm definitely not worried about performing one such recomputation per
key press.  The problem of the O(N) issue you point out might come up
when we have to repeat that O(N) for every buffer position where there's
an "overlay change", but if it's done once per redisplay (or once per
window being redisplayed), it should be lost in the noise.


        Stefan