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

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

[Matt Armstrong]

[-- Attachment #1: Type: text/plain, Size: 4079 bytes --]

First let me preface:

A) I hope I'm wrong here, but after careful thought I've failed to
convince myself that I am, so I am either right or need help from others
to spot my flawed logic.

B) Even if I'm right the problem may not be judged serious enough to
address.

I believe that the feature/noverlay branch uses an O(N) algorithm for
next-overlay-change and previous-overlay-change.  Or, more precisely,
O(MIN(N, (buffer-size))), where N is the overlay count.

Now, in "normal" cases the real world achieved performance will be fine.
If overlays form mostly disjoint intervals, without too many overlapping
overlays, without too many overlays that span large portions of the
buffer, the algorithm used will find the next/previous change quickly.

However, consider the new next_overlay_change:

     1	ptrdiff_t
     2	next_overlay_change (ptrdiff_t pos)
     3	{
     4	  ptrdiff_t next = ZV;
     5	  struct interval_node *node;
     6	  ITREE_FOREACH (node, current_buffer->overlays, pos, next, ASCENDING)
     7	    {
     8	      if (node->begin > pos)
     9	        {
    10	          /* If we reach this branch, node->begin must be the least upper bound
    11	             of pos, because the search is limited to [pos,next) . */
    12	          eassert (node->begin < next);
    13	          next = node->begin;
    14	          ITREE_FOREACH_ABORT ();
    15	          break;
    16	        }
    17	      else if (node->begin < node->end && node->end < next)
    18	        {
    19	          next = node->end;
    20	          ITREE_FOREACH_NARROW (pos, next);
    21	        }
    22	    }
    23	  return next;
    24	}

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
positions in the buffer after POS.  It is always going to be possible to
construct pathalogical cases where lines 19-20 are taken for as many
positions as there are in the buffer after POS, since the tree is not
ordered by END.

I've attached a patch that can go in to itree.c (which, if I'm right, I
think would be good to add, especially if we decide to not improve the
data structure).  I've quoted the text:

   ====
   FIXME: this data structure is O(N) for important operations -matt
   ====

   The amortized costs of Emacs' previous-overlay-change and
   next-overlay-change functions are O(N) with this data structure.
   The root problem is that we only have an order for the BEG field,
   but not the END.  The previous/next overlay change operations need
   to find the nearest point where there is *either* an interval BEG
   or END point, but there is no efficient way to narrow the search
   space over END postions.

   Consider the case where next-overlay-change is called at POS, all
   interval BEG positions are less than pos POS and all interval END
   posistions are after.  These END positions have no order, and so
   *every* interval must be examined.  This is at least O(N).  The
   previous-overlay-change case is similar.  The root issue is that
   the iterative "narrowing" approach is not guaranteed to reduce the
   search space in logarithmic time, since END is not ordered in the
   tree.

   One might argue that the LIMIT value will do this narrowing, but
   this narrowing is O(K*log(N)) where K is the size of the result
   set.  If we are interested in finding the node in a range with the
   smallest END, we might have to examine all K nodes in that range.
   In the case of the *-overlay-channge functions, K may well be equal
   to N.

   Ideally, a tree based data structure for overlays would have
   O(log(N)) performance for previous-overlay-change and
   next-overlay-change, as these are called in performance sensitive
   situations such as redisplay.  The only way I can think of
   achieving this is by keeping one ordering by BEG and a separate
   ordering by END, and then performing logic quite similar to the
   current Emacs overlays-before and overlays-after lists.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0005-src-itree.c-Add-comment-describing-when-noverlay-is-.patch --]
[-- Type: text/x-diff, Size: 2596 bytes --]

From 6ca364a6ad45b1cfdcf080c492fde536975f6e09 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Thu, 6 Oct 2022 15:47:20 -0700
Subject: [PATCH 5/5] ; * src/itree.c: Add comment describing when noverlay is
 O(N)

---
 src/itree.c | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)

diff --git a/src/itree.c b/src/itree.c
index 79e39d6e2a..6de84ae0b8 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -62,6 +62,42 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
    complexity of O(K*log(N)) for this operation, where K is the size
    of the result set and N the size of the tree.
 
