算法与数据结构 / 文本缓冲 · 从 gap buffer 到 piece table 与 rope / 一个字符串不够用：编辑的代价账 待审核 1 / 6
局部性 · 搬移代价 · 评价维度

一个字符串不够用：编辑的代价账

一个文本编辑器要把打开的文件放在某处。最直白的选择是一段连续内存，或者在 JS 里一个字符串。读取快得没话说：第 ii 个字符是一次寻址，取一段子串是一次 memcpy。问题出在写。

在长度 nn 的连续内存正中插入一个字符，后半段 n/2n/2 个字符全部要往后挪一格。删除同理。一个 10 MB 的文件在中间敲一个字符，逻辑上要搬走 500 万个字符；换成 JS 字符串还要更糟，字符串不可变，s.slice(0, p) + c + s.slice(p) 每次重建全串，搬的是 nn 而不是 n/2n/2。

这个代价本身不新鲜。值得算清楚的是：它在什么规模上真的开始疼，以及换掉它要付出什么。

1 · 编辑操作的分布

编辑器的操作并不是均匀地落在文档各处。把一次真实的编辑会话拆开看，大致是三类：

  • 写操作高度局部化。连续输入时，相邻两次插入的位置只差一格；即使是查找替换，也是一批彼此相距很远但各自成簇的编辑点。
  • 读操作遍布全文。语法高亮要顺序扫过可视区，查找要扫全文，跳转到某一行要立即给出偏移。
  • 随机访问的粒度是字符，行号查询的粒度是行。这两个坐标系必须同时便宜，而它们的换算关系随每次编辑变化。

朴素字符串在后两类上无可挑剔，在第一类上无可救药。而第一类正是交互延迟的所在：读操作可以摊在渲染帧里做，插入必须在下一帧之前完成。

2 · 五种实现的同一串编辑

本系列实现了四种缓冲结构，外加一个朴素字符串作为对照与真值。五者共用同一个接口：insert(pos, text) / delete(pos, len) / charAt(i) / substring(a, b) / lineStart(k) / toString()，每个操作都统计搬移量（既有内容被挪动的字符数，不含新插入的文本本身，那笔开销五种实现完全一样）。

图 2-1 · 同一串编辑脚本喂给五种实现后各自的累计搬移量。可切换编辑模式与步数，观察 gap buffer 在单光标与多光标下相差两个数量级。

在 1 MB 的样本文档（1048576 个字符、39834 行）正中连续插入 1000 个字符，五者的搬移量是：

实现 搬移字符数
朴素字符串 1049075500
gap buffer 1572880
piece table（数组） 0
piece tree（树） 0
rope 0

三个零不是取整的结果，是精确值：piece table 与 rope 的插入只改指针与下标。gap buffer 的 157 万里有 152 万是一次性的，拆开看是 524288（光标从文档末尾跳到正中）加 1048592（洞用完后整体重排一次），中间那 15 次插入一个字符也没搬。

把插入位置改成随机，账立刻变样：rope 涨到 62346（每次插入平均切开一个 63 字符的叶子），gap buffer 涨到 342887016，两版 piece table 仍是 0。

3 · 规模与击键延迟

搬移量是逻辑量，真正决定手感的是墙钟。这两者的关系没有想象中直接。

最初的猜想是：朴素字符串搬 10.49 亿个字符只花 26.4 毫秒，快得不合理，V8 大概是用 ConsString 把拼接推迟了，slice 也可能只产生 SlicedString 而不复制。做一组控制实验就否掉了这个猜想：用 Uint16Array.set 老老实实搬同样多的 16 位字符，耗时 22.4 毫秒，等效 93.7 GB/s。1 MB 的文档整个待在 L2 里，搬移就是这么快。26.4 毫秒是真搬出来的。

图 3-1 · 每次击键的耗时随文档规模的变化，数据取自实测。可切换纵轴在耗时与等效带宽之间，观察 4 MB 附近等效带宽掉下去的那一档。

于是问题变成规模。实测每次击键的耗时随文档变大而变化：

