学习React时间切片，任务调度scheduler

最近想起月初看到的魔术师卡颂的一个公开直播——《手写React优先级调度算法》，虽然我更倾向于认为直播内容是演示如何利用React官方同款调度库手写代码了解优先级调度，但是这并不影响我对直播内容的高质量的认可。

直播UP主魔术师卡颂给出的完整demo代码可以在https://codesandbox.io/s/xenodochial-alex-db74g?file=/src/index.ts中看到

执行效果如下

点击按钮生成的新任务，先将该任务放入到任务队列进行调度，然后选出最高优先级的先执行，在执行的过程中，如果发现有更高优先级的新任务（点击等其它操作生成的）插入进来，继续选出高优先级任务先执行，待当前最高优先级任务执行完毕后，继续在队列中选中剩下的最高优先级的执行，如此往复，直至队列任务全部执行完毕。

总体的执行流程就是：onclick加入任务 -> schedule -> perform -> schedule -> perform ...

完整代码如下：

// index.ts
import {
  unstable_IdlePriority as IdlePriority,
  unstable_ImmediatePriority as ImmediatePriority,
  unstable_LowPriority as LowPriority,
  unstable_NormalPriority as NormalPriority,
  unstable_UserBlockingPriority as UserBlockingPriority,
  unstable_getFirstCallbackNode as getFirstCallbackNode,
  unstable_scheduleCallback as scheduleCallback,
  unstable_shouldYield as shouldYield,
  unstable_cancelCallback as cancelCallback,
  CallbackNode
} from "scheduler";

import "./style.css";

type Priority =
  | typeof IdlePriority
  | typeof ImmediatePriority
  | typeof LowPriority
  | typeof NormalPriority
  | typeof UserBlockingPriority;

interface Work {
  priority: Priority;
  count: number;
}

const priority2UseList: Priority[] = [
  ImmediatePriority,
  UserBlockingPriority,
  NormalPriority,
  LowPriority
];

const priority2Name = [
  "noop",
  "ImmediatePriority",
  "UserBlockingPriority",
  "NormalPriority",
  "LowPriority",
  "IdlePriority"
];

const root = document.querySelector("#root") as Element;
const contentBox = document.querySelector("#content") as Element;

const workList: Work[] = [];
let prevPriority: Priority = IdlePriority;
let curCallback: CallbackNode | null;

// 初始化优先级对应按钮
priority2UseList.forEach((priority) => {
  const btn = document.createElement("button");
  root.appendChild(btn);
  btn.innerText = priority2Name[priority];

  btn.onclick = () => {
    // 插入工作
    workList.push({
      priority,
      count: 100
    });
    schedule();
  };
});

/**
 * 调度的逻辑
 */
function schedule() {
  // 当前可能存在正在调度的回调
  const cbNode = getFirstCallbackNode();
  // 取出最高优先级的工作
  const curWork = workList.sort((w1, w2) => {
    return w1.priority - w2.priority;
  })[0];

  if (!curWork) {
    // 没有工作需要执行，退出调度
    curCallback = null;
    cbNode && cancelCallback(cbNode);
    return;
  }

  const { priority: curPriority } = curWork;

  if (curPriority === prevPriority) {
    // 有工作在进行，比较该工作与正在进行的工作的优先级
    // 如果优先级相同，则不需要调度新的，退出调度
    return;
  }

  // 准备调度当前最高优先级的工作
  // 调度之前，如果有工作在进行，则中断他
  cbNode && cancelCallback(cbNode);

  // 调度当前最高优先级的工作
  curCallback = scheduleCallback(curPriority, perform.bind(null, curWork));
}

// 执行具体的工作
function perform(work: Work, didTimeout?: boolean): any {
  // 是否需要同步执行，满足1.工作是同步优先级 2.当前调度的任务过期了，需要同步执行
  const needSync = work.priority === ImmediatePriority || didTimeout;
  while ((needSync || !shouldYield()) && work.count) {
    work.count--;
    // 执行具体的工作
    insertItem(work.priority + "");
  }
  prevPriority = work.priority;

  if (!work.count) {
    // 完成的work，从workList中删除
    const workIndex = workList.indexOf(work);
    workList.splice(workIndex, 1);
    // 重置优先级
    prevPriority = IdlePriority;
  }

  const prevCallback = curCallback;
  // 调度完后，如果callback变化，代表这是新的work
  schedule();
  const newCallback = curCallback;

  if (newCallback && prevCallback === newCallback) {
    // callback没变，代表是同一个work，只不过时间切片时间用尽（5ms）
    // 返回的函数会被Scheduler继续调用
    return perform.bind(null, work);
  }
}

