Reactのアーキテクチャを知る Scheduler編2

こんにちは、noyanです。React内部実装アドベントカレンダーの12日目です。

今日もSchedulerというパッケージのコードを読んでいきます。

前回、Schedulerの機能は現在と未来のタスク管理であり、workLoop関数がこの両方に深く関わっていることを確認しました。

今回はMin Heapの実装を確認します。というかヒープの勉強ログですね。

Heapとは

最も大きい・小さい値のpopが高速なデータ構造です。ここでは最小値を取り出すmin heapで例示します。

木の親ノードの値 <= 子ノードの値が任意のノードで成立している二分木があるとします。すると木の根は必ず最小値になるため、最小値は根を確認すれば良いです。

ヒープ (データ構造)

追加

新しい値を追加するときは、木の深さをなるべく増さないように子を２つ持たないノードに追加します。このとき、親ノード <= 子ノードの関係が崩れることがあります。その場合、子ノードの値を親ノードと交換し（再帰的に）、必ず小さい値が親ノードにあるようにします。

Pop

Popすると最小値を削除し、根を埋めます。素朴な発想では、子ノードの小さい方を再帰的に親ノードへ動かすと思います。これは（木の高さhに対してh-1は少なくとも）完全二分木であるという性質を壊す場合があり、実装上この性質を活かしたいので別の手法を取りましょう。

実際の実装では、深さhの葉の値(画像の25や100)をpopし根に代入します。こうすると消えるノードの位置が固定できます。

配列でヒープを表現する

このようにして完全二分木の性質を保つと木構造を配列で表現できます。

Heap[0]を根とし、子ノードを配列にpushし続けると、以下の性質が成り立ちます。

親ノードのインデックスをKとすると、K2K + 1 , 2K + 2が子ノードになる

実装では削除の際にArray.prototype.pop()を用い、最後の値が削除されるようにします。

Scheduler実装の面白いところ

あとは実装するだけなので、一般的な Min Heapと同じです。

function siftDown(heap, node, i) {
  let index = i;
  const length = heap.length;
  const halfLength = length >>> 1;
  while (index < halfLength) {
    const leftIndex = (index + 1) * 2 - 1;
    const left = heap[leftIndex];
    const rightIndex = leftIndex + 1;
    const right = heap[rightIndex];

    // If the left or right node is smaller, swap with the smaller of those.
    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;
    }
  }
}

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

ここで興味深いパフォーマンス改善が行われていて、rightIndex < lengthで配列外参照を防いでいる点がコアです。配列外参照をすると、v8は戻り値の型が同じであると想定した高速化が効かなくなり、たとえばv8のブログで出ている例では6倍パフォーマンスが落ちるそうです。

https://github.com/facebook/react/blob/main/packages/scheduler/src/SchedulerMinHeap.js

Here, the last iteration reads beyond the array’s length, which returns undefined, which taints not just the load but also the comparison: instead of comparing only numbers, it now has to deal with special cases. Fixing the termination condition to the proper i < array.length yields a 6× performance improvement for this example (measured on arrays with 10,000 elements, so the number of iterations only drops by 0.01%).

https://v8.dev/blog/elements-kinds#avoid-reading-beyond-the-length-of-the-array

おわりに

次回はunstable_scheduleCallbackでtaskQueueに入るタスクや、schedulerが呼び出すReactのタスクについて見て、schedulerを終わりにしようと思います。