从 V8 源码看 JS 数组排序的诡异问题

MkkHou 发布于2019-08-21 11:53 / 2030人阅读

摘要：前几天一个朋友在微信里面问我一个关于数组排序的问题。对数组的进行排序，然后把排完序的数组进行处理。翻译成编程术语就是排序算法是不稳定排序。因此第二个排序算法会把移动到最后，然后对剩余的数据进行排序。

前几天一个朋友在微信里面问我一个关于 JS 数组排序的问题。

原始数组如下：

var data = [
  {value: 4}, 
  {value: 2}, 
  {value: undefined}, 
  {value: undefined}, 
  {value: 1}, 
  {value: undefined}, 
  {value: undefined}, 
  {value: 7}, 
  {value: undefined}, 
  {value: 4}
];

data 是个数组，数组的每一项都是一个拥有 value 作为 key 的对象，值为数字或者 undefined。

data
  .sort((x, y) => x.value - y.value)
  .map(x => x.value);

对数组的 value 进行排序，然后把排完序的数组进行 flat 处理。得到的结果如下：

[2, 4, undefined, undefined, 1, undefined, undefined, 7, undefined, 4]

显然这没有达到我们的目的。

现在我们修改一下排序，挑战一下函数的调用顺序：先对数组进行扁平化(flat)处理，然后再排序。

data
  .map(x => x.value)
  .sort((x, y) => x - y)

这时我们得到的结果和之前截然不同：

[1, 2, 4, 4, 7, undefined, undefined, undefined, undefined, undefined]

遇到这种情况第一感觉肯定是要去看看 ECMA 规范，万一是 JS 引擎的 bug 呢。

在 ES6 规范 22.1.3.24 节写道：

Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments. Furthermore, Type(v) is Number, and v is not NaN. Note that this implies that exactly one of a < b, a = b, and a > b will be true for a given pair of a and b.

简单翻译一下就是：第二个参数 comparefn 返回一个数字，并且不是 NaN。一个注意事项是，对于参与比较的两个数 a 小于 b、a 等于 b、a 大于 b 这三种情况必须有一个为 true。

所以严格意义上来说，这段代码是有 bug 的，因为比较的结果出现了 NaN。

在 MDN 文档上还有一个细节：

如果 comparefn(a, b) 等于 0， a 和 b 的相对位置不变。备注：ECMAScript 标准并不保证这一行为，而且也不是所有浏览器都会遵守。

翻译成编程术语就是：sort 排序算法是不稳定排序。

其实我们最疑惑的问题上，上面两行代码为什么会输出不同的结果。我们只能通过查看 V8 源码去找答案了。

V8 对数组排序是这样进行的：

如果没有定义 comparefn 参数，则生成一个（高能预警，有坑啊）：

comparefn = function (x, y) {
  if (x === y) return 0;
  if (%_IsSmi(x) && %_IsSmi(y)) {
    return %SmiLexicographicCompare(x, y);
  }
  x = TO_STRING(x);   // <----- 坑
  y = TO_STRING(y);   // <----- 坑
  if (x == y) return 0;
  else return x < y ? -1 : 1;
};

然后定义了一个插入排序算法：

