Re: Overlays as an AA-tree

[Andreas Politz <politza@hochschule-trier.de>]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> Is there a reason why "struct Lisp_Overlay" and "struct interval_node"
> are separate?

The main reason is that it can't be used for anything else, once the
nodes are all Lisp_Overlay's .  There are at least two other balanced
trees in Emacs and maybe, at some time, there should be only one. (Also,
initially I didn't need to worry about the Emacs side.)

> [...] That means an overlay takes up about twice the size of a marker.
>
> Should we then (re)implement markers as degenerate overlays?  [it's not
> as simple as it sounds: contrary to overlays markers can be GC'd if not
> referenced, so we'd need to add support for "weakly referenced
> overlays".  Furthermore markers are used to speed up byte<->char
> conversions, so we'd need to replace that code accordingly.  ]

Could we use the end attribute as byte value ?  Also, does Emacs create
extra markers for this lookup or can this be called a "opportunistic
optimization" ?

I did some comparisons between marker and empty overlays regarding
insertions and deletions.  *-before and *-after insert/delete at
point-min resp. -max, scatter means randomly.  In each case 4096
single character were inserted/deleted.

===============================================
                     32K               64K
                 ------------     -------------
4096 edits        ma    ov         ma     ov
-----------------------------------------------
insert-before    4.20  0.22       16.66  0.44

insert-after     3.28  0.12       12.96  0.20

insert-scatter   4.84  0.21       18.74  0.37

delete-before    4.09  60.32      16.16  277.75

delete-after     3.75  35.49      14.74  160.91

delete-scatter   4.02  0.36       15.64  0.86
===============================================

As you can see the delete-before/after cases are still somewhat
problematic.  Maybe we should think about using a single node per
position combined with a list.  What do you think ?

-ap