带你彻底读懂React任务调度以及背后的算法

前端bubucuo

发布于 2022-09-16 17:44:19

4910

发布于 2022-09-16 17:44:19

文章被收录于专栏：bubucuobubucuo

小思考

刚刚遇到小明，问了他一个问题: 给你一个数字数组，找出最小的数字，怎么整？

小明：Array.sort！

我：如果这个数组是动态的，每次我都要找最小值，找到之后就从数组里删除这个元素，然后下次还想找最小值，怎么整。并且这个过程中，还会不断有新的数字插入数组。

小明：Array.sort！

我：可是数组是动态的，每次sort，但是我只要最小值，你浪费那么多时间把第二和第一万都排那么准确，不觉得在浪费时间吗？

小明：好像确实是浪费时间。可能是个算法吧，没做过。

React中的任务池

其实这不是个纯算法题，说回React，大家肯定听过React中有个fiber任务吧，而且不同的fiber任务有不同的优先级，为了用户体验，React需要先处理优先级高的任务。

为了存储这些任务，React中有两个任务池，源码中定义如下：

// Tasks are stored on a min heap
var taskQueue = [];
var timerQueue = [];

taskQueue与timerQueue都是数组，前者存储的是立即要执行的任务，而后者存的则是可以延迟执行的任务。

源码中任务的初始结构定义如下：

  var newTask = {
    id: taskIdCounter++, // 标记任务id
    callback, // 回调函数
    priorityLevel, // 任务优先级
    startTime, // 任务开始时间，时间点
    expirationTime, // 过期时间，时间点
    sortIndex: -1, // 任务排序，取值来自过期时间，因此值越小，优先级越高
  };

React中一旦来了新任务，就会先用currentTime记录当前时间(performance.now()或者Date.now())，如果任务有delay参数，那么任务开始执行时间startTime = currentTime + delay;。接下来通过startTime > currentTime如果成立，证明任务是可以延期的，那么任务进入timerQueue，否则进入taskQueue。

React中的任务调度

那么问题来了，怎么找到优先级最高的任务呢，以taskQueue为例，它是动态的任务池，数据形式上就是个数组。Array.sort可行，但不是最优方案，每次sort，平均时间复杂度高达nlog(n)。这个时候我们需要了解个数据结构：最小堆，也叫小顶堆。

当然可能有人问了，为什么不是最大堆呢？这是因为taskQueue的newTask中的排序用的是sortIndex，这个值取自过期时间expirationTime，也就意味着优先级越高的任务越需要立马执行，那么过期时间自然也就越小了，换句话说就是，优先级越高，过期时间越小。当然有可能两个任务的过期时间一样，那这个时候就要看是谁先进的任务池了，也就是newTask中的id嘛，每次来了新任务，id都会加1。因此React源码中任务比较优先级的函数如下：

function compare(a, b) {
  // Compare sort index first, then task id.
  const diff = a.sortIndex - b.sortIndex;
  return diff !== 0 ? diff : a.id - b.id;
}

其实用到最小堆，也就是把taskQueue做成最小堆的数据结构，然后执行任务的时候，取最小堆的最小任务，如果任务执行完毕，那么需要把这个任务从taskQueue中删除，并重新调整剩下的任务池，依然保证它是最小堆的数据结构。当然，往taskQueue中插入新任务的时候，也要调整taskQueue，保证新的任务池仍然是最小堆。

最小堆

了解最小堆之前，先来熟悉三个基本数据结构的概念：

二叉树

是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。

满二叉树

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。

从图形形态上看，满二叉树外观上是一个三角形。

如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

注意： 关于满二叉树定义这里，国内外定义有分歧，本文采用的是国内定义。满二叉树英文是Full Binary Tree，是指所有的节点的度只能是0或者2。

如下图，国外也认为是Full Binary Tree：

而对于我们本文所说的满二叉树，国外的概念叫完美二叉树。

完全二叉树

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。叶子结点只可能在最大的两层出现。

最小堆

