The next article

React Scheduler

1, the introduction

Since React 16 came out, there have been a lot of articles about React Fiber, but most of them focus on fiber’s data structures and how the diff of component trees is changed from recursion to loop traversal. Descriptions of time slicing generally say that requestIdleCallback API is used to do scheduling, but it is difficult to find detailed description of task scheduling.

React Scheduler Scheduler Scheduler Scheduler Scheduler Scheduler Scheduler Scheduler Scheduler

Although the title is React Scheduler, the content of this article is irrelevant to React, because the task Scheduler has nothing to do with React. It only describes how to execute some tasks at the right time. That is to say, you can read this article even if you have no basic knowledge of React. You can also use this scheduler implementation to schedule tasks in your own framework.

  • This article is aboutThe react v16.7.0Version of the source code, please note the timeliness.
  • The source path scheduler.js

2. Basic knowledge

Here are some of the basics you need to know to read this article.

1.window.performance.now

This is the browser’s built-in clock that starts when the page loads and returns to the current total time in ms. This means that you call this method on the console 10 minutes after opening the page, and the number returned is about 600,000.

2,window.requestAnimationFrame

  • This method should be quite common, and it allows us to call the specified function at the beginning of the next frame. Its execution follows the refresh rate of the system. The requestAnimationFrame method takes one parameter, the callback function to execute. By default, the callback function passes in an argument, in milliseconds, the length of time from when the page is opened to when the callback function is fired.

  • The performance. Now () is passed to the callback immediately before the callback is called. This way we can know the current execution time when executing the callback.

     requestAnimationFrame(function F(t) {
       console.log(t, '= = = ='); RequestAnimationFrame (F)}Copy the code

  • A feature of requestAnimationFrame is that requestAnimationFrame will stop executing when the page processing is not active; When the page is activated again later, requestAnimationFrame will resume execution where it left off.

3,window.MessageChannel

This interface allows us to create a new message channel and send data through its two MessagePort(port1,port2) properties. Sample code is as follows

    var channel = new MessageChannel();
    var port1 = channel.port1;
    var port2 = channel.port2;
    port1.onmessage = function(event){
        console.log(event.data)  // someData
    }
    port2.postMessage('someData')
Copy the code

It is important to note that the onMessage callback is called after a paint frame has been completed. It has been observed that Vue’s nextTick also uses MessageChannel to do fallbacks (setImmediate is preferred). React Scheduler takes advantage of this internally to execute tasks during the remaining time after a frame has been rendered

4, list

I’m going to assume that you have a basic understanding of linked lists. If not, go to fill up your knowledge.

Here is a bidirectional circular linked list

  • A bidirectional linked list means that each node haspreviousandnextTwo properties to point to the two nodes.
  • The loop means that the next of the last node points to the first node, and the next of the first nodepreviousPointing to the last node, forming a ringHuman centipede.
  • We also need a variable firstNode to store the firstNode.
  • Let’s take a concrete example of the insert and delete operation of a two-way circular list. Suppose there is a group of people who need to queue by age. Children stand in front and adults stand in back. There’s going to be people coming in over the course of a process, and we need to get them in the right place. Delete only consider each time the person at the top of the row to remove.
Interface person {name: string // age: number // age: number // next: Person // next Person, default is null previous: Person // next Person, default is null} // There is no logic to insert nodes in the list at firstfunction insertByAge(newPerson:Person){
        if(firstNode = null){// If firstNode is null, newPerson is the first person, // assign it to firstNode and point the next and previous attributes to itself as a ring. firstNode = newPerson.next = newPerson.previous = newPerson; }elseVar next = null; var next = null; Var person = firstNode; // person will start from the first person in the loop belowdo {
                  if(person.age > newperson. age) {// if person is older than the newPerson, the newPerson has found a place, and he is right in front of person, end next = person;break; } // continue to find the next person node = node.next; }while(node ! == firstNode); / / herewhileTo prevent an infinite loop, it's a circular structureif(next === null){// There is no person with an age greater than newPerson, which means newPerson should be placed at the end of the queue. next = firstNode; }else if(next === firstNode){// newPerson should be placed before firstNode, FirstNode = newPerson} // Insert newPerson, NewPerson var previous = next. Previous; newPerson var previous = next. previous.next = next.previous = newPerson; newPerson.next = next; newPerson.previous = previous; } // Insert successfully} // Delete the first nodefunction deleteFirstPerson() {if(firstNode === null) return; Var next = firstnode.next; // The second personif(firstNode === next) {firstNode = null; next = null; }else{ var lastPerson = firstNode.previous; FirstNode = lastPerson. Next = next; // Next. Previout = lastPerson; // Create a connection between the new first and last person}}Copy the code

Because react16 uses a lot of linked lists to record data, especially react Scheduler uses a two-way circular linked list structure for task operations. React scheduling tasks should be easier to understand with this code.

3, the body

Note: The following sample code may be slightly deleted from the source code base in order to clarify the overall operation process

0. Several methods will not be described below

``` getCurrentTime = function() { return performance.now(); // If performance is not supported, use date.now () to do fallback} ' 'Copy the code

1. Task priority

React defines five priorities for tasks. A smaller number indicates a higher priority

var ImmediatePriority = 1; Var UserBlockingPriority = 2; Var NormalPriority = 3; Var LowPriority = 4; Var IdlePriority = 5; // Idle priorityCopy the code

The five priorities correspond to five expiration times

   // Max 31 bit integer. The max integer size in V8 for32-bit systems. // Math.pow(2, 30) - 1 var maxSigned31BitInt = 1073741823; ImmediatePriority ==> IMMEDIATE_PRIORITY_TIMEOUT = -1; Var USER_BLOCKING_PRIORITY = 250; // var NORMAL_PRIORITY_TIMEOUT = 5000; // var LOW_PRIORITY_TIMEOUT = 10000; Var IDLE_PRIORITY = maxSigned31BitInt;Copy the code

When each task is added to the linked list, the expiration time of the task will be calculated by performance.now() + timeout. As time goes by, the current time will be closer to the expiration time. Therefore, the smaller the expiration time is, the higher the priority is. If the expiration time is smaller than the current time, the task has expired and has not been executed. You need to execute it immediately (ASAP).

MaxSigned31BitInt is the largest integer in a 32-bit V8 engine. React uses this as the expiration time for IdlePriority.

That’s roughly 12.427 days, according to rough calculations. In extreme cases, if your TAB stays open for 12 and a half days, the task will expire.

2,function scheduleCallback()

  • The method in this code is calledunstable_scheduleCallbackIt is not stable at the momentscheduleCallbackAs the name.
  • The function of this method is to sort tasks by expiration time as a priority, similar to the operation process of two-way circular linked list above.

So here’s the code

   function scheduleCallback(callback, options? : {timeout:number} ) {
       //to be coutinued
   }
Copy the code

This method takes two inputs, the first of which is the callback to be executed, which is temporarily understood as a task. The second parameter is optional, and a timeout can be passed to indicate how long the task has timed out. If not, the expiration time is determined based on the task priority described above.

// This is a global variable that represents the priority of the current task. The default is normal var currentPriorityLevel = NormalPriorityfunction scheduleCallback(callback, options? : {timeout:number} ) {
      var startTime = getCurrentTime()
      if (
          typeof options === 'object'&& options ! == null && typeof options.timeout ==='number'){// expirationTime = startTime + options.timeout; // expirationTime = startTime + options.timeout; }elseSwitch (currentPriorityLevel) {case ImmediatePriority:
              expirationTime = startTime + IMMEDIATE_PRIORITY_TIMEOUT;
              break;
            case UserBlockingPriority:
              expirationTime = startTime + USER_BLOCKING_PRIORITY;
              break;
            case IdlePriority:
              expirationTime = startTime + IDLE_PRIORITY;
              break;
            case LowPriority:
              expirationTime = startTime + LOW_PRIORITY_TIMEOUT;
              break;
            caseNormalPriority: default: expirationTime = startTime + NORMAL_PRIORITY_TIMEOUT; Var newNode = {callback, priorityLevel = {callback, priorityLevel = { CurrentPriorityLevel, // task priority expirationTime, // task expirationTime next: null, // next node previous: null, // previous node}; //to be coutinued }Copy the code

The code above determines the expiration time of the current callback based on the input parameter or current priority and generates a real task node. The next step is to insert this object into the task’s linked list in the order of expirationTime.

Var firstCallbackNode = null;functionscheduleCallback(callback, options? : {timeout:number} ) { ... Var newNode = {callback, priorityLevel: currentPriorityLevel, // task priority expirationTime, // task expirationTime next: Null, // Next node previous: null, // previous node}; // You would like to add newNode to a task queue according to expirationTime. Refer to the Person queuing example in basicsif(firstCallbackNode === null) { firstCallbackNode = newNode.next = newNode.previous = newNode; ensureHostCallbackIsScheduled(); // This method is ignored for the first time.else {
           var next = null;
           var node = firstCallbackNode;
           do {
             if (node.expirationTime > expirationTime) {
               next = node;
               break;
             }
             node = node.next;
           } while(node ! == firstCallbackNode);if (next === null) {
         next = firstCallbackNode;
       } else if(next === firstCallbackNode) { firstCallbackNode = newNode; ensureHostCallbackIsScheduled(); } var previous = next. Previous; previous.next = next.previous = newNode; newNode.next = next; newNode.previous = previous; }return newNode;
       
   }
Copy the code
  • The above logic exceptensureHostCallbackIsScheduledThis is the insertion logic of the bidirectional circular list.
  • This is the end of how a new task determines its expiration date and how to insert an existing task queue.
  • The question arises at this point: We’ve sorted the tasks by expiration time, so when do we execute them?
  • The answer is that there are two cases, 1 is when the first task node is added to start the task execution, 2 is when the newly added task replaces the previous node as the new first node. Because 1 means the task starts from scratch and should start right away. 2 indicates that a new task with the highest priority has arrived. You should stop the previous task and start from the new task.
  • The two cases above correspondensureHostCallbackIsScheduledTwo branches of method execution. So we should know by now,ensureHostCallbackIsScheduledIt is used to initiate task execution at the right time.
  • What exactly is the right time? It can be described as the idle time after each frame is drawn. This ensures that the browser draws each frame as often as the system refreshes it, without dropping frames.

The next step is to implement such a function, how to implement a function at the right time.

3 requestIdleCallback pollyfill

Now forget about the task queue for a moment, and think about how you can do something during the free time that the browser draws each frame.

The answer could have been requestIdleCallback, but for some reason the React team dropped this API, Instead, a requestIdleCallback is created using the requestAnimationFrame and MessageChannel Pollyfill

1.function requestAnimationFrameWithTimeout()

First, a super powerful function, the code is as follows

    var requestAnimationFrameWithTimeout = function(callback) {
      rAFID = requestAnimationFrame(function(timestamp) {
        clearTimeout(rAFTimeoutID);
        callback(timestamp);
      });
      rAFTimeoutID = setTimeout(function() {
        cancelAnimationFrame(rAFID);
        callback(getCurrentTime());
      }, 100);
    }
Copy the code

So what does this code mean?

  • When we call requestAnimationFrameWithTimeout and pass in a callback, will start a requestAnimationFrame and a setTimeout, both to carry out the callback. However, since requestAnimationFrame has a higher execution priority, it internally calls clearTimeout to cancel the following timer. So the performance of the page in the active case is consistent with requestAnimationFrame.

  • Here you should see, at the start of the foundation in the knowledge that requestAnimationFrame the page when switching to inactive is not working, then requestAnimationFrameWithTimeout is equivalent to launched a 100 ms of the timer, Take over the execution of tasks. This execution frequency is neither high nor low, which not only does not affect CPU power consumption, but also ensures that the task can be executed with a certain efficiency.

  • Below we think requestAnimationFrameWithTimeout equivalent to requestAnimationFrame for a moment

(The space is already so long, so I’ll write it here and write more next time.)