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

[Stefan Monnier]

> 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`.
It's considered OK if this takes O(N) where N is the number of overlays
that are returned, since that's the best we can do.

In practice itree.c takes a bit more than O(N) for that, there's
an additional log(M) factor where M is the total number of overlays, but
it's still overall significantly better at this operation than the old
code which was O(M).

In practice the expectation is that N is relatively small.  Of course,
we don't have any such guarantee, there might be cases where packages
create many overlays each of which covers almost all the buffer.
IIUC this situation is poorly handled both by the old and the new
code, tho.
Realistic benchmarks would be most welcome.

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

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


        Stefan