From: Thomas Lord <lord@emf.net>
To: "Stephen J. Turnbull" <stephen@xemacs.org>
Cc: Stefan Monnier <monnier@iro.umontreal.ca>,
rms@gnu.org, emacs-devel@gnu.org
Subject: Re: Release plans
Date: Tue, 02 Sep 2008 13:43:24 -0700 [thread overview]
Message-ID: <48BDA56C.10502@emf.net> (raw)
In-Reply-To: <87ljybp6t1.fsf@uwakimon.sk.tsukuba.ac.jp>
Stephen J. Turnbull wrote:
> Thomas Lord writes:
>
> > of markers, but because this will be a self-adjusting tree
> > all those operations will be O(1) in the expected case where
> > changes display pretty good locality.
>
> I would advise you not to expect that case.
That's two of you now (saying that). Ok, then, I'll assume the
worst (which should still be "good enough").
> Experience in XEmacs
> shows that some applications (the VM MUA in particular, but also the
> old implementation of font-lock, dunno about jit-lock) like to run up
> and down the buffer a lot. AFAICS it's really important to have O(log
> N) worst-case behavior.
>
> Sorry I can't be much more precise about why this happens, I just know
> that our algorithms that deal with extents (which we use to support
> overlay-like behavior and text properties) are tuned for good locality
> and lose badly in large buffers; they show up as time hogs in profiling.
>
>
I looked at (an old version of?) the XEmacs internals manual.
It says extents are implemented as a pair of gap buffers. It also talks
about the concept of cached stacks of events -- e.g., a cache
of the list of extents at a given point from which the extents over
a nearby point can be quickly computed.
I don't know if that's current.
The gap buffer and extent-stack cache would fit your
description of "optimized for locality" and would exhibit
the (performance) failure mode you describe under
access patterns about like you describe ("[running] up and down
the buffer"). In that access pattern, you're frequently
moving lots of data across the gap and if you're jumping around
at all during this traversal then you're constantly getting
cache misses or unwanted cache hits for the extent stack.
The splay tree of gap buffers should do considerably better
with those access patterns. That's the theory, anyway:
The new data structure has an operation equivalent
to "move the gap" (so, e.g., insertions just write to
a linear piece of memory) however gap motion
is O(log N) buffer size in terms of operations and
O(1) for the amount of text that has to move. Marker
updates, getting the position of a marker, and getting
back a list of text properties over a given point are all
O(log N) -- O(1) with good locality.
When I say "locality" I'm using that more loosely than
it is used when talking about ordinary gap buffers.
With ordinary gap buffers, the optimized case is a
lot of action near one point at a buffer, then an
infrequent motion far away, then lots of closely
placed action. When I say "locality" I mean to
include (a) cases where the action at a given time
forms a dense set, even if that set is scattered; (b)
linear access patterns. By "dense set" I mean that
programs can be simultaneously modifying, say,
5 widely separated areas of the buffer in a multiplexed
way -- every modification is probably close to a recent
modification (so the set is dense) but every modification
is also probably far from the *most* recent modification
(so the set is scattered). By "linear access" I mean cases
where code is scanning forwards or backwards.
> It's possible it's something internal to the implementation of
> extents, too, but I think a word to the wise is appropriate here.
>
If extents are still the double gap buffer + extent stack
cache then I can see where you'd have problems like those
you describe. In theory, this new thing does better in
those cases.
Thanks,
-t
next prev parent reply other threads:[~2008-09-02 20:43 UTC|newest]
Thread overview: 338+ messages / expand[flat|nested] mbox.gz Atom feed top
2008-08-12 14:34 Release plans A Soare
2008-08-12 14:52 ` Lennart Borgman (gmail)
2008-08-12 17:14 ` Alan Mackenzie
2008-08-13 6:26 ` Richard M. Stallman
2008-08-13 9:20 ` Alan Mackenzie
2008-08-14 5:19 ` Richard M. Stallman
2008-08-14 8:38 ` Alan Mackenzie
2008-08-14 9:33 ` Johannes Weiner
2008-08-14 9:49 ` Alfred M. Szmidt
2008-08-14 10:04 ` Johannes Weiner
2008-08-14 10:30 ` Alan Mackenzie
2008-08-14 11:07 ` Johannes Weiner
2008-08-14 11:44 ` Tassilo Horn
2008-08-14 12:27 ` Johannes Weiner
2008-08-15 12:45 ` Richard M. Stallman
2008-08-14 12:39 ` Alan Mackenzie
2008-08-14 13:15 ` Johannes Weiner
2008-08-14 13:28 ` Alan Mackenzie
2008-08-14 13:41 ` Johannes Weiner
2008-08-14 17:08 ` Stephen J. Turnbull
2008-08-14 14:30 ` Gilaras Drakeson
2008-08-14 18:00 ` Stephen J. Turnbull
2008-08-15 12:45 ` Richard M. Stallman
2008-08-15 14:18 ` Alan Mackenzie
2008-08-15 17:54 ` Stephen J. Turnbull
2008-08-15 12:45 ` Richard M. Stallman
2008-08-15 16:29 ` Johannes Weiner
2008-08-16 10:40 ` Richard M. Stallman
2008-08-14 10:37 ` Alfred M. Szmidt
2008-08-14 11:24 ` Johannes Weiner
2008-08-14 12:54 ` Alfred M. Szmidt
2008-08-14 13:31 ` Johannes Weiner
2008-08-14 14:02 ` Alfred M. Szmidt
2008-08-14 16:55 ` Stephen J. Turnbull
2008-08-15 12:45 ` Richard M. Stallman
2008-08-16 1:41 ` Lennart Borgman (gmail)
2008-08-17 7:16 ` Richard M. Stallman
2008-08-15 3:41 ` Richard M. Stallman
2008-08-15 4:04 ` Sean O'Rourke
2008-08-15 20:12 ` Michael Ekstrand
2008-08-15 5:08 ` Johannes Weiner
2008-08-16 0:08 ` Richard M. Stallman
2008-08-16 5:14 ` Johannes Weiner
2008-08-15 17:20 ` Thomas Lord
2008-08-16 10:39 ` Richard M. Stallman
2008-08-16 12:05 ` joakim
2008-08-17 7:16 ` Richard M. Stallman
2008-08-17 9:32 ` joakim
2008-08-18 6:14 ` Richard M. Stallman
2008-08-18 7:19 ` Tassilo Horn
2008-08-18 8:03 ` Stefan Monnier
2008-08-18 8:26 ` joakim
2008-08-19 12:21 ` Richard M. Stallman
2008-08-19 13:02 ` Johannes Weiner
2008-08-20 3:47 ` Richard M. Stallman
2008-08-20 5:20 ` Johannes Weiner
2008-08-19 13:42 ` Tassilo Horn
2008-08-20 3:48 ` Richard M. Stallman
2008-08-18 14:20 ` Gilaras Drakeson
2008-08-18 17:13 ` Stephen J. Turnbull
2008-08-18 17:42 ` Paul R
2008-08-19 12:21 ` Richard M. Stallman
2008-08-20 0:01 ` Stephen J. Turnbull
2008-08-21 23:09 ` Richard M. Stallman
2008-08-22 0:34 ` whither GNU Thomas Lord
2008-08-22 0:17 ` Juanma Barranquero
2008-08-22 3:40 ` David Robinow
2008-08-22 7:36 ` Johannes Weiner
2008-08-23 5:09 ` Richard M. Stallman
2008-08-22 10:21 ` Juanma Barranquero
2008-08-22 21:31 ` Thomas Lord
[not found] ` <858wuoad0u.fsf@lola.goethe.zz>
2008-08-23 4:56 ` Thomas Lord
2008-08-16 16:29 ` Release plans Stephen J. Turnbull
2008-08-16 21:04 ` Thomas Lord
2008-08-16 21:35 ` Alan Mackenzie
2008-08-16 22:43 ` Stephen J. Turnbull
2008-08-17 7:31 ` Alan Mackenzie
2008-08-18 0:01 ` Stephen J. Turnbull
2008-08-18 10:18 ` Alan Mackenzie
2008-08-18 17:58 ` Stephen J. Turnbull
2008-08-18 20:20 ` Dynamic loading (was: Release plans) Stefan Monnier
2008-08-18 22:18 ` Stephen J. Turnbull
2008-08-20 16:15 ` Dynamic loading Stefan Monnier
2008-08-20 16:57 ` joakim
2008-08-25 13:09 ` Stephen J. Turnbull
2008-08-26 16:37 ` Richard M. Stallman
2008-08-18 21:09 ` Release plans Alan Mackenzie
2008-08-18 23:27 ` Johannes Weiner
2008-08-19 10:23 ` Alan Mackenzie
2008-08-19 11:56 ` Johannes Weiner
2008-08-19 9:46 ` Stephen J. Turnbull
2008-08-19 12:36 ` Robert J. Chassell
2008-08-20 5:55 ` Stephen J. Turnbull
2008-08-20 17:48 ` Robert J. Chassell
2008-08-25 1:34 ` Stephen J. Turnbull
2008-08-25 10:47 ` Robert J. Chassell
2008-08-25 13:13 ` Stephen J. Turnbull
2008-08-25 15:19 ` Robert J. Chassell
2008-08-25 17:11 ` Thomas Lord
2008-08-26 4:10 ` Stephen J. Turnbull
2008-08-26 10:59 ` Robert J. Chassell
2008-08-27 5:00 ` Stephen J. Turnbull
2008-08-27 11:37 ` Robert J. Chassell
2008-08-28 5:42 ` Stephen J. Turnbull
2008-08-28 10:17 ` Robert J. Chassell
2008-08-26 16:37 ` Richard M. Stallman
2008-08-26 18:14 ` Thomas Lord
2008-08-27 18:54 ` Richard M. Stallman
2008-08-27 20:33 ` Paul R
2008-08-29 2:41 ` Richard M. Stallman
2008-08-29 5:34 ` Thomas Lord
2008-08-29 11:39 ` Bruce Stephens
2008-08-29 13:11 ` Lennart Borgman (gmail)
2008-08-29 19:23 ` Thomas Lord
2008-08-29 20:03 ` Thien-Thi Nguyen
2008-08-29 20:20 ` Stefan Monnier
2008-08-29 20:53 ` Lennart Borgman (gmail)
2008-08-29 23:24 ` Thomas Lord
2008-08-29 22:56 ` Thomas Lord
2008-08-30 19:51 ` Thien-Thi Nguyen
2008-08-30 23:07 ` Thomas Lord
2008-08-31 9:09 ` Thien-Thi Nguyen
2008-08-29 22:53 ` Thomas Lord
2008-08-31 9:27 ` Thien-Thi Nguyen
2008-08-29 19:13 ` Thomas Lord
2008-08-29 23:48 ` Richard M. Stallman
2008-09-01 6:11 ` Richard M. Stallman
2008-09-01 18:25 ` Thomas Lord
2008-08-27 22:32 ` Thomas Lord
2008-08-27 21:57 ` Alfred M. Szmidt
2008-08-28 0:10 ` Thomas Lord
2008-08-29 2:40 ` Richard M. Stallman
2008-08-29 5:30 ` Thomas Lord
2008-08-27 22:09 ` Alan Mackenzie
2008-08-28 1:10 ` Thomas Lord
2008-09-01 6:11 ` Richard M. Stallman
2008-09-01 18:09 ` Thomas Lord
2008-09-02 1:09 ` Richard M. Stallman
2008-09-02 2:18 ` Thomas Lord
2008-09-02 14:13 ` Richard M. Stallman
2008-09-02 20:48 ` Thomas Lord
2008-09-01 18:20 ` Stefan Monnier
2008-09-01 20:17 ` Thomas Lord
2008-09-01 19:53 ` Stefan Monnier
2008-09-01 21:23 ` Thomas Lord
2008-09-02 3:26 ` Stephen J. Turnbull
2008-09-02 20:43 ` Thomas Lord [this message]
2008-09-03 5:08 ` Stephen J. Turnbull
2008-08-27 23:09 ` Lennart Borgman (gmail)
2008-08-28 0:22 ` Thomas Lord
2008-08-28 1:01 ` Lennart Borgman (gmail)
2008-08-26 21:25 ` joakim
2008-08-29 2:41 ` Richard M. Stallman
2008-08-19 15:52 ` Alan Mackenzie
2008-08-25 14:39 ` Stephen J. Turnbull
2008-08-25 22:01 ` Alan Mackenzie
2008-08-25 22:19 ` Lennart Borgman (gmail)
2008-08-26 4:54 ` Stephen J. Turnbull
2008-08-26 7:16 ` ["agree"] " Thomas Lord
2008-08-27 5:10 ` Stephen J. Turnbull
2008-08-27 16:00 ` Thomas Lord
2008-08-26 10:02 ` Alan Mackenzie
2008-08-27 5:38 ` Stephen J. Turnbull
2008-08-27 21:06 ` Alan Mackenzie
2008-08-27 21:12 ` Lennart Borgman (gmail)
2008-08-28 20:01 ` Sean Sieger
2008-08-28 6:07 ` Stephen J. Turnbull
2008-08-27 15:57 ` Thien-Thi Nguyen
2008-08-27 18:33 ` tomas
2008-08-28 6:09 ` Stephen J. Turnbull
2008-08-28 8:14 ` tomas
2008-08-28 7:25 ` Alan Mackenzie
2008-08-28 8:23 ` tomas
2008-08-28 6:26 ` Stephen J. Turnbull
2008-08-19 16:31 ` Thomas Lord
2008-08-20 3:47 ` Richard M. Stallman
2008-08-20 6:14 ` Stephen J. Turnbull
2008-08-19 12:21 ` Richard M. Stallman
2008-08-19 13:04 ` Paul R
2008-08-20 3:48 ` Richard M. Stallman
2008-08-17 2:37 ` Thomas Lord
2008-08-17 8:01 ` Alan Mackenzie
2008-08-17 17:42 ` Thomas Lord
2008-08-17 21:07 ` Alan Mackenzie
2008-08-17 21:24 ` Johannes Weiner
2008-08-17 21:33 ` Alfred M. Szmidt
2008-08-17 22:31 ` Johannes Weiner
2008-08-18 3:06 ` Thomas Lord
2008-08-18 6:14 ` Richard M. Stallman
2008-08-17 21:45 ` Thien-Thi Nguyen
2008-08-18 6:14 ` Richard M. Stallman
2008-08-18 17:09 ` Thomas Lord
2008-08-19 16:28 ` René Kyllingstad
2008-08-20 3:48 ` Richard M. Stallman
2008-08-17 7:16 ` Richard M. Stallman
2008-08-15 3:41 ` Richard M. Stallman
2008-08-15 17:17 ` Thomas Lord
2008-08-16 10:40 ` Richard M. Stallman
2008-08-16 7:14 ` Alfred M. Szmidt
2008-08-14 17:24 ` Stefan Monnier
2008-08-15 3:41 ` Richard M. Stallman
2008-08-15 14:04 ` Alan Mackenzie
2008-08-15 15:10 ` [OT] " Yavor Doganov
2008-08-16 7:05 ` Miles Bader
2008-08-17 7:16 ` Richard M. Stallman
2008-08-15 16:35 ` Stephen J. Turnbull
2008-08-15 18:07 ` Thomas Lord
2008-08-16 10:40 ` Richard M. Stallman
2008-08-16 10:40 ` Richard M. Stallman
-- strict thread matches above, loose matches on Subject: below --
2008-08-14 15:36 Robert J. Chassell
2008-08-14 15:51 ` Johannes Weiner
2008-08-14 21:00 ` Robert J. Chassell
2008-08-14 22:58 ` Johannes Weiner
[not found] <SRV-ADEXCHyjlMFAVNL0000090e@waccglobal.org>
2008-08-13 14:07 ` Mike Rowse
2008-08-13 1:30 A Soare
2008-08-12 20:51 A Soare
2008-08-12 21:35 ` Lennart Borgman (gmail)
2008-08-12 20:16 christophe
2008-08-12 18:57 A Soare
2008-08-12 18:54 A Soare
2008-08-12 18:58 ` Lennart Borgman (gmail)
2008-08-12 18:41 A Soare
2008-08-12 18:46 ` Lennart Borgman (gmail)
2008-08-12 18:55 ` Eli Zaretskii
2008-08-12 18:38 A Soare
2008-08-12 18:36 A Soare
2008-08-12 18:04 A Soare
2008-08-12 18:21 ` Lennart Borgman (gmail)
2008-08-12 18:25 ` Lennart Borgman (gmail)
2008-08-12 15:34 A Soare
2008-08-12 15:59 ` Lennart Borgman (gmail)
2008-08-12 13:51 A Soare
2008-08-12 13:37 A Soare
2008-08-12 13:50 ` martin rudalics
2008-08-12 17:16 ` Johannes Weiner
2008-08-12 14:02 ` Lennart Borgman (gmail)
2008-08-12 14:54 ` Paul R
2008-08-12 18:37 ` Eli Zaretskii
2008-08-12 19:16 ` Óscar Fuentes
2008-08-12 19:41 ` Paul R
2008-08-12 13:11 A Soare
2008-08-12 13:20 ` Juanma Barranquero
2008-08-12 15:54 ` Johannes Weiner
2008-08-13 6:26 ` Richard M. Stallman
2008-08-13 7:05 ` Johannes Weiner
2008-08-12 13:24 ` Lennart Borgman (gmail)
2008-08-12 12:21 A Soare
2008-08-12 12:33 ` Lennart Borgman (gmail)
2008-08-12 13:42 ` Michael Ekstrand
2008-08-13 6:27 ` Richard M. Stallman
2008-08-13 7:14 ` Alex Ott
2008-08-12 14:45 ` Miles Bader
2008-08-12 14:56 ` Lennart Borgman (gmail)
2008-08-12 16:47 ` Drew Adams
2008-08-13 20:20 ` Richard M. Stallman
2008-08-12 18:34 ` Eli Zaretskii
2008-08-05 2:53 dhruva
2008-08-05 4:43 ` tomas
2008-08-05 21:48 ` Richard M. Stallman
2008-07-31 9:54 dhruva
2008-07-31 22:01 ` Richard M Stallman
2008-07-30 9:58 dhruva
2008-07-31 1:59 ` Richard M Stallman
2008-07-31 9:30 ` Alan Mackenzie
2008-07-31 22:01 ` Richard M Stallman
2008-08-01 14:15 ` Frank Schmitt
2008-08-01 14:51 ` Miles Bader
2008-08-02 5:12 ` Richard M Stallman
2008-08-02 7:20 ` Frank Schmitt
2008-08-03 1:33 ` Richard M. Stallman
2008-08-03 11:38 ` Juanma Barranquero
2008-08-03 22:42 ` Richard M. Stallman
2008-08-03 23:16 ` Juanma Barranquero
2008-08-04 15:55 ` Davi Leal
2008-08-05 21:48 ` Richard M. Stallman
2008-08-12 4:48 ` Thomas Lord
2008-08-12 7:30 ` Miles Bader
2008-08-12 15:37 ` Thomas Lord
2008-08-12 10:32 ` Richard M. Stallman
2008-08-12 16:08 ` Thomas Lord
2008-08-13 20:20 ` Richard M. Stallman
2008-08-03 13:48 ` Nic
2008-08-03 22:42 ` Richard M. Stallman
2008-08-01 15:31 ` Alan Mackenzie
2008-08-02 5:12 ` Richard M Stallman
2008-08-02 17:12 ` Alan Mackenzie
2008-08-02 23:46 ` Lennart Borgman (gmail)
2008-08-03 1:33 ` Richard M. Stallman
2008-08-03 18:01 ` Alan Mackenzie
2008-08-04 15:33 ` Richard M. Stallman
2008-08-12 4:24 ` Thomas Lord
2008-08-12 10:32 ` Richard M. Stallman
2008-08-12 16:12 ` Thomas Lord
2008-08-03 1:33 ` Richard M. Stallman
2008-08-03 17:51 ` Alan Mackenzie
2008-08-04 15:33 ` Richard M. Stallman
2008-08-04 19:08 ` Alan Mackenzie
2008-08-05 8:05 ` Richard M. Stallman
2008-08-01 17:39 ` Davi Leal
2008-08-02 5:12 ` Richard M Stallman
2008-07-14 15:07 Chong Yidong
2008-07-17 0:27 ` Juri Linkov
2008-07-17 6:41 ` David Kastrup
2008-07-21 4:49 ` Chong Yidong
2008-07-21 8:06 ` Thien-Thi Nguyen
2008-07-21 13:32 ` Chong Yidong
2008-07-21 14:19 ` Thien-Thi Nguyen
2008-07-23 20:52 ` Michael Albinus
2008-07-23 21:42 ` Chong Yidong
2008-07-26 7:39 ` Eli Zaretskii
2008-07-26 21:33 ` Richard M Stallman
2008-07-27 3:22 ` Eli Zaretskii
2008-07-27 17:14 ` Richard M Stallman
2008-07-27 19:14 ` Eli Zaretskii
2008-07-28 21:46 ` Richard M Stallman
2008-07-29 3:12 ` Eli Zaretskii
2008-07-30 3:47 ` Richard M Stallman
2008-07-30 17:33 ` Eli Zaretskii
2008-07-28 13:43 ` Juri Linkov
2008-07-28 14:10 ` Chong Yidong
2008-07-28 14:33 ` Juri Linkov
2008-07-29 17:11 ` Chong Yidong
2008-07-29 17:54 ` Stefan Monnier
2008-07-29 15:21 ` Roland Winkler
2008-08-02 17:34 ` Eli Zaretskii
2008-08-09 18:29 ` Eli Zaretskii
2008-08-09 18:34 ` Juanma Barranquero
2008-08-09 19:06 ` Eli Zaretskii
2008-07-31 2:10 ` Bastien
2008-07-31 2:43 ` Chong Yidong
2008-07-31 8:06 ` Lennart Borgman (gmail)
2008-08-01 2:53 ` Bastien
2008-08-01 19:26 ` Jay Belanger
2008-08-01 19:32 ` Chong Yidong
2008-08-02 16:12 ` Jay Belanger
2008-08-02 4:08 ` Stephen J. Turnbull
2008-08-02 17:30 ` Richard M Stallman
2008-08-05 4:04 ` Bill Wohler
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=48BDA56C.10502@emf.net \
--to=lord@emf.net \
--cc=emacs-devel@gnu.org \
--cc=monnier@iro.umontreal.ca \
--cc=rms@gnu.org \
--cc=stephen@xemacs.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.