新版 scheduler

上节说到了在 react16.8 版本的 scheduler 由requestAnimation以及 postmessage 实现，即对齐 frame 的计划。依据 react 官网相干 issue)的形容，scheduler 中 requestAnimation 形成的循环对 CPU 的利用率低于新版本 scheduler 中 message 形成的循环。此外通过一些 issue 也能看到 react 对代码品质的诸多考量。

​ 当初开始新版 scheduler 的实现，大抵画了一张运行流程图，有上面几点须要留神：

1. taskQueue 与 timerQueue 是两个最小堆，后者的工作在肯定工夫 (delay) 之后被放到 taskQueue 中，taskQueue 中的工作在到期之后才会执行。
2. timerQueue 依照 current+delay 工夫排序，taskQueue 依照 current+delay+priorityTime 排序
3. 工作无奈做到肯定是在 delay 工夫之后从 timerQueue 转移到 taskQueue
4. wookloop每次批量执行工作的工夫管制在 5m s 内，每次执行一个task 之前会查看以后 wookloop 执行是否曾经超过了5ms
5. task的到期工夫雷同的时候先退出的先执行

工具

获取以后工夫

代码品质体现在细节上：这里是间接替换掉 getCurrentTime，而不是每次在函数中判断是否存在 performance.now

var hasNativePerformanceNow =
  typeof performance === 'object' && typeof performance.now === 'function';
var localDate = Date;
var getCurrentTime;
if (hasNativePerformanceNow) {
  var Performance = performance;
  getCurrentTime = function() {return Performance.now();
  };
} else {getCurrentTime = function() {return localDate.now();
  };
}

定义优先级对应的工夫

预期的用户交互的工夫：USER_BLOCKING_PRIORITY_TIMEOUT

const ImmediatePriority = 1;
const UserBlockingPriority = 2;
const NormalPriority = 3;
const LowPriority = 4;
const IdlePriority = 5;

const IMMEDIATE_PRIORITY_TIMEOUT = -1;
const USER_BLOCKING_PRIORITY_TIMEOUT = 250;
const NORMAL_PRIORITY_TIMEOUT = 5000;
const LOW_PRIORITY_TIMEOUT = 10000;
const IDLE_PRIORITY_TIMEOUT = 1073741823;

const priorityMap = {[ImmediatePriority]: IMMEDIATE_PRIORITY_TIMEOUT,
  [UserBlockingPriority]: USER_BLOCKING_PRIORITY_TIMEOUT,
  [NormalPriority]: NORMAL_PRIORITY_TIMEOUT,
  [LowPriority]: LOW_PRIORITY_TIMEOUT,
  [IdlePriority]: IDLE_PRIORITY_TIMEOUT
}

一个简略的定时器

function requestHostTimeout(callback, ms) {taskTimeoutID = setTimeout(() => {callback(getCurrentTime());
  }, ms);
}

最小堆

最小堆必然是一个齐全二叉树，而齐全二叉树的父子节点之间的地位关系是确定的，因而能够通过数组来实现一个最小堆

代码略微长，这里不做展现，因而列举上面要点：

1. 最小堆特点：在最小堆中节点的值是其子树的最小值。
2. 最小堆定理：数组中已知以后节点下标为index，那么左子节点为2*index+1，右子节点为2*index+2，父节点为Math.floor((index - 1)/2)
3. 最小堆插入元素：将新插入的元素 push 到数组，新插入的元素与其父节点比拟，如果比父节点小，则替换父子节点地位。新插入的节点顺次一直向上寻找，直到没有符合条件的节点为止。
4. 最小堆删除最小值元素：将最初一个节点替换到第一个节点的地位，而后将第一个节点下沉(满足节点是其子树的最小值即可)。

增加工作

伪代码如下，接管的参数形容如下

1. priorityLevel：优先级
2. delay：提早调度的延时工夫
3. callback：工作

let taskIdCounter = 1;
function scheduleCallback(priorityLevel, callback, delay = 0) {const currentTime = getCurrentTime();
        let startTime = currentTime + delay;
        let expirationTime = startTime + priorityMap[priorityLevel];
        const newTask = {
          id: taskIdCounter++,
          callback,
          priorityLevel,
          startTime,
          expirationTime,
          sortIndex: -1,
        };
        if (startTime > currentTime) {
          newTask.sortIndex = startTime;
          push(timerQueue, newTask);
          if (peek(taskQueue) === null && newTask === peek(timerQueue)) {
                        // 在此之前还需勾销掉之前的 timeout，因而当初才是最小的定时器工夫
            requestHostTimeout(handleTimeout, startTime - currentTime);
          }
        } else {
          newTask.sortIndex = expirationTime;
          push(taskQueue, newTask);
          if (!isHostCallbackScheduled && !isPerformingWork) {
            isHostCallbackScheduled = true; // 边界解决，确保一个事件循环外面只执行一个 flushWork
            requestHostCallback(flushWork);
          }
        }     
        return newTask;
}

