扒开V8引擎的源码,我找到了你们想要的前端算法

更新日期: 2019-08-05阅读: 2.3k标签: 源码

算法对于前端工程师来说总有一层神秘色彩,这篇文章通过解读V8源码,带你探索 Array.prototype.sort 函数下的算法实现。来,先把你用过的和听说过的排序算法都列出来:

  • 快速排序
  • 冒泡排序
  • 插入排序
  • 归并排序
  • 堆排序
  • 希尔排序
  • 选择排序
  • 计数排序
  • 桶排序
  • 基数排序

答题环节到了, sort 函数使用的以上哪一种算法?

如果你在网上搜索过关于 sort 源码的文章,可能会告诉你数组长度小于10用插入排序,否则用快速排序。

开始我也是这么认为的,可当我带着答案去 GitHub 验证的时候发现并非如此。

首先我并没有找到对应的 js 源码(文章说实现逻辑是用js写的),因为但新版本的V8源码已经修改,改用 V8 Torque 。 V8 Torque 是专门用来开发V8而创造的语言,语法类似TypeScript(再一次证明TypeScript的价值),它的编译器使用 CodeStubAssembler 转换成高效的汇编代码。

简单理解起来就是创造了一个类似TypeScript的高效的高级语言,这个语言的文件后缀是 tq 。

这里需要感谢 justjavac大神指点~

其次当我开始阅读源码的时候,并没有找到使用快速排序的代码,也没有找到判断数组长度的常数值10。

所有的证据表明,之前的源码解读文章很可能已经过时。

那么最新版本的 V8 用的是什么排序算法呢?


算法解读

V8引擎在xx版本之后就舍弃了快速排序,因为它不是稳定的排序算法,在最坏情况下,时间复杂度会降级到O(n^2)。

而是采用了一种混合排序的算法:TimSort。

这种功能算法最初用于Python语言中,严格地说它t不属于以上10种排序算法中的任何一种,属于一种混合排序算法:

在数据量小的子数组中使用 插入排序 ,然后再使用 归并排序 将有序的子数组进行合并排序,时间复杂度为 O(nlogn) 。

结合V8源码,具体实现步骤如下:

  1. 判断数组长度,小于2直接返回,不排序。
  2. 开始循环。
  3. 找出一个有序子数组,我们称之为“run”,长度为 currentRunLength 。
  4. 计算最小合并序列长度 minRunLength (这个值会根据数组长度动态变化,在32~64之间)。
  5. 比较 currentRunLength 和 minRunLength ,如果 currentRunLength >= minRunLength ,否则采用插入排序补足数组长度至 minRunLength ,将 run 压入栈 pendingRuns 中。
  6. 每次有新的 run 被压入 pendingRuns 时保证栈内任意3个连续的 run(run0, run1, run2)从下至上满足run0>run1+run2 && run1>run2 ,不满足的话进行调整直至满足。
  7. 如果剩余子数组为0,结束循环。
  8. 合并栈中所有 run,排序结束。


源码解读

源码路径

/thrid_party/v8/builtins/array-sort.tq

调用栈

1386 ArrayPrototypeSort
1403 ArrayTimSort
1369 ArrayTimSortImpl
1260 ComputeMinRunLength // 计算 minRunLength
// while循环 
1262 CountAndMakeRun // 计算当前 run 的长度
1267 BinaryInsertionSort // 用插入排序补足 run 长度
1274 MergeCollapse // 放入 pendingRuns 并根据需要进行调整
// 循环结束 
1281 MergeForceCollapse // 合并 pendingRuns 中所有 run

核心源码

tq语言虽然有些不一样,但如果有TypeScript基础的话阅读起来应该不成问题。

下面重点解读3个函数的源码:

