【IT168 评论】作为Github上一款开源的文本编辑器，Atom一经推出就受到了广泛的欢迎。Atom的几个功能取决于基于开放缓冲区内容的潜在的长时间运行计算，但直到最近，才有可能从主线程上运行的JavaScript访问缓冲区的文本。这使得很难保证Atom在所有场景下的响应能力，特别是在编辑较大的文件时。

　　随着Atom 1.19版本的发布，这种情况发生了变化，这开辟了通过C ++实现的新文本存储数据结构显著增加并行性的途径。这种新的设计为性能和可扩展性提供了许多好处，其中主要的工作线程能够读取先前缓冲区状态的快照，而不会阻塞主线程上的写入操作。在这篇文章中，将深入介绍Atom对文本存储的新方法，然后探索将其成为许多优化中的第一步。

　　分层更改

　　Atom新的缓冲区表示的关键思想是将缓冲区的内容分为两个主要的状态。首先，有一个基本文本，它对应于最近读取或写入磁盘的文档版本。基本的文本是不可变的，并存储在连续分配的单个内存块中。而叠加在基本文本上面的是未保存的更改，它们存储在称为Patch(补丁)的单独的稀疏数据结构中。为了记录编辑，而不是将缓冲区的全部内容移动到内存中，只需对这个Patch进行变更。

　　实际上在任何时候都可以存在多个Patch(补丁)块。最顶层的Patch(补丁)始终是可变的，但是可以通过冻结最顶层的Patch(补丁)并将新Patch(补丁)推送到堆栈的顶部，来创建当前缓冲区内容的只读快照。将流编辑到这个新Patch(补丁)中，直到不再需要快照，此时最顶层的补丁可以合并到前一层的Patch(补丁)中。

　　要读取缓冲区状态，需要遍历连续的“块”，其中每个块对应于一个分层Patch(补丁)的更改或包含基本文本的数组的切片。

　　Patch(补丁)数据结构

　　整个系统的核心是Patch(补丁)数据结构，它描述了如何将一系列文本更改应用于某些输入以产生新的输出。它基本上是通过在输入和输出上运行差异来获得相同的信息，但不是通过比较两个缓冲区的内容来构建的，而是通过组合一系列的编辑来逐步构建的。

　　需要解决的问题

　　希望更好地了解Patch(补丁)解决的问题，请参考一下这个示例。先从包含xxxx的缓冲区开始，然后执行以下插入：

　　insert B @ 2 -> xxBxx

　　insert C @ 4 -> xxBxCx

　　insert A @ 1 -> xAxBxCx

　　之后，需要一个对变更内容的总结，需要diff字符来表达(diff是Unix系统的一个很重要的工具，用来比较两个文本文件的差异)。就像这样：

　　[

　　{oldRange: [1, 1], oldText: '', newRange: [1, 2], newText: 'A'},

　　{oldRange: [2, 2], oldText: '', newRange: [3, 4], newText: 'B'},

　　{oldRange: [3, 3], oldText: '', newRange: [5, 6], newText: 'C'}

　　]

　　这个diff中的每个entry(接口)都有一个oldRange，不考虑Patch中存在的任何其他更改。例如，描述插入C的entry具有[3，3]的oldRange，它包括了插入A和B的影响。相反，每个变化的newRange反映了Patch中所有其他编辑的空间影响。例如，插入C具有[5,6]的newRange，这说明了缓冲区中插入A和B比较早。

　　这种总结不需要从原始编辑流中获得，无需额外处理。考虑在索引4插入C。这个索引已经解释了B的先前插入，但是它并没有考虑到A在C之前被插入，而是在C之后插入。要在上面所示的diff平台中生成oldRange和newRange，人们需要了解每个变化与其他变化的空间关系，而不管其时间顺序如何。

　　一个简单的解决方案

　　这个问题的一个简单的解决方案是将每个更改存储在一个列表中，每个更改都存储其oldText，newText和distanceFromPreviousChange。人们通过浏览现有的更改来确定列表中每个新条目的插入位置。下面是根据上面示例中的插入如何更改列表的方法。

　　assert.deepEqual(patch.changes, [])

　　patch.splice(2, '', 'B')

　　assert.deepEqual(patch.changes, [

　　{distanceFromPreviousChange: 2, oldText: '', newText: 'B'}

　　])

　　patch.splice(4, '', 'C')

　　assert.deepEqual(patch.changes, [

　　{oldText: '', newText: 'B', distanceFromPreviousChange: 2},

　　{oldText: '', newText: 'C', distanceFromPreviousChange: 1}

　　])

