React源码解析系列（九）------ schedule优先级
前言
在React中，初次渲染，还有改变状态引起的调度更新等都视为一个大任务，这些大任务的本质都是为了构建视图，也就是构建新的fiber，再结合之前的讲fiber的概念时，我们就可以知道fiber就是任务的最小单元了，也就是最小的任务了，而本文的schedule优先级，就主要是将这些任务是排队的。毕竟React在同一时间接收到的任务是很多的，如果没有一个合理的执行顺序，那必定会乱套的。
前置知识
schedule优先级，翻译过来也就是调度优先级，那么这些调度优先级是怎样的一个规则呢？
无论是构建fiber树或者是挂载/卸载副作用等操作都会调用schedule，构建fiber树等操作都会按优先级存放到一个最小堆中，浏览器工作的每一帧中，React都会向浏览器申请5ms的时间去执行最小堆中的任务。
最小堆
上面这段话就引出了关键，那就是最小堆。最小堆是一种经过排序的完全二叉树，其中任意非终端节点数值均不大于其左子节点和右子节点的值。如果满足最小堆的要求，那堆顶元素就是整个序列中的最小的元素。
最小堆的数据形式
可以将最小堆看成一个排好序的数组，比如我们一个符合最小堆的数组为[1, 2, 3, 4, 5, 6, 7]，那么他就长下图👇这样
最小堆是怎么工作的呢？他如何保证堆顶元素必定是最小的。主要分为两点：
- 如果是要向数组添加元素，在添加元素后进行一个向上调整（向上调整具体步骤请看下文）
- 如果是要讲堆顶元素取出来，那么就要讲堆顶元素和堆底元素进行换位，然后弹出堆底元素，再依据堆顶元素进行向下调整（向下调整具体步骤请看下文）
向上调整
我们先来看向上调整。假设我们现在有一个最小堆长这样：[1, 2, 4, 7, 10, 15, 16, 17, 20, 24, 21, 23, 25, 26]。
不必诧异为什么最后一排橙色的元素没有从小到大排序，因为最小堆不需要向左或向右调整，只要父节点比两个子字节大就是了，所以在同一层中，无序的情况是很正常的。
此时，假设有一个元素3进入到了堆中[1, 2, 4, 7, 10, 15, 16, 17, 20, 24, 21, 23, 25, 26, 3]，现在有新元素进来了，那么我们按照前面所说的，进行向上调整。
根据概念，我们要保证父节点比子节点小，那么向上调整其实就是和父节点比较大小，如果小于父节点，那么两者换位。
走完上面两步之后，3和1再1比较大小，1小，所以就结束了向上调整，那么此时的最小堆就是[1, 2, 3,, 7, 10, 15, 4, 17, 20, 24, 21, 23, 25, 16]。
向下调整
我们继续拿上面的例子演示向下调整，在加入元素3之后，我们现在要取出堆顶元素（也就是1）。按照上面说的步骤，那么我们先将元素1和元素16进行换位，然后将元素1 pop出来，接着进行向下调整。
所谓的向下调整就是将要调整的元素和较小子元素进行比较，如果子元素比较小，那么两者换位。
最后16和17还有20比较大小，16比较小，所以就不用动了，此时最小堆为：[2, 7, 3, 16, 10, 15, 4, 17, 20, 24, 21, 23, 25, 26]
以上就是最小堆的图文解说，下面给出代码实现。
/**
* 向最小堆里添加一个节点
* @date 2023-04-05
* @param {any} heap 最小堆
* @param {any} node 节点
* @returns {any}
*/
function push(heap, node) {
// 获取元素的数量
const index = heap.length;
// 先把获取到的元素放在数组的尾部
heap.push(node);
// 向上调整到合适的位置
siftUp(heap, node, index);
}
/**
* 查看最小堆顶的元素
* @date 2023-04-05
* @param {any} heap
* @returns {any}
*/
function peek(heap) {
const first = heap[0];
return first === undefined ? null : first;
}
/**
* 弹出最小堆顶元素
* @date 2023-04-05
* @param {any} heap
* @returns {any}
*/
function pop(heap) {
// 去除数组中的第一个（堆顶元素）
const first = heap[0];
if (first !== undefined) {
// 弹出数组中的最后一个元素
const last = heap.pop();
if (last !== first) {
heap[0] = last;
siftDown(heap, last, 0);
}
}
}
/**
* 向上调整某个节点，使其位于正确的位置
* @date 2023-04-05
* @param {any} heap 最小堆
* @param {any} node 节点
* @param {any} i 节点所在的索引
* @returns {any}
*/
function siftUp(heap, node, i) {
let index = i;
while (true) {
// 获取父节点的索引
const parentIndex = index - 1 >>> 1;
// 获取父节点
const parent = node[parentIndex];
// 如果父节点存在且父节点比子节点要大
if (parent !== undefined && compare(parent, node) > 0) {
// 把儿子的值给父索引
heap[parentIndex] = node;
// 把父亲的值给子索引
heap[index] = parent;
// 让index等于父亲的索引
index = parentIndex;
} else {
// 如果子节点比父节点要大就退出
return;
}
}
}
/**
* 向下调整某个节点，使其位于正确的位置
* @date 2023-04-05
* @param {any} heap 最小堆
* @param {any} node 节点
* @param {any} i 节点所在的索引
* @returns {any}
*/
function siftDown(heap, node, i) {
let index = i;
const length = heap.length;
while (index < length) {
// 左子节点的索引
const leftIndex = (index + 1) * 2 - 1;
const left = heap[leftIndex];
// 右子节点的索引
const rightIndex = leftIndex + 1;
const right = heap[rightIndex];
// 如果左子节点存在且左子节点比父节点要小
if (left !== undefined && compare(left, node) < 0) {
// 如果右节点存在且右节点比左节点要小，则父节点与右子节点交换位置
if (right !== undefined && compare(right, left) < 0) {
heap[index] = right;
heap[rightIndex] = node;
index = rightIndex;
} else {
// 否则就跟左子节点交换
heap[index] = left;
heap[leftIndex] = node;
index = leftIndex;
}
} else if (right !== undefined && compare(right, node) < 0) {
heap[index] = right;
heap[rightIndex] = node;
index = rightIndex;
} else {
return;
}
}
}
function compare(a, b) {
const diff = a.sortIndex - b.sortIndex;
return diff !== 0 ? diff : (a.id - b.id);
}
测试例子：
let heap = [];
let id = 1;
push(heap, { sortIndex: 1, id: id++ });
push(heap, { sortIndex: 2, id: id++ });
push(heap, { sortIndex: 3, id: id++ });
push(heap, { sortIndex: 4, id: id++ });
push(heap, { sortIndex: 5, id: id++ });
push(heap, { sortIndex: 6, id: id++ });
push(heap, { sortIndex: 7, id: id++ });
pop(heap)
console.log(peek(heap), heap);
结果：
MessageChannel
React调度任务的方式一般都是通过MessageChannel/setTimeout，setTimeou大家足够了解了，但MessageChannel可能会有些陌生。
MessageChannel就是一个消息管道，它有着两个端口，我们可以通过两个端口进行通信，其中一个端口通过portMessage传送消息，另一个端口通过onmessage事件接受消息。
<body>
<button class="btn">传送消息</button>
<script>
const btn = document.querySelector('.btn');
const channel = new MessageChannel();
const { port1, port2 } = channel;
btn.onclick = () => {
port1.postMessage({ msg: 'port2传送的消息' });
};
port2.onmessage = (e) => {
console.log(e.data);
};
</script>
</body>
schedule优先级
了解了最小堆之后，我们正式进入到schedule优先级，每次进行调度时，React会根据一些逻辑给此次的调度任务打上优先级（这部分下一篇lane优先级才讲，敬请期待）。在schedule优先级里，一共有5种优先级，这些优先级都是不同时间长度的过期时间。
var maxSigned31BitInt = 1073741823;
// Times out immediately 立刻过期
var IMMEDIATE_PRIORITY_TIMEOUT = -1;
// Eventually times out
var USER_BLOCKING_PRIORITY_TIMEOUT = 250;
// 正常优先级的过期时间
var NORMAL_PRIORITY_TIMEOUT = 5000;
// 低优先级的过期时间
var LOW_PRIORITY_TIMEOUT = 10000;
// Never times out 永远不过期，只要有别的优先级都能打断，仅在空闲的时候执行的任务
var IDLE_PRIORITY_TIMEOUT = maxSigned31BitInt;
之所以以时间作为优先级，这是为了避免一些进入堆时被贴上很低优先级的任务一直得不到执行的机会，因为时间一直在流逝，那么进入到堆中越早的任务，随着时间的流逝，他的过期时间也会越来越小，那么这些曾经低优先级的任务在某一刻之后也会成为非常高优先级的任务，从而获取到执行的机会。
最后，我们经过上述内容的讲解，可以得知，React的schedule优先级的完整样貌就是，当我们执行调度之后，会先对任务贴上一个过期时间作为优先级标识，然后push进最小堆中，再执行向上调整。而当React执行任务时，就会取出堆顶任务（过期时间最小）进行执行，然后执行向下调整。下面附上schedule优先级的流程图。
结尾
本文我们讲解了最小堆和MessageChannel，然后通过这两个知识点了解了React的schedule优先级是如何排队，执行任务的，总的来说是比较好理解的一部分，主要的知识点在于对最小堆的理解。那么，好了，本文就到此结束，下面会和惯例一样，附上截止至schedule为止的代码仓库和React18.2的完整源码。
仅包含至schedule的代码仓库：点这里
完整版源码：点这里
上一篇：context