我曾經(jīng)寫了一本書《JavaScript 核心進(jìn)階》，我用大量文字篇幅以及配套詳細(xì)視頻講解，在《V8 的垃圾回收機(jī)制底層算法原理》一文中，跟大家介紹了算法上如何從深度優(yōu)先遍歷，轉(zhuǎn)向廣度優(yōu)先遍歷。以及為什么廣度優(yōu)先遍歷可以做到任務(wù)可中斷而深度優(yōu)先遍歷做不到。又在《數(shù)據(jù)結(jié)構(gòu)堆》一文中，跟大家分享了如何利用二叉堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列。

這可就趕巧了，React 的優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)方式，居然跟我書里里介紹的方法幾乎一樣。

一、React 中的優(yōu)先級(jí)隊(duì)列

我們來(lái)看一下 React 源碼里是怎么寫的。

在這之前，先瞄一眼二叉堆的可視圖形結(jié)構(gòu)如下。這是一個(gè)小頂堆。父節(jié)點(diǎn)的數(shù)字總是比子節(jié)點(diǎn)小。

當(dāng)我想要插入一個(gè)節(jié)點(diǎn)時(shí)，只能從二叉堆結(jié)構(gòu)的最后一個(gè)位置插入。但是他插入進(jìn)來(lái)之后，如果優(yōu)先級(jí)不符合小頂堆/大頂堆的比較規(guī)則，則需要調(diào)整新節(jié)點(diǎn)的位置。因此，新的節(jié)點(diǎn)需要跟它的父節(jié)點(diǎn)進(jìn)行優(yōu)先級(jí)的比較，然后根據(jù)比較結(jié)果調(diào)整位置，這個(gè)比較可能會(huì)發(fā)生多次，直到完全符合規(guī)則為止。

React 源碼里定義了一個(gè) shftUp 來(lái)實(shí)現(xiàn)這個(gè)邏輯。

function siftUp(heap, node, i) {
  var index = i;

  while (index > 0) {
    var parentIndex = index - 1 >>> 1;
    var parent = heap[parentIndex];

    if (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;
    }
  }
}

從邏輯里來(lái)看，React 實(shí)現(xiàn)的是一個(gè)小頂堆。數(shù)字越小，優(yōu)先級(jí)越高。

在這個(gè)基礎(chǔ)之上，React 又封裝了一個(gè)更語(yǔ)義化的 push 方法來(lái)完成任務(wù)節(jié)點(diǎn)的插入。傳入的參數(shù) heap 就是 React 源碼里維護(hù)的隊(duì)列。

function push(heap, node) {
  var index = heap.length;
  heap.push(node);
  siftUp(heap, node, index);
}

當(dāng)小頂堆最頂部的元素被刪掉之后，二叉堆結(jié)構(gòu)就出現(xiàn)了混亂，我們會(huì)首先將樹結(jié)構(gòu)中的最后一個(gè)節(jié)點(diǎn)，補(bǔ)充到堆頂位置。

補(bǔ)充之后，當(dāng)前的樹結(jié)構(gòu)多半不符合小頂堆的特性，因此我們需要將新的堆頂?shù)脑嘏c它子元素進(jìn)行比較，找到最小子元素并與其交換位置，這個(gè)行為，我們可以稱之為下沉。這個(gè)比較可能會(huì)發(fā)生多次，至少完全符合規(guī)則為止。

react 源碼里也提供了一個(gè)下沉的方法

function siftDown(heap, node, i) {
  var index = i;
  var length = heap.length;
  var halfLength = length >>> 1;

  while (index < halfLength) {
    var leftIndex = (index + 1) * 2 - 1;
    var left = heap[leftIndex];
    var rightIndex = leftIndex + 1;
    // If the left or right node is smaller, swap with the smaller of those.
    var right = heap[rightIndex]; 

    if (compare(left, node) < 0) {
      if (rightIndex < length && compare(right, left) < 0) {
        heap[index] = right;
        heap[rightIndex] = node;
        index = rightIndex;
      } else {
        heap[index] = left;
        heap[leftIndex] = node;
        index = leftIndex;
      }
    } else if (rightIndex < length && compare(right, node) < 0) {
      heap[index] = right;
      heap[rightIndex] = node;
      index = rightIndex;
    } else {
      // Neither child is smaller. Exit.
      return;
    }
  }
}

有了這個(gè)方法之后，刪除節(jié)點(diǎn)的封裝就比較簡(jiǎn)單了。

function pop(heap) {
  if (heap.length === 0) {
    return null;
  }

  var first = heap[0];
  var last = heap.pop();

  if (last !== first) {
    heap[0] = last;
    siftDown(heap, last, 0);
  }

  return first;
}

React 還提供了一個(gè)工具方法 peek，用于獲取當(dāng)前的堆頂元素。

function peek(heap) {
  return heap.length === 0 ? null : heap[0];
}

最關(guān)鍵的是優(yōu)先級(jí)的比較方法。非常的簡(jiǎn)單，就跟 sort 排序需要的參數(shù)長(zhǎng)得差不多。

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

