Re: Overlay mechanic improvements

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

    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.

Yes, that's true.

    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.

Why not do it for all markers, then?  A large number of markers will
cause the same slowdown even if they are not made for overlays.

    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.

I don't think the data structure of intervals lends itself directly to
markers.  A marker, whether it's on its own or an end of an overlay,
has an identity that is permanent, whereas intervals are split and
recombined whenever useful.

-- 
Dr Richard Stallman
President, Free Software Foundation
51 Franklin St
Boston MA 02110
USA
www.fsf.org  www.gnu.org
Skype: No way! That's nonfree (freedom-denying) software.
  Use Ekiga or an ordinary phone call.