all messages for Emacs-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
* bug#58342: 29.0.50; noverlay branch is O(N) for important calls
@ 2022-10-06 23:25 Matt Armstrong
  2022-10-07  1:12 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
  0 siblings, 1 reply; 18+ messages in thread
From: Matt Armstrong @ 2022-10-06 23:25 UTC (permalink / raw)
  To: 58342; +Cc: Gerd Möllmann, Eli Zaretskii, Andreas Politz, Stefan Monnier

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


^ permalink raw reply related	[flat|nested] 18+ messages in thread

* bug#58342: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-06 23:25 bug#58342: 29.0.50; noverlay branch is O(N) for important calls Matt Armstrong
@ 2022-10-07  1:12 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
  2022-10-07  7:09   ` Eli Zaretskii
  2022-10-07 15:23   ` Matt Armstrong
  0 siblings, 2 replies; 18+ messages in thread
From: Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors @ 2022-10-07  1:12 UTC (permalink / raw)
  To: Matt Armstrong; +Cc: gerd.moellmann, 58342, mail, eliz

> 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






^ permalink raw reply	[flat|nested] 18+ messages in thread

* bug#58342: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-07  1:12 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
@ 2022-10-07  7:09   ` Eli Zaretskii
  2022-10-07 13:36     ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
  2022-10-07 15:23   ` Matt Armstrong
  1 sibling, 1 reply; 18+ messages in thread
From: Eli Zaretskii @ 2022-10-07  7:09 UTC (permalink / raw)
  To: Stefan Monnier; +Cc: gerd.moellmann, matt, 58342, mail

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





^ permalink raw reply	[flat|nested] 18+ messages in thread

* bug#58342: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-07  7:09   ` Eli Zaretskii
@ 2022-10-07 13:36     ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
  2022-10-07 13:57       ` Eli Zaretskii
  0 siblings, 1 reply; 18+ messages in thread
From: Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors @ 2022-10-07 13:36 UTC (permalink / raw)
  To: Eli Zaretskii; +Cc: gerd.moellmann, matt, 58342, mail

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






^ permalink raw reply	[flat|nested] 18+ messages in thread

* bug#58342: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-07 13:36     ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
@ 2022-10-07 13:57       ` Eli Zaretskii
  2022-10-07 14:47         ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
  0 siblings, 1 reply; 18+ messages in thread
From: Eli Zaretskii @ 2022-10-07 13:57 UTC (permalink / raw)
  To: Stefan Monnier; +Cc: gerd.moellmann, matt, 58342, mail

> 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





^ permalink raw reply	[flat|nested] 18+ messages in thread

* bug#58342: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-07 13:57       ` Eli Zaretskii
@ 2022-10-07 14:47         ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
  0 siblings, 0 replies; 18+ messages in thread
From: Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors @ 2022-10-07 14:47 UTC (permalink / raw)
  To: Eli Zaretskii; +Cc: gerd.moellmann, matt, 58342, mail

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






^ permalink raw reply	[flat|nested] 18+ messages in thread

* bug#58342: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-07  1:12 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
  2022-10-07  7:09   ` Eli Zaretskii
@ 2022-10-07 15:23   ` Matt Armstrong
  2022-10-07 16:51     ` bug#58361: " Andreas Politz
  2022-10-07 17:11     ` bug#58342: " Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
  1 sibling, 2 replies; 18+ messages in thread
From: Matt Armstrong @ 2022-10-07 15:23 UTC (permalink / raw)
  To: Stefan Monnier; +Cc: gerd.moellmann, 58342, mail, eliz

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.





^ permalink raw reply	[flat|nested] 18+ messages in thread

* bug#58361: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-07 15:23   ` Matt Armstrong
@ 2022-10-07 16:51     ` Andreas Politz
  2022-10-07 18:38       ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
  2022-10-07 17:11     ` bug#58342: " Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
  1 sibling, 1 reply; 18+ messages in thread
From: Andreas Politz @ 2022-10-07 16:51 UTC (permalink / raw)
  To: Matt Armstrong; +Cc: gerd.moellmann, 58361, eliz, monnier

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.






^ permalink raw reply	[flat|nested] 18+ messages in thread

* bug#58342: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-07 15:23   ` Matt Armstrong
  2022-10-07 16:51     ` bug#58361: " Andreas Politz
@ 2022-10-07 17:11     ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
  2022-10-07 20:37       ` Matt Armstrong
  1 sibling, 1 reply; 18+ messages in thread
From: Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors @ 2022-10-07 17:11 UTC (permalink / raw)
  To: Matt Armstrong; +Cc: gerd.moellmann, 58342, mail, eliz

> 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






^ permalink raw reply	[flat|nested] 18+ messages in thread

* bug#58361: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-07 16:51     ` bug#58361: " Andreas Politz
@ 2022-10-07 18:38       ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
  0 siblings, 0 replies; 18+ messages in thread
From: Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors @ 2022-10-07 18:38 UTC (permalink / raw)
  To: Andreas Politz; +Cc: gerd.moellmann, matt, 58361, eliz

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






^ permalink raw reply	[flat|nested] 18+ messages in thread

