In-depth understanding of task scheduling algorithms in React

This article will teach you about React and give you an in-depth understanding of the task scheduling algorithm in React. I hope it will be helpful to you!

Task pool in React

You should know about the Fiber tasks in React, and different Fiber tasks have different Priority, React needs to process tasks with high priority first. For example, the user's clicks and inputs are high-priority tasks, because the user's operations definitely hope to have immediate effects, so as to improve the user experience. For example, the priority of animation events must be lower. After a new high-priority task enters the queue, React needs to process it first. [Related recommendations: Redis Video Tutorial]

In order to store these tasks, there are two task pools in React.

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

taskQueue and timerQueue are both arrays. The former stores tasks to be executed immediately, while the latter stores tasks that can be delayed.

  var newTask = {
    id: taskIdCounter++, // 标记任务id
    callback, // 回调函数
    priorityLevel, // 任务优先级
    startTime, // 任务开始时间，时间点
    expirationTime, // 过期时间，时间点
    sortIndex: -1, // 任务排序，取值来自过期时间，因此值越小，优先级越高
  };

Once a new task comes in React, currentTime will be used to record the current time (performance.now() or Date.now()). If the task has a delay parameter, then the task start execution time startTime = currentTime delay;. Next, if startTime > currentTime is established, it proves that the task can be postponed, then the task enters the timerQueue, otherwise it enters the taskQueue.

Task Scheduling in React

How does React find the highest priority task? Take taskQueue as an example. It is a dynamic task pool (task queue), data Formally it is an array. Of course, you can sort according to priority, that is, Array.sort. When a new task is added to the queue, it is sorted first, and then the task with the highest priority is found and executed. But the average time complexity of Array.sort is O(nlogn), which is not the best solution.

TaskQueue's newTask uses sortIndex for sorting. This value is taken from the expiration time, which means that the higher the priority task, the more it needs to be understood and executed, so the expiration time will be smaller. In other words, The higher the priority, the smaller the expiration time, and the smaller the sortIndex will naturally be. In fact, This is a priority queue.

Priority queue

Priority queue is also a queue (First it is a queue, followed by tail-in-head out), the only difference is that the dequeuing order of the priority queue is based on priority; in some cases, you may need to find the smallest or largest element in the element set, and you can use the priority queue ADT to complete the operation , a priority queue ADT is a data structure that supports insert and delete minimum operations (return and delete the smallest element) or delete maximum operations (return and delete the largest element).

If the smallest key value element has the highest priority, then this priority queue is called an ascending priority queue (that is, the smallest element is always deleted first). Similarly, if the element with the largest key value has the highest priority, then this type of priority queue is called a descending priority queue (that is, the largest element is always deleted first); since these two types are symmetrical, you only need to focus on one of them. kind, such as ascending priority queue.

For example: When we were buying tickets, we were all queuing up, and the priority was the same. Whoever was in front of the queue would buy the ticket first, but then a soldier came and he has high priority and is directly at the front of the queue.

Use minimum heap (small root heap, small top heap...) to achieve this function in React. That is to turn the taskQueue into a minimum heap, then take out the top task for execution, heap the taskQueue, and maintain it as a minimum heap data structure. When inserting a new task into the taskQueue, it must also be heaped and always keep it as a minimum heap.

The relationship between priority queue and heap

Some places call the heap a priority queue (not accurate). First of all, it is a queue and has the characteristics of a queue, that is, "FIFO". Secondly, the elements in this queue have priorities, and those with higher priorities will be ranked first.

To be precise, the heap is a way to implement a priority queue. Of course, priority queues can also be implemented in other ways.

Minimum heap in React

We said before that heap sorting is an unstable sorting, but taskQueue hopes that this process is stable In other words, if it is possible that the expiration time of two tasks is the same, then it depends on who enters the task pool first, that is, the value of the id of newTask. Every time a new task comes, the id will be increased by 1. .

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

Minimum Heap

Before understanding the minimum heap, let’s review the basic knowledge.

Binary tree

refers to an ordered tree in which the degree of the nodes in the tree is no greater than 2. It is the simplest and most important tree.

Full Binary Tree

A binary tree in which all nodes on each level have two child nodes except the last level which does not have any child nodes.

From a graphical perspective, a full binary tree looks like a triangle.

