Gap Buffers, or, Don't Get Tied Up With Ropes?

Feb 18 2009 Published by under Data Structures

Last week, I promised to continue my discussion of ropes. I'm going to
break that promise. But it's in a good cause.

If you're a decent engineer, one of the basic principles you should
for keeping things simple is realizing when you're making something
overly complicated - even if it's cool, and fun, and interesting.

thinking that it really seemed complex for what I was doing. What I'm
doing is writing myself a text editor. I'm not writing a string
processing framework for managing gigabytes of data; I'm just writing a
text editor.

the simpler data structures. A classic structure for implementing editor
buffers is called a gap buffer. I'll explain the details below.
expensive - the cost of moving the cursor is proportional to the distance
that you move it.

that includes resizing the buffer 12 times, because of a deliberately
stupid buffer sizing and copying strategy.

of a second are roughly when people start to notice that an editor is slow. If you can respond is less than 1/10th of a second, people don't perceive a troublesome delay.)
If the gap buffer can achieve the needed perfomance that easily, then there's
absolutely no reason to do anything more complicated.

Ok. So, what's a gap buffer?

It's a fascinatingly simple data structure - exactly the kind of
thing that appeals to my sense of software aesthetics. It's a great big
buffer - an array of characters. It's got two segments of text - one at
is called the gap. The gap is the cursor in the
from the length of the beginning segment.

For example, below is a diagram of a gap buffer. In the first version, it contains the text "Hello there readers", with the cursor
after the "r" in "readers".


The next version
and then adjust the pointers. We don't even bother to erase the buffer
position within the gap that used to contain the "r" - we just move
the pre-gap pointer.

In the third version, we insert the string "my" - just write the characters "m" and "y" into the next positions in the pre-gap region,
and advance the pre pointer. The resulting buffer contains the text
"Hello there myreaders".

That's all there is to it. A gap buffer is just a character array, with two pointers/indices to track the position of the beginning and ending segments. It's incredibly simple - and yet, it's also
quite surprising. I certainly wouldn't have thought of it on my own!


  • Local cursor motions are extremely fast; it's always exactly
    cursor motions.
  • Character inserts are really fast. They've got an amortized
    because you sometimes need to expand the buffer, which
    requires a lot of copying.)
  • Character deletes are super fast - just increment or decrement
    a pointer - O(1).
  • Search/scan is reasonable. Stream oriented operations like
    search have an absolute linear-time lower bound, which is
    obviously achieved by the gap buffer. And as important,
    implementing stream-oriented operations is extremely
    easy to do correctly on a gap buffer.

Finally, I'll close with some code. This is a basic gap buffer
implementation in Scala, my new favorite programming language. (I'm
for the JVM, with a better syntax.)