const insertItem = (content: string) => {
  const ele = document.createElement("span");
  ele.innerText = `${content}`;
  ele.className = `pri-${content}`;
  doSomeBuzyWork(10000000);
  contentBox.appendChild(ele);
};

const doSomeBuzyWork = (len: number) => {
  let result = 0;
  while (len--) {
    result += len;
  }
};

上面的代码中的schedule方法里面是有一个根据priority的排序，简单判断高优先级任务是可以自行实现的，但是当优先级相同时，如果继续执行呢？这是不能直接简单的执行perform方法，否则的话里面的while就不知道怎么中断，如果同步将while执行完，那样就不是异步可中断了。

我自己根据魔术师卡颂的讲解写了类似的代码，并将prevPriority的初始值和任务调度完成后对其赋值改成了Infinity。

实测在任务的priority为1或者2的时候都容易“卡顿”，在执行任务的priority为2时，插入priority为1的任务，带概率会先把priority为2执行完毕再执行priority为1。

上面的代码已经很好的演示了React是如何进行任务调度的，我们如果想继续了解这个调度算法是如何实现的，如何中断while循环，就需要深入了解scheduler库了。

判断是否需要中断while已经用到了scheduler库的以下部分：

• curCallback = scheduleCallback(curPriority, perform.bind(null, curWork));
• const needSync = work.priority === ImmediatePriority || didTimeout;

下面我把/node_modules/scheduler/index.js的源码略作精简，仅考虑宿主为浏览器的情况。

// /node_modules/scheduler/index.js
var channel = new MessageChannel();
var port = channel.port2;
channel.port1.onmessage = performWorkUntilDeadline;

function performWorkUntilDeadline() {
  if (scheduledHostCallback !== null) {
    var currentTime = exports.unstable_now(); // Yield after `yieldInterval` ms, regardless of where we are in the vsync
    // cycle. This means there's always time remaining at the beginning of
    // the message event.

    deadline = currentTime + yieldInterval;
    var hasTimeRemaining = true;

    try {
      var hasMoreWork = scheduledHostCallback(hasTimeRemaining, currentTime);

      if (!hasMoreWork) {
        isMessageLoopRunning = false;
        scheduledHostCallback = null;
      } else {
        // If there's more work, schedule the next message event at the end
        // of the preceding one.
        port.postMessage(null);
      }
    } catch (error) {
      // If a scheduler task throws, exit the current browser task so the
      // error can be observed.
      port.postMessage(null);
      throw error;
    }
  } else {
    isMessageLoopRunning = false;
  } // Yielding to the browser will give it a chance to paint, so we can
}

function unstable_scheduleCallback(priorityLevel, callback) {
  const currentTime = unstable_now();
  let startTime = currentTime;
  const timeout = timeoutMap[priorityLevel]; // 根据不同的优先级得到对应的超时时间，可以认为加上不同的bounce
  let expirationTime = startTime + timeout;

  var newTask = {
    id: taskIdCounter++,
    callback: callback,
    priorityLevel: priorityLevel,
    startTime: startTime,
    expirationTime: expirationTime,
    sortIndex: -1
  };

  newTask.sortIndex = expirationTime; // 后面就可以直接根据expirationTime来判断优先级了，与当初的priorityLevel无关了
  push(taskQueue, newTask);
  // wait until the next time we yield.

  if (!isHostCallbackScheduled && !isPerformingWork) {
    isHostCallbackScheduled = true;
    requestHostCallback(flushWork);
  }

  return newTask
}

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

function flushWork(hasTimeRemaining, initialTime) {
  isHostCallbackScheduled = false;

  if (isHostTimeoutScheduled) {
    // We scheduled a timeout but it's no longer needed. Cancel it.
    isHostTimeoutScheduled = false;
    cancelHostTimeout();
  }

  isPerformingWork = true;
  var previousPriorityLevel = currentPriorityLevel;

  try {
    return workLoop(hasTimeRemaining, initialTime);
  } finally {
    currentTask = null;
    currentPriorityLevel = previousPriorityLevel;
    isPerformingWork = false;
  }
}

