The new scheduler
In the previous section, the Scheduler in act16.8 is implemented by requestAnimation and PostMessage, which aligns frames. According to the description of the official issue of React, the CPU utilization of the loop formed by requestAnimation in scheduler is lower than that of the loop formed by Message in the new version of Scheduler. In addition, you can also see react’s concerns about code quality through some issues.
Now the implementation of the new scheduler is started, and a running flow chart is roughly drawn. The following points need to be noted:
- TaskQueue and timerQueue are the two smallest heaps. The tasks of the latter are put to the taskQueue after a certain delay, and the tasks of the taskQueue are not executed until they expire.
- TimerQueue is sorted by current+delay, and taskQueue is sorted by current+ Delay +priorityTime
- The task must be moved from timerQueue to taskQueue after the delay
wookloopEach batch task is executed within the time range5mWithin s, one at a timetaskThe current is checked beforewookloopWhether execution has been exceeded5mstaskIf the expiration time is the same, the first to be added is executed first
tool
Get the current time
The quality of the code is in the details: instead of checking the presence of Performing.now in the function each time, getCurrentTime is replaced directly
var hasNativePerformanceNow =
typeof performance === 'object' && typeof performance.now === 'function';
var localDate = Date;
var getCurrentTime;
if (hasNativePerformanceNow) {
var Performance = performance;
getCurrentTime = function() {
return Performance.now();
};
} else {
getCurrentTime = function() {
return localDate.now();
};
}
Copy the codeDefine the time corresponding to the priority
Expected user interaction time: USER_BLOCKING_PRIORITY_TIMEOUT
const ImmediatePriority = 1;
const UserBlockingPriority = 2;
const NormalPriority = 3;
const LowPriority = 4;
const IdlePriority = 5;
const IMMEDIATE_PRIORITY_TIMEOUT = -1;
const USER_BLOCKING_PRIORITY_TIMEOUT = 250;
const NORMAL_PRIORITY_TIMEOUT = 5000;
const LOW_PRIORITY_TIMEOUT = 10000;
const IDLE_PRIORITY_TIMEOUT = 1073741823;
const priorityMap = {
[ImmediatePriority]: IMMEDIATE_PRIORITY_TIMEOUT,
[UserBlockingPriority]: USER_BLOCKING_PRIORITY_TIMEOUT,
[NormalPriority]: NORMAL_PRIORITY_TIMEOUT,
[LowPriority]: LOW_PRIORITY_TIMEOUT,
[IdlePriority]: IDLE_PRIORITY_TIMEOUT
}
Copy the codeA simple timer
function requestHostTimeout(callback, ms) {
taskTimeoutID = setTimeout(() => {
callback(getCurrentTime());
}, ms);
}
Copy the codeThe minimum heap
The minimum heap must be a complete binary tree, and the relationship between parent and child nodes in a complete binary tree is determined, so a minimum heap can be realized by arrays
The code is a bit long and I won’t show it here, so here are the main points:
-
Minimum heap: The value of a node in the minimum heap is the minimum of its subtree.
-
Math.floor((index – 1)/2); math.floor ((index – 1)/2);
-
Minimal heap insert element: Push the newly inserted element into the array, compare the newly inserted element to its parent, and swap the parent node if it is smaller. The newly inserted nodes are successively searched upward until no one matches the criteria.
-
Minimum heap removes minimum element: The last node is replaced by the first node, and then the first node is sunk (as long as the node is the minimum of its subtree).
Add tasks
The pseudocodes are as follows, and the received parameters are described as follows
- PriorityLevel: indicates the priority
- Delay: indicates the delay time of scheduling
- The callback: task
let taskIdCounter = 1;
function scheduleCallback(priorityLevel, callback, delay = 0) {
const currentTime = getCurrentTime();
let startTime = currentTime + delay;
let expirationTime = startTime + priorityMap[priorityLevel];
const newTask = {
id: taskIdCounter++,
callback,
priorityLevel,
startTime,
expirationTime,
sortIndex: -1};if (startTime > currentTime) {
newTask.sortIndex = startTime;
push(timerQueue, newTask);
if (peek(taskQueue) === null && newTask === peek(timerQueue)) {
// Before this, you need to cancel the previous timeout, so now is the minimum timer timerequestHostTimeout(handleTimeout, startTime - currentTime); }}else {
newTask.sortIndex = expirationTime;
push(taskQueue, newTask);
if(! isHostCallbackScheduled && ! isPerformingWork) { isHostCallbackScheduled =true; FlushWork () {flushWork () {flushWork () {flushWork () {flushWork ()requestHostCallback(flushWork); }}return newTask;
}
Copy the codeContext scheduleCallback constructs a heap node with expirationTime=currentTime+ Delay +priorityTime.
TaskQueue (currentTime+ Delay) and timerQueue (priorityTime
-
When delay>0 is received, a new heap is added to the timerQueue, and if taskQueue is empty and the new heap is the minimum, tasks in timerQueue and taskQueue are scheduled after delay.
-
When delay<=0 is received, a new heap is added to the minimum heap taskQueue, or scheduling is enabled if it is not in the scheduling loop.
In the first case, delay>0, when there are no tasks in the taskQueue and the new node expires at a time other than the timerQueue minimum, the scheduler stays in the second count of the timer. Once the second count is over, the scheduler continues to refresh the tasks in the two smallest heaps. Note that polling is not done all the time in the new scheme. Unlike the frame alignment scheme, it is not done every frame to determine if there are due tasks that need to be executed.
Note: Polling with requestAnimation does not have much of a performance penalty for the average application, so don’t worry too much about the value of the improvement. When you ask this question, your application is probably simpler than it should be.
You can see that adding a new task here doesn’t necessarily start a new round of scheduling, because it might be in the middle of scheduling, or it might be reading seconds, and then it will start. In order to ensure the integrity of the scheduling mechanism, it is necessary to judge the state of the minimum heap before the end of the scheduling function workLoop to start a new round of scheduling.
Delay time before deciding whether to enable scheduling
AdvanceTimers are used to add tasks that are timeout in timerQueue to taskQueue. Note the following
Scheduler provides the ability to execute tasks that are added later, as long as the priority is high enough
HandleTimeout calls advanceTimers to update the two minimum heaps and decide whether to count the seconds or start scheduling in the next event loop based on the following.
- if
taskQueueIf the command is not empty, the command is used to start scheduling as soon as possiblerequestHostCallbackScheduling begins in the next event loop - if
taskQueueNull andtimerQueueIf it is not empty, it needs to be read in seconds and invoked when the time is uphandleTimeoutTo determine whether to count seconds or dispatch as soon as possible.
function advanceTimers(currentTime) {
// Check for tasks that are no longer delayed and add them to the queue.
let timer = peek(timerQueue);
while(timer ! = =null) {
if (timer.callback === null) {
// Timer was cancelled.
pop(timerQueue);
} else if (timer.startTime <= currentTime) {
// Timer fired. Transfer to the task queue.
pop(timerQueue);
timer.sortIndex = timer.expirationTime;
push(taskQueue, timer);
} else {
// Remaining timers are pending.
return; } timer = peek(timerQueue); }}function handleTimeout(currentTime) {
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); }}}}Copy the codeStart dispatch as soon as possible
The scheduledHostCallback is an entry function to start the refresh task and is ignored here. What conditions are described here for executing this entry function?
First of all, we need to know what MessageChannel is. Those of you who have built a WebSocket service or run a Chrome plugin will be familiar with MessageChannel. Here is a related practice called SAN-DevTools. In short, it’s a communication channel. So why not use MessageChannel instead of window. postMessage? Using window. postMessage triggers all message event handlers bound by addEventlistener, In order to reduce crosstalk, React uses MessageChannel to build a dedicated channel to reduce external crosstalk (when the amount of frequent external communication data is too large, the buffer queue overflow leads to pipeline congestion, which affects react scheduling performance) and interference to the outside world. Window. postMessage is meant to be a global pipe, so MessageChannel has the disadvantage of being only scoped.
Postmessage /setImmediate triggers a macro task, so there is an idle interval between the two event loops to process the page’s interaction events, ScheduledHostCallback is called in the message event handler/timer callback function performWorkUntilDeadline to start scheduling. The scheduledHostCallback yieldInterval=5ms yieldInterval= 0 scheduledHostCallback yieldInterval=5ms scheduledHostCallback yieldInterval=5ms And try to start a new schedule in the next event loop if there are any remaining tasks. Stopping tasks in the smallest heap is also in response to user interactions. However, if the user’s interaction logic is too long, it can lead to too many tasks in the minimum heap, so too much interaction logic time is a sign of poor application developer code.
let schedulePerformWorkUntilDeadline;
if (typeof setImmediate === "function") {
schedulePerformWorkUntilDeadline = () = > {
setImmediate(performWorkUntilDeadline);
};
} else {
const channel = new MessageChannel();
const port = channel.port2;
channel.port1.onmessage = performWorkUntilDeadline;
schedulePerformWorkUntilDeadline = () = > {
port.postMessage(null);
};
}
function requestHostCallback(callback) {
scheduledHostCallback = callback;
if(! isMessageLoopRunning) { isMessageLoopRunning =true; schedulePerformWorkUntilDeadline(); }}let yieldInterval = 5;
const performWorkUntilDeadline = () = > {
if(scheduledHostCallback ! = =null) {
const currentTime = getCurrentTime();
deadline = currentTime + yieldInterval;
const hasTimeRemaining = true;
let hasMoreWork = true;
try {
hasMoreWork = scheduledHostCallback(hasTimeRemaining, currentTime);
} finally {
if (hasMoreWork) {
schedulePerformWorkUntilDeadline();
} else {
isMessageLoopRunning = false;
scheduledHostCallback = null; }}}else {
isMessageLoopRunning = false; }};Copy the codescheduling
In flushWork, we need to ensure that there is only one flushWork at a time, so we need to uncount the requestHostCallback and use isPerformingWork to lock the flushWork.
function flushWork(hasTimeRemaining, initialTime) {
isHostCallbackScheduled = false;
if (isHostTimeoutScheduled) {
isHostTimeoutScheduled = false;
cancelHostTimeout();
}
isPerformingWork = true;
try {
return workLoop(hasTimeRemaining, initialTime);
} finally {
isPerformingWork = false; }}Copy the codeFormal scheduling in workLoop, code that is too long can be understood in conjunction with the diagram at the beginning of this article.
- Start each time
taskBefore we do that, let’stimerQueueThe timeout task is pressed intaskQueue, and then determine whether the current entire schedule times out (5ms), refresh without timeouttaskQueueThe task is due in. Return to the task in the process, if a function, this function will inherit this task at the end of time, which is equivalent to simulate a small task queue, user can add the function returns a function, this function will be executed immediately (in the current event loop, and other than the current event loop micro earlier task execution). - Stop pairing when scheduling times out or there are no expired tasks
taskQueueThe task is scanned (executed), and then iftaskQueueIf it is not empty, returntrue, then scheduling will continue in the next event loop (flushWork). iftaskQueueIs empty,timerQueueIf it is not empty, it starts to count seconds at the minimum value of the smallest heap, and passes after the second count is completehandleTimeoutDetermine whether to continue counting seconds or start a new schedule as soon as possible.
function workLoop(hasTimeRemaining, initialTime) {
let currentTime = initialTime;
advanceTimers(currentTime);
currentTask = peek(taskQueue);
while(currentTask ! = =null) {
if( currentTask.expirationTime > currentTime && (! 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;
} else {
if (currentTask === peek(taskQueue)) {
pop(taskQueue);
}
}
advanceTimers(currentTime);
} else {
pop(taskQueue);
}
currentTask = peek(taskQueue);
}
// Return whether there's additional work
if(currentTask ! = =null) {
return true;
} else {
const firstTimer = peek(timerQueue);
if(firstTimer ! = =null) {
requestHostTimeout(handleTimeout, firstTimer.startTime - currentTime);
}
return false; }}Copy the codeconclusion
In this section, the implementation principle of the new scheduler is introduced. Compared with the old version, when there are enough tasks, the new version cuts the time into a finer piece of 5ms, so that there is more time to respond to user operations. When there are no tasks, the runtime code is cleaner because external PostMessage does not execute message event handlers in React. The next section introduces the principles of heuristic algorithms in frame alignment schemes and the concept of vsync in games.
Please comment directly or contact me if you have any inaccuracies.