從 compare 方法中，我們可以發(fā)現(xiàn)，React 的優(yōu)先級(jí)的比較，會(huì)先比較 sortIndex，然后比較節(jié)點(diǎn) id。我們可以繼續(xù)通過(guò)源碼學(xué)習(xí)他們代表的具體含義來(lái)進(jìn)一步理解這個(gè)規(guī)則。

二、具體的優(yōu)先級(jí)

React 中，有三套不同的優(yōu)先級(jí)機(jī)制：事件優(yōu)先級(jí)、Lane 優(yōu)先級(jí)、Scheduler 優(yōu)先級(jí)。他們可以在特定的場(chǎng)景相互轉(zhuǎn)換，我們這篇文章主要探討 Scheduler 中的優(yōu)先級(jí)規(guī)則是如何設(shè)計(jì)的，在并發(fā)模式中，這是最重要的一個(gè)部分，Lane 優(yōu)先級(jí)最終也會(huì)轉(zhuǎn)換為 Scheduler 的優(yōu)先級(jí)

React 內(nèi)部有一個(gè)方法 unstable_scheduleCallback，該方法是專門用來(lái)調(diào)度任務(wù)的。

function unstable_scheduleCallback(priorityLevel, callback, options) {
  ...
}

在這個(gè)方法中，新的任務(wù)節(jié)點(diǎn)會(huì)被創(chuàng)建。

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

我們可以看到，id 屬性是一個(gè)遞增值，這個(gè)就比較好理解。

sortIndex 的默認(rèn)值為 -1，但是他后續(xù)的邏輯會(huì)因?yàn)?nbsp;startTime 與 currentTime 的比較結(jié)果重新賦值。

if (startTime > currentTime) {
  // This is a delayed task.
  newTask.sortIndex = startTime;
  push(timerQueue, newTask);
  ...
} else {
  newTask.sortIndex = expirationTime;
  push(taskQueue, newTask);
  // wait until the next time we yield.
  ...
}

所以這里的三個(gè)時(shí)間 startTime currentTime expirationTime 就非常關(guān)鍵，我們要去一一搞清楚他們都是干什么的。

先來(lái)看看 currentTime 的邏輯。

var currentTime = getCurrentTime();

/* eslint-disable no-var */
var getCurrentTime;
var hasPerformanceNow = typeof performance === 'object' && typeof performance.now === 'function';

if (hasPerformanceNow) {
  var localPerformance = performance;

  getCurrentTime = function () {
    return localPerformance.now();
  };
} else {
  var localDate = Date;
  var initialTime = localDate.now();

  getCurrentTime = function () {
    return localDate.now() - initialTime;
  };

這里做了一個(gè) performance.now() 與 Date.now() 的兼容處理?？赡軙?huì)涉及到部分同學(xué)的知識(shí)盲區(qū)。這里給大家額外科普一下

perfomance.now() 返回值表示從時(shí)間源開始算起，到調(diào)用該方法時(shí)所經(jīng)歷的時(shí)間。單位是 ms。一般來(lái)說(shuō)，當(dāng)全局對(duì)象是 Window 時(shí)，時(shí)間源會(huì)從創(chuàng)建頁(yè)面上下文開始算起。

而 Date.now() 的時(shí)間源是從 1970 年 1 月 1 日 00:00:00 (UTC) 開始算起。因此，React 源碼里，會(huì)在 JS 邏輯里重新定義一個(gè)初始時(shí)間源，然后用調(diào)用時(shí)的當(dāng)前時(shí)間減去初始時(shí)間源，這樣他們所表達(dá)的含義就基本一致了。

所以，getCurrentTime() 表達(dá)的含義為，頁(yè)面創(chuàng)建之初，到當(dāng)前我調(diào)用該方法時(shí)，這中間經(jīng)歷的時(shí)間（ms）。

我們?cè)賮?lái)看 startTime 的含義。

他的邏輯如下：

var startTime;

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;
}

可以看到，startTime 基本上都是等于 currentTime，不過(guò)當(dāng) unstable_scheduleCallback 傳入合理的 delay 時(shí)，則會(huì)在 currentTime 的基礎(chǔ)之上，加上 delay 的值，例如：

unstable_scheduleCallback(NormalPriority, cb, { delay: 2000 });

最后我們來(lái)看一下 expirationTime 的邏輯，發(fā)現(xiàn)他最終的值與 priorityLevel 有關(guān)。

var timeout;

switch (priorityLevel) {
  case ImmediatePriority:
    timeout = IMMEDIATE_PRIORITY_TIMEOUT;
    break;

  case UserBlockingPriority:
    timeout = USER_BLOCKING_PRIORITY_TIMEOUT;
    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;

那我們?cè)偻献匪菀幌聨讉€(gè)常量的值。

// 表示已經(jīng)到期，立即執(zhí)行
var IMMEDIATE_PRIORITY_TIMEOUT = -1;

var USER_BLOCKING_PRIORITY_TIMEOUT = 250;
var NORMAL_PRIORITY_TIMEOUT = 5000;

// 設(shè)置一個(gè)大值，表示永不過(guò)期
var LOW_PRIORITY_TIMEOUT = 10000;

