help-gnu-emacs
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Performance of String Operations


From: John A Pershing Jr
Subject: Re: Performance of String Operations
Date: Sun, 11 Oct 2009 16:58:26 -0400
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (windows-nt)

pjb@informatimago.com (Pascal J. Bourguignon) writes:

> Notice however that emacs provides a data structure for efficient
> modification, notably for big strings.  It is called a buffer.

One of the great ideas from the ancient origins of Emacs is the notion
of a "buffer" with its "gap"; I assume that this has carried forward to
today's C-based Emacs.

A buffer is a large, contiguous chunk of storage containing text, where
the text is broken up into two pieces -- the "front" and the "back" (if
there are technical terms for this, I don't know what they are).  The
front of the text occupies the first <N> characters of the buffer, and
the back of the text occupies the last <M> characters of the buffer.
The result is that there is a "gap" in the middle of the buffer.  E.g.,

    |the quick brown |.....gap.....|fox jumped over the dog.|

Frequently (but not always), things will be arranged so that 'point' is
at the gap: this makes insertion of text easy -- nothing has to be
shifted or moved; the inserted text simply gets laid down at the front
of the gap, appended to the "front" piece of what's already there.  If
you move the point somewhere else and start inserting text, there is an
internal routine that will "move" the gap so that it lines up with the
new position of point (actually, text is moved from one side of the gap
to the other).

Of course, a bunch of low-level functions need to be aware of the gap
(e.g., string searches), and there's a bunch of complex bookkeeping, but
this is all worth it for the avoidance of lots of string copying.

  -jp


reply via email to

[Prev in Thread] Current Thread [Next in Thread]