React scheduling algorithm

Weng Binbin, the front-end engineer of Micro Medical cloud, will never stop on the road of programmer training.

The following analysis is based on React, ReactDOM version 16.13.1

preface

In React16, we rewrote the new Fiber architecture, which introduced a new scheduling algorithm. In the previous version, diff of the React virtual DOM did not interrupt, which took up a lot of execution time, resulting in delayed rendering and page stutter. The React team wanted to be able to do diff’s work by performing small asynchronous tasks without causing pages to stall. Today we’ll take a closer look at this scheduling algorithm.

How to split a giant task?

Instead of thinking about how React implements the scheduling algorithm, let’s ask how to split up a huge task. Here’s an example. What would you do?

<script>
function read(arr) {
  arr.forEach((_, i) = > {
    console.log(i);
  });
}

const array = Array.from(Array(1000000)).fill(1);

console.log('task start');
read(array);
console.log('task end');
</script>
<h1>hello world</h1>
Copy the code

As you all know, the above code will print task Start, and then the browser TAB will start spinning in a circle. If you have a bad computer, the circle may take a long time, and after a few seconds, you will print Task End. Then you will see hello World rendered on the page. This is because js execution blocks the browser rendering, causing the browser to render the UI after JS runs. How to solve this problem?

Break it down into small tasks

We can divide a million numbers into 10,000 tasks by 100, and then put them in the timer to be executed in the next event loop. In this way, we can solve the problem of blocking rendering caused by js running too long. In fact, the React scheduling algorithm is basically the same basic idea.

To verify this point, the yellow JS task is split and interlaced with purple Layout and green Print.

An improved version of the above example is shown below

const array = Array.from(Array(100000)).map((_, index) = > index);
function read(arr) {
  arr.forEach(function readCallback(item) {
    console.log(item);
  });
}
console.log('task start');
let i = 0;
const len = 100;
function task() {
  setTimeout(function setTimeoutCallback(r) {
    const results = array.slice(i, i + len);
    if (results.length === 0) {
      console.log('task end');
      return;
    }
    read(results);
    i += len;
    task();
  }, 0);
}
task();
Copy the code

When you open the browser again, you will find that it can be opened instantly without any lag.

Scheduling concept

The scheduling algorithm has two kinds, which are frequently used, the first is a preemptive scheduling in the operating system level said the CPU which can determine the current time slice to process, but the browser and don’t have the permission, the second is the React to use collaborative scheduling, also is everyone agreed in advance how long each takes up time slice, all by consciously.

Why does React need scheduling?

1. Break upThe diff operation
2. Prioritize your tasks

Scheduling is mainly used to split diff operations, so when diFF occurs, the only operation that can cause diFF is to trigger an update, Reactdom. render; setState; forceUpdate; useState; useReducer

Google proposes the RAIL model:

• User-centered; The ultimate goal is not to make your site run fast on any particular device, but to make your users happy.
• Immediate response to users; Confirm user input within 100ms. For discrete interactive operations, response is required within 100ms
• Generate frames within 16ms when setting up animation or scrolling.
• Maximizes the idle time of the main thread to ensure that the JS single task execution time does not exceed 50ms.
• Keep attracting users; Interactive content will be presented within 1000ms, and the first screen will open in seconds.

Not all operations have the same priority. React classifies user operations into the following categories. The scheduling system also serves for operation priorities.

// Execute immediately
const ImmediatePriority = 1;
var IMMEDIATE_PRIORITY_TIMEOUT = -1;

// after 250ms expired users block priority text input, etc
const UserBlockingPriority = 2;
var USER_BLOCKING_PRIORITY = 250;

// expire after 5000ms common priority network request
const NormalPriority = 3;
var NORMAL_PRIORITY_TIMEOUT = 5000;

// Analysis of expired low-priority data after 10000ms
const LowPriority = 4;
var LOW_PRIORITY_TIMEOUT = 10000;

// Theoretically never expire idle priority
const IdlePriority = 5;
var IDLE_PRIORITY = 1073741823;
Copy the code

Trigger a scheduling

render

• In the previousReactDOM#render worksAs analyzed in this article,renderMethod will eventually be calledscheduleUpdateOnFiberTo start scheduling

setState, forceUpdate

• By a number of means (not the focus of this article, so I’ll skip the details), we can see that there will be twoenqueueSetState.enqueueReplaceStateIn the call

scheduleUpdateOnFiber

useState, useReducer

• useStateThe underlying method is actually calleduseReducerSo just lookuseReducerThe implementation will be found indispatchActionFunction is calledscheduleUpdateOnFiber

According to the above conclusion, we can know that scheduling starts in scheduleUpdateOnFiber method. Next, let’s look at scheduleUpdateOnFiber

