Open astak16 opened 1 year ago
根据任务的开始时间(startTime
)和当前时间(currentTime
)来判断是否是延迟任务
timerQueue
中,并根据任务的开始时间来安排一个定时器来执行任务;taskQueue
中,并根据任务的过期时间来安排一个回调函数来执行任务如果任务的开始时间大于当前时间,说明任务还没有到达执行的时间,需要等待一段时间。(因为立即执行的任务开始 timeout
是 -1
)
对于延迟任务,排序索引就是开始时间(升序排序)(排序索引:newTask.sortIndex = startTime
)
timerQueue
队列中(push(timerQueue, newTask)
)requestHostTimeout(handleTimeout, startTime - currentTime)
是设置一个定时器,在 startTime - currentTime
这么长的时间后执行 handleTimeout
这个函数,它会从 timerQueue
中取出最紧急的延迟任务并执行它。对于非延迟任务,排序索引就是过期时间(升序排列)(排序索引:newTask.sortIndex = expirationTime
)
taskQueue
队列中(push(taskQueue, newTask)
)isHostCallbackScheduled = true
是标记已经安排了一个回调函数。requestHostCallback(flushWork)
是安排一个回调函数,在浏览器空闲时执行 flushWork
这个函数,它会从 taskQueue
中取出最紧急的非延迟任务并执行它。
timerQueue
:是用来存放延迟任务的,也就是那些还没有到达执行时间的任务。它们会在定时器触发后被执行taskQueue
:是用来存放非延迟任务的,也就是那些可以立即执行的任务。它们会在浏览器空闲时被执行
根据任务的 sortIndex
优先级,安排任务的执行顺序
timerQueue
:sortIndex
是 startTime
taskQueue
:sortIndex
是 expirationTime
timerQueue
和 taskQueue
队列是个最小堆,每次取出堆顶的任务执行
如何保证元素添加到堆中后,能够快速放到合适的位置呢?
一个元素的父节点的索引,就是那个元素的索引除以 2
,向下取整
由于这里使用数组存放二叉堆,所以元素索引的方式:(index - 1) >>> 1
index - 1
的作用是对应数组的索引,因为数组的索引是从 0
开始的遍历条件通过判断父元素索引是否大于 0
来实现最少遍历次数
比如说当前的索引是 12
,要在 12
后面插入一个新的元素:
11 -> 5
5 -> 2
2 -> 1
通过三次遍历就能找到将一个元素放合适位置了
function push<T: Node>(heap: Heap<T>, node: T): void {
const index = heap.length;
heap.push(node);
siftUp(heap, node, index);
}
function siftUp<T: Node>(heap: Heap<T>, node: T, i: number): void {
let index = i;
while (index > 0) {
const parentIndex = (index - 1) >>> 1;
const parent = heap[parentIndex];
if (compare(parent, node) > 0) {
// The parent is larger. Swap positions.
heap[parentIndex] = node;
heap[index] = parent;
index = parentIndex;
} else {
// The parent is smaller. Exit.
return;
}
}
}
react
从堆中取去一个元素有两种方法:
peek
pop
这两个函数的区别是:
peek
方法只是取出堆顶的元素,不会删除堆顶的元素pop
方法会删除堆顶的元素,并且重新安排堆的结构(最小堆)这里主要看 pop
是如何实现的
删除堆顶元素后,pop
将最后一个元素放到堆顶,然后调用 siftDown
方法,重新安排最小堆
从根元素开始,比较根元素和左右子元素的大小,如果根元素比左右子元素都大,那么就交换根元素和左右子元素中较小的那个元素的位置
一个元素的子节点的索引:
left = index * 2
right = left + 1
因为这里采用的是用数组存放二叉堆,所以元素索引的方式:
left = (index + 1) * 2 - 1
right = left + 1
这里为什么用 length >>> 1
,是因为非叶子节点的个数恰好等于 length / 2
向下取整
遍历条件通过判断父元素索引是否小于 length / 2
来实现最少遍历次数
比如说当前的 length
是 13
,要取出堆顶元素
index = 0
, length = 12
, halfLength = 6
leftIndex = 1
, rightIndex = 2
left
比 node
小, index = 1
index = 1
, length = 12
, halfLength = 6
leftIndex = 3
, rightIndex = 4
left
比 node
小, index = 3
index = 3
, left = 12
, halfLength = 6
leftIndex = 7
, rightIndex = 8
left
比 node
小, index = 7
index = 7
, left = 24
, halfLength = 6
,循环结束通过三次遍历就能找到将一个元素放合适位置了
function pop<T: Node>(heap: Heap<T>): T | null {
if (heap.length === 0) {
return null;
}
const first = heap[0];
const last = heap.pop();
if (last !== first) {
heap[0] = last;
siftDown(heap, last, 0);
}
return first;
}
function siftDown<T: Node>(heap: Heap<T>, node: T, i: number): void {
let index = i;
const length = heap.length;
const halfLength = length >>> 1;
while (index < halfLength) {
const leftIndex = (index + 1) * 2 - 1;
const left = heap[leftIndex];
const rightIndex = leftIndex + 1;
const right = heap[rightIndex];
// If the left or right node is smaller, swap with the smaller of those.
if (compare(left, node) < 0) {
if (rightIndex < length && compare(right, left) < 0) {
heap[index] = right;
heap[rightIndex] = node;
index = rightIndex;
} else {
heap[index] = left;
heap[leftIndex] = node;
index = leftIndex;
}
} else if (rightIndex < length && compare(right, node) < 0) {
heap[index] = right;
heap[rightIndex] = node;
index = rightIndex;
} else {
// Neither child is smaller. Exit.
return;
}
}
}
compare
函数的实现如下:
sortIndex
是任务的优先级,id
是任务的唯一标识id
compare(a, b) > 0
说明 a
任务的优先级更高,b
任务的优先级更低,反之亦然。
function compare(a: Node, b: Node) {
// Compare sort index first, then task id.
const diff = a.sortIndex - b.sortIndex;
return diff !== 0 ? diff : a.id - b.id;
}
用数组存储最小堆,一共需要遍历多少次,可以通过 Math.floor(Math.log2(length - 1))
计算
这个变量的作用是保证调度器的稳定和效率,避免不必要的重复或者中断
在调用 flushWork
函数之前,先把 isHostCallbackScheduled
置为 true
,然后再 flushWork
调用时将 isHostCallbackScheduled
设置为 false
如果在 flushWork
函数执行过程中, requestHostCallback
函数被调用了,requestHostCallback
调用说明有新的任务被安排了,那么就需要检查当前是否有任务在执行中
如果有,就不会安排新的任务(超时函数触发、其他新的任务),而是等待当前任务执行完毕后再安排(等待 flushWork
执行完毕)
延迟任务调度:requestHostTimeout(handleTimeout, startTime - currentTime)
执行逻辑:
requestHostCallback(flushWork)
执行任务requestHostTimeout(handleTimeout, firstTimer.startTime - currentTime)
设置延迟任务总结来说延迟任务的执行逻辑就是:如果任务列表中有任务,执行任务,如果没有,判断延迟队列中是否有任务,如果有,设置延迟任务
function handleTimeout(currentTime: number) {
isHostTimeoutScheduled = false;
advanceTimers(currentTime);
if (!isHostCallbackScheduled) {
if (peek(taskQueue) !== null) {
isHostCallbackScheduled = true;
requestHostCallback(flushWork);
} else {
const firstTimer = peek(timerQueue);
if (firstTimer !== null) {
requestHostTimeout(handleTimeout, firstTimer.startTime - currentTime);
}
}
}
}
非延迟任务调度:requestHostCallback(flushWork)
由宿主回调函数调用(requestHostCallback
),内部调用 workLoop
函数,workLoop
函数会根据任务的优先级和过期时间,以及浏览器的空闲时间,决定是否继续执行下一个任务,还是暂停执行并交还控制权给浏览器
function flushWork(hasTimeRemaining: boolean, initialTime: number) {
isHostCallbackScheduled = false;
if (isHostTimeoutScheduled) {
isHostTimeoutScheduled = false;
cancelHostTimeout();
}
isPerformingWork = true;
const previousPriorityLevel = currentPriorityLevel;
try {
return workLoop(hasTimeRemaining, initialTime);
} finally {
currentTask = null;
currentPriorityLevel = previousPriorityLevel;
isPerformingWork = false;
}
}
wookLoop
函数在浏览器空闲时执行 taskQueue
具体逻辑如下:
第一个条件判断:当前的任务,如果任务的过期时间大于当前时间,并且没有剩余的时间或者应该让出控制权,就跳出循环(注释 ①)
如果任务没有过期,并且还有剩余时间(或者不需要让出控制权),它会执行当前任务的回调函数,并传入一个布尔值表示是否超时(注释 ②)
如果回调函数返回了一个新的函数,说明当前任务还没有完成,需要继续执行,那么它会把新的函数赋值给当前任务的回调,并返回 true
表示还有未完成的任务(注释 ③)
如果回调函数没有返回新的函数,说明当前任务已经完成,那么它会从任务队列中移除当前任务(注释 ④)
最后,重复上述步骤,直到任务队列为空或者遇到需要暂停或者让出的情况
function workLoop(hasTimeRemaining: boolean, initialTime: number) {
let currentTime = initialTime;
advanceTimers(currentTime);
currentTask = peek(taskQueue);
while (
currentTask !== null &&
!(enableSchedulerDebugging && isSchedulerPaused)
) {
if (
// ① 表示当前任务过期时间大于当前时间
currentTask.expirationTime > currentTime &&
// hasTimeRemaining 表示有没有剩余时间
// shouldYidldToHost() 表示需要让出给主机
(!hasTimeRemaining || shouldYieldToHost())
) {
break;
}
// 任务没有过期并且还有剩余时间(或者不需要让出控制权)
const callback = currentTask.callback;
if (typeof callback === "function") {
// 将当前任务的回调函数清空
currentTask.callback = null;
// 设置当前的优先级
currentPriorityLevel = currentTask.priorityLevel;
// 任务是否超时
const didUserCallbackTimeout = currentTask.expirationTime <= currentTime;
// ② 执行当前任务回调函数传入是否超时,并返回一个函数
const continuationCallback = callback(didUserCallbackTimeout);
currentTime = getCurrentTime();
// ③ 如果返回了一个函数,说明当前任务还没有完成,需要继续执行
if (typeof continuationCallback === "function") {
currentTask.callback = continuationCallback;
advanceTimers(currentTime);
return true;
} else {
// ④ 没返回函数,说明当前任务已经完成,从任务队列中移除
if (currentTask === peek(taskQueue)) {
pop(taskQueue);
}
advanceTimers(currentTime);
}
} else {
// 如果任务没有回到函数,就从任务队列中移除
pop(taskQueue);
}
currentTask = peek(taskQueue);
}
}
timerQueue
队列是用来存放延时任务的
非延迟队列 taskQueue
的优先级比较高,如果一直在执行这个任务队列,可能会导致 timerQueue
中的任务过期
react 通过 advanceTimers
函数,将过期任务从 timerQueue
中取出,放入 taskQueue
中
第一个条件判断 timer.callback === null
,说明这个任务已经被取消了,就用 pop
函数把它从 timerQueue
中移除
第二个条件判断 timer.startTime <= currentTime
,说明这个任务已经可以开始执行了,就用 pop
函数把它从 timerQueue
中移除,并把它的 sortIndex
设置为 expirationTime
,然后用 push
函数把它加入到 taskQueue
中
function advanceTimers(currentTime: number) {
let timer = peek(timerQueue);
while (timer !== null) {
if (timer.callback === null) {
pop(timerQueue);
} else if (timer.startTime <= currentTime) {
pop(timerQueue);
timer.sortIndex = timer.expirationTime;
push(taskQueue, timer);
} else {
return;
}
timer = peek(timerQueue);
}
}
延时任务调度使用 requestHostTimeout
,非延时任务调度使用 requestHostCallback
requestHostTimeout
它设置了一个回调函数在指定的延迟时间后被调用,用于在一定的时间过去后安排一个回调函数requestHostCallback
它设置了一个回调函数在浏览器下一个帧被调用,用于在下一帧安排一个回调函数这函数就是一个 setTimeout
,在延时时间后执行 callback
const requestHostTimeout = (callback, ms) => {
return setTimeout(() => {
callback(getCurrentTime());
}, ms);
};
执行过程:
requestHostCallback
执行时,调用 schedulePerformWorkUntilDeadline
schedulePerformWorkUntilDeadline
被调用了,会执行 port2.postMessage(null)
port2.postMessage
执行时, port1.onmessage
将会被调用port1.onmessage
函数体是 performWorkUntilDeadline
,所以 performWorkUntilDeadline
会被执行react
为什么使用使用 MessageChannel
而不是 setTimeout
?(setTimeout
是个托底方案)
setTimeout
是基于时间的,如果浏览器被挂起(例如,当用户切换到其他标签或最小化窗口时),setTimeout
也会被挂起,而 MessageChannel
不会setTimeout
的精度也不够,可能存在一定的误差setTimeout
会产生很多的定时器,从而影响性能源码简化:
let scheduledHostCallback = null;
let schedulePerformWorkUntilDeadline;
const performWorkUntilDeadline = () => {
if (scheduledHostCallback !== null) {
const hasMoreWork = scheduledHostCallback();
if (hasMoreWork) {
schedulePerformWorkUntilDeadline();
}
}
};
const channel = new MessageChannel();
const port = channel.port2;
channel.port1.onmessage = performWorkUntilDeadline;
schedulePerformWorkUntilDeadline = () => {
port.postMessage(null);
};
const requestHostCallback = (callback) => {
scheduledHostCallback = callback;
schedulePerformWorkUntilDeadline();
};
task(任务)
task 是
react
中的一个任务,它有下面几个属性:id
: 使用的是一个全局变量taskIdCounter
,每次创建任务的时候都会自动加一,用于区分不同的任务callback
:一个函数,表示要执行的任务,它会在调度器安排好时间后被调用priorityLevel
:优先级,会影响任务何时被执行,有五种:ImmediatePriority
、UserBlockingPriority
、IdlePriority
、LowPriority
和NormalPriority
startTime
:任务开始时间,它是使用getCurrentTime
函数获取的微秒级别的当前时间expirationTime
:任务过期的时间,它是根据startTime
和priorityLevel
计算出来的。过期时间越小,表示任务越紧急,越需要优先执行expirationTime
的计算公式为:startTime + timeout
,timeout
的值取决于priorityLevel
,它们的对应关系如下:ImmediatePriority
:-1
(立即执行)UserBlockingPriority
:250
(250ms
后执行)NormalPriority
:5000
(5s
后执行)LowPriority
:10000
(10s
后执行)IdlePriority
:1073741823
(1073741.823s
后执行)react
这么设计是因为expirationTime
的值越小,表示任务越紧急,越需要优先执行sortIndex
:任务在队列中的排序索引,默认为-1
。它实际上会被设置成startTime
或expirationTime
,以便在插入队列时按照升序排列isQueued
:任务是否已经被加入到队列中。这个属性是为了避免重复插入或删除任务而设置的