* bug#58342: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-07 17:11     ` bug#58342: " Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
@ 2022-10-07 20:37       ` Matt Armstrong
  2022-10-07 21:22         ` Drew Adams
                           ` (2 more replies)
  0 siblings, 3 replies; 18+ messages in thread
From: Matt Armstrong @ 2022-10-07 20:37 UTC (permalink / raw)
  To: Stefan Monnier; +Cc: gerd.moellmann, 58342, mail, eliz

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!





^ permalink raw reply	[flat|nested] 18+ messages in thread

* bug#58342: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-07 20:37       ` Matt Armstrong
@ 2022-10-07 21:22         ` Drew Adams
  2022-10-08  0:27           ` Drew Adams
  2022-10-07 21:58         ` Dmitry Gutov
  2022-10-08  6:20         ` Eli Zaretskii
  2 siblings, 1 reply; 18+ messages in thread
From: Drew Adams @ 2022-10-07 21:22 UTC (permalink / raw)
  To: Matt Armstrong, Stefan Monnier
  Cc: gerd.moellmann@gmail.com, eliz@gnu.org, mail@andreas-politz.de,
	58342@debbugs.gnu.org

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






^ permalink raw reply	[flat|nested] 18+ messages in thread

* bug#58342: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-07 20:37       ` Matt Armstrong
  2022-10-07 21:22         ` Drew Adams
@ 2022-10-07 21:58         ` Dmitry Gutov
  2022-10-08  6:20         ` Eli Zaretskii
  2 siblings, 0 replies; 18+ messages in thread
From: Dmitry Gutov @ 2022-10-07 21:58 UTC (permalink / raw)
  To: Matt Armstrong, Stefan Monnier; +Cc: gerd.moellmann, eliz, mail, 58342

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.





^ permalink raw reply	[flat|nested] 18+ messages in thread

* bug#58342: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-07 21:22         ` Drew Adams
@ 2022-10-08  0:27           ` Drew Adams
  0 siblings, 0 replies; 18+ messages in thread
From: Drew Adams @ 2022-10-08  0:27 UTC (permalink / raw)
  To: Drew Adams, Matt Armstrong, Stefan Monnier
  Cc: gerd.moellmann@gmail.com, eliz@gnu.org, mail@andreas-politz.de,
	58342@debbugs.gnu.org

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






^ permalink raw reply	[flat|nested] 18+ messages in thread

* bug#58342: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-07 20:37       ` Matt Armstrong
  2022-10-07 21:22         ` Drew Adams
  2022-10-07 21:58         ` Dmitry Gutov
@ 2022-10-08  6:20         ` Eli Zaretskii
  2022-10-08 13:08           ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
  2 siblings, 1 reply; 18+ messages in thread
From: Eli Zaretskii @ 2022-10-08  6:20 UTC (permalink / raw)
  To: Matt Armstrong; +Cc: gerd.moellmann, 58342, mail, monnier

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





^ permalink raw reply	[flat|nested] 18+ messages in thread

* bug#58342: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-08  6:20         ` Eli Zaretskii
@ 2022-10-08 13:08           ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
  2022-10-08 17:24             ` Drew Adams
  0 siblings, 1 reply; 18+ messages in thread
From: Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors @ 2022-10-08 13:08 UTC (permalink / raw)
  To: Eli Zaretskii; +Cc: gerd.moellmann, matt, 58342, mail

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






^ permalink raw reply	[flat|nested] 18+ messages in thread

* bug#58342: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-08 13:08           ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
@ 2022-10-08 17:24             ` Drew Adams
  2022-10-08 23:08               ` Matt Armstrong
  0 siblings, 1 reply; 18+ messages in thread
From: Drew Adams @ 2022-10-08 17:24 UTC (permalink / raw)
  To: Stefan Monnier, Eli Zaretskii
  Cc: gerd.moellmann@gmail.com, matt@rfc20.org, mail@andreas-politz.de,
	58342@debbugs.gnu.org

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





^ permalink raw reply	[flat|nested] 18+ messages in thread

* bug#58342: 29.0.50; noverlay branch is O(N) for important calls
  2022-10-08 17:24             ` Drew Adams
@ 2022-10-08 23:08               ` Matt Armstrong
  0 siblings, 0 replies; 18+ messages in thread
From: Matt Armstrong @ 2022-10-08 23:08 UTC (permalink / raw)
  To: Drew Adams, Stefan Monnier, Eli Zaretskii
  Cc: gerd.moellmann@gmail.com, mail@andreas-politz.de,
	58342@debbugs.gnu.org

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.





^ permalink raw reply	[flat|nested] 18+ messages in thread

end of thread, other threads:[~2022-10-08 23:08 UTC | newest]

Thread overview: 18+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2022-10-06 23:25 bug#58342: 29.0.50; noverlay branch is O(N) for important calls Matt Armstrong
2022-10-07  1:12 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-07  7:09   ` Eli Zaretskii
2022-10-07 13:36     ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-07 13:57       ` Eli Zaretskii
2022-10-07 14:47         ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-07 15:23   ` Matt Armstrong
2022-10-07 16:51     ` bug#58361: " Andreas Politz
2022-10-07 18:38       ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-07 17:11     ` bug#58342: " Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-07 20:37       ` Matt Armstrong
2022-10-07 21:22         ` Drew Adams
2022-10-08  0:27           ` Drew Adams
2022-10-07 21:58         ` Dmitry Gutov
2022-10-08  6:20         ` Eli Zaretskii
2022-10-08 13:08           ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-08 17:24             ` Drew Adams
2022-10-08 23:08               ` Matt Armstrong

Code repositories for project(s) associated with this external index

	https://git.savannah.gnu.org/cgit/emacs.git
	https://git.savannah.gnu.org/cgit/emacs/org-mode.git

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.