算法与数据结构 / 文本缓冲 · 从 gap buffer 到 piece table 与 rope 待审核 6 页

文本缓冲 · 从 gap buffer 到 piece table 与 rope

打开一个文件，编辑器要把它放进某个结构里。用一个 JS 字符串或一块连续内存是最直白的选择，代价也一眼可见：在正中插入一个字符，后半篇全部要往后挪一格。1 MB 文档实测每次击键搬移 52 万字符，64 MB 文档每次击键 4.19 毫秒，已经吃掉一帧预算的四分之一。

出路来自编辑操作本身的形状。插入与删除高度局部化，几乎总发生在光标附近；而只读查询是另一副面貌，「第 $n$ 个字符是什么」与「第 $k$ 行从哪开始」随时被渲染、查找、跳转调用。三种经典结构各自挑了一条路：gap buffer 把空闲空间做成一个跟着光标走的洞，光标不动时插入不搬一个字符，Emacs 用的就是它；piece table 把文档表示成一串指向两个只增缓冲的 piece，原始文本从不被改写，撤销与内存碎片都因此便宜，VS Code 在 2018 年从行数组换成了它；rope 把文本切成叶子挂上平衡树，定位、拼接、切分一律 $O(\log n)$ 。

本系列用同一套接口实现这三种结构外加一个朴素字符串基线，每个操作统计搬移的字符数与访问的结点数，于是横向对照有据可查。全部实现共用一组 oracle 测试：同一串随机编辑喂给全部五种，每一步之后与朴素字符串逐字比对。

代价：编辑操作的形状

先把账算清楚。评价一个文本缓冲要看五项：局部编辑代价、随机访问、行号查询、内存开销、撤销与协同编辑的支持。朴素字符串在第二项与第三项上无可挑剔，第一项上无可救药，而编辑器的负载恰恰以第一项为主。

局部性 · 搬移代价 · 评价维度

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

编辑器的负载极不均匀：插入删除集中在光标附近，而随机访问与行号查询随时发生。朴素字符串把前者做成 O(n)，1 MB 文档每次击键搬走 52 万字符。本页把这笔账算清，并给出五项评价维度与本系列统一的计量口径。

搬移量与墙钟不成正比

本系列的横向对照一律用搬移的字符数，不用墙钟，理由是墙钟在小文档上会给出误导性的结论。1 MB 文档正中插入 1000 次，朴素字符串逻辑上搬了 10.49 亿字符，实测只花 26.4 毫秒。做一组控制实验就知道这个数没有异常：用 Uint16Array.set 老老实实搬同样多的 16 位字符，耗时 22.4 毫秒，等效 93.7 GB/s。1 MB 的文档整个待在 L2 里，搬移根本不慢。把文档放大到超出 cache，账才对得上：每次击键的耗时从 1 MB 的 0.031 毫秒涨到 16 MB 的 1.007 毫秒、64 MB 的 4.191 毫秒，等效带宽从 68.6 GB/s 掉到 32.0 GB/s。同一区间里 piece tree 每次插入稳定在 0.001 毫秒量级，且随文档变大略微变快。

三种结构

gap buffer 押注「编辑集中在一处」，piece table 押注「原始文本不必改」，rope 押注「什么都用树上的子树和来答」。三者的搬移量在同一串编辑下相差六个数量级，但各有自己会输的负载形态：gap buffer 怕多光标，piece table 怕碎片化，rope 怕叶子太小。

gap · 光标就位 · 扩容

gap buffer：跟着光标走的洞

把空闲空间集中成一个位于光标处的洞，插入就只是往洞里写一个字符，不搬任何既有内容。代价转移到光标移动上：把洞挪 k 格要搬 k 个字符。Emacs 用的就是这一套。

original · added · 碎片化

piece table：原始文本从不被改

文档表示成一串指向两个只增缓冲的 piece，插入把一段拆成三段，删除拆成两段，谁也不改写既有字符。撤销与内存碎片因此便宜，代价是 piece 数随编辑次数线性增长。VS Code 2018 年换的就是它。

叶子 · 子树长度和 · split/concat

rope：把字符串挂上平衡树

