[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Overlays as an AA-tree
From: |
Andreas Politz |
Subject: |
Re: Overlays as an AA-tree |
Date: |
Fri, 24 Feb 2017 09:43:16 +0100 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (gnu/linux) |
Stefan Monnier <address@hidden> 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
- Re: Overlays as an AA-tree, (continued)
- Re: Overlays as an AA-tree, Eli Zaretskii, 2017/02/20
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/21
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/21
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/21
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/21
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/21
- Re: Overlays as an AA-tree,
Andreas Politz <=
- Re: Overlays as an AA-tree, Richard Stallman, 2017/02/13
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/14
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/06
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/06
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/06
- Re: Overlays as an AA-tree, Joakim Jalap, 2017/02/06
- Re: Overlays as an AA-tree, Clément Pit-Claudel, 2017/02/06
Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/03