function workLoop(hasTimeRemaining, initialTime) {
  var currentTime = initialTime;
  advanceTimers(currentTime);
  currentTask = peek(taskQueue);

  while (currentTask !== null && !(enableSchedulerDebugging )) {
    if (currentTask.expirationTime > currentTime && (!hasTimeRemaining || exports.unstable_shouldYield())) {
      // This currentTask hasn't expired, and we've reached the deadline.
      break;
    }

    var callback = currentTask.callback;

    if (typeof callback === 'function') {
      currentTask.callback = null;
      currentPriorityLevel = currentTask.priorityLevel;
      var didUserCallbackTimeout = currentTask.expirationTime <= currentTime;

      var continuationCallback = callback(didUserCallbackTimeout);
      currentTime = exports.unstable_now();

      if (typeof continuationCallback === 'function') {
        currentTask.callback = continuationCallback;
      } else {
        if (currentTask === peek(taskQueue)) {
          pop(taskQueue);
        }
      }

      advanceTimers(currentTime);
    } else {
      pop(taskQueue);
    }

    currentTask = peek(taskQueue);
  } // Return whether there's additional work

在执行unstable_scheduleCallback的时候，我们根据入参优先级和执行回调生成新的任务newTask，并将newTask推入任务队列，然后执行requestHostCallback(flushWork)。

requestHostCallback是将入参回调函数赋值给全局变量scheduledHostCallback，然后通过port.postMessage触发port的onMessage回调performWorkUntilDeadline ，在该回调中再执行scheduledHostCallback（如果存在的话）

所以下一个宏任务开始时会执行flushWork 方法，它的任务就是执行workLoop方法，根据workLoop返回结果判断是否还有其它任务hasMoreWork。 如果hasMoreWork为true或者有报错的话，我们就继续用port.postMessage再触发一次performWorkUntilDeadline ； 如果hasMoreWork为false，则将全局的scheduledHostCallback置为null，一切回归初始态继续待命。

workLoop方法当然不是简单的返回hasMoreWork结果这么简单，好歹方法名带个loop呢。 它会从任务队列里面取第0个任务作为currentWork，并经历一个while循环，直至currentWork为空：

1. currentWork已经过期了，则break跳出while循环，

2. currentWork的callback是一个函数（还记得newTask上面加上的callback属性吗）则直接执行该callback，如果返回的结果是一个函数，则将该函数作为currentWork新的callback，否则判断下currentWork是否是任务队列的第0个，是的话将其从任务队列中弹出。

   currentTask.callback = null;
   currentPriorityLevel = currentTask.priorityLevel;
   var didUserCallbackTimeout = currentTask.expirationTime <= currentTime;
   var continuationCallback = callback(didUserCallbackTimeout);
   if (typeof continuationCallback === 'function') {
   currentTask.callback = continuationCallback;
   } else {
   if (currentTask === peek(taskQueue)) {
   pop(taskQueue);
   }
   }

3. currentWork的callback不是一个函数，直接`pop(taskQueue)`直接将任务队里的第0个弹出

4. `currentTask = peek(taskQueue)`重新将任务队列里面取第0个任务作为currentWork，继续执行while循环。

在上述while循环完毕后，根据currentWork是否存在返回前面提到的布尔值hasMoreWork

if (currentTask !== null) {
    return true;
  } else {
    var firstTimer = peek(timerQueue);

    if (firstTimer !== null) {
      requestHostTimeout(handleTimeout, firstTimer.startTime - currentTime);
    }

    return false;
  }

如果为null的根据时间队列判断是否需要执行`requestHostTimeout`

function handleTimeout(currentTime) {
  isHostTimeoutScheduled = false;
  advanceTimers(currentTime);

  if (!isHostCallbackScheduled) {
    if (peek(taskQueue) !== null) {
      isHostCallbackScheduled = true;
      requestHostCallback(flushWork);
    } else {
      var firstTimer = peek(timerQueue);

      if (firstTimer !== null) {
        requestHostTimeout(handleTimeout, firstTimer.startTime - currentTime);
      }
    }
  }
}

• 魔术师卡颂很厉害！
• 深入学习下源码很爽，虽然有时很费时间。
• MessageChannel是以DOM Event的形式发送消息，所以它是一个宏任务，会在下一个事件循环的开头执行。scheduler这里的用法很巧妙
• scheduler源码中unstable_now类似用法自己也可以试试。