all messages for Emacs-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
From: Stefan Monnier <monnier@iro.umontreal.ca>
To: Dmitry Antipov <dmantipov@yandex.ru>
Cc: Eli Zaretskii <eliz@gnu.org>, emacs-devel@gnu.org
Subject: Re: Markers/intervals/overlays + trees
Date: Thu, 09 Aug 2012 13:16:19 -0400	[thread overview]
Message-ID: <jwvy5low80n.fsf-monnier+emacs@gnu.org> (raw)
In-Reply-To: <5023344C.6020603@yandex.ru> (Dmitry Antipov's message of "Thu, 09 Aug 2012 07:53:48 +0400")

> 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



      parent reply	other threads:[~2012-08-09 17:16 UTC|newest]

Thread overview: 9+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
     [not found] <E1Sz80a-0000RM-Qp@vcs.savannah.gnu.org>
2012-08-08 15:45 ` [Emacs-diffs] /srv/bzr/emacs/trunk r109512: Inline functions to examine and change buffer overlays Stefan Monnier
2012-08-08 16:26   ` Dmitry Antipov
2012-08-08 18:05     ` Stefan Monnier
2012-08-08 18:16       ` Eli Zaretskii
2012-08-08 19:47         ` Stefan Monnier
2012-08-08 20:44           ` Eli Zaretskii
2012-08-09  3:53             ` Markers/intervals/overlays + trees Dmitry Antipov
2012-08-09 16:15               ` Eli Zaretskii
2012-08-09 17:16               ` Stefan Monnier [this message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=jwvy5low80n.fsf-monnier+emacs@gnu.org \
    --to=monnier@iro.umontreal.ca \
    --cc=dmantipov@yandex.ru \
    --cc=eliz@gnu.org \
    --cc=emacs-devel@gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this external index

	https://git.savannah.gnu.org/cgit/emacs.git
	https://git.savannah.gnu.org/cgit/emacs/org-mode.git

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.