+   ====
+   FIXME: this data structure is O(N) for important operations -matt
+   ====
+
+   The amortized costs of Emacs' previous-overlay-change and
+   next-overlay-change functions are O(N) with this data structure.
+   The root problem is that we only have an order for the BEG field,
+   but not the END.  The previous/next overlay change operations need
+   to find the nearest point where there is *either* an interval BEG
+   or END point, but there is no efficient way to narrow the search
+   space over END postions.
+
+   Consider the case where next-overlay-change is called at POS, all
+   interval BEG positions are less than pos POS and all interval END
+   posistions are after.  These END positions have no order, and so
+   *every* interval must be examined.  This is at least O(N).  The
+   previous-overlay-change case is similar.  The root issue is that
+   the iterative "narrowing" approach is not guaranteed to reduce the
+   search space in logarithmic time, since END is not ordered in the
+   tree.
+
+   One might argue that the LIMIT value will do this narrowing, but
+   this narrowing is O(K*log(N)) where K is the size of the result
+   set.  If we are interested in finding the node in a range with the
+   smallest END, we might have to examine all K nodes in that range.
+   In the case of the *-overlay-channge functions, K may well be equal
+   to N.
+
+   Ideally, a tree based data structure for overlays would have
+   O(log(N)) performance for previous-overlay-change and
+   next-overlay-change, as these are called in performance sensitive
+   situations such as redisplay.  The only way I can think of
+   achieving this is by keeping one ordering by BEG and a separate
+   ordering by END, and then performing logic quite similar to the
+   current Emacs overlays-before and overlays-after lists.
+
    ==== Adjusting intervals ====
 
    Since this data-structure will be used for overlays in an Emacs