// 在while循环之前调用,每次排序只调用一次,用来计算 minRunLength
macro ComputeMinRunLength(nArg: Smi): Smi {
  let n: Smi = nArg;
  let r: Smi = 0;

  assert(n >= 0);
  // 不断除以2,得到结果在 32~64 之间
  while (n >= 64) {
    r = r | (n & 1);
    n = n >> 1;
  }

  const minRunLength: Smi = n + r;
  assert(nArg < 64 || (32 <= minRunLength && minRunLength <= 64));
  return minRunLength;
}
// 计算第一个 run 的长度
macro CountAndMakeRun(implicit context: Context, sortState: SortState)(
    lowArg: Smi, high: Smi): Smi {
  assert(lowArg < high);
  // 这里保存的才是我们传入的数组数据
  const workArray = sortState.workArray;

  const low: Smi = lowArg + 1;
  if (low == high) return 1;

  let runLength: Smi = 2;

  const elementLow = UnsafeCast<JSAny>(workArray.objects[low]);
  const elementLowPred = UnsafeCast<JSAny>(workArray.objects[low - 1]);
  // 调用比对函数来比对数据
  let order = sortState.Compare(elementLow, elementLowPred);

  const isDescending: bool = order < 0 ? true : false;

  let previousElement: JSAny = elementLow;
  // 遍历子数组并计算 run 的长度
  for (let idx: Smi = low + 1; idx < high; ++idx) {
    const currentElement = UnsafeCast<JSAny>(workArray.objects[idx]);
    order = sortState.Compare(currentElement, previousElement);

    if (isDescending) {
      if (order >= 0) break;
    } else {
      if (order < 0) break;
    }

    previousElement = currentElement;
    ++runLength;
  }

  if (isDescending) {
    ReverseRange(workArray, lowArg, lowArg + runLength);
  }

  return runLength;
}
// 调整 pendingRuns ,使栈长度大于3时,所有 run 都满足 run[n]>run[n+1]+run[n+2] 且 run[n+1]>run2[n+2]
transitioning macro MergeCollapse(context: Context, sortState: SortState) {
    const pendingRuns: FixedArray = sortState.pendingRuns;

    while (GetPendingRunsSize(sortState) > 1) {
      let n: Smi = GetPendingRunsSize(sortState) - 2;

      if (!RunInvariantEstablished(pendingRuns, n + 1) ||
          !RunInvariantEstablished(pendingRuns, n)) {
        if (GetPendingRunLength(pendingRuns, n - 1) <
            GetPendingRunLength(pendingRuns, n + 1)) {
          --n;
        }
        MergeAt(n); // 将第 n 个 run 和第 n+1 个 run 进行合并
      } else if (
          GetPendingRunLength(pendingRuns, n) <=
          GetPendingRunLength(pendingRuns, n + 1)) {
        MergeAt(n); // 将第 n 个 run 和第 n+1 个 run 进行合并
      } else {
        break;
      }
    }
  }


总结

下次面试前端岗位的时候,如果面试官问你算法题,你可以莞尔一笑地问他/她:知道 Array 的 sort 函数使用了什么算法吗?TimSort要不要了解一下?

当然如果因此搞得面试官难堪而导致拿不到offer可别怪作者~

原文 http://yalishizhude.github.io/2019/09/05/v8-sort/


链接: https://www.fly63.com/article/detial/5164

Js中的 forEach 源码

在日常 Coding 中,码农们肯定少不了对数组的操作,其中很常用的一个操作就是对数组进行遍历,查看数组中的元素,然后一顿操作猛如虎。今天暂且简单地说说在 JavaScript 中 forEach。

微信小程序代码源码案例大全

克隆项目代码到本地(git应该都要会哈,现在源码几乎都会放github上,会git才方便,不会的可以自学一下哦,不会的也没关系,gitHub上也提供直接下载的链接);打开微信开发者工具;

Node 集群源码初探

随着这些模块逐渐完善, Nodejs 在服务端的使用场景也越来越丰富,如果你仅仅是因为JS 这个后缀而注意到它的话, 那么我希望你能暂停脚步,好好了解一下这门年轻的语言,相信它会给你带来惊喜

Vue源码之实例方法

在 Vue 内部,有一段这样的代码:上面5个函数的作用是在Vue的原型上面挂载方法。initMixin 函数;可以看到在 initMixin 方法中,实现了一系列的初始化操作,包括生命周期流程以及响应式系统流程的启动

vue源码解析:nextTick

nextTick的使用:vue中dom的更像并不是实时的,当数据改变后,vue会把渲染watcher添加到异步队列,异步执行,同步代码执行完成后再统一修改dom,我们看下面的代码。

React源码解析之ReactDOM.render()

React更新的方式有三种:(1)ReactDOM.render() || hydrate(ReactDOMServer渲染)(2)setState(3)forceUpdate;接下来,我们就来看下ReactDOM.render()源码

React源码解析之ExpirationTime

在React中,为防止某个update因为优先级的原因一直被打断而未能执行。React会设置一个ExpirationTime,当时间到了ExpirationTime的时候,如果某个update还未执行的话,React将会强制执行该update,这就是ExpirationTime的作用。

jQuery源码之extend的实现

extend是jQuery中一个比较核心的代码,如果有查看jQuery的源码的话,就会发现jQuery在多处调用了extend方法。作用:对任意对象进行扩;’扩展某个实例对象

vuex源码:state及strict属性

state也就是vuex里的值,也即是整个vuex的状态,而strict和state的设置有关,如果设置strict为true,那么不能直接修改state里的值,只能通过mutation来设置

webpack 源码从零开始:apable模型

最近在看webpack的源码,发现有个比较头疼的点是:代码看起来非常跳跃,往往看不到几行就插入一段新内容,为了理解又不得不先学习相关的前置知识。层层嵌套之后,发现最基础的还是tapable模型,因此先对这部分的内容做一个介绍。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!