Please check for details

• Github.com/AfterThreeY…
• Github.com/AfterThreeY…

Start scheduling

                                     scheduleUpdateOnFiber 
                                              |
                                              |
                                              |
                                              V
scheduleSyncCallback <-----(SYNC)----- ensureRootIsScheduled -----(ASYNC)-----> scheduleCallback
        |                                                                           |
        |                                                                           |
        |                                                                           |
        |                                                                           |
        -------------------------> Scheduler_scheduleCallback <----------------------
        
Copy the code

The expirationTime variable, whether one is Sync or not, will eventually be called to the ensureRootIsScheduled function. EnsureRootIsScheduled determines whether scheduleSyncCallback or scheduleCallback is called based on the current running environment (synchronous or asynchronous). By observing the implementation of scheduleSyncCallback and scheduleCallback functions, it can be seen that the internal Scheduler_scheduleCallback function is called. The only difference is that the first argument that scheduleCallback passes in is a priority calculated by the current expirationTime. The priority given by the scheduleSyncCallback is the fixed writing-dead Scheduler_ImmediatePriority (-1), which indicates the immediate simultaneous execution of the callback function. So Scheduler_scheduleCallback can be understood as: if -1 is passed, the callback function is called synchronously. If other numbers are passed, setTimeout is called asynchronously to execute the callback after the time required by the numbers. What exactly does Scheduler_scheduleCallback do?

