From: Richard Stallman <rms@gnu.org>
To: Stefan Monnier <monnier@iro.umontreal.ca>
Cc: dak@gnu.org, emacs-devel@gnu.org
Subject: Re: Overlay mechanic improvements
Date: Sun, 21 Sep 2014 17:48:15 -0400 [thread overview]
Message-ID: <E1XVozP-0003WP-UF@fencepost.gnu.org> (raw)
In-Reply-To: <jwv8uld0y7f.fsf-monnier+emacs@gnu.org> (message from Stefan Monnier on Sun, 21 Sep 2014 12:07:48 -0400)
[[[ To any NSA and FBI agents reading my email: please consider ]]]
[[[ whether defending the US Constitution against all enemies, ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]
Reasons for overlays being slow are:
- if you have N overlays, you have 2N markers, so every
insertion/deletion of text will involve a traversal of those 2N elements.
- when we need to move from bytepos to charpos (or vice versa), we go
through the 2N markers again.
- when the Elisp code didn't know to overlay-recenter, or when overlays
are added/removed from the "wrong" place (w.r.t to the overlay
"center"), every overlay creation/removal takes O(N) time.
Yes, that's true.
Moving overlays into a balanced binary tree will remove those
algorithmic performance problems. I'm not sue why you'd be opposed,
since it will provide the exact same functionality anyway. It's just an
internal detail of implementation.
Why not do it for all markers, then? A large number of markers will
cause the same slowdown even if they are not made for overlays.
Note that I suggest to use the balanced binary tree used by
text-properties, but there is no need for the two trees to be linked.
I don't think the data structure of intervals lends itself directly to
markers. A marker, whether it's on its own or an end of an overlay,
has an identity that is permanent, whereas intervals are split and
recombined whenever useful.
--
Dr Richard Stallman
President, Free Software Foundation
51 Franklin St
Boston MA 02110
USA
www.fsf.org www.gnu.org
Skype: No way! That's nonfree (freedom-denying) software.
Use Ekiga or an ordinary phone call.
next prev parent reply other threads:[~2014-09-21 21:48 UTC|newest]
Thread overview: 72+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-09-19 14:59 Overlay mechanic improvements Vladimir Kazanov
2014-09-19 17:22 ` Stefan Monnier
2014-09-20 13:19 ` Richard Stallman
2014-09-20 13:37 ` David Kastrup
2014-09-21 13:35 ` Richard Stallman
2014-09-21 13:52 ` David Kastrup
2014-09-21 21:48 ` Richard Stallman
2014-09-21 22:06 ` David Kastrup
2014-09-22 23:11 ` Richard Stallman
2014-09-22 23:50 ` David Kastrup
2014-09-23 19:15 ` Richard Stallman
2014-09-21 16:07 ` Stefan Monnier
2014-09-21 16:14 ` David Kastrup
2014-09-21 21:48 ` Richard Stallman
2014-09-21 22:19 ` David Kastrup
2014-09-23 19:16 ` Richard Stallman
2014-09-23 19:27 ` David Kastrup
2014-09-28 23:24 ` Richard Stallman
2014-09-29 5:45 ` David Kastrup
2014-09-29 20:48 ` Richard Stallman
2014-09-30 1:21 ` Stephen J. Turnbull
2014-09-30 8:43 ` David Kastrup
2014-09-30 10:35 ` Rasmus
2014-09-30 14:22 ` Eli Zaretskii
2014-09-30 16:20 ` David Kastrup
2014-09-30 16:35 ` Eli Zaretskii
2014-09-30 14:32 ` Stefan Monnier
2014-10-02 16:12 ` Uwe Brauer
2014-09-30 19:23 ` Richard Stallman
2014-10-01 3:38 ` Stephen J. Turnbull
2014-10-01 12:53 ` Richard Stallman
2014-10-01 13:11 ` David Kastrup
2014-10-02 1:26 ` Stephen J. Turnbull
2014-09-30 5:52 ` David Kastrup
2014-10-06 19:14 ` Richard Stallman
2014-10-06 21:02 ` David Kastrup
2014-09-21 16:56 ` Eli Zaretskii
2014-09-21 18:42 ` Stefan Monnier
2014-09-21 18:58 ` Eli Zaretskii
2014-09-21 20:12 ` Stefan Monnier
2014-09-21 21:48 ` Richard Stallman [this message]
2014-09-22 0:31 ` Stefan Monnier
2014-09-22 23:11 ` Richard Stallman
2014-09-20 15:56 ` Eli Zaretskii
2014-09-20 19:49 ` Stefan Monnier
2014-09-21 13:36 ` Richard Stallman
2014-09-19 18:03 ` Richard Stallman
2014-09-20 8:08 ` Vladimir Kazanov
2014-09-20 13:21 ` Richard Stallman
2014-09-20 16:28 ` Stephen Leake
2014-09-20 13:21 ` Tokenizing Richard Stallman
2014-09-20 16:24 ` Tokenizing Stephen Leake
2014-09-20 16:40 ` Tokenizing Vladimir Kazanov
2014-09-20 20:16 ` Tokenizing Eric Ludlam
2014-09-20 20:35 ` Tokenizing Vladimir Kazanov
2014-09-21 15:13 ` parsing (was tokenizing) Stephen Leake
2014-09-20 16:36 ` Tokenizing Vladimir Kazanov
2014-09-20 19:55 ` Tokenizing Stefan Monnier
2014-09-21 15:35 ` Tokenizing Stephen Leake
2014-09-21 16:43 ` Tokenizing Stefan Monnier
2014-09-22 14:05 ` Tokenizing Stephen Leake
2014-09-21 13:35 ` Tokenizing Richard Stallman
2014-09-21 14:24 ` Tokenizing Vladimir Kazanov
2014-09-21 15:32 ` Tokenizing Stephen Leake
2014-09-21 16:42 ` Tokenizing Stefan Monnier
2014-09-21 18:55 ` Tokenizing Vladimir Kazanov
2014-09-21 22:01 ` Tokenizing Daniel Colascione
2014-09-22 10:21 ` Tokenizing Vladimir Kazanov
2014-09-22 13:55 ` Tokenizing Daniel Colascione
2014-09-22 14:02 ` Tokenizing Stephen Leake
2014-09-22 14:14 ` Tokenizing Daniel Colascione
2014-09-22 13:15 ` Tokenizing Stephen Leake
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=E1XVozP-0003WP-UF@fencepost.gnu.org \
--to=rms@gnu.org \
--cc=dak@gnu.org \
--cc=emacs-devel@gnu.org \
--cc=monnier@iro.umontreal.ca \
/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.