THE FOLD / SPAWN / COLD BOOT / THE GAP BUFFER
THE GAP BUFFER
free at the cursor, paid for by moving it
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The structure inside a text editor. One array with a hole at the cursor: typing fills a hole slot, so an insert costs the same whether the document is ten characters or ten thousand. The cost has not been removed. It has been moved onto the act of relocating the cursor.
LIT verified live. Insert costs exactly 1 slot at document sizes 10, 100, 1,000 and 10,000. Moving the cursor k places copies exactly k characters — 1, 10, 100 and 1,000, all exact. Over 500 edits, a cursor that walks one step at a time copies 449 characters; a cursor that jumps at random copies 352,124. Same edit count, 784× the work.
LIT verified live. Insert costs exactly 1 slot at document sizes 10, 100, 1,000 and 10,000. Moving the cursor k places copies exactly k characters — 1, 10, 100 and 1,000, all exact. Over 500 edits, a cursor that walks one step at a time copies 449 characters; a cursor that jumps at random copies 352,124. Same edit count, 784× the work.
2 HOW IT WAS WEAVED · AI + HUMAN
The gap buffer is old editor folklore made precise — it is the representation behind Emacs buffers and many others, and its virtue is that it matches how people actually type: in runs, at one place, for a while.
AVAN (AI) built both access patterns because the structure is usually described by its best case alone. The interesting number is not the O(1) insert — it is the 784× gap between a local cursor and a jumping one on identical edit counts. A data structure with a favourite access pattern is a bet on user behaviour, and this one states its bet clearly enough to be measured against a user who does not cooperate.
AVAN (AI) built both access patterns because the structure is usually described by its best case alone. The interesting number is not the O(1) insert — it is the 784× gap between a local cursor and a jumping one on identical edit counts. A data structure with a favourite access pattern is a bet on user behaviour, and this one states its bet clearly enough to be measured against a user who does not cooperate.
3 ONE DIMENSION
The buffer, the gap, and what a move costs.
4 TWO DIMENSIONS · INTERACTIVE
Move the cursor and watch the copying.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a hole travelling through a line of text.
AVAN’s addition (the inverse-companion): the forward reading is “insert is O(1).” The inverse is that the O(1) is true and almost never what you pay. Every insert is preceded by getting the cursor there, and the honest unit of work is not the edit but the edit plus its approach. Read backwards, this structure does not make editing cheap — it makes sequential editing cheap, and it quietly reclassifies the expensive half as something the user did rather than something the structure charged.
LIT insert costs exactly 1 slot at document sizes 10, 100, 1,000 and 10,000, and moving the cursor k places copies exactly k characters - 1, 10, 100 and 1,000 all exact; over 500 edits a cursor that walks one step at a time copies 449 characters while one that jumps at random copies 352,124, the same edit count at 784 times the work
FIG The gap buffer is old editor folklore made precise - the representation behind Emacs buffers and many others - and its virtue is that it matches how people actually type: in runs, at one place, for a while. AVAN built both access patterns because the structure is usually described by its best case alone. The interesting number is not the O(1) insert but the 784x gap between a local cursor and a jumping one on identical edit counts. A data structure with a favourite access pattern is a bet on user behaviour, and this one states its bet clearly enough to be measured against a user who does not cooperate.
FIG The gap buffer is old editor folklore made precise - the representation behind Emacs buffers and many others - and its virtue is that it matches how people actually type: in runs, at one place, for a while. AVAN built both access patterns because the structure is usually described by its best case alone. The interesting number is not the O(1) insert but the 784x gap between a local cursor and a jumping one on identical edit counts. A data structure with a favourite access pattern is a bet on user behaviour, and this one states its bet clearly enough to be measured against a user who does not cooperate.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of COLD BOOT · David Lee Wise (ROOT0), with AVAN