function InsertionSort(a, from, to) {
  for (var i = from + 1; i < to; i++) {
    var element = a[i];
    for (var j = i - 1; j >= from; j--) {
      var tmp = a[j];
      var order = comparefn(tmp, element);
      if (order > 0) {   // <---- 注意这里
        a[j + 1] = tmp;
      } else {
        break;
      }
  }
  a[j + 1] = element;
}

为什么是插入排序？V8 为了性能考虑，当数组元素个数少于 10 个时，使用插入排序；大于 10 个时使用快速排序。

后面还定义了快速排序函数和其它几个函数，我就不一一列出了。

函数都定义完成后，开始正式的排序操作：

// %RemoveArrayHoles returns -1 if fast removal is not supported.
var num_non_undefined = %RemoveArrayHoles(array, length);

if (num_non_undefined == -1) {
  // There were indexed accessors in the array.
  // Move array holes and undefineds to the end using a Javascript function
  // that is safe in the presence of accessors.
  num_non_undefined = SafeRemoveArrayHoles(array);
}

中间的注释：Move array holes and undefineds to the end using a Javascript function。排序之前会把数组里面的 undefined 移动到最后。因此第二个排序算法会把 undefined 移动到最后，然后对剩余的数据 [4,2,1,7,4] 进行排序。

而在第一种写法时，数组的每一项都是一个 Object，然后最 Object 调用 x.value - y.value 进行计算，当 undefined 参与运算时比较的结果是 NaN。当返回 NaN 时 V8 怎么处理的呢？我前面标注过，再贴一次：

var order = comparefn(tmp, element);
if (order > 0) {  // <---- 这里
  a[j + 1] = tmp;
} else {
  break;
}

NaN > 0 为 false，执行了 else 分支代码。

思考题，以下代码的结果：

[1, 23, 2, 3].sort()

扫码二维码关注我的公众号

云服务器 GPU云服务器加皮肤后的诡异问题 js v8源码解读 JS数组排序 js 数组数据排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/87238.html

2017-08-13 前端日报

摘要：前端日报精选从源码看数组排序的诡异问题显示网格和隐式网格的区别打包工具完全入门指南使用之前要在里学的件事工作机制第部分中文深入理解中的代码片段，你能猜对几个掘金深入理解笔记中的类深入理解笔记迭代器和生成器最新版构建分享小王子 2017-08-13 前端日报精选从 V8 源码看 JS 数组排序的诡异问题显示网格和隐式网格的区别JS打包工具rollup——完全入门指南使用 Redux ...

Eastboat 2019-08-21 11:54 评论0 收藏0
JavaScript专题之解读 v8 排序源码

摘要：插入排序是稳定的算法。所以准确的说，当数组长度大于的时候，采用了快速排序和插入排序的混合排序方法。在对数组进行了一次快速排序后，然后对两个子集分别进行了插入排序，最终修改数组为正确排序后的数组。 JavaScript 专题系列第二十篇，也是最后一篇，解读 v8 排序源码前言 v8 是 Chrome 的 JavaScript 引擎，其中关于数组的排序完全采用了 JavaScript 实...

princekin 2019-08-21 17:07 评论0 收藏0
JavaScript专题之乱序

摘要：源码地址为了简化篇幅，我们对这个数组进行分析，数组长度为，此时采用的是插入排序。插入排序的源码是其原理在于将第一个元素视为有序序列，遍历数组，将之后的元素依次插入这个构建的有序序列中。 JavaScript 专题系列第十九篇，讲解数组乱序，重点探究 Math.random() 为什么不能真正的乱序？乱序乱序的意思就是将数组打乱。嗯，没有了，直接看代码吧。 Math.random ...

I_Am 2019-08-21 17:00 评论0 收藏0
JavaScript专题系列20篇正式完结！

摘要：写在前面专题系列是我写的第二个系列，第一个系列是深入系列。专题系列自月日发布第一篇文章，到月日发布最后一篇，感谢各位朋友的收藏点赞，鼓励指正。写在前面 JavaScript 专题系列是我写的第二个系列，第一个系列是 JavaScript 深入系列。 JavaScript 专题系列共计 20 篇，主要研究日常开发中一些功能点的实现，比如防抖、节流、去重、类型判断、拷贝、最值、扁平、柯里...

sixleaves 2019-08-21 17:15 评论0 收藏0
控制台诡异录之展开与缩略不同

摘要：问题复现最近朋友发给我这样的一个串代码朋友说，这个输出不正确。我表示不信，就试了下从结果看，没毛病啊。朋友说，你展开看看，一看果然有问题缩略状态的显示与展开的显示不同问题思考这个问题的表现是缩略状态下显示原数组，展开状态下显示排序后的数组。问题复现最近朋友发给我这样的一个串代码： var arr = [1, 4, 2, 3 ]; console.log(arr); arr.sort...

opengps 2019-08-21 17:17 评论0 收藏0