[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Markers/intervals/overlays + trees
From: |
Stefan Monnier |
Subject: |
Re: Markers/intervals/overlays + trees |
Date: |
Thu, 09 Aug 2012 13:16:19 -0400 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/24.1.50 (gnu/linux) |
> The more I do different things around buffers and
> markers/intervals/overlays, the more I think that the last three ones
> represents nearly the same thing, i.e. "buffer range with properties"
> (marker is the range of length 0 (or 1, that's may be the question),
Definitely 0.
> and without properties). Is it reasonable/ possible/feasible to
> generalize them into the only type and use it everywhere?
As mentioned elsewhere, we could/should move overlays to the tree
currently used for text-properties (using the "augmented tree" approach
described in http://en.wikipedia.org/wiki/Interval_tree, and using the
"interval tree" of text-properties as the simple underlying balanced
binary tree).
This wouldn't quite merge text-properties and overlays (the two concepts
are subtly different), but it would bring the implementation of the two
closer and should make overlays a lot more scalable/efficient.
I suspect that once this is done, markers wouldn't matter much any more
(because overlays wouldn't use them internally), so we could keep the
current implementation or turn them into "degenerate overlays".
> If not, shouldn't markers and overlays be chained into double-linked
> lists instead of single-linked, for the sake of fast unchain/re-chain
> and in-place sort?
Not sure it's worth the trouble:
- doubly-linked lists wouldn't speed up chaining.
- while unchaining would be faster, this is normally not a common
operation (hopefully most markers should be unchained lazily in batch
by the GC, which can do it efficiently).
Of course, this is only true of real markers, not of overlay's markers
since these aren't implicitly reclaimed by the GC.
- sorting would slow down insertion and would only speed up other
operations by a factor 2 (you only need to traverse half the list on
average). When the list is long enough to be a problem, a factor 2 is
not sufficient, we need algorithmic improvement.
> Finally, what about an idea to generalize red-black tree from alloc.c
> and use it everywhere when O(log(n)) data structure is needed?
> I suppose that we can even avoid our own tree implementation while
> compiling for GNU/Linux because glibc trees (tsearch/tfind/etc.) are
> balanced and good enough in general.
If we have to provide our own implementation in some cases, then we may
as well use it everywhere. OTOH we could maybe use Glib's trees.
It would probably be fairly easy to do for alloc.c's redblack trees, but
changing text-properties's intervals trees to some "standard" balanced
tree library would probably take more work.
Also it would be less efficient since every node would be split into the
"tree node" and the "value node".
Stefan
- Re: [Emacs-diffs] /srv/bzr/emacs/trunk r109512: Inline functions to examine and change buffer overlays., Stefan Monnier, 2012/08/08
- Re: [Emacs-diffs] /srv/bzr/emacs/trunk r109512: Inline functions to examine and change buffer overlays., Dmitry Antipov, 2012/08/08
- Re: [Emacs-diffs] /srv/bzr/emacs/trunk r109512: Inline functions to examine and change buffer overlays., Stefan Monnier, 2012/08/08
- Re: [Emacs-diffs] /srv/bzr/emacs/trunk r109512: Inline functions to examine and change buffer overlays., Eli Zaretskii, 2012/08/08
- Re: [Emacs-diffs] /srv/bzr/emacs/trunk r109512: Inline functions to examine and change buffer overlays., Stefan Monnier, 2012/08/08
- Re: [Emacs-diffs] /srv/bzr/emacs/trunk r109512: Inline functions to examine and change buffer overlays., Eli Zaretskii, 2012/08/08
- Markers/intervals/overlays + trees, Dmitry Antipov, 2012/08/08
- Re: Markers/intervals/overlays + trees, Eli Zaretskii, 2012/08/09
- Re: Markers/intervals/overlays + trees,
Stefan Monnier <=