React task scheduling and the algorithm behind it

Small thinking

Just met Xiao Ming, asked him a question: give you a number array, find out the smallest number, how to complete?

Xiaoming: Array.sort!

Me: If the array is dynamic, each time I find the minimum value, then I delete the element from the array, and then the next time I want to find the minimum value, how to complete. And as we do that, we’re constantly inserting new numbers into the array.

Xiaoming: Array.sort!

Me: but array is dynamic, every time SORT, but I just want the minimum value, you waste so much time to put the second and ten thousand are so accurate, don’t feel like a waste of time?

Xiaoming: It does seem to be a waste of time. Maybe it’s an algorithm. Never done it.

Task pools in React

There is a fiber task in React, and different fiber tasks have different priorities. For user experience, React needs to handle high-priority tasks first.

To store these tasks, React has two task pools, as defined in the source code:

// Tasks are stored on a min heap
var taskQueue = [];
var timerQueue = [];
Copy the code

TaskQueue and timerQueue are arrays. The former stores tasks to be executed immediately, while the latter stores tasks that can be deferred.

The initial structure of the task in the source code is defined as follows:

  var newTask = {
    id: taskIdCounter++, // Mark the task ID
    callback, // The callback function
    priorityLevel, // Task priority
    startTime, // Task start time, time point
    expirationTime, // Expiration time, time point
    sortIndex: -1.// Task sort. The value comes from the expiration time. Therefore, the smaller the value, the higher the priority
  };
Copy the code

CurrentTime (performance. Now () or date.now ())) is used when a new task is created. StartTime = currentTime + delay; . StartTime > currentTime indicates that the task is deferrable, so the task goes to timerQueue, otherwise it goes to taskQueue.

Task scheduling in React

So the question is, how do you find the highest priority task? Take taskQueue, which is a dynamic pool of tasks, and the data is an array. Array.sort is feasible, but not optimal. The average time complexity of each sort is as high as Nlog (n). At this point we need to understand a data structure: the smallest heap, also known as the small top heap.

Of course, one might ask, why not the biggest pile? This is because taskQueue’s newTask is sorted using sortIndex. This value is extracted from the expirationTime when a task with a higher priority would have to be executed immediately, so the expirationTime would be smaller. It is possible for both tasks to expire at the same time, depending on which task is the first in the pool, i.e. the id of the newTask is increased by 1 each time a newTask is added. The React source code has the following task priority functions:

function compare(a, b) {
  // Compare sort index first, then task id.
  const diff = a.sortIndex - b.sortIndex;
  returndiff ! = =0 ? diff : a.id - b.id;
}
Copy the code

To use the smallest heap, make the taskQueue the smallest heap data structure, and then take the smallest task from the smallest heap when the task is executed. If the task is completed, remove the task from the taskQueue and rearrange the remaining task pool so that it is still the smallest heap data structure. Of course, when inserting new tasks into the taskQueue, adjust the taskQueue to ensure that the new task pool remains the smallest heap.

The minimum heap

Before getting to know the minimum heap, familiarize yourself with three basic data structure concepts:

Binary tree

It is the simplest and most important tree in which the degree of the nodes is not greater than 2.

Full binary tree

All nodes on each layer have a binary tree of two children except the last layer, which has no children.

From the point of view of shape, full binary tree is a triangle in appearance.

A binary tree is full if the number of levels is K and the total number of nodes is (2^ K) -1.

Complete binary tree

A binary tree of depth K with n nodes is numbered from top to bottom and from left to right. If the node numbered I (1≤ I ≤n) is in the same position as the node numbered I in the full binary tree, the binary tree is called a complete binary tree. Leaf nodes can only occur in the largest two layers.

The minimum heap

Is a sorted complete binary tree in which the data value of any non-terminal node is not greater than the value of its left and right children.

For example, for the minimum heap above, after observation, the corresponding depth and array subscripts are:

After observation, it is found that the subscript relationship of parent-child nodes is as follows:

Calculate the subscript of the parent node based on the subscript of the child node: parentIndex = (childIndex – 1) >>> 1

Calculate the subscripts of child nodes according to the subscripts of parent nodes: leftIndex = (index +1) 2-1, rightIndex = leftIndex +1

At this point, we can try to implement the push delete (pop) check (peek) function for the minimum heap:

peek

Peek gets the top value of the smallest heap.

export function peek(heap) { 
    return heap.length === 0 ? null : heap[0];
}
Copy the code

push

Add an element to the smallest heap. Since taskQueue is already the smallest heap and is an array store, to reuse as much of the original structure as possible, we can insert the new element at the end of the array and adjust the smallest heap from the bottom up:

export function push(heap, node) {
  const index = heap.length;
  heap.push(node);
  siftUp(heap, node, index);
}
Copy the code

How do you adjust from the bottom up? Because the typical characteristic of the smallest heap is that the parent node is smaller than the left and right child nodes, then everything except the tail element satisfies this characteristic. All we need to do at this point is adjust the tail element and the ancestor of the tail element, all the way up until we no longer need to adjust. The code is as follows:

// Adjust the minimum heap upward
function siftUp(heap, node, i) {
  let index = i;
  while (index > 0) {
    // Subscript the parent node
    const parentIndex = (index - 1) > > >1;
    / / the parent node
    const parent = heap[parentIndex];
    if (compare(parent, node) > 0) {
      // parent>node, does not fit the minimum heap
      heap[parentIndex] = node;
      heap[index] = parent;
      index = parentIndex;
    } else {
      // The ancestor above is itself a minimal heap structure, so the adjustment is stopped
      return; }}}Copy the code

pop

Delete the heaptop element. React When a task is executed, it must be removed from the taskQueue. The top element is taskQueue[0], which we definitely need to use, and as with push, to reuse the original minimum heap structure as much as possible, we can do this by overwriting the top element with the last element and then adjusting the minimum heap from the top down.

export function pop(heap) {
  if (heap.length === 0) {
    return null;
  }
  const first = heap[0];
  const last = heap.pop();
  // If the top and bottom of the heap are not equal, prove that the total number of elements >1, need to adjust down
  if(first ! == last) { heap[0] = last;
    siftDown(heap, last, 0);
  }
   
  return first;
}
Copy the code

To adjust down, we simply check the structure of each child heap to make sure the minimum value is at the parent node. If not, we swap parent and left or parent and right as follows, with as many detailed comments as possible:

function siftDown(heap, node, i) {
  let index = i;
  const len = heap.length;
  const halfLen = len >>> 1;

  while (index < halfLen) {
    let leftIndex = (index + 1) * 2 - 1;
    let left = heap[leftIndex];
    let rightIndex = leftIndex + 1;
    let right = heap[rightIndex];
    // todo compares the size of parent and left and right
    // If parent is not the smallest, compare left and right, and swap the smallest with parent
    // If parent is the smallest, stop
    if (compare(left, node) < 0) {
      // left < parent
      // To keep the root node minimum, compare left and right
      if (rightIndex < len && compare(right, left) < 0) {
        // Right 
        heap[index] = right;
        heap[rightIndex] = node;
        index = rightIndex;
      } else {
        // right>left, left is the smallest, swap parent and leftheap[index] = left; heap[leftIndex] = node; index = leftIndex; }}else if (rightIndex < len && compare(right, node) < 0) {
      // left > parent
      // check right, right
      heap[index] = right;
      heap[rightIndex] = node;
      index = rightIndex;
    } else {
      / / parnent is minimal
      return; }}}Copy the code

conclusion

React task scheduling and minimum heap.

Finally, I’m writing a Mini React. This code is part of it. Please follow me at github.com/bubucuo/min…