scheduler&Lane

Video explanation (efficient learning) :Into the study

Previous articles:

1. Introduction and questions

2. React design philosophy

React source code architecture

4. Source directory structure and debugging

5. JSX & core API

Legacy and Concurrent mode entry functions

7. Fiber architecture

8. Render phase

9. The diff algorithm

10. com MIT stage

11. Life cycle

12. Status update process

13. Hooks the source code

14. Handwritten hooks

15.scheduler&Lane

16. Concurrent mode

17.context

18 Event System

19. Write the React mini

20. Summary & Answers to interview questions in Chapter 1

21.demo

When we are in a similar search will find the following search box components, components are divided into search and display list of search results, we expect input box to immediately response, result list can have waiting time, if the result list data volume is very big, at the time of rendering is done, we input some words again, because of the high priority is of user input events, So stop rendering the result list, which leads to prioritization and scheduling between tasks

Scheduler

We know that if our application takes a long js execution time, such as one frame longer than the device, then the device’s drawing will not work.

The main functions of Scheduler are time slice and scheduling priority. React takes up a certain js execution time when comparing differences. The Scheduler uses MessageChannel to specify a time slice before browser drawing. Scheduler forces execution to be handed over to the browser

Time slice

The js execution time in a browser frame is as follows

RequestIdleCallback is executed after the redraw of the browser, if there is still free time, so in order not to affect the redraw of the browser, you can perform the performance calculation in the requestIdleCallback. However, due to the problems of compatibility and unstable trigger timing of requestIdleCallback, MessageChannel is used in Scheduler to implement requestIdleCallback. Use setTimeout if the current environment does not support MessageChannel.

PerformUnitOfWork executes the Render phase and commit phase. If the CPU is not completed in the browser frame, js execution will be granted to the browser. ShouldYield is to tell if the remaining time is used up. In the source code each time slice is 5ms, this value is adjusted according to the FPS of the device.

function workLoopConcurrent() {
  while(workInProgress ! = =null&&! shouldYield()) { performUnitOfWork(workInProgress); }}Copy the code
