跳到主要内容

V8-排序

背景​

在比较不同的排序算法时, 我们将它们的最差性能和平均性能, 看做是对内存访问或比较次数的渐进增长的约束.

在动态语言中, 比较操作通常比内存访问更加昂贵. 这是因为在排序时比较两个值通常涉及对用户代码的调用

客户代码理解为排序中引擎外的代码, 比如我们再用Array.prototype.sort一般会传入回调函数 [...].sort((a, b)=> a-b); 没有回调的情况也会有值处理，比如[1,'2']，在比较数字和字符串前，Javascript会做类型转换。

示例:

const array = [4, 2, 5, 3, 1];

function compare(a, b) {
 // 任意代码, 例如 `array.push(1);`
 return a - b;
}

// 一个“典型的”sort调用
array.sort(compare);

排序之前​

V8在实际的排序之前有两个预处理步骤

首先, 如果要排序的对象在原型链上有孔和元素, 会将它们从原型链上复制到对象本身. 这样在后续的所有步骤中, 我们都不需要再关注原型链.

目前V8只会对非标准的JSArrays进行这样的处理, 而其他引擎对于标准的JSArrays也会进行这样的复制处理.

第二个步骤是去孔(hole). V8引擎会将排序范围中的所有元素都引动到对象的开头. 之后移动undefined. 这在某种程度上其实是规范所要求的, 因为规范要求引擎始终将undefined排序到最后.

历史​

Array.prototype.sort和TypedArray.prototype.sort都基于同一种用JavaScript编写的Quicksort实现。排序算法本身非常简单:

基础是一个Quicksort（快速排序），对于较短的数组（长度<10）则降级为插入排序（Insertion Sort）

当Quicksort在分治的处理中递归出长度小于10的子数组时，就使用插入排序。因为插入排序对于较短的数组更高效。主要是快排在递归的过程中有创建和销毁函数的开销.

对于选择合适的轴元素(pivot)对快排的性能由比较大的影响. V8采用了两种策略:

  • 找到数组中的第一个, 最后一个和'第三个'元素, 然后选择这个三个元素的中间值作为pivot. 对于较短数组, '第三个'元素就是中间元素
  • 对于较长的数组, 就从中抽出一个小数组进行排序, 并将排序后中位数作为上述计算中的"第三个"元素

快排的优先之一是: 它是就地排序, 内存开销少. 只有在处理大型数组的时候, 需要为选择的样本数组分配内存, 以及log(n)栈空间. 它的缺点是: 它是不稳定的排序算法, 并且在最坏情况下, 时间复杂度会降级到O(n^2).

V8 Torque​

CSA(CodeStubAssembler)是V8的一个组件, 它允许我们直接用C++编写级别的TurboFan IR, 后来用TurboFan的后端(编译器后端)将其合理结构的机器码.

CSA被大量应用于为js内置函数编写所谓的快速路径. 内置的快速路径版本通常检查某些特别的条件是否成立(例如原型链上没有元素, 没有访问器等), 然后使用更快, 更特殊优化的操作来实现内置函数的功能. 这可以使函数执行时间比通用版本高一个数量级.

CSA的缺点是它确实可以被认为是汇编语言. 流程控制使用明确的label和goto进行建模, 这使得在CSA中实现复杂算法时, 代码会变得难以阅读并且容易出错.

然后是V8 Torque. Torque是一种领域专用语言, 具有类似ts的语法, 目前使用CSA作为其唯一的编译目标. Torque允许开发者使用与CSA几乎相同层次的流程控制操作, 同时提供更高级别的构造, 例如while和for循环

用V8 Torque重写的第一个重要的内置函数式TypedArray # sort和Dataview. 这两者的重写都有另外的目的, 即向Torque开发人员反馈所需要的语言功能, 以及使用那些模式会可以更高效的编写内置函数.

将Array#sort迁移到Torque​

最初的版本基本上是js实现的直接搬运, 唯一的区别在于对较长的数组不进行小数组采样, 而是随机选择数组中的某个元素作为轴元素中的第三个元素.

这种方式运行的不错, 但是仍然使用快排, 所以依然是不稳定的. 接下来尝试使用了TimSort代替. 首先这是一个稳定的算法, 并提供一些很好的算法保证.

TimSort​

最早有Tim Peters在2002年开发的TimSort, 可以被认为是自适应的稳定的归并排序(Mergesort)的变种. 其实现细节比较复杂.

Mergesort是基于递归的, 而TimSort是以迭代进行的.

  1. TimSort从左到右迭代一个数组, 并寻找有所谓的__runs__.
  2. 一个run可以认为是已经排序的小数组, 也包括以逆向排序的, 因为这些数组可以简单的翻转就称为一个run.
  3. 在排序开始的时候, 算法会根据输入数组的长度, 确定一个run的最小长度.
  4. 如果Timsort无法在数组中找到满足这个最小长度的run, 则使用插入排序人为的生成一个run
  5. 找到的runs在一个栈中追踪, 这个栈会记录起始的索引位置和每个run的长度.
  6. 栈上的run会逐渐合并在一起, 直到只剩下一个排序号的run.
  7. 在确定合并那些run时, timsort会试图保持两方面的平衡:
    1. 希望尽早尝试合并, 因为这些run的数据很可能已经存在缓存中
    2. 希望尽可能晚的合并, 以利用数据中可能出现的某些特征.
  8. 为了实现这个平衡, Timsort遵循两个原则.

假设A, B和C是三个最顶级的runs:

  • |C| > |B| + |A|
  • |B| > |A|

这里的大于是指长度的比较

此时, A和B就会合并. 注意Timsort仅合并连续的run, 这是为了维持算法的稳定性, 否则大小相等的元素会在run中转移. 此外, 第一个原则确保了run的长度, 最慢也会以Fibonacci数列增长, 这样当我们知道数组的最大边界时, runs栈大小的上下界也可以确定了.

现在可以看出, 对于已经排好序的数组, 会以O(n)的时间内完完成排序, 因为这样的数组将只产生单个run, 不需要合并操作, 最坏的情况是O(n log n). 这样的算法性能参数, 以及Timsort天生的稳定性就是V8 sort的理由之一.

参考​