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

[Matt Armstrong <matt@rfc20.org>]

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!