If the number of levels of a binary tree is K and the total number of nodes is (2^k) -1, then it is a full binary tree.

The full binary tree is "a daughter with both sides" and is very perfect, so it is called a full binary tree.

Perfect Binary Tree

Except for leaf nodes, the degree of all nodes is 2. In other words, the degree of all nodes can only be 0 or 2.

Perfect binary tree has either no children or both children.

Full Binary Tree VS Perfect Binary Tree

Full Binary Tree original English text:
A Full Binary Tree (FBT) is a tree in which every node other than the leaves has two children.

The original English text of perfect binary tree:

A Perfect Binary Tree(PBT) is a tree with all leaf nodes at the same depth. All internal nodes have degree 2.

All foreign books refer to the earliest translated textbooks on full binary trees and perfect binary trees, but the earliest translated articles are wrongly translated. Now in China, we can only make mistakes when they are wrong (everyone is wrong, then the wrong one is also right. For example, lobbyists...). If you want to discuss these two concepts with foreign friends, you should pay attention.

Complete Binary Tree

A Complete Binary Tree (CBT) is a binary tree in which every level,except possibly the last, is completely filled, and all nodes are as far left as possible.

A binary tree with n nodes of depth k. The nodes in the tree are numbered from top to bottom and from left to right. If the number is i The node (1≤i≤n) has the same position in the binary tree as the node numbered i in the full binary tree, then this binary tree is called a complete binary tree.

• Except for the last layer, all layers are perfectly filled
• All leaf nodes of the last layer are aligned to the left

Heap

Heap is a complete binary tree.

The heap always satisfies the following properties:

• The heap is always a complete binary tree;
• The value of a node in the heap is always not greater than Or not less than the value of its parent node;

We also need to first understand the big root heap and the small root heap. All nodes in a complete binary tree are greater than (or less than) its child nodes, so here we divide There are two situations, max-heap and min-heap.

Maximum Heap

• If all nodes** are "greater than" the child node value, then this heap is called "Maximum Heap"* *, the maximum value of the heap is at the root node.

Minimal Heap

• If all nodes ** "less than" child node values, then this heap is called "Minimal Heap"**, the minimum value of the heap is at the root node.

The heap is usually an array object that can be viewed as a complete binary tree . Of course, binary trees can also be represented by arrays.

Implementation of heap

The core idea is to build the heap first and then adjust it.

Create a heap

For binary trees (array representation), we adjust from bottom to top, starting from **"the first non-leaf node"** to Before adjustment, the rules for adjustment are as follows:

Building a heap is an O(n) time complexity process.

①Start from the first non-leaf node to determine the swap down (shiftDown), so that the current node and children can maintain the nature of the heap

②But ordinary node replacement may not be a problem, for if If the exchange breaks the nature of the child heap structure, then the exchanged node must be shifted down again (shiftDown) until it stops.

调整堆

堆构造完成，取第一个堆顶元素为最小(最大)，剩下左右孩子依然满足堆的性值，但是缺个堆顶元素，如果给孩子调上来，可能会调动太多并且可能破坏堆结构。