-- 
2.35.1

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

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> 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

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

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: bug-gnu-emacs@gnu.org,  Andreas Politz <mail@andreas-politz.de>,  Gerd
>  Möllmann <gerd.moellmann@gmail.com>,  Eli Zaretskii
>  <eliz@gnu.org>
> Date: Thu, 06 Oct 2022 21:12:26 -0400
> 
> [ 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.

previous-overlay-change is also called by redisplay (but I didn't see
how frequently), at least if you look at the code from the static
analysis POV.

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

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Eli Zaretskii [2022-10-07 10:09:39] wrote:
>> [ 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.
> previous-overlay-change is also called by redisplay (but I didn't see
> how frequently), at least if you look at the code from the static
> analysis POV.

Do you happen to know via which path it can be called (beside the obvious
ones when the redisplay ends up calling ELisp, such as via jit-lock)?


        Stefan

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

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: matt@rfc20.org,  bug-gnu-emacs@gnu.org,  mail@andreas-politz.de,
>   gerd.moellmann@gmail.com
> Date: Fri, 07 Oct 2022 09:36:50 -0400
> 
> Eli Zaretskii [2022-10-07 10:09:39] wrote:
> >> [ 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.
> > previous-overlay-change is also called by redisplay (but I didn't see
> > how frequently), at least if you look at the code from the static
> > analysis POV.
> 
> Do you happen to know via which path it can be called (beside the obvious
> ones when the redisplay ends up calling ELisp, such as via jit-lock)?

 pos_visible_p
  -> previous-single-char-property-change
      -> previous-char-property-change
          -> previous-overlay-change

Also:

 set_point_both
  -> previous-char-property-change
      -> previous-overlay-change

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

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

>> Do you happen to know via which path it can be called (beside the obvious
>> ones when the redisplay ends up calling ELisp, such as via jit-lock)?
>
>  pos_visible_p
>   -> previous-single-char-property-change

Ah, thanks, indeed.  Hadn't noticed this one.

>  set_point_both
>   -> previous-char-property-change
>       -> previous-overlay-change

I knew about this one but AFAIC it doesn't count :-) because it's only
triggered when `inhibit-point-motion-hooks` is nil, and this var has
defaulted to t (and been marked obsolete) since Emacs-25.


        Stefan

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.

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.

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

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

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

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> 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

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

[Matt Armstrong]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

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

First, we need benchmark that demonstrates a problem.  You've asked for
this.

I've simply pointed out that there is no algorithmic protection from bad
performance, but I haven't yet come up with a practical example.

I understand your concerns about the costs of maintaining a separate
tree, but I think this design brainstorm is getting ahead of things.  I
would advocate for such a "dual tree" design only if it made sense on
some demonstrated engineering basis.  Goals are always balancing simple
code, simple design, and efficiency.  Opinions can differ, but they're
difficult to settle out without something concrete to talk about.

Does anybody know of an Emacs package that uses a large number of
overlays that span large amounts of the buffer in complex ways?  If none
exist, maybe we can just close this bug!

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

[Drew Adams]

> Does anybody know of an Emacs package that uses a large number of
> overlays that span large amounts of the buffer in complex ways?

Sure.  zones.el does (especially the version
I use, which I haven't yet exposed externally).

The point of zones.el is to manipulate arbitrary
sets of buffer zones, which can be implemented
as overlays (as one possibility).

They can overlap in any way, as the library is
a utility that you can use in any way.  And you
can sort zones, unite/coalesce them, etc.  It's
not at all unusual to deal with many overlapping
zones, e.g., overlays.

Dunno what the "noverlay" branch is.  I haven't
seen any description of it or its purpose,
despite the many, many emails here and in
emacs-devel with "noverlay" in the Subject line.
As a result, those many messages get only an
uninformed glance from me.

But if the "noverlay" branch is supposed to deal
with overlays _in general_ in some way, then I'd
think that the case of many overlapping overlays
wouldn't necessarily be rare.  Why would it be?

You can use an overlay for anything: store any
information on for buffer zone.  An overlay is
just two buffer positions plus a set of
properties - any properties.  _Super_ general.

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

[Drew Adams]

> > Does anybody know of an Emacs package that uses a large number of
> > overlays that span large amounts of the buffer in complex ways?
> 
> Sure.  zones.el does (especially the version
> I use, which I haven't yet exposed externally).
> 
> The point of zones.el is to manipulate arbitrary
> sets of buffer zones, which can be implemented
> as overlays (as one possibility).
> 
> They can overlap in any way, as the library is
> a utility that you can use in any way.  And you
> can sort zones, unite/coalesce them, etc.  It's
> not at all unusual to deal with many overlapping
> zones, e.g., overlays.
> 
> Dunno what the "noverlay" branch is.  I haven't
> seen any description of it or its purpose,
> despite the many, many emails here and in
> emacs-devel with "noverlay" in the Subject line.
> As a result, those many messages get only an
> uninformed glance from me.
> 
> But if the "noverlay" branch is supposed to deal
> with overlays _in general_ in some way, then I'd
> think that the case of many overlapping overlays
> wouldn't necessarily be rare.  Why would it be?
> 
> You can use an overlay for anything: store any
> information on for buffer zone.  An overlay is
> just two buffer positions plus a set of
> properties - any properties.  _Super_ general.

As an example just one use of arbitrarily
positioned overlays, you can save narrowings
to a set of zones (which can be overlays), and
later reactivate any of them on demand.

Narrowings can have any limits, of course.  The
overlays in a zones set can overlap in arbitrary
ways, like Venn diagrams.

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

[Dmitry Gutov]

On 07.10.2022 23:37, Matt Armstrong wrote:
> Does anybody know of an Emacs package that uses a large number of
> overlays that span large amounts of the buffer in complex ways?  If none
> exist, maybe we can just close this bug!

mmm-mode, perhaps.

But that depends on what you mean by "large" and "complex". The overlay 
nesting scheme is usually straightforward.

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

[Eli Zaretskii]

> From: Matt Armstrong <matt@rfc20.org>
> Cc: bug-gnu-emacs@gnu.org, Andreas Politz <mail@andreas-politz.de>, Gerd
>  Möllmann <gerd.moellmann@gmail.com>, Eli Zaretskii
>  <eliz@gnu.org>
> Date: Fri, 07 Oct 2022 13:37:31 -0700
> 
> Does anybody know of an Emacs package that uses a large number of
> overlays that span large amounts of the buffer in complex ways?

What are those "complex ways" you are talking about?

In general, Isearch can potentially produce thousands of overlays,
especially if you do that in a buffer where lines are truncated.  But
I don't know if that's what you are looking for.

linum.el is another potential example: it produces an overlay for each
line.

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

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

>> Does anybody know of an Emacs package that uses a large number of
>> overlays that span large amounts of the buffer in complex ways?
>
> What are those "complex ways" you are talking about?
>
> In general, Isearch can potentially produce thousands of overlays,
> especially if you do that in a buffer where lines are truncated.  But
> I don't know if that's what you are looking for.
>
> linum.el is another potential example: it produces an overlay for each
> line.

For the potential performance problem with next-overlay-change to appear
you need overlays to overlap, so not something like linum or nhexl-mode.
Maybe a package which places an overlay over every pair of matched
parentheses in a Lisp buffer?


        Stefan

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

[Drew Adams]

> For the potential performance problem with next-overlay-change to appear
> you need overlays to overlap, so not something like linum or nhexl-mode.

Which is why I mentioned zones.el.

And I don't expect it to be alone in this.
Overlays can be anywhere.

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

[Matt Armstrong]

Drew Adams <drew.adams@oracle.com> writes:

>> For the potential performance problem with next-overlay-change to appear
>> you need overlays to overlap, so not something like linum or nhexl-mode.
>
> Which is why I mentioned zones.el.
>
> And I don't expect it to be alone in this.
> Overlays can be anywhere.

For what it is worth, the use cases where this bug applies are likely to
be noticeably slow in Emacs today as well.