scheduleCallback 首先会构建一个堆节点，其到期工夫expirationTime=currentTime+delay+priorityTime。

taskQueue 依据 currentTime+delay 来进行排序，timerQueue 依据 currentTime+delay+priorityTime 来进行排序

1. 当接管的参数 delay>0 的时候，会将新的堆节点增加到最小堆 timerQueue 中，并且如果 taskQueue 为空，并且新的堆节点是最小值，那么会在 delay 工夫之后开始调度 timerQueue 与taskQueue中的各个工作。
2. 当接管到的参数 delay<=0 的时候，会将新的堆节点增加到最小堆 taskQueue 中，如果没有在调度的循环里，则开启调度。

这里能够看到在第一种状况 delay>0 的时候，在 taskQueue 中没有工作并且新节点到期工夫不是 timerQueue 最小值的状况下，scheduler始终处于定时器的读秒阶段，一旦读秒完结，则持续开始刷新两个最小堆中的工作。留神新计划中并不会始终去轮询，与 对齐 frame 的计划 不同，不会每一帧都去判断是否有到期的工作须要执行。

留神：利用 requestAnimation 轮询对个别的利用来说，不会有太多的性能损耗，所以不用过多纠结这里的改良的价值在哪里，当你问到这个问题的时候，阐明你的利用或者比较简单，基本用不着关怀这一点。

能够看到这里增加一个新的工作不肯定会开启新一轮的调度，因为有可能正在调度中，或者正在读秒，读秒之后就开始调度。为了确保调度机制的残缺，须要在调度函数 workLoop 函数完结之前判断最小堆的状态来开启新一轮的调度。

delay 工夫之后再决定是否开启调度

advanceTimers用于将 timerQueue 中timeout的工作增加到 taskQueue 中，这里须要留神上面一点

scheduler 提供了一种能力，即便是后退出的工作，只有优先级足够高，那么就有可能在后面增加的工作之前执行

handleTimeout会调用 advanceTimers 来更新一下两个最小堆，而后依据上面的状况来来决定是读秒还是在下个事件循环中开始调度。

1. 如果 taskQueue 不为空，阐明要尽快开始调度，则利用 requestHostCallback 在下个事件循环中开始调度
2. 如果 taskQueue 为空并且 timerQueue 不为空，则须要读秒，工夫到了之后再调用 handleTimeout 来判断是读秒还是尽快调度。

function advanceTimers(currentTime) {
  // Check for tasks that are no longer delayed and add them to the queue.
  let timer = peek(timerQueue);
  while (timer !== null) {if (timer.callback === null) {
      // Timer was cancelled.
      pop(timerQueue);
    } else if (timer.startTime <= currentTime) {
      // Timer fired. Transfer to the task queue.
      pop(timerQueue);
      timer.sortIndex = timer.expirationTime;
      push(taskQueue, timer);
    } else {
      // Remaining timers are pending.
      return;
    }
    timer = peek(timerQueue);
  }
}

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

  if (!isHostCallbackScheduled) {if (peek(taskQueue) !== null) {
      isHostCallbackScheduled = true;
      requestHostCallback(flushWork);
    } else {const firstTimer = peek(timerQueue);
      if (firstTimer !== null) {requestHostTimeout(handleTimeout, firstTimer.startTime - currentTime);
      }
    }
  }
}

尽快开始调度

scheduledHostCallback是开始刷新工作的一个入口函数，这里先不予理睬。这里介绍的是什么条件才会去执行这个入口函数？

首先咱们须要晓得什么是 MessageChannel，如果搭建过 websocket 服务或者开过 chrome 插件的同学应该会很相熟这个，这里提供一个相干的实际，san-devtools。简而言之就是一个通信管道。那么为什弃用window.postmessage 而应用 MessageChannel 呢，咱们在应用 window.postmessage 的时候会触发所有通过 addEventlistener 绑定的 message 事件处理函数，因而 react 为了缩小串扰，用 MessageChannel 构建了一个专属管道，缩小了外界的串扰（当外界通信频繁数据量过大，引起缓冲队列溢出而导致管道阻塞便会影响到 react 的调度性能）以及对外界的烦扰。window.postmessage意味着是一个全局的管道，因而 MessageChannel 的毛病则是只能在肯定的作用域下才失效。

