React 任务调度

React 任务池

不同的fiber任务有不同的优先级，为了用户体验，React需要先处理优先级高的任务。
为了存储这些任务，React中有两个任务池：

// Tasks are stored on a min heap
var taskQueue = []; // 存储立即要执行的任务
var timerQueue = [];  // 存储可以延迟执行的任务
1
2
3

源码中任务的初始结构：

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

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){
	const diff = a.sortIndex - b.sortIndex;
 return diff !== 0 ? diff : a.id - b.id;
}
1
2
3
4

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

完全二叉树

一颗深度为k的有n个节点的二叉树，对树中的节点按从上至下、从左至右的顺序进行编号，如果编号为i（1<=i <=n）的节点与满二叉树中的位置相同，则这颗二叉树称为完全二叉树。

最小堆

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

查

获取最小堆的堆顶值。

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

添加

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

export function push (heap, node) {
	const index = heap.length;
	heap.push(node);
	siftUp(heap, node, index);
}
1
2
3
4
5

向上调整最小堆：

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 {
			// 已经符合
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17