文档规模 朴素字符串每次击键 等效带宽 piece tree 每次插入
0.25 MB 0.009 ms 61.5 GB/s —
1 MB 0.031 ms 68.6 GB/s 0.0022 ms
4 MB 0.236 ms 35.6 GB/s —
16 MB 1.007 ms 33.3 GB/s 0.0015 ms
64 MB 4.191 ms 32.0 GB/s 0.0007 ms

等效带宽在 4 MB 一档掉了一半，那是文档溢出末级 cache 的位置。此后带宽稳定在 32 GB/s 左右，耗时随文档长度线性增长。64 MB 时每次击键 4.19 毫秒，已经吃掉 60 fps 一帧预算的四分之一，而这还只是搬移，不含重新分词、高亮与布局。

同一区间里 piece tree 每次插入稳定在 0.001 毫秒量级，且随文档变大略微变快（大文档的 piece 更少、树更浅）。这个反向趋势不是错觉，它来自 piece 数只随编辑次数增长、与文档长度无关。

警示 · 用小文档量出来的墙钟不能外推。0.25 MB 与 64 MB 之间，朴素字符串每次击键的耗时差 465 倍，而搬移量只差 256 倍——多出来的那 1.8 倍全是 cache 的账。本系列此后一律用搬移量与访问结点数做横向对照，墙钟只在本页出现一次。

4 · 评价维度

把上面的观察整理成可对照的五项。后面三页每讲一种结构，都回到这张表上看它在哪一格上赢、哪一格上输。

定义 4.1（文本缓冲的评价维度）

  1. 局部编辑代价：在给定位置插入或删除，要搬动多少既有内容。
  2. 随机访问：charAt(i) 与 substring(a, b) 要访问多少结点。
  3. 行号查询：lineStart(k) 给出第 kk 行的起始偏移要多少工作。
  4. 内存开销：结构本身相对文档长度的额外占用，以及碎片化程度。
  5. 撤销与协同：能否廉价地保存历史版本，能否表达「谁在什么位置插入了什么」。

第五项常被忽略，但它决定了结构能不能长成一个真实产品。撤销要求能回到任一历史版本；协同编辑要求把编辑表达成可交换、可重放的操作。这两条对「原地改写文本」的结构都不友好。

5 · 计量口径

三个计数器贯穿本系列，含义要先定死，否则跨结构的数字没法比。

moved 记既有内容被搬动的字符数。这是唯一可以跨五种实现直接比大小的量。新插入的文本本身不计，因为每种实现都得把它写进某处一次。

visited 记访问的结点数，单位随结构而变：朴素字符串与 gap buffer 记触碰的数组格，数组版 piece table 记扫过的 piece，piece tree 与 rope 记下降经过的树结点，另加换行位置表上的二分探测次数。跨家族只能比数量级，不能比绝对值。

scanned 记为统计换行而扫读的字符数。它不搬动任何东西，但确实是 CPU 时间，而且是行号查询在朴素结构上的全部代价。

这套口径有一处刻意的不对称值得说明：piece table 拆分一个 piece 时要重新数这一段里有几个换行，数组版是逐字符扫（记进 scanned），树版靠缓冲区的换行位置表二分（记进 visited）。同一件事落在两个计数器上，是因为两种实现做的确实是两件不同的事，合并计数会把 §5 的对照抹平。

注 · 五种实现按 UTF-16 code unit 计位，与 JS 的 String.length 同一口径。surrogate pair 因此可能被切在中间：delete(3, 1) 作用在 'ab😀cd' 上会留下一个孤立的高位代理。这是刻意保留的限制而非疏漏，buffer.test.ts 里有一组测试把它显式测出来。生产实现（如 ropey）会额外维护 code point 与 grapheme cluster 两套坐标。

6 · 参考文献

  1. Crowley, C. (1998). Data structures for text sequences. University of New Mexico, Technical Report.
  2. Boehm, H.-J., Atkinson, R., & Plass, M. (1995). Ropes: an alternative to strings. Software: Practice and Experience, 25(12), 1315–1330.
  3. Microsoft. (2018). Text buffer reimplementation. VS Code Blog, 2018-03-23.
  4. Finseth, C. A. (1991). The Craft of Text Editing: Emacs for the Modern World. Springer-Verlag. 第 6 章逐项对照了缓冲结构的取舍。