　　patch.splice(1, '', 'A')

　　assert.deepEqual(patch.changes, [

　　{oldText: '', newText: 'A', distanceFromPreviousChange: 1},

　　{oldText: '', newText: 'B', distanceFromPreviousChange: 1},

　　{oldText: '', newText: 'C', distanceFromPreviousChange: 1}

　　])

　　在这种情况下，oldText始终为空，因为人们只执行插入操作，但通过对oldText使用非空值可以轻松地表达删除或替换。一旦有了这个更改列表，就可以通过遍历列表来生成所需的摘要，根据上一次更改的这些Range的结尾，将每个变更的oldRange和newRange放在开头。

　　伸展树(Splay trees)

　　采用上述方法的问题是，在列表中插入更改可能需要人们检查每一个其他更改，这会产生O(n2)的时间复杂度。

　　为了确保在生产中实现良好性能，人们通过使用Splay树而不是简单的列表来提高对O(n·log 2n)的限制。伸展树是一种二进制搜索树的版本，可以相当简单的实现，并具有“自我优化”的非常良好的属性。这意味着当它们被查询和修改时，它们会自动调整其结构，使得访问最近访问节点附近的节点更便宜。对于随机工作负载，此属性没有什么帮助，但对于表现出高度局部性(如文本编辑器中出现的)的工作负载，这种自优化行为是非常有用的。

　　Splay树围绕着一个非常简单的原则。每次访问一个节点时，它将通过splay的特殊指针旋转到树的根。splay不仅将节点移动到节点树的根，而且还减少了节点附近的树的深度，确保下一次访问附近的节点时，它将更接近根，因此可以更快地找到。

　　这个方法的值得注意的是O(n·log 2n)是一个摊销的边界。任何单一操作的成本可能与O(n)一样多，从而使后续操作低本更低。实际上，这很好。任何单一的线性时间操作通常不会导致性能问题。只有当人们开始执行时间复杂度变成二次执行多个线性时间的操作，并且恰好Splay树可以有助于避免这种情况。

　　如果想了解更多有关伸展树的信息，麻省理工学院David Karger的讲座做了一个很好的介绍。

　　为用例增加Splay树

　　在文献中，Splay树总是作为键和值之间的简单有序映射呈现。使用Patch，正在解决一个更复杂的问题：伸展树需要在新旧的坐标空间中保持每个节点的位置，以便可以有效地更新所有后续节点的位置，插入更改。为了做到这一点，人们将每个节点与常量密钥相关联，而不是将每个节点与相对表达的值相关联，这些值表示节点与旧祖先和新坐标空间之间的距离。

　　在上面的图表中，每个变化都显示为梯形，以图形方式表示替换一行字符的空间影响。在前面所说明的列表表示中，与上一次更改的距离在两个坐标空间中总是相同的，因为任何两个更改之间的文本都不会被修改。在Splay树的版本中，每个更改都要存储与其左祖先节点的距离，其总结了整个子树对该更改左侧的空间影响。以上每个阴影较深的节点都在其左子树中有变化，因此每个坐标空间的距离与其左祖先节点的距离不同。要将这些相对距离转换为绝对位置，在从根降到叶的同时，在两个坐标空间中累加一个运行总数。

　　要插入新的更改，将显示正在替换的最接近范围的现有更改。当在splay树操作期间重新排列指针时，可以根据本地可用的信息更新到每个节点的左祖先节点的距离。一旦下限和上限节点已经旋转到树的根，它们之间的任何节点将被插入的更改所包含，这意味着它们可以被删除。然后，插入新的更改，将其与树的根目录中的一个或两个节点进行合并，这取决于它是否重叠。

　　对于patch结构，显示不仅仅是一个保持Splay树更平衡的机制。实际上依赖于将节点移动到根的能力，以便将新的变化连接到结构中。使用更加刚性平衡的数据结构(如红黑树)，在不违反关键不变量的情况下，更难将节点旋转到根上。

　　值得注意的是，在上述所有示例中，为了清楚起见，使用标量值来表示位置和距离。实际上，这些值被表示为由行和列组成的二维向量。这增加了一些复杂性，但基本思想保持不变。还值得注意的是，该结构具有超出本文中描述的缓冲区表示的实用性。人们最初创建它来聚合每个事务中发生的所有更改，以便人们可以通过diff工具通知变更监听器，并将最紧凑的表示存储在撤消堆栈中。还使用patch在存在面向表达式转换(如软包装和代码折叠)的情况下对缓冲区和屏幕坐标之间的转换进行索引。这是一个复杂的代码段，但是人们从中得到了很多。