// Copyright 2009, Mark C. Chu-Carroll
package com.scienceblogs.goodmath.apex.buffer
class GapBuffer(size : Int) {
var _size = size
var _presize = 0;
var _postsize = 0;
* Move the cursor one character forward.
def stepCursorForward() = {
if (_postsize > 0) {
_buf(_presize) = _buf(_size - _postsize)
_presize = _presize + 1
_postsize = _postsize + 1
* Move the cursor one character backward.
def stepCursorBackward() = {
if (_presize > 0) {
val c = _buf(_presize - 1)
_buf(_size - _postsize - 1) = c
_postsize = _postsize + 1
_presize = _presize - 1
* Move the cursor.
* @param distance the distance to move the cursor.
def moveCursor(distance : Int) = {
if (distance > 0) {
for (i <- 0 until distance) {
} else {
val d = - distance
for (i <- 0 until d) {
* Move the cursor to a specific position.
* @param loc the desired cursor position.
def moveCursorTo(loc : Int) = {
moveCursor(loc - _presize)
* Insert a character immediately after the cursor position.
* @param c the character to insert.
def insertChar(c : Char) = {
if (_presize + _postsize == _size) {
_buf(_presize) = c
_presize = _presize + 1
* Insert a string after the cursor position, and advance
* the cursor to the position after the inserted string.
* @param s the string to insert
def insertString(s : String) = {
for (i <- 0 until s.size) {
* Double the size of the character storage buffer.
def expand() = {
val newsize = _size * 2
var newbuf = new Array[Char](newsize)
for (i <- 0 until _presize) {
newbuf(i) = _buf(i)
for (i <- 0 until _postsize) {
_buf = newbuf
_size = newsize

25 responses so far

  • Mu says:

    Implement line length, and you have fast WYSIWYG for the VT100

  • Mark C. Chu-Carroll says:

    Re #1:
    In fact, I've actually got an implementation working which includes line/column tracking,
    cut and paste, and undo. But I thought that that added too much noise - the basic concept of the gap buffer is so beautifully simple, and I wanted to try to really show that. This dinkly little fragment of code does most of the work for an editor back-end!

  • William Wallace says:


  • KeithB says:


  • Uncle Al says:

    WordStar 6.0 for DOS with user-customized Function and Ctrl-Function keys. Unformatted mode. Add mouse utilities if you are feeling gnarly. It will handle 20 MB files no sweat in modern iron... and you get column-block operations.
    WordStar sort utilities are slow, especially column block sorts. Use Robert Pirko's RPSORT (102) on text files.

  • KeithB says:

    Uh, Uncle Al:
    But, if he uses Boot Camp...

  • Mark C. Chu-Carroll says:

    Re KeithB, UncleAl:
    Actually, I'd rather use something that's already been written. I just haven't been able to find what I want.
    But the way it's designed, it makes very heavy use of the mouse. In Acme, you can't even move the cursor up one line without using the mouse. You can't start a search without the mouse. Nothing. With my RSI trouble, I can't rely on the mouse that much. It hurts to go back and forth between keyboard and mouse.
    I haven't been able to find anything that's built on a basic design like Acme, but doesn't rely on the mouse for *everything*. If I could find something that did what I wanted, or even came *close* to doing what I wanted, I'd drop this code like a hot rock. I don't *want* to build an editor. I just don't know how else to get the kind of tool that I want.
    If you know of anything that sounds like what I've talked about, *please* let me know. I'd really love to find something.

  • Mu says:

    MCC, regarding RSI, I got over mine by using a mouse left handed at work and right-hand a thumb-operated track ball at home. I'd switch hands too, but I haven't found a left handed track ball yet.

  • William Wallace says:

    I like codewrite.

  • Mark C. Chu-Carroll says:

    Re #8:
    Believe me, I've tried just about everything for my RSI.
    My main problem isn't the mouse. It's not that using the mouse will make it worse, but just the constant arm motion hurts because of the damage that's already done.
    At work, I use a Kinesis Countoured keyboard, which is absolutely wonderful. I can use that for hours on end without any problem; it lets me take all of the weight off my wrists, and to type at speed with minimal finger extension. So when I'm on that keyboard, I'm good. But when I need to take my hands off of it, that's the problem. Doing it once in a while is fine. But doing it the way you need to for Acme or Sam? Every single time I need to move my cursor? No.

  • Mark C. Chu-Carroll says:

    Re #9:
    Defunct commercial development tools for Windows are not exactly what I'm looking for...

  • SAWells says:

    Does anyone make a foot-operated mouse? I can imagine Mark's desk transforming into some crazed phantom-of-the-Opera organ console 🙂

  • William Wallace says:

    I am not sure why Borland discontinued CodeWrite, but probably because there wasn't much left to improve, and the trend for tool providers to package text editing/project management as part of an IDE. Even without an RSI, I loathe being a slave to the mouse.
    Foot-operated mouse: what's the market for that? It wouldn't be hard for me (or many others) to design if there were a market. Voice controlled mouse is another option, but might not be useful if you work in a cubicle environment. Keyboard alt and esc sequences, cscope (or similar) and emacs seem to be more efficient solutions, especially if you program your own macros--but I haven't used them in years.

  • KeithB says:


  • jefu says:

    Since then I've used them in a couple of classes (in "C") as an assignment - but with a wrinkle. Start with the basic gap array, then add more gaps, which mean that the bookkeeping increases - in the simplest way linearly with the number of gaps. Set up a test harness that does random (but correlated in position) inserts and deletes and see how well they perform as the number of gaps increases.

  • Buffer gaps don't need multi-GHz CPUs, they were invented before multi-MHz CPUs. The canonical description was in Craig Finseth's 1980 Master's thesis, and the technique was used in TECO.
    For details, see Finseth's "The Craft of Text Editing":

  • Mark C. Chu-Carroll says:

    Re #16:
    Gap buffers passed through a time when they weren't the best solution.
    At some point in time, when file sizes had gotten much larger, but processors weren't so fast, it made sense to try to use some kind of more clever structure, like Ropes - because they allowed you to avoid doing large copies for large cursor motion.
    Now we're back at the point where the copying makes sense again. But I think it's not really because of the raw speed of processors, but because of cache effects. Caches have gotten so large that you'll typically have the entire buffer in cache. With the pointer games in structures like ropes, you're much more likely to wind up with cache misses.

  • Alex Besogonov says:

    I use FAR Manager ( for most of my programming in dynamic languages (IDE doesn't make a lot of sense for them and REPL is good enough for debugging). FAR is absolutely powerful tool, it doesn't rely on mouse AT ALL (though it supports it, of course).
    Actually, FAR is the only application which still holds me on Windows. Alas, it's Windows-only 🙁

  • Paul Murray says:

    But the only reason that this looks so simple is that the JVM does all of the tricksy work of making virtual memory look like a big array of char. All the "ropes" (or whatever) and block buffering and whatnot is still there - it's just that application programmers these days don't have to write them.

  • Paul Murray says:

    re #17

  • Mark C. Chu-Carroll says:

    Re #19:
    That's really not true.
    For a 16 megabyte file - which is far larger than anything I expect to encounter in real use in an editor buffer - there's no virtual memory work going on to maintain the buffer. It's completely in a single contiguous memory segment. There's nothing fancy going on, in either the JVM or the OS virtual memory system. It really is this straightforward.
    On the other hand, given modern perfomance characteristics, the "tree of gap buffers" is likely to perform very poorly - it takes what is conceptually a contiguous sequence of characters, and breaks it into pieces, which are scattered around in memory. The standard algorithms used by the processor cache for prefetching fail in that layout, and you wind up paying a very significant performance penalty as a result of cache misses.

  • edwin says:

    With a bit more book-keeping you could lazily move the gap only when there's an insert. Ie if I do down/down/down/left 17 times, then type something, you could wait to move the gap until I try to insert something at that point.

  • kaleberg says:

    Gap buffers have been around for ages. I believe that Expensive Typewriter used them on the old PDP 1-X with its Friden Flexowriters. It gibed well with paper tape oriented editors like TECO. Early TECOs didn't have a read file command, but rather a read another chunk, write another chunk primitive, so for larger files the user was responsible for paging.

  • Kevin Krouse says:

    You may want to take a look at Evergreen. It's an Acme-like editor written in Java. Sounds like it might be what you're looking for.

  • mikhailfranco says:

    Sounds like what would be called a 'zipper' in functional programming - the beauty being that the two segments can be stored in cons lists headed at the current position. Check out Gerard Huet's 'Functional Pearl' (OK, he did it for trees), and papers that generalize to differentiating data structures:

Leave a Reply