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

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

一、React 中的優(yōu)先級隊列

我們來看一下 React 源碼里是怎么寫的。

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

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

React 源碼里定義了一個 shftUp 來實現(xiàn)這個邏輯。

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

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

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

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

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

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

react 源碼里也提供了一個下沉的方法

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

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

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 還提供了一個工具方法 peek，用于獲取當(dāng)前的堆頂元素。

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

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

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)先級的比較，會先比較 sortIndex，然后比較節(jié)點 id。我們可以繼續(xù)通過源碼學(xué)習(xí)他們代表的具體含義來進(jìn)一步理解這個規(guī)則。

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

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

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

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

在這個方法中，新的任務(wù)節(jié)點會被創(chuàng)建。

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

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

sortIndex 的默認(rèn)值為 -1，但是他后續(xù)的邏輯會因為 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.
  ...
}

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

先來看看 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;
  };

這里做了一個 performance.now() 與 Date.now() 的兼容處理?？赡軙婕暗讲糠滞瑢W(xué)的知識盲區(qū)。這里給大家額外科普一下

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

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

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

我們再來看 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，不過當(dāng) unstable_scheduleCallback 傳入合理的 delay 時，則會在 currentTime 的基礎(chǔ)之上，加上 delay 的值，例如：

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

最后我們來看一下 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;

那我們再往上追溯一下幾個常量的值。

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

var USER_BLOCKING_PRIORITY_TIMEOUT = 250;
var NORMAL_PRIORITY_TIMEOUT = 5000;

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

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

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

這樣，我們再回過頭來去看優(yōu)先級比較的 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)先級越低。

其次，React 源碼里會維護(hù)兩個隊列。

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

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

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

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

閱讀過我在 《JavaScript 核心進(jìn)階》 中的 Event Loop 章節(jié)的同學(xué)應(yīng)該可以聯(lián)想到，這里的 timerQueue，跟我們在事件循環(huán)里的講的 [[PromiseFulfillReactions]] 隊列非常相似。

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

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

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

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

三、思考

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

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

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

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

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