文本切成叶子，用平衡树串起来，每个内部结点记录左子树的字符数与换行数。按下标定位、切分、拼接一律 O(log n)。叶子上限是唯一的调参旋钮，它在结点数与每次切分的复制量之间取舍。

三种结构的分工判据

搬移字符数不是唯一指标，选型实践中真正起作用的有四条。 编辑的空间分布。单光标顺序输入是 gap buffer 的理想负载，实测 1 MB 文档连续插入 1000 次只搬 157 万字符，其中 152 万还是一次性的光标就位与扩容；同一串编辑改成两端交替，搬移量跳到 10.08 亿。多光标编辑在 gap buffer 上没有便宜可占。 是否需要廉价撤销。piece table 的原始缓冲逐字符不变，撤销只要换回一份 piece 列表。500 次编辑的全部快照共 165183 条 piece 记录，换成整串快照是 519 万字符。 行号查询的频率。渲染与跳转都要「第

k

行从哪开始」。gap buffer 与朴素字符串只能扫，1 MB 文档单次查询平均扫 51 万字符；树结构在结点里存一个换行计数就把它压到几十次探测。 碎片化的容忍度。piece table 的 piece 数随编辑次数线性增长，10 KB 文档 2000 次随机编辑后碎成 2982 个 piece、平均每个 3.8 字符。数组实现此时定位一次要扫 1705 个 piece，这正是 VS Code 给 piece 挂一棵平衡树的理由。

三种结构的一手文献

Crowley · Data Structures for Text Sequences (1998) cs.unm.edu 文本序列结构的综述与实测对照：数组、gap buffer、行表、piece table、piece chain、fixed size buffers，逐项给出各操作的代价模型。本系列的评价维度取自它。
Boehm, Atkinson & Plass · Ropes: an Alternative to Strings (1995) citeseerx.ist.psu.edu rope 的原始论文：concat 只新建一个根、按下标定位与切分走树上的长度和，以及惰性求值与平衡条件。
VS Code · Text Buffer Reimplementation (2018) code.visualstudio.com 从行数组换成 piece table 加红黑树的完整记录：换之前的内存与长行问题、为什么不用 rope、以及换之后各项 benchmark 的实测对照。
GNU Emacs Lisp Reference · Buffer Gap gnu.org Emacs 的 gap buffer 一手说明：gap 的位置、buffer-size 与 gap-size 的关系，以及点移动如何触发 gap 搬移。

索引与协同

把「按下标定位」推广成「按任意可加权重定位」，行号查询就只是换一个权重字段。而 piece table 的只增缓冲与 CRDT 的不可变操作日志是同一个想法的两处应用，两者的接口比看起来近。

索引、协同与工程实现

Rope science — xi-editor xi-editor.io Raph Levien 的系列笔记：把 rope 的结点权重推广成 monoid，于是行号、宽度、语法状态都能挂在同一棵树上。本系列 §5 的推广即出自这个视角。
ropey github.com Rust 的生产级 rope：按 code point 与按行两套坐标、叶子大小的选择依据、以及 grapheme 边界不被切开的保证。
How Figma’s multiplayer technology works figma.com 工程视角的协同编辑：为什么 Figma 没有对文本用完整 CRDT，以及不可变操作日志与服务端定序的分工。
Joseph Gentle · 5000x faster CRDTs josephg.com Yjs 与 Automerge 的性能拆解，含把 CRDT 的 item 列表挂上 range tree 的做法 —— 与 piece table 挂平衡树是同一手法。

换行计数 · 二分 · monoid

行号索引：按可加权重定位

渲染与跳转都要「第 k 行从哪开始」。在结点里多存一个换行计数，同一棵树就能按行定位。这是把「按字符定位」推广成「按任意可加权重定位」的标准手法，代价只是每个结点多一个整数。

撤销 · 稳定标识 · CRDT

不可变缓冲与协同编辑的接口

piece table 的原始文本不可变，撤销只要换回一份 piece 列表，实测比整串快照省 31 倍。但 piece 的「缓冲加偏移」不是稳定标识，两个副本各自追加就会撞车，这正是 CRDT 要补的那一层。