其次 postmessage/setImmediate 触发的是一个宏工作，因而两个事件循环之间会有一段闲暇工夫解决页面的交互事件，message事件处理函数 / 定时器回调函数 performWorkUntilDeadline 中会调用 scheduledHostCallback 开始调度。并且在此之前设置了到期工夫 deadline，示意从以后工夫开始，scheduledHostCallback 只可能执行yieldInterval=5ms，在执行最小堆中的下一个工作之前如果发现超时了，那么会进行执行最小堆中的工作，并且如果有工作存留则在下一个事件循环中试图开启新的调度。进行执行最小堆中的工作也是为了响应用户的交互。不过如果这里用户的交互解决逻辑过长，会导致最小堆中的工作过多，因而交互解决逻辑耗时过多则表明利用开发者的代码低劣。

let schedulePerformWorkUntilDeadline;
if (typeof setImmediate === "function") {schedulePerformWorkUntilDeadline = () => {setImmediate(performWorkUntilDeadline);
  };
} else {const channel = new MessageChannel();
  const port = channel.port2;
  channel.port1.onmessage = performWorkUntilDeadline;
  schedulePerformWorkUntilDeadline = () => {port.postMessage(null);
  };
}

function requestHostCallback(callback) {
  scheduledHostCallback = callback;
  if (!isMessageLoopRunning) {
    isMessageLoopRunning = true;
    schedulePerformWorkUntilDeadline();}
}

let yieldInterval = 5;
const performWorkUntilDeadline = () => {if (scheduledHostCallback !== null) {const currentTime = getCurrentTime();
    deadline = currentTime + yieldInterval;
    const hasTimeRemaining = true;
    let hasMoreWork = true;
    try {hasMoreWork = scheduledHostCallback(hasTimeRemaining, currentTime);
    } finally {if (hasMoreWork) {schedulePerformWorkUntilDeadline();
      } else {
        isMessageLoopRunning = false;
        scheduledHostCallback = null;
      }
    }
  } else {isMessageLoopRunning = false;}
};

调度

在 flushWork 中须要确保一段时间只有一个 flushWork，因而须要勾销requestHostCallback 读秒，以及利用 isPerformingWork 加锁。

function flushWork(hasTimeRemaining, initialTime) {
  isHostCallbackScheduled = false;
  if (isHostTimeoutScheduled) {
    isHostTimeoutScheduled = false;
    cancelHostTimeout();}
  isPerformingWork = true;
  try {return workLoop(hasTimeRemaining, initialTime);
  } finally {isPerformingWork = false;}
}

正式调度在 workLoop 中，代码太长能够联合文章结尾的图来了解。

1. 每次开始执行 task 之前，先把 timerQueue 中超时的工作压入 taskQueue，而后判断以后整个调度是否超时了(5ms)，没有超时那么刷新taskQueue 中到期的工作。在此过程中，如果工作返回了一个函数，那么这个函数会继承这个工作的到期工夫，也就是相当于模仿了一个微工作队列，用户能够在增加的函数中返回一个函数，这个函数会立刻执行（也就在以后事件循环中，并且比以后事件循环中其余的微工作更早执行）。
2. 当调度超时或者没有过期的工作的时候，进行对 taskQueue 中的工作进行扫描（执行），而后如果 taskQueue 不为空，那么返回 true，那么在下一个事件循环中会持续调度(flushWork)。如果taskQueue 为空，timerQueue不为空，则开始以最小堆的最小值读秒，读秒实现之后再通过 handleTimeout 判断是否持续读秒还是尽快开启新的调度。

function workLoop(hasTimeRemaining, initialTime) {
  let currentTime = initialTime;
  advanceTimers(currentTime);
  currentTask = peek(taskQueue);
  while (currentTask !== null) {
    if (
      currentTask.expirationTime > currentTime &&
      (!hasTimeRemaining || shouldYieldToHost())
    ) {break;}
    const callback = currentTask.callback;
    if (typeof callback === "function") {
      currentTask.callback = null;
      currentPriorityLevel = currentTask.priorityLevel;
      const didUserCallbackTimeout = currentTask.expirationTime <= currentTime;
      const continuationCallback = callback(didUserCallbackTimeout);
      currentTime = getCurrentTime();
      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
  if (currentTask !== null) {return true;} else {const firstTimer = peek(timerQueue);
    if (firstTimer !== null) {requestHostTimeout(handleTimeout, firstTimer.startTime - currentTime);
    }
    return false;
  }
}

总结

​ 这一大节，介绍了新版 scheduler 的实现原理，绝对于老版而言，在有足够工作的时候，新版将工夫切得更细，5ms一片，这样有更多的工夫来响应用户的操作。当没有工作的时候，不会因为内部 postmessage 执行 react 中的 message 事件处理函数，运行时代码更加洁净。下一节会介绍 帧对齐计划 中的启发式算法的原理，以及游戏中的 vsync 概念。

​ 有任何不正确的中央请间接评论或者分割我。