① 所以索性把最后一个元素放到第一位。这样只需要判断交换下移(shiftDown）,不过需要注意此时整个堆的大小已经发生了变化，我们在逻辑上不会使用被抛弃的位置，所以在设计函数的时候需要附带一个堆大小的参数。

② 重复以上操作，一直堆中所有元素都被取得停止。

而堆算法复杂度的分析上，之前建堆时间复杂度是O(n)。而每次删除堆顶然后需要向下交换，每个个数为logn个。这样复杂度就为O(nlogn)，总的时间复杂度为O(n)+O(nlogn)=O(nlogn)。

堆的应用场景

堆适合维护集合的最值。

堆pop出一个元素后，再次调整获取堆顶元素（也就是第二个最值）的花销比较低，因为pop出元素后，堆是一个半成品，在一个半成品上获取第二个最值的cost当然比较低，时间复杂度为O(logn)，但如果遍历一遍找到第二个最值的话，时间复杂度为O(n)。

代码实现

代码采用Javascript ES6的写法。

代码

class Heap {
    constructor(data, comp) {
       this.data = data ? data : [];
 
       // 比较规则：更加灵活，可以比较数值，也可以比较对象
       this.compartor = comp ? comp : (a-b) => a-b;
 
       // 调整为堆(优先队列)
       this.heapify();
    }
 
    heapify() {
       if(this.size() =0; i--) {
          // 调整堆, 向下调整也可以用递归来实现，这里用迭代来实现
          this.shiftDown(i);
       }
    }
 
    // 向下调整
    shiftDown(i) {
       let left = 2*i +1;
       let right = 2*i +2;
 
       let len = this.size();
       while(i =0 ) {
          let findIndex = i;
          if(this.compartor(this.data[parentIndex], this.data[findIndex]) > 0) {
             findIndex = parentIndex;
          }
 
          if(findIndex !== i) {
             [this.data[i], this.data[findIndex]] = [this.data[findIndex], this.data[i]];
             i = findIndex;
             parentIndex = Math.floor((i-1)/2);
          }
          else {
              break;
          }
       }
    }
 
    // 获取堆中所有元素的个数
    size(){
        return this.data.length;
    }
 
    // 获取堆首部元素
    peek(){
        if(!this.size()) return null;
 
        return this.data[0];
    }
 
    // 往堆中添加一个元素
    push(x){
       this.data.push(x);
       
       this.shiftUp(this.data.length-1);
    }
 
    // 从堆里弹出堆首元素
    pop(){
      if(!this.size()) return null;
 
      let res = this.data[0];
 
      if(this.size() == 1) {
         this.data.pop();
      }
      else {
          this.data[0] = this.data[this.data.length-1];
          this.data.length = this.data.length-1;
          this.shiftDown(0);
      }
 
      return res;
    }
 }

测试

 let arr = [2,9,8,6,3,10,5,7,4,1];
 let comp = (a, b) => a-b;
 let heap = new Heap(arr, comp);
 
 let res = [];
 while(heap.size()) {
    res.push(heap.pop());
 }

 console.log(res);

arr里的元素也可以是一个对象。

React源码部分

React源码中的目录packages/scheduler，就是React的任务调度模块相关的代码。

https://github.com/facebook/react/blob/17.0.2/packages/scheduler/src/Scheduler.js

https://github.com/facebook/react/blob/17.0.2/packages/scheduler/src/SchedulerMinHeap.js

/**
 * Copyright (c) Facebook, Inc. and its affiliates.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 *
 * @flow strict
 */

type Heap = Array<node>;
type Node = {|
  id: number,
  sortIndex: number,
|};

export function push(heap: Heap, node: Node): void {
  const index = heap.length;
  heap.push(node);
  siftUp(heap, node, index);
}

export function peek(heap: Heap): Node | null {
  const first = heap[0];
  return first === undefined ? null : first;
}

export function pop(heap: Heap): Node | null {
  const first = heap[0];
  if (first !== undefined) {
    const last = heap.pop();
    if (last !== first) {
      heap[0] = last;
      siftDown(heap, last, 0);
    }
    return first;
  } else {
    return null;
  }
}

function siftUp(heap, node, i) {
  let index = i;
  while (true) {
    const parentIndex = (index - 1) >>> 1;
    const parent = heap[parentIndex];
    if (parent !== undefined && 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;
    }
  }
}

function siftDown(heap, node, i) {
  let index = i;
  const length = heap.length;
  while (index <p>我们自己实现的最小堆和React中的实现略有不同，但是思路是一样的，只是代码写法不同而已。</p>
<h2 data-id="heading-22"><strong>总结</strong></h2>
<p>React中的任务调度是用最小堆来实现的，如果我们之前就对最小堆有一定了解，那在学习这块内容的时候就会更快一点。个人认为，前期知识积累是多么重要啊，但是这个过程可能会比较枯燥。 这个时候，是不是觉得自己也会一些算法了，其实这些算法是入门级别的，甚至还没有入门。因为在React的任务调度场景中，要实现的需求是非常明确的，而且要采用什么样的数据结构和算法也是明确的。在实际的一些场景中，我们知道了具体的需求，但是并不知道用什么数据结果和算法，就需要把需求抽象一下，根据抽象的数据模型来设计具体的数据结构和算法，这些才是重点。</p>
<p>更多编程相关知识，请访问：<a href="https://www.php.cn/course.html" target="_blank" textvalue="编程视频">编程视频</a>！！</p></node>

The above is the detailed content of In-depth understanding of task scheduling algorithms in React. For more information, please follow other related articles on the PHP Chinese website!