avatar

Coderek's blog

Loneliness is the gift of life

React Internals - scheduler

(The discussions in the React Internals Series will be based on React v16.9.0-rc.0 and for web only)

Scheduler rewrite is a key part of React team to achieve cooperative scheduling hence concurrent rendering.

It's also the lowest level of dependencies of the new fiber-based reconciliation algorithm. The good thing about learning it is that the scheduler actually does not depend on any upper level things, thus makes it simpler to understand.

Why there is a need for new scheduler. This video explains it well.

Essentially, tree rendering in React traditionally takes up too much time on main thread at one chunk. Now we want to break it up into smaller chunks and at the end of each chunk, give a chance to the main thread to clear the event queue. Thus it doesn't block main thread and the UI would become responsive.

The main idea is to utilize the idle time in each browser frame for rendering work. And when the frame time is up, the scheduler will pause and return control back to consume more events. And in the next idle time, it will resume where it left.

The scheduler maintains a task queue which stores the functions to be executed in order. The flushWork function of the Scheduler will be watching over for the deadline and reschedule work when necessary.

The task queue is a Doubly-Linked Sorted List. A task has the following structure.

var newTask = {
  callback,       // task function
  priorityLevel,  // priority of the task
  startTime,      // the time that this task should start
  expirationTime, // the time that this task is considered expired
  next: null,     // next task in the queue, it will point to the head if it's the last task
  previous: null, // previous task in the queue
};

The expirationTime is used for ranking the task in the queue. Earlier expiration will put a task in position nearer to the front. If the two task have the same expiration, it will rank in the insertion order.

The expirationTime is calculated by add current time by a time value. The time value is determined by the priorityLevel of the task.

These are the priority levels

var ImmediatePriority = 1;      // -1ms
var UserBlockingPriority = 2;   // 250ms
var NormalPriority = 3;         // 5000ms
var LowPriority = 4;            // 1000ms
var IdlePriority = 5;           // ~Infinity

There is an important concept of expired task. A task will expirationTime earlier than current time is considered expired. An expired task needs to be worked on immediately.

That's why the ImmediatePriority has expirationTime = currentTime -1. The immediate task is expired right away.

"To be worked on immediately" means executed synchronously without yielding to the main thread. It's equivalent to the stack based reconciliation method.

UserBlockingPriority is usually used for user input events like text input which requires response in UI in no less than 250 milliseconds.

There is a variant to execute tasks in batch. Essentially it means flush a number of adjacent tasks synchronously after they are scheduled.

The Scheduler provides a function to schedule a task.

function unstable_scheduleCallback(callback)

The function returns a handler to cancel the scheduled task. The callback is usually flushWork function.

function unstable_runWithPriority(priorityLevel, eventHandler)

The function is used to set the priority when schedule callback. it can be run in combination with scheduleCallback.

Key properties of the scheduler

The Scheduler has the following properties.

1. It can yield and resume

As a task queue, you can fully control the behavior of the consumption of tasks.

The scheduler provides a flushWork method to give back (yield) control the flow of the process to the main thread.

The host can implement shouldYieldToHost method to tell scheduler to give back control at appropriate time. By default it's set to yield when frame deadline is up.

Yielding is important as it allows main thread to slot in higher priority task just in time.

2. It can cancel tasks

The task scheduled can be cancelled. This can be useful if a later task supercede the previous task.

3. It can flush all the remaining tasks immediately

The flushWork takes in a didTimeout parameter, which indicate the remaining tasks have to be run immediately. The host can control the expiry of all the tasks.

4. It can prioritise tasks

The priority levels mentioned above is used to prioritise tasks. The default priority level is NormalPriority.

The host can use the following method to schedule a task with desired priority level.

function unstable_runWithPriority(priorityLevel, eventHandler)

So even some tasks were scheduled earlier, but it may run after the new task depending on the priority level.

5. It can spawn new task from existing tasks

The new task will be added to the queue.

The new task spawned will inherit the priority level of the parent task. This essentially enabled batch processing of tasks.

SchedulerHostConfig

It's a set of interface functions for the host to implement.

requestHostCallback

Used by scheduler to request to do work on the platform. In the case of browser, it means the CPU cycles in the main thread.

Here is the key part of the new scheduler, it wants to split work among the idling CPU cycles in each rendering frame. The frame is artificially set to 16ms, since it implies 60 frames/second. Given that the Flash was about 24 frames/second. 60 is a pretty good value that human eyes wouldn't detect any lag in UI.

In each frame, the browser has to do the followings

JS / CSS > Style > Layout > Paint > Composite

If this is done before 16ms, then there is some free time, and React would want to use that free time to do it's own work.

requestIdleCallback is used to get the idle CPU cycles in browser to run the scheduled tasks.

It will request one chunk of idle time at once with a timeout. If the idles time is not enough for all the tasks to finish, then it will stop and request another idle time.

If the time has exceeded the timeout, then all the tasks will be flushed out synchronously even though it might overshoot the frame.

requestIdleCallback is polyfilled by React due to incomplete browser support.

Take note that there are a couple of functions in browser that allows precise scheduling of callbacks.

Function Timing Timing Enforced?
requestAnimationFrame Beginning of the frame True
requestIdleCallback After paint and before next frame begin True
setTimeout After certain timeout in the macro task queue False
promise After current frame in the micro task queue False
postMessage After paint True

shouldYieldToHost

It basically gives a chance to the browser to run its own tasks. Part of cooperative scheduling.

Simple implementation on browser.

shouldYieldToHost = function() {
    return frameDeadline <= getCurrentTime();
};

The scheduler actually also support delayed task. They are the tasks that React want to execute at a later time for some reason.

The scheduler maintains a separate queue for delayed tasks. And they are sorted by startTime.

Here are the references:

Scheduler.js

Scheduler-test.js

SchedulerHostConfig.default.js

SchedulerHostConfig.mock.js

(End of article)