// Tasks are stored on a min heap
var IDLE_PRIORITY_TIMEOUT = maxSigned31BitInt;

那么此時(shí)任務(wù)過(guò)期時(shí)間 expirationTime 所代表的含義就非常明確了。

這樣，我們?cè)倩剡^(guò)頭來(lái)去看優(yōu)先級(jí)比較的 sortIndex 邏輯。

if (startTime > currentTime) {
  // This is a delayed task.
  newTask.sortIndex = startTime;
  push(timerQueue, newTask);
  ...
} else {
  newTask.sortIndex = expirationTime;
  push(taskQueue, newTask);
  // wait until the next time we yield.
  ...
}

我們可以得出如下結(jié)論。

首先，sortIndex 值越大，優(yōu)先級(jí)越低。

其次，React 源碼里會(huì)維護(hù)兩個(gè)隊(duì)列。

var taskQueue = [];
// Incrementing id counter. Used to maintain insertion order.
var timerQueue = [];

當(dāng)我們?cè)谡{(diào)度一個(gè)任務(wù)時(shí)，如果傳入 delay 值，任務(wù)會(huì)進(jìn)入 timerQueue，優(yōu)先級(jí) 由 delay 決定，當(dāng) delay 值越大，優(yōu)先級(jí)越低。

如果不傳入 delay， 任務(wù)會(huì)直接進(jìn)入 taskQueue，優(yōu)先級(jí)由上面幾個(gè)常量值來(lái)決定，值越大，優(yōu)先級(jí)越低。

timerQueue 中的任務(wù)，會(huì)結(jié)合 setTimeout，在 delay 結(jié)束時(shí) push 到 taskQueue 中。然后根據(jù)優(yōu)先級(jí)執(zhí)行。

閱讀過(guò)我在 《JavaScript 核心進(jìn)階》 中的 Event Loop 章節(jié)的同學(xué)應(yīng)該可以聯(lián)想到，這里的 timerQueue，跟我們?cè)谑录h(huán)里的講的 [[PromiseFulfillReactions]] 隊(duì)列非常相似。

這就是 React 的優(yōu)先級(jí)調(diào)度器邏輯。

有了這一套基礎(chǔ)邏輯，我們就可以在此基礎(chǔ)之上，非常方便的實(shí)現(xiàn)

• 高優(yōu)先級(jí)插隊(duì)
• 任務(wù)切片
• 任務(wù)中斷
• 任務(wù)延遲

這里就不再繼續(xù)擴(kuò)展，留給大家去探索。

三、思考

不知道大家有沒有玩過(guò)網(wǎng)易的手游陰陽(yáng)師。一個(gè)回合制游戲，這個(gè)游戲的戰(zhàn)斗畫場(chǎng)景中，出手順序是按照角色/式神的速度屬性值來(lái)決定的，速度越快，越早出手。但是呢，這個(gè)游戲還設(shè)定了一個(gè)非常有意思的機(jī)制，那就是他給場(chǎng)上角色設(shè)置了一個(gè)出手進(jìn)度條，你速度越快，進(jìn)度條跑得就越快，誰(shuí)跑得越快，就越早出手。除此之外，還有很多技能可以提高進(jìn)度條的進(jìn)度，也可以有技能擊退別人的進(jìn)度條。這個(gè)機(jī)制給 PK 帶來(lái)了非常多的新玩法

比如，速度慢的出手優(yōu)先級(jí)，會(huì)隨著時(shí)間的推移變得越來(lái)越高。理解這個(gè)現(xiàn)象非常的重要，但是在我們剛才的實(shí)現(xiàn)機(jī)制中其實(shí)已經(jīng)做到了這一點(diǎn)。因?yàn)?nbsp;getCurrentTime 獲取到的時(shí)間，會(huì)隨著時(shí)間的推移變得越來(lái)越大，因此新任務(wù)的 currentTime 總比老任務(wù)更大，優(yōu)先級(jí)就更低。

又比如，速度快的，可能出手了兩次，速度慢的，都沒機(jī)會(huì)出手。我們可以用優(yōu)先出手的式神釋放一個(gè)技能去擊退目標(biāo)的進(jìn)度條，去降低他的出手優(yōu)先級(jí)。也就是說(shuō)，我們可以在優(yōu)先級(jí)高的任務(wù)邏輯里，擊退低優(yōu)先級(jí)任務(wù)的 expirationTime，讓它的優(yōu)先級(jí)進(jìn)一步變低，這樣它就有可能總是會(huì)被高優(yōu)先級(jí)的任務(wù)插隊(duì)。

因此，我們可以借鑒 react 里的任務(wù)調(diào)度機(jī)制來(lái)實(shí)現(xiàn)陰陽(yáng)師戰(zhàn)斗的這個(gè)邏輯。

我的解釋可能不那么詳細(xì)，不過(guò)玩過(guò)陰陽(yáng)師的朋友估計(jì)能理解我大概說(shuō)的是什么，可以思考一下這個(gè)機(jī)制的具體實(shí)現(xiàn)，想清楚了拿下網(wǎng)易的 offer 沒難度！