Re: Overlay mechanic improvements

[Stefan Monnier]

> The existing code should be fat if you recenter the overlays
> frequently at point, unless you have lots of overlays on one screen.
> Do you recenter them?  If so, why is it slow?

Reasons for overlays being slow are:
- if you have N overlays, you have 2N markers, so every
  insertion/deletion of text will involve a traversal of those 2N elements.
- when we need to move from bytepos to charpos (or vice versa), we go
  through the 2N markers again.
- when the Elisp code didn't know to overlay-recenter, or when overlays
  are added/removed from the "wrong" place (w.r.t to the overlay
  "center"), every overlay creation/removal takes O(N) time.

We rarely suffer from overlay's performance issues because most codes
that could suffer from it simply avoid using overlays (or they try to
minimize the number of overlays used, e.g. by flushing those overlays
currently not visible), even when they would be the right tool.  Or they
add calls to overlay-recenter when the performance problem is diagnosed.

Moving overlays into a balanced binary tree will remove those
algorithmic performance problems.  I'm not sue why you'd be opposed,
since it will provide the exact same functionality anyway.  It's just an
internal detail of implementation.

Note that I suggest to use the balanced binary tree used by
text-properties, but there is no need for the two trees to be linked.
We could as well use a separate tree for overlays.  I'm not sure which
of the two options is best in this regard, but at least I don't see any
obvious reason why re-using the existing intervals.c tree wouldn't
work well.

Of course, I don't know for a fact that the end result will be better
than what we currently have.  We will of course need to experiment with
it a bit.

> Why aren't text properties right for this?

There are various things which are difficult to do with text-properties.
E.g. the lack of after/before_string is the most obvious difference.


        Stefan