是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于其左子节点和右子节点的值。

如对于上面这个最小堆来说，经过观察，对应的深度与数组下标分别是：

经过观察，发现父子节点下标关系如下：

根据子节点下标推算父节点下标：parentIndex = (childIndex - 1) >>> 1

根据父节点下标推算子节点下标：

leftIndex = (index +1 )2 - 1,

rightIndex = leftIndex + 1

至此，我们就可以尝试去实现最小堆的增(push)删(pop)查(peek)函数了：

peek

peek，瞄一下嘛，即获取最小堆的堆顶值。

export function peek(heap) { 
    return heap.length === 0 ? null : heap[0];
}

push

往最小堆中添加一个元素，因为taskQueue本身已经是最小堆，并且是数组存储，这时候为了尽可能多的复用原先的结构，我们可以先把新元素插入数组尾部，然后从下往上调整最小堆：

export function push(heap, node) {
  const index = heap.length;
  heap.push(node);
  siftUp(heap, node, index);
}

怎么从下往上调整呢？因为最小堆的典型特点就是父节点比左右子节点都小，那这时候除了尾部元素，其他都是满足这个特点的。这个时候我们只需要调整尾部元素以及和尾部元素的祖先就可以了，一直往上调整，直到不再需要调整为止。代码如下：

// 向上调整最小堆
function siftUp(heap, node, i) {
  let index = i;
  while (index > 0) {
    // 父节点下标
    const parentIndex = (index - 1) >>> 1;
    // 父节点
    const parent = heap[parentIndex];
    if (compare(parent, node) > 0) {
      // parent>node, 不符合最小堆
      heap[parentIndex] = node;
      heap[index] = parent;
      index = parentIndex;
    } else {
      // 已经符合最小堆，上面的祖先本身就是最小堆结构，因此停止调整
      return;
    }
  }
}

pop

删除堆顶元素。即React一个任务执行完了，那么肯定要把这个任务从任务池taskQueue中删除。问题来了，怎么删除呢，堆顶元素其实就是taskQueue[0]，这个位置我们肯定还是要用的，并且和push一样，为了尽可能复用原先的最小堆结构，我们可以采取一个办法：把最后一个元素覆盖堆顶元素，然后从堆顶往下调整最小堆。

export function pop(heap) {
  if (heap.length === 0) {
    return null;
  }
  const first = heap[0];
  const last = heap.pop();
  // 如果堆顶和堆尾元素不相等，证明现在的元素总数>1，需要往下调整
  if (first !== last) {
    heap[0] = last;
    siftDown(heap, last, 0);
  }

  return first;
}

关于往下调整，其实就是检查每个子堆的结构，确保最小值在父节点，不满足就交换父与左或者父与右，代码如下，我加了尽可能多的详细注释：

function siftDown(heap, node, i) {
  let index = i;
  const len = heap.length;
  const halfLen = len >>> 1;

  while (index < halfLen) {
    let leftIndex = (index + 1) * 2 - 1;
    let left = heap[leftIndex];
    let rightIndex = leftIndex + 1;
    let right = heap[rightIndex];
    // todo 比较parent与left与right的大小
    // 如果parent不是最小的，那就比较left和right谁最小，然后把最小的和parent交换位置
    // 如果parent是最小的，那就停止
    if (compare(left, node) < 0) {
      // left < parent
      // 为了保证根节点最小，比较left和right
      if (rightIndex < len && compare(right, left) < 0) {
        // right<left, right是最小的，交换parent和right
        heap[index] = right;
        heap[rightIndex] = node;
        index = rightIndex;
      } else {
        // right>left, left是最小的，交换parent和left
        heap[index] = left;
        heap[leftIndex] = node;
        index = leftIndex;
      }
    } else if (rightIndex < len && compare(right, node) < 0) {
      // left > parent
      //   检查right, right<parent
      heap[index] = right;
      heap[rightIndex] = node;
      index = rightIndex;
    } else {
      // parnent最小
      return;
    }
  }
}