From: Thomas Lord <lord@emf.net>
To: Alan Mackenzie <acm@muc.de>
Cc: bob@rattlesnake.com, rms@gnu.org, emacs-devel@gnu.org
Subject: Re: Release plans
Date: Wed, 27 Aug 2008 18:10:41 -0700 [thread overview]
Message-ID: <48B5FB11.6090708@emf.net> (raw)
In-Reply-To: <20080827220906.GB5374@muc.de>
Alan Mackenzie wrote:
> If you were to fix a bug, or start implementing a cool new feature - you
> know, make some sort of contribution, no matter how small - it would be
> really appreciated.
>
I'm working on a new implementation of strings and buffers,
including support for undo, markers, properties, and overlays.
That's going well.
If it finishes well, then I might make a new implementation of
interact loops and redisplay primitives, add a dynamic loader,
and call it a day. (After which I might work on a dynamically
loadable extension language interpreter.)
There is a fork in the road coming up, though. I started on the
strings and buffers project for a different purpose, originally: I
want them for an extended XML parser with SAX and DOM
models. After I get strings and buffers working I'll have to consider
what to work on next out of the set: XML foo, Emacs interact loop,
or Emacs-style redisplay. I'm not sure which I'll pick.
The new strings and buffers implementation is inspired by
several needs including but not limited to:
1) to have such as a stand-alone C library
2) to be useful for a lisp implementation without requiring all
the baggage of a lisp implementation
3) to fix some performance problems that gap buffers have
4) to handle unicode very cleanly
5) to make string-handling C code easier to get right
The string representation is based on splay trees: a string
is a splay tree of gap buffers. There are various invariants
(that I won't get into here) that make these trees more than
ordinary splay trees -- they are a new data structure (afaict).
The string representation is (semantically) functional: strings
are never modified. Instead, strings share state (i.e., share
sub-trees) and linear styles of programming are rewarded (e.g.,
sometimes new strings are constructed by cheaply modifying
existing strings *if* there are no other references left to the unmodified
string).
Because strings are functional and share state, "undo" is pretty
trivial. To snapshot the state of a buffer at some instant,
just make a copy of the string it contains. That copy
will share state (so it is space efficient and cheap to create).
That copy won't change (since the string representation is
functional).
The splay tree of gap buffers representation means that the
amortized cost of shifting characters from one side of the
conceptual gap to another (moving the point) is O(log n) (compared
to gap buffers which are O(n)). At the
same time, the space inefficiency of the tree and time inefficiency
of scanning it are no worse than O(n) (in the length of the string) --
the same as gap buffers. So the new data structure is at least
asymptotically faster.
Another interesting advantage of this string/buffer representation
is that it is very good at representing *sparse* buffers -- buffers that
are mostly just a string of a single character repeated, only in a few
places interrupted with others. As a consequence, these new
strings/buffers
can be used for non-traditional purposes, such as huge sparse bitsets, or
large hash tables. (A buffer as a hash table? Roughly speaking: compute
an N-bit hash value, then go to that line of the buffer -- that line of
the buffer
contains the corresponding (possibly empty) hash bucket. This
splay-of-gap-buffers
thing can handle that quite efficiently -- O (log N) for the "goto step"
with amortized
cost much lower if access patterns display locality. It's not really
*quite* that
simple for a fast hash table but it's close.)
This kind of project is very much Emacs related and, also, is slower
than just looking up a minor bug with a quick fix. I like to get some
orientation
to the terrain along the way, hence the bursts of verbosity (which, really,
aren't *that* much in the overall ebb and flow).
Oh, the meat of the new string data structure looks like it will weigh in
far under 5K lines of code -- the whole buffer support perhaps doubling it.
It's shaping up as pretty tight code that is pretty and simple to follow
(another
of the goals). The main logic for editing primitives and splaying look to
come in under 1K lines of code -- maybe 2K.
Thinking of the possible follow-on projects of interact loop, redisplay, and
dynamic loader:
Interact loops are easy enough and I can certainly make a "stackless"
version (so, no more "recursive minibuffers" hair).
Redisplay is the intimidating one, still, because it just looks hopelessly
tedious. Conceptually easy, sure, but tedious and requiring too much code.
I'm still thinking about that part.
The combination of the buffers, interact loop, redisplay and loader would
be "an Emacs", stripped of lisp, but ready to dynamically load a lisp
(or any other language) interpreter.
Since you asked so nicely,
-t
next prev parent reply other threads:[~2008-08-28 1:10 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 [this message]
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
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=48B5FB11.6090708@emf.net \
--to=lord@emf.net \
--cc=acm@muc.de \
--cc=bob@rattlesnake.com \
--cc=emacs-devel@gnu.org \
--cc=rms@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.