　　一些初步的优化

　　C++实现缓冲区本身就是一个胜利，可以获得Atom的整体效率。JavaScript可能相当快，但从根本上说，它是一种脚本语言，具有不可避免的开销。通过在C ++中实现缓冲区，消除了JS的开销，并获得了最大化效率所需的控制权限。还通过简化堆并在热代码路径上分配更少的短期对象来减轻对V8垃圾收集器的压力。但这些改进只是一个开始。这种新表现的真正价值在于其分层设计实现的优化。

　　未保存更改的进行有效备份

　　去年一月，当人们发现一个令人沮丧的瓶颈时，刚刚完成了另一项改进，使Atom可以处理更大的文件。编辑大文件时最大的麻烦之一是需要周期性地将大缓冲区的未保存状态写入磁盘。在容量足够的情况下，甚至收集了写缓冲异步介绍明显停顿的内容，虽然可以巧妙地利用requestIdleCallback和输出流，但担心写入时的能量冲击。人们一直在考虑这个新的缓冲区设计，并认为高效的后台保存是构建它的一个很好的初始动机。

　　出于崩溃恢复的目的，人们只关心新的缓冲区表示方式提供的未保存的更改。现在，不用写出缓冲区的全部内容，而是将所有未完成的层组合成一个patch，并将其序列化为磁盘以及基本文本的摘要。人们正在编写的数据量随着更改次数的增加而不再担心文件的大小，从而在大多数情况下效率更高。对于几十兆字节的未保存更改的文件，还有一些工作要做，但是这些情况是相当罕见的。

　　异步保存

　　在Atom1.19之前的版本中，在Atom中保存缓冲区是一个同步操作。这是因为在创建Electron工具之前编写文件的代码路径，以及在那些从基于浏览器的桌面应用程序执行异步I/O的时候并不像现在这样简单。如今，这个新的缓冲区实现让人们有机会以优雅的方式来解决这个问题。将缓冲区的内容从UTF-16转换为用户所需的编码，并将其写入磁盘，现在完全用C ++在后台线程上执行。在开始保存之前，创建一个快照，这样用户即使在保存速度较慢时也可以进行额外的更改，比如使用网络驱动器时。

　　在背景中自动完成子序列匹配

　　在默认情况下，Atom的自动完成系统会根据与光标前面的字符的子序列匹配来建立来自开放缓冲区的单词。例如，bna |将会产生banana, bandaid, bandana等建议。然后，根据表示匹配质量的分数对建议进行排序。

　　在Atom 1.22版本之前，是通过为每个缓冲区维护唯一的单词列表并在主线程上运行JavaScript来匹配、分数和排序建议来实现此功能。虽然这对大多数文件来说都是可行的，但随着文件大小的增加，单词列表开始消耗严重的内存，主线程上的匹配建议可能会对用户接口(UI)造成明显的阻碍。

　　由于新的缓冲区实现，在Atom 1.22之后推出了一个新的自动完成提供程序，它利用快照来执行相同的作业，没有内存开销，也不会对Atom的响应性产生威胁。现在，大部分任务繁重的升级都是以核心中的一个新的textbuffer.findwordswithsubsequence(文本缓冲区查找带有子序列的单词)方法执行的，该方法在后台线程中执行匹配，评分和排序。这意味着可以在每次按下按键之后可以立即开始搜索建议，而其他工作则在主线程上进行。到下一帧的时候，这些建议通常是可用的，但是当搜索它们时，不会拖延一帧。在极少的情况下，建议需要比一个计算时间更长的时间，将简单地将它们呈现在后续的框架中。

　　未来的回报

　　这种新的缓冲区意味着为未来的许多改进奠定了基础。在短期内，在工作线程中进行非阻塞读取的能力将有助于人们在许多领域提高响应能力，而其中许多领域还没有探索。

　　从长远来看，将缓冲区实现转换为C ++也为其他子系统的移植打下了基础。如今正在逐渐建立一个名为superstring的本地库，它实现了Atom核心的多个性能关键组件，如本文中描述的patch和文本存储数据结构。人们通过V8嵌入API与JavaScript通过JavaScript进行交互操作，但它还具有在Electron之外使用的Emscripten绑定。现在，与缓冲区关联的关键状态已经成为超级管道，人们可以逐步移植任何需要访问缓冲区内容的关键性代码路径。

　　需要明确的是，JavaScript的可接近性和灵活性是一个巨大的资产，所以人们会在C ++的原始性能交易之前总是慎重考虑，但是这篇博文表明，JavaScript的限制不代表所提供的表现出色的Atom也具有基本限制。