Re: Performance of String Operations

[John A Pershing Jr <pershing@alum.mit.edu>]

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