Re: Overlay mechanic improvements

[Stefan Monnier]

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

We could try, but it wouldn't address the last problem above.

> A large number of markers will cause the same slowdown even if they
> are not made for overlays.

Indeed.  But I've never seen this problem, except via the creation of
many overlays.

Note that if/when overlays are made efficient and markers's efficiency
becomes a problem, we can use the new overlay implementation for markers
(in the worst case, representing markers as degenerate overlays).

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

I must say I'm troubled by your questions and objections.  What is the
problem with my proposal?  Are you afraid it will make Emacs worse?
Or are you afraid it simply won't work?  Why do you care if we keep
overlays in a tree instead of singly-linked lists?


        Stefan