Re: Overlay mechanic improvements

[Stefan Monnier]

> After answering my question Stefan (Monnier?) mentioned that overlay
> behavior can be fixed from N^2 to N*logN, which would make them
> asymptotically equivalent to text properties; adding that he has no time to
> implement the fix.

So, here's the idea:

Currently overlays are implemented as (two) sorted singly linked lists (one
for overlays_before some position and one for overlay_after that
position, for some quirky definition of "before" and "after").
The function `overlay-recenter' changes the position used for the split
(and is called internally in various situations).

Each overlay is itself implemented with two markers (which keep track of
the overlay-start and overlay-end).  Markers are implemented as
a non-sorted singly linked list of markers.  So every text
insertion/deletion requires O(N) time, where N is the number of markers
since we have to go down that list to update those markers that are
affected by the modification.

You can start in src/buffer.[ch], maybe grepping for overlays_before for
a starting point.

Text-properties, OTOH, are implemented with a (mostly) balanced binary
tree.  This is implemented in src/intervals.[ch].

So we'd like to change overlays so that they don't use markers (and we
don't keep them in two sorted singly-linked lists) any more.  Instead,
we'll store them inside the balanced binary tree used for
text-properties.  I think we can use the "augmented tree" approach
described in https://en.wikipedia.org/wiki/Interval_tree.

To ease up debugging during development, I'd guess the implementation
would first add the new stuff, keeping the old stuff (i.e. add to
Lisp_Overlay whichever fields are needed for the new code, while keeping
the old ones, add needed overlay fields to the intervals tree, but keep
the old fields, the overlays_before etc...).  This way, you can add
consistency checks that make sure the new code computes the same results
as the old code.  And once that works well, we can remove the old code
and old fields.

So I suggest you start looking at src/buffer.[ch] and
src/intervals.[ch].  That should make you ask many more questions.


        Stefan