export function scheduleUpdateOnFiber(fiber: Fiber, expirationTime: ExpirationTime,) {
  const root = markUpdateTimeFromFiberToRoot(fiber, expirationTime);
  if (root === null) {
    return;
  }
  // ...
  if (expirationTime === Sync) {
    // ...
    ensureRootIsScheduled(root);
    schedulePendingInteractions(root, expirationTime);
    if(executionContext === NoContext) { flushSyncCallbackQueue(); }}else {
    // ...ensureRootIsScheduled(root); schedulePendingInteractions(root, expirationTime); }}function ensureRootIsScheduled(root: FiberRoot) {
  // ..
  if (/ /...). {
    callbackNode = scheduleSyncCallback(performSyncWorkOnRoot.bind(null, root));
  } else if ( / /...). {
    callbackNode = scheduleCallback(
      priorityLevel,
      performConcurrentWorkOnRoot.bind(null, root),
    );
  } else {
    callbackNode = scheduleCallback(
      priorityLevel,
      performConcurrentWorkOnRoot.bind(null, root),
      {timeout: expirationTimeToMs(expirationTime) - now()},
    );
  }

  root.callbackNode = callbackNode;
}

export function scheduleCallback(reactPriorityLevel, callback, options) {
  const priorityLevel = reactPriorityToSchedulerPriority(reactPriorityLevel);
  return Scheduler_scheduleCallback(priorityLevel, callback, options);
}

export function scheduleSyncCallback(callback: SchedulerCallback) {
  if (syncQueue === null) {
    // ...
    immediateQueueCallbackNode = Scheduler_scheduleCallback(
      // Scheduler_ImmediatePriority = -1
      Scheduler_ImmediatePriority,
      flushSyncCallbackQueueImpl,
    );
  } else {
    // ...
  }
  // ...
}

Copy the code

Small root pile

The heap is a binary tree, so it also conforms to some characteristics of binary trees. For example, there is a node N (n >= 1), n >> 1, which indicates the location of the parent node of this node. N * 2 said is the node’s left child node position, n * 2 + 1 is the node’s right child node position, pile was also distinguish between big root pile and small heap, and root pile said every parent node is greater than its two child nodes, and the little root pile, on the other hand, every parent node is less than its two child nodes, through this feature, The ability to implement a dynamic priority queue with O(logn) time complexity is a very efficient data structure.

React needs a data structure to help it store diff tasks, which requires frequent insertion of single nodes and single fetching of nodes with the highest priority. The minimum heap perfectly matches the features required by React.

In JS, we can realize this data structure by array. According to the specification, we can define such a set of interfaces. The specific implementation is not described here, and there are many algorithms on the network:

interface HeapNode<T> {
    value: T;
    sortIndex: T;
}

type Compare = (a: HeapNode<string>, b: HeapNode<string>) = > boolean;

abstract class Heap<T> {
    private compare: Compare;
    constructor(compare: Compare) {
        this.compare = compare;
    }
    abstract peek(): HeapNode<T>;

    abstract pop(): HeapNode<T>;
    abstract siftDown(n: number) :void;

    abstract push(node: HeapNode<T>): void;
    abstract siftUp(n: number) :void;

    abstract parent(n: number) :number;
    abstract left(n: number) :number;
    abstract right(n: number) :number;

    abstract swap(n: number.m: number) :void;
    abstract toString(): string;
    abstract size(): number;

    abstract heapify(nodes: HeapNode<T>[], compare: Compare): Heap<T>;
}
Copy the code

The two core methods are siftUp and siftDown, which represent the ascending and descending of nodes respectively:

floating

• When a node is added to the end of the small root heap, it is necessary to reposition the node to comply with the small root heap rule. If the new node is larger than the parent node, it does not need to be moved, but if it is smaller than the parent node, it needs to be swapped with the parent node, and then continue to be compared with the new parent node.

sinking

• When a node is removed from the root pile, you will take the first node and end node to heap swap, and then pop up at the end of the node, this time from end to replace the new node may be bigger than it’s child nodes, so you need to put it down to the small root pile composite rules, first through the comparison, the left and right child nodes to find bigger of the two nodes, Then compare it with the new node. If the new node is large, move its position. Then compare it with the new child node again.

Peek is used to view nodes on the top of the heap, POP is used to pop nodes on the top of the heap, and push is used to add new nodes

case

There is a set of initial values [5, 4, 3, 2, 1], which will appear after our small heap

          1
        2   4
      5   3
Copy the code

Insert a new node, 0, and float up to create the following structure.

          0
        2   1
       5 3 4
Copy the code

Scheduling process

Firstly, it will be introduced that there are two main task piles in the scheduling process, namely real-time task pile and delayed task pile. Tasks without delay parameter will be put into real-time task pile, otherwise, they will be pushed into delayed task pile. The significance of delayed task pile is mainly in the tasks with long delay. Reduces useless postMessage recursive calls.

In unstable_scheduleCallback, the priority of the current task is passed, the callback function, and additional options. The system automatically sets the expirationTime of a task according to the priority or timeout or delay in the additional options. Then startTime is used to determine whether the current task should be put into the real-time task heap or the delayed task heap. If it is a delayed task, it will be put into the delayed task heap. SetTimeout is used to schedule according to whether there are real-time tasks that can be scheduled and the current task has the highest priority in the delayed task heap. The workLoop function is called asynchronously. RequestHostCallback is used to add the workLoop to the next macro task. Makes the final correction loop will execute the next time, will workLoop from real-time tasks pile cap to take out the highest priority task, then view the current browser rendering time frame do you have time to execute js, and the current task is expired, if the task has not yet expired but have no time, will hand over first to control access to the browser, Wait for the next call; If the task has expired, the task needs to be executed immediately. After the execution, check whether there are still tasks in the real-time task heap. If there are, the currentTask value is assigned to the currentTask. If the real-time task is empty, the delayed task heap is scheduled and false is returned to indicate that the current task is complete.

let taskIdCounter = 1;
// Delay task heap
const timerQueue = [];
// Real-time task heap
const taskQueue = [];

function unstable_scheduleCallback(priorityLevel, callback, options) {
  var currentTime = getCurrentTime();

  var startTime;
  var timeout;
  if (typeof options === 'object'&& options ! = =null) {
    var delay = options.delay;
    if (typeof delay === 'number' && delay > 0) {
      startTime = currentTime + delay;
    } else {
      startTime = currentTime;
    }
    timeout =
      typeof options.timeout === 'number'
        ? options.timeout
        : timeoutForPriorityLevel(priorityLevel);
  } else {
    timeout = timeoutForPriorityLevel(priorityLevel);
    startTime = currentTime;
  }

  var expirationTime = startTime + timeout;

  var newTask = {
    id: taskIdCounter++,
    callback,
    priorityLevel,
    startTime,
    expirationTime,
    sortIndex: -1};// Delay tasks
  if (startTime > currentTime) {
    newTask.sortIndex = startTime;
    push(timerQueue, newTask);
    // There is no real-time task and the current task is equal to the task on the top of the heap in the delayed task. Start the delayed scheduling, and the waiting time is the time difference between the current time and the delayed task start time
    if (peek(taskQueue) === null && newTask === peek(timerQueue)) {
      // ...requestHostTimeout(handleTimeout, startTime - currentTime); }}else {
    // If there are real-time tasks, schedule real-time tasks
    newTask.sortIndex = expirationTime;
    push(taskQueue, newTask);
    if(! isHostCallbackScheduled && ! isPerformingWork) { isHostCallbackScheduled =true; requestHostCallback(flushWork); }}return newTask;
}

function flushWork(hasTimeRemaining, initialTime) {
  // ...
  try {
    return workLoop(hasTimeRemaining, initialTime);
  } finally {
    // ...}}function workLoop(hasTimeRemaining, initialTime) {
  let currentTime = initialTime;
  // Check whether there are any expired tasks in the delayed task, if so, kick them out of the delayed heap and put them into the real-time heap
  advanceTimers(currentTime);
  currentTask = peek(taskQueue);
  while(currentTask ! = =null) {
    if( currentTask.expirationTime > currentTime && (! hasTimeRemaining || shouldYieldToHost()) ) {// The task has not expired, but the time slice of this tick is used up, so skip this task first
      break;
    }
    const callback = currentTask.callback;
    if(callback ! = =null) {
      currentTask.callback = null;
      currentPriorityLevel = currentTask.priorityLevel;
      // The didTimeout argument, similar to requestIdleCallback, is used to determine whether the task is expired
      const didUserCallbackTimeout = currentTask.expirationTime <= currentTime;
      callback(didUserCallbackTimeout);
      currentTime = getCurrentTime();
      {
        // Task node The task node is displayed
        if(currentTask === peek(taskQueue)) { pop(taskQueue); }}// Check whether there are any expired tasks in the delayed task, if so, kick them out of the delayed heap and put them into the real-time heap
      advanceTimers(currentTime);
    } else {
      // ...
    }
    // Get the next task node
    currentTask = peek(taskQueue);
  }
  if(currentTask ! = =null) {
    // The real-time task heap is not available yet
    return true;
  } else {
    // The real-time task heap is empty, and the deferred task heap needs to schedule itself
    const firstTimer = peek(timerQueue);
    if(firstTimer ! = =null) {
      requestHostTimeout(handleTimeout, firstTimer.startTime - currentTime);
    }
    return false; }}Copy the code

RequestHostCallback implementation

Internally, the requestHostCallback uses MessageChanel to determine whether to recursively call performWorkUntilDeadline based on the return value of the workLoop, thus splitting each task into each event loop in the browser. When you call performWorkUntilDeadline, you add the current time to the value of the yieldInterval (default: 5ms) as a time slice that can be executed. In this case, the time slice is 5ms. React allows the React scheduler to know whether the current task will be executed in the current slice or the next slice. This slice is not a browser frame, but at a 60 frame rendering rate, three more slices will be executed in a frame. The recursive call performWorkUntilDeadline is ultimately determined by the return value of scheduledHostCallback.

  const performance = window.performance;

  getCurrentTime = () = > performance.now();

  let isMessageLoopRunning = false;
  let scheduledHostCallback = null;

  let yieldInterval = 5;
  let deadline = 0;

  const shouldYieldToHost = function() {
      return getCurrentTime() >= deadline;
  };

  const performWorkUntilDeadline = () = > {
    if(scheduledHostCallback ! = =null) {
      const currentTime = getCurrentTime();
      deadline = currentTime + yieldInterval;
      const hasTimeRemaining = true;
      try {
        const hasMoreWork = scheduledHostCallback(
          hasTimeRemaining,
          currentTime,
        );
        if(! hasMoreWork) { isMessageLoopRunning =false;
          scheduledHostCallback = null;
        } else {
          port.postMessage(null); }}catch (error) {
        port.postMessage(null);
        throwerror; }}else {
      isMessageLoopRunning = false; }};const channel = new MessageChannel();
  const port = channel.port2;
  channel.port1.onmessage = performWorkUntilDeadline;

  requestHostCallback = function(callback) {
    scheduledHostCallback = callback;
    if(! isMessageLoopRunning) { isMessageLoopRunning =true;
      port.postMessage(null); }}; cancelHostCallback =function() {
    scheduledHostCallback = null;
  };
Copy the code

requestIdleCallback

There are several main reasons why requestIdleCallback is not used as an alternative to requestHostCallback, but rather implements it yourself:

1. Poor compatibility, basically dead on IOS.
2. The timeRemaining function will return up to 50ms, which is not enough to support smooth rendering.
3. In addition to defaulttimeoutIn addition, it has been extendedpriorityLevel.delaySuch as options.

For these three reasons, the React team chose not to use the native requestIdleCallback API.

The current scheduling mode of the production environment

We are currently using reactdom.render for application creation, so the requestHostCallback will execute in the next event loop, but the internal multiple tasks will not be interrupted. React does everything in one slice at a time, so it’s not like the current version of React can interrupt rendering. It’s important to note that if you want to try the interruptible React render mode, Also need to install the experimental version * * zh-hans.reactjs.org/docs/concur… Concurrent mode, with interruptible, multi-task time slices.

conclusion

Through the analysis of React Scheduler, we know how it calls small diff tasks in multiple time slices through cooperative scheduling scheme, without blocking browser rendering, and brings users a silky browsing experience.

Further reading

• Scheduling in React juejin.cn/post/684490…
• Introduction to the React zhuanlan.zhihu.com/p/48254036 Scheduler task management