function forceFrameRate(fps) {// Calculate the time slice
  if (fps < 0 || fps > 125) {
    console['error'] ('forceFrameRate takes a positive int between 0 and 125, ' +
        'forcing frame rates higher than 125 fps is not supported',);return;
  }
  if (fps > 0) {
    yieldInterval = Math.floor(1000 / fps);
  } else {
    yieldInterval = 5;// The time slice defaults to 5ms}}Copy the code

Suspension of tasks

You have a section in the shouldYield function, so you know that if the current time is greater than the time the task started + the yieldInterval, you are interrupting the task.

// Deadline = currentTime + yieldInterval The deadline is calculated in performWorkUntilDeadline
if (currentTime >= deadline) {
  / /...
	return true
}
Copy the code

Scheduling priority

There are two functions in Scheduler that create tasks with priority

  • RunWithPriority: as a priority to perform the callback, if the task is synchronous, priority is ImmediateSchedulerPriority

    function unstable_runWithPriority(priorityLevel, eventHandler) {
      switch (priorityLevel) {//5 priorities
        case ImmediatePriority:
        case UserBlockingPriority:
        case NormalPriority:
        case LowPriority:
        case IdlePriority:
          break;
        default:
          priorityLevel = NormalPriority;
      }
    
      var previousPriorityLevel = currentPriorityLevel;// Save the current priority
      currentPriorityLevel = priorityLevel;// Assign priorityLevel to currentPriorityLevel
    
      try {
        return eventHandler();// The callback function
      } finally {
        currentPriorityLevel = previousPriorityLevel;// Restore the previous priority}}Copy the code
  • ScheduleCallback: Callback is registered with a priority and executed at the appropriate time because scheduleCallback is more granular than runWithPriority because it involves calculations of expiration time.

    • The higher the priority, the smaller the priorityLevel, the closer the expirationTime is to the current time. Var expirationTime = startTime + timeout; For example, IMMEDIATE_PRIORITY_TIMEOUT=-1, then var expirationTime = startTime + (-1); Is less than the current time, so execute immediately.

    • The small top heap is used in the scheduling process of scheduleCallback, so we can find the task with the highest priority in the complexity of O(1). If you don’t know anything about it, you can refer to the information. The small top heap stores tasks in the source code, and peek can pick the task with the nearest expiration time every time.

    • In scheduleCallback, unexpired tasks are stored in timerQueue and expired tasks are stored in taskQueue.

      After a newTask is created, check whether the newTask has expired and add it to the timerQueue. If no task in the taskQueue has expired and the task in the timerQueue whose time is closest to expiration is newTask, set a timer. Join the taskQueue when it expires.

      When there are tasks in timerQueue, the earliest expired tasks are fetched and executed.

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

  var startTime;// Start time
  if (typeof options === 'object'&& options ! = =null) {
    var delay = options.delay;
    if (typeof delay === 'number' && delay > 0) {
      startTime = currentTime + delay;
    } else{ startTime = currentTime; }}else {
    startTime = currentTime;
  }

  var timeout;
  switch (priorityLevel) {
    case ImmediatePriority:// The higher the priority, the smaller the timeout
      timeout = IMMEDIATE_PRIORITY_TIMEOUT;/ / 1
      break;
    case UserBlockingPriority:
      timeout = USER_BLOCKING_PRIORITY_TIMEOUT;/ / 250
      break;
    case IdlePriority:
      timeout = IDLE_PRIORITY_TIMEOUT;
      break;
    case LowPriority:
      timeout = LOW_PRIORITY_TIMEOUT;
      break;
    case NormalPriority:
    default:
      timeout = NORMAL_PRIORITY_TIMEOUT;
      break;
  }

  var expirationTime = startTime + timeout;// The higher the priority, the smaller the expiration time

  var newTask = {/ / the new task
    id: taskIdCounter++,
    callback// The callback function
    priorityLevel,
    startTime,// Start time
    expirationTime,// Expiration time
    sortIndex: -1};if (enableProfiling) {
    newTask.isQueued = false;
  }

  if (startTime > currentTime) {// There is no expiration date
    newTask.sortIndex = startTime;
    push(timerQueue, newTask);/ / to join timerQueue
    // There are no expired tasks in taskQueue, and the task whose expiry time is closest to timerQueue is newTask
    if (peek(taskQueue) === null && newTask === peek(timerQueue)) {
      if (isHostTimeoutScheduled) {
        cancelHostTimeout();
      } else {
        isHostTimeoutScheduled = true;
      }
      // The taskQueue is added to the timer when it expiresrequestHostTimeout(handleTimeout, startTime - currentTime); }}else {
    newTask.sortIndex = expirationTime;
    push(taskQueue, newTask);/ / to join taskQueue
    if (enableProfiling) {
      markTaskStart(newTask, currentTime);
      newTask.isQueued = true;
    }
    if(! isHostCallbackScheduled && ! isPerformingWork) { isHostCallbackScheduled =true;
      requestHostCallback(flushWork);// Execute expired tasks}}return newTask;
}
Copy the code

How do you resume a mission after it’s paused

There is such a section in the workLoop function

const continuationCallback = callback(didUserCallbackTimeout);// Callback is the scheduled callback
currentTime = getCurrentTime();
if (typeof continuationCallback === 'function') {// Determine the type of value returned after callback execution
  currentTask.callback = continuationCallback;// Currenttask.callback is assigned to currenttask.callback if it is function
  markTaskYield(currentTask, currentTime);
} else {
  if (enableProfiling) {
    markTaskCompleted(currentTask, currentTime);
    currentTask.isQueued = false;
  }
  if (currentTask === peek(taskQueue)) {
    pop(taskQueue);// If it is a function type, remove it from the taskQueue
  }
}
advanceTimers(currentTime);

Copy the code

At the end of the performConcurrentWorkOnRoot function has such a judgment, if callbackNode equals originalCallbackNode restore task execution

if (root.callbackNode === originalCallbackNode) {
  // The task node scheduled for this root is the same one that's
  // currently executed. Need to return a continuation.
  return performConcurrentWorkOnRoot.bind(null, root);
}
Copy the code

Lane

The priority of Lane and Scheduler are two sets of priority mechanisms. Comparatively, the priority of Lane is more fine-grained. Lane means Lane, similar to racing car, when task obtains priority, it always takes the track in the inner circle.

  • Can represent the priority of different batches

    As you can see from the code, each priority is a 31-bit binary number, 1 means that the position is available, 0 means that the position is not available, the priority from the first priority NoLanes to OffscreenLane is reduced, and the lower the priority is, the more 1s there are (the more cars on the outer lap of the race). In other words, the priority with multiple ones is the same batch.

    export const NoLanes: Lanes = / * * / 0b0000000000000000000000000000000;
    export const NoLane: Lane = / * * / 0b0000000000000000000000000000000;
    
    export const SyncLane: Lane = / * * / 0b0000000000000000000000000000001;
    export const SyncBatchedLane: Lane = / * * / 0b0000000000000000000000000000010;
    
    export const InputDiscreteHydrationLane: Lane = / * * / 0b0000000000000000000000000000100;
    const InputDiscreteLanes: Lanes = / * * / 0b0000000000000000000000000011000;
    
    const InputContinuousHydrationLane: Lane = / * * / 0b0000000000000000000000000100000;
    const InputContinuousLanes: Lanes = / * * / 0b0000000000000000000000011000000;
    
    export const DefaultHydrationLane: Lane = / * * / 0b0000000000000000000000100000000;
    export const DefaultLanes: Lanes = / * * / 0b0000000000000000000111000000000;
    
    const TransitionHydrationLane: Lane = / * * / 0b0000000000000000001000000000000;
    const TransitionLanes: Lanes = / * * / 0b0000000001111111110000000000000;
    
    const RetryLanes: Lanes = / * * / 0b0000011110000000000000000000000;
    
    export const SomeRetryLane: Lanes = / * * / 0b0000010000000000000000000000000;
    
    export const SelectiveHydrationLane: Lane = / * * / 0b0000100000000000000000000000000;
    
    const NonIdleLanes = / * * / 0b0000111111111111111111111111111;
    
    export const IdleHydrationLane: Lane = / * * / 0b0001000000000000000000000000000;
    const IdleLanes: Lanes = / * * / 0b0110000000000000000000000000000;
    
    export const OffscreenLane: Lane = / * * / 0b1000000000000000000000000000000;
    Copy the code
  • Priority calculation has high performance

    For example, the intersection of lanes represented by A and B can be determined by binary bitwise and

    export function includesSomeLane(a: Lanes | Lane, b: Lanes | Lane) {
      return(a & b) ! == NoLanes; }Copy the code

How tasks are prioritized in the Lane model (the car’s initial track)

The quest obtains the track from the higher-priority lanes, which happens in the findUpdateLane function. If there are no lanes available at the higher-priority level, it drops down to the lower-priority lanes. PickArbitraryLane calls getHighestPriorityLane to obtain the number of lanes with the highest priority, that is, to obtain the rightmost lanes from lanes & -lanes

export function findUpdateLane(lanePriority: LanePriority, wipLanes: Lanes,) :Lane {
  switch (lanePriority) {
    / /...
    case DefaultLanePriority: {
      let lane = pickArbitraryLane(DefaultLanes & ~wipLanes);// Find the next lane with the highest priority
      if (lane === NoLane) {// the lanes at the previous level are full. Drop to TransitionLanes to continue looking for available lanes
        lane = pickArbitraryLane(TransitionLanes & ~wipLanes);
        if (lane === NoLane) {/ / TransitionLanes also full
          lane = pickArbitraryLane(DefaultLanes);// start with DefaultLanes}}returnlane; }}}Copy the code

How to cut in line with high priority in Lane model

In the Lane model if a low priority task execution, and scheduling the trigger when a higher-priority task, the high-priority task interrupted low priority tasks, should cancel a lower-priority task at this time, because the lower priority task may have been a period of time, has built part of Fiber tree, So you need to restore the Fiber tree, which happens in the function prepareFreshStack, where the Fiber tree is initialized

function ensureRootIsScheduled(root: FiberRoot, currentTime: number) {
  const existingCallbackNode = root.callbackNode;// The setState callback that was previously called
  / /...
	if(existingCallbackNode ! = =null) {
    const existingCallbackPriority = root.callbackPriority;
    // The new setState callback and the previous setState callback with equal priority enter batchedUpdate logic
    if (existingCallbackPriority === newCallbackPriority) {
      return;
    }
    // If the priorities of the two callbacks are inconsistent, the task with a higher priority will be interrupted and the task with a lower priority will be cancelled
    cancelCallback(existingCallbackNode);
  }
	// Dispatch the start of the render phase
	newCallbackNode = scheduleCallback(
    schedulerPriorityLevel,
    performConcurrentWorkOnRoot.bind(null, root),
  );
	/ /...
}
Copy the code

function prepareFreshStack(root: FiberRoot, lanes: Lanes) {
  root.finishedWork = null;
  root.finishedLanes = NoLanes;
	/ /...
  //workInProgressRoot and other variables are reassigned and initialized
  workInProgressRoot = root;
  workInProgress = createWorkInProgress(root.current, null);
  workInProgressRootRenderLanes = subtreeRenderLanes = workInProgressRootIncludedLanes = lanes;
  workInProgressRootExitStatus = RootIncomplete;
  workInProgressRootFatalError = null;
  workInProgressRootSkippedLanes = NoLanes;
  workInProgressRootUpdatedLanes = NoLanes;
  workInProgressRootPingedLanes = NoLanes;
	/ /...
}
Copy the code

How to solve hunger problem in Lane model

In the process of scheduling priority, and calls the markStarvedLanesAsExpired traversal pendingLanes (not perform tasks include lane), if you don’t have a expiration time, expiration time is calculated if expired join root expiredLanes, It then returns expiredLanes first the next time it calls getNextLane

export function markStarvedLanesAsExpired(root: FiberRoot, currentTime: number,) :void {

  const pendingLanes = root.pendingLanes;
  const suspendedLanes = root.suspendedLanes;
  const pingedLanes = root.pingedLanes;
  const expirationTimes = root.expirationTimes;

  let lanes = pendingLanes;
  while (lanes > 0) {/ / traverse the lanes
    const index = pickArbitraryLaneIndex(lanes);
    const lane = 1 << index;

    const expirationTime = expirationTimes[index];
    if (expirationTime === NoTimestamp) {

      if( (lane & suspendedLanes) === NoLanes || (lane & pingedLanes) ! == NoLanes ) { expirationTimes[index] = computeExpirationTime(lane, currentTime);// Calculate the expiration time}}else if (expirationTime <= currentTime) {/ / is out of date
      root.expiredLanes |= lane;// Add the lane currently traversed at expiredLanes} lanes &= ~lane; }}Copy the code

export function getNextLanes(root: FiberRoot, wipLanes: Lanes) :Lanes {
 	/ /...
  if(expiredLanes ! == NoLanes) { nextLanes = expiredLanes; nextLanePriority = return_highestLanePriority = SyncLanePriority;// Return expired lanes first
  } else {
  / /...
    }
  return nextLanes;
}

Copy the code

The graph below is more intuitive. Over time, low-priority tasks get cut in line and eventually become high-priority tasks