React の更新はいつ実行されるのか — Scheduler のタスクキューを読む【Part 1】

はじめに

React のアプリで重い処理を走らせても、ブラウザが完全に固まらず、クリックや入力にちゃんと反応する。これはなぜでしょうか。

答えの中心にあるのが React の Scheduler です。React 内部の「次に何を、いつ実行するか」を協調的に決めるパッケージで、重い更新処理を細切れにし、ブラウザに制御を返しながら進めます。コンポーネントの再レンダリングや useTransition の遅延更新など、React の Concurrent な更新スケジューリングの中心にあるのがこの Scheduler です（同期更新や React の外で走る JavaScript 処理まで面倒を見るわけではありません）。

本記事はこの Scheduler のソースを読み解く連載の第1回です。まず取り上げるのは、Scheduler の中で「次に実行すべきタスク」を選び出すデータ構造 — ミニヒープ です。

Scheduler.js の冒頭にはこう書かれています。

// packages/scheduler/src/forks/Scheduler.js（一部抜粋）

// Tasks are stored on a min heap
var taskQueue: Array<Task> = [];
var timerQueue: Array<Task> = [];

「キュー」という名前なのに min heap というコメント。しかも 2 つあります。この 2 つの配列はただの FIFO でも単なる配列でもなく、ミニヒープというデータ構造として運用されている。さらに taskQueue と timerQueue という別物のヒープが 2 つ並走している、というのが Scheduler の挙動を読み解くうえで最初に押さえる土台になります。

この記事では、その「タスクキューの実体」を読み解いていきます。

この記事でわかること:

• min-heap が「親 ≤ 子」というたった1つのルールで成り立つデータ構造であること（基礎から組み立てる）
• React Scheduler のタスクキューは「配列ベースの min-heap」で実装されている
• taskQueue と timerQueue の 2 つのヒープがあり、並べる軸が違う
• sortIndex の値はキューによって expirationTime か startTime に切り替わる
• なぜ連結リストから min-heap に書き換えられたのか
• siftUp / siftDown を具体的なヒープに対して手で追える

連載内での位置:

連載: React Scheduler パッケージの詳細
├── 第1回: ミニヒープによる優先度管理   ← ★今回
├── 第2回: 優先度とタイムアウトの設計
├── 第3回: MessageChannel と協調スケジューリング
└── 第4回: Reconciler との接続

全体像 — 2つのキューと min-heap

細部に入る前に、Scheduler のキュー構造を俯瞰した図と登場人物の名前を整理しておきます。

• scheduleCallback — 「このタスクをいつか実行してね」と Scheduler に頼む入口の関数。優先度と delay（遅延ミリ秒）を渡せる
• taskQueue — いまから実行できるタスクを並べておく場所
• timerQueue — delay 指定で「まだ動かしてはいけない」タスクを並べておく場所
• workLoop — 実際にタスクを取り出して走らせる、Scheduler の心臓部
• advanceTimers — timerQueue で待機中のタスクの「実行可能時刻」が来ていないかを確認し、来ていたら taskQueue に移し替える関数

これだけ押さえれば、次の図が読めます。

この図で押さえておきたいのは次の 3 点です。

1. キューが 2 つある — taskQueue（実行可能なもの）と timerQueue（まだ delay 中で待機しているもの）
2. どちらもミニヒープ — 配列だが、根（インデックス 0）に常に最小値が来るよう維持されている
3. 昇格がある — 待機中のタスクの startTime が来たら advanceTimers が taskQueue に移し替える

ヒープを採用したことで、workLoop は taskQueue の根を peek するだけで「次に実行すべき最も期限の迫ったタスク」を即座に参照できます（peek は配列から要素を取り除かず、根を覗き見るだけの操作。計算量が O(1) で済む理由は次節「min-heap とはそもそも何か」で見ます）。実際にタスクを取り出して処理するのは pop の役割で、こちらは O(log n) です。これは後の章で繰り返し効いてくる性質です。

以降のセクションでは、この全体像の各パーツを順に掘っていきます。

min-heap とはそもそも何か — 基礎から組み立てる

ここまで「ミニヒープ」という単語をすでに使ってきましたが、ここで一度立ち止まって、min-heap がそもそも何なのかをこのセクションだけで基礎から組み上げます。すでに馴染みがある人は読み飛ばして問題ありません。

解きたい問題は「最小値だけ高速にほしい」

Scheduler が困っているのはこういう状況です。

やりたいこと:
  「次に実行すべきタスク」(= 期限が一番近いタスク) を毎回ほしい

タスクは増えたり減ったりする:
  ・新しいタスクが scheduleCallback で追加される
  ・実行が終わったタスクは取り除かれる

毎回ソートし直すのは遅い。
最小値だけ高速に取り出せる仕組みがほしい。 ← これが min-heap

「全体の順序はどうでもいい、最小値だけ即座にほしい」という要求に特化したデータ構造が min-heap です。「全部ソートしておく」のは、この要求に対して過剰です。

ルールは1つだけ — 「親 ≤ 子」

min-heap は木構造ですが、約束事はたった1つです。

親は子より小さい (または等しい)

これだけ。兄弟同士の大小関係は問いません。この一点が、後の操作コストすべてに効いてきます。

例えばこれは正しい min-heap です。

        5
       / \
      8   7
     / \
    9  10

• 5 ≤ 8 ✓
• 5 ≤ 7 ✓
• 8 ≤ 9 ✓
• 8 ≤ 10 ✓

ここで気になるのが 8 と 7 の関係です。兄弟ですが 8 > 7。それでも OK。「左の子が右の子より小さい」みたいな約束はないです。

この「親 ≤ 子だけ守る」というゆるさのおかげで、整理の手間が小さく抑えられます。完全にソートされた状態を維持しようとすると要素数に応じてコストがかさみますが、「親子関係だけ守る」なら局所的な入れ替えで済む。親 ≤ 子がツリー全体で成り立っているなら、根（一番上）には必ず最小値が来る。これが min-heap の仕組みです。

なぜ「ツリー」なのに「配列」で表現できるのか

手がかりは、min-heap が完全二分木（上から左詰めで隙間なく埋まる形）という制約を持つことです。隙間がないので、上から順に番号を振れます。

ツリー:                  幅優先で番号を振る:

        5  ←── index 0           5 (0)
       / \                       / \
      8   7  ←── index 1, 2    (1) (2)
     / \                        8   7
    9  10  ←── index 3, 4      / \
                              (3) (4)
                               9   10

配列で書くと: [5, 8, 7, 9, 10]
              ↑  ↑  ↑  ↑  ↑
          index 0  1  2  3  4

この番号の振り方には、親子の位置が計算で出せるという便利な性質があります。

index i のノードについて:
  親:    (i - 1) / 2  を切り捨て
  左の子: i * 2 + 1
  右の子: i * 2 + 2

試しに index 1（値 8）で 3 つとも計算してみます。

• 親：(1 - 1) / 2 = 0 → index 0（値 5）
• 左の子：1 * 2 + 1 = 3 → index 3（値 9）
• 右の子：1 * 2 + 2 = 4 → index 4（値 10）

ツリーを見ると確かに 8 の親は 5、子は 9 と 10。3 つの式すべてが図と一致しています。

「ツリー」と言いながら、実体は配列1本です。ノードを指すのに「ポインタ」も「左右の子へのリンク」も要らず、index の足し算引き算で動き回れます。Scheduler の実装が taskQueue: Array<Task> = [] というただの配列で済んでいるのはこのためです。

push を実例で — 末尾に置いて浮上させる

新しい値を入れるときの基本動作は次の 2 ステップだけです。

1. 末尾にくっつける — 完全二分木の形を保つには、これしか選択肢がありません
2. 親と比べて、小さければ入れ替えながら根に向かって登る — 「親 ≤ 子」のルールが回復するまで

例えば [5, 8, 7, 9, 10] に 3 を追加するなら、まず末尾に置いて [5, 8, 7, 9, 10, 3]、そこから「3 の親（index 2 の 7）と比較 → swap」「さらに親（index 0 の 5）と比較 → swap」と上がっていき、最終的に [3, 8, 5, 9, 10, 7] で根が最小値になります。具体的なステップごとの配列・ツリー対応は後段の「siftUp / siftDown を手で追う」で改めてトレースします。

この動きで効いてくるのが、最初に書いた「兄弟同士の大小は問わない」というルールです。例えば最終形 [3, 8, 5, 9, 10, 7] を見ると、8 と 5 は兄弟関係なのに 8 > 5 で、左右の大小が逆。それでも OK。だから siftUp は「自分から根への一直線」だけを面倒見ればよく、ツリー全体を走査する必要がない。これが O(log n) で済む理由です。

なぜ「自分→根」だけ見れば全体が整うのか

ここは引っかかりやすいポイントです。「自分の周りだけ swap を繰り返して、ツリー全体のルールが本当に保たれるのか」 — 触っていない枝が壊れていないか、不安になる箇所だと思います。

実際には保たれます。理由は 3 つの条件が同時に成立しているからです。

1. push 前のツリーはすでに min-heap だった — 新ノード以外の親子関係は全て成立済み。触らない枝は元から正しい
2. 新ノードは葉である — 末尾に追加されるノードは子を持たない。だから子方向のルール違反は最初から発生しない
3. swap で下に落ちる値は、元々その位置の親だった — その値は元の子に対して「親 ≤ 子」を満たしていた。swap 後にその位置に座っても、元の子との関係は壊れない

3 番目は具体例で追います。先ほどの [5, 8, 7, 9, 10] に 3 を push したケースで、2 回目の swap（5 と 3 の入れ替え）を見ます。この swap で 5 は index 0 から index 2、すなわち「子の位置」に落ちます。

swap 前:                  swap 後:
   5 (0)                    3 (0)
  / \                      / \
 8   3 (2)                8   5 (2)  ← 5 が降りてきた
 ...  \                   ...  \
       7 (5)                    7 (5)  ← この 7 と 5 の関係が問題

落ちた 5 が新しく持つ子は、index 5 にある 7 です。この 7 はもともと index 2 にあった値で、push 前のツリーでは 5 の直接の子でした（より一般のケースでは「子孫」になります）。push 前のヒープ性から「5 ≤ 7」が保証されているので、5 が 7 の親の位置に座っても「親 ≤ 子」のルールは壊れません。

一般化するとこうです: swap で下に落ちる値は、push 前にそこの「祖先」だった値（直接の親の場合も含む）。降りた先の子は push 前の「子孫」（直接の子の場合も含む）。祖先 ≤ 子孫は push 前のヒープ性で保証済みなので、新しい親子関係も自動的に成立します。

siftUp が見るのは「新ノードと祖先のライン」だけで十分、というわけです。

触る:      触らない:
  ┌─┐         ┌─┐
  │5│         │5│
  └┬┘         └┬┘
   ├──○       ├──○ ← 触らない枝（元から正しい）
   ○           ○
   ├──○       ├──○ ← 触らない枝（元から正しい）
   ○           ○
   └──新       └──新 ← 自分→根の一直線だけ swap

「自分の周りだけ整えれば全体が整う」のは、push 前にすでに整っていたから。データ構造の操作は「ゼロから作る」のではなく「正しい状態を保ったまま変化させる」のが基本発想。後で出てくる pop（siftDown）も対称な論理で、「根に末尾を置く → 子方向に降ろす」という反対向きの操作になります。

pop を実例で — 末尾を根に置いて沈める

最小値を取り出すときの動きは push の逆向き、こちらも基本は 2 ステップです。

1. 根（heap[0]）を返り値として取り出す — これだけだと「穴」が空くので、形を保つ補修が必要
2. 末尾の要素を根の位置に移し、子の小さい方と比べて入れ替えながら降りていく — こちらは siftDown

なぜわざわざ末尾を根に持ってくるのか? と疑問に思うかもしれません。素直に「shift() で先頭を抜いて全要素を1つずつ前にずらす」を選ぶと n 個の要素を全部スライドすることになり O(n)。一方、末尾を抜く操作は O(1)、それを根に置いて適切な位置まで沈めるコストも O(log n) で済みます。形を崩さずにコストを抑える、というのが選ばれた理由です。

push と同じく、こちらも具体的なステップごとのトレースは後段の siftDown セクションで配列とツリーを並走させながら追います。ここでは「子のうち小さい方と比べて、自分の方が大きければ入れ替えて降りていく」という動きの要旨だけ押さえておけば十分です。

なぜ O(log n) なのか

完全二分木の高さは log₂ n です。要素が 1024 個でも高さは 10、100 万個でも 20 程度。

• siftUp/siftDown は「自分の系統（親 → 親 → 親… or 子 → 子 → 子…）」を辿るだけ
• 1ステップで深さが1ずつ動く
• だから最悪でも log₂ n ステップで終わる

100 万個のタスクがあっても、たった 20 回程度の比較で挿入や削除が済む。「全部はソートしないけど、最小値だけは即座に分かる」を log n で実現しているのが min-heap です。

Scheduler の文脈に戻すと

ここまで分かれば、Scheduler のコードを読む準備が整いました。

用語	意味
taskQueue	min-heap。sortIndex = expirationTime で並ぶ。根 = 期限が最も近いタスク
peek(taskQueue)	heap[0] を返すだけ。O(1) で「時刻上は次に候補となるタスク」が分かる
push(taskQueue, t)	末尾追加 → siftUp で正しい位置に浮上
pop(taskQueue)	根を取得 → 末尾を根に → siftDown で沈める
compare(a, b)	「親 ≤ 子」判定の本体。sortIndex 比較 + tie-breaker は id

Scheduler の workLoop は実行中、何度も「次のタスクは?」とヒープに問い合わせます。peek が O(1) で済むからこそ、問い合わせのたびに pop のコスト（最小値を物理的に取り出して siftDown する O(log n)）を払わずに済み、実際に削除が必要になったときだけ O(log n) を支払う形になります。

ここまでで min-heap のメカニズムが揃ったので、次は「なぜ React がこれを採用したか」の歴史的経緯を見ていきます。

なぜ min-heap なのか — 連結リストからの移行

「キューにヒープを使う」というのは、データ構造の教科書では割と当たり前の選択です。ですが React 自身は最初からそうではありませんでした。SchedulerMinHeap.js が導入されたのは PR #16245（2019 年 8 月）で、それ以前は循環双方向連結リストで実装されていました。

v16.8.6 のソースを見ると、firstCallbackNode という変数を中心に線形探索で挿入位置を決めていたことがわかります。

// packages/scheduler/src/Scheduler.js（v16.8.6, 一部抜粋）

// Callbacks are stored as a circular, doubly linked list.
var firstCallbackNode = null;

// 挿入時：expirationTime 順にリストを線形探索して挿入位置を決める
var next = null;
var node = firstCallbackNode;
do {
  if (node.expirationTime > expirationTime) {
    next = node;
    break;
  }
  node = node.next;
} while (node !== firstCallbackNode);

挿入位置を見つけるためにリストを舐めていく実装です。タスク数 n に対して挿入が O(n)。

PR #16245 の description に動機が書かれています。要約すると「Scheduler は元々 React root のスケジューリング用で、root の数はせいぜい 1 個だったから連結リストでも足りていた。だが現在はタイマー等を含む多種のタスクを扱うようになり、タスク総数がずっと多くなった」という流れで、挿入 O(n) のままでは足りなくなった、という現実的な動機です。

主要操作の計算量を比較すると、

操作	連結リスト（旧）	min-heap（現在）
挿入	O(n)（線形探索）	最悪 O(log n)
最小値取得（peek）	O(1)	O(1)
最小値削除	O(1)（firstCallbackNode を次のノードに進めるだけ）	O(log n)（pop 後の siftDown）
任意位置削除（ノード参照あり）	O(1)（next/previous で外すだけ）	探索なしでは外せない（後述）
任意位置削除（探索からの場合）	O(n)（探索）+ O(1)	O(n)（探索）+ O(log n)

補足：min-heap の挿入は最悪 O(log n) ですが、push の中身は Array.prototype.push での末尾追加（O(1)）+ siftUp（最悪 O(log n)）なので、挿入位置がたまたま末尾近くで決着すれば O(1) で済みます。ランダムな入力ではこの「途中で止まる」ケースが多く、経験的には O(log n) より小さい時間で動くことが多い、というのが実用的な特性です。

「任意位置削除」の行を 2 段に分けたのは、Scheduler の実 API がそうなっているから。連結リスト時代の unstable_scheduleCallback は コールバックノードへの参照そのものを戻り値として返し、unstable_cancelCallback(callbackNode) でそのノード参照を受け取って callbackNode.next / callbackNode.previous を付け替えるだけで外せる設計でした（v16.8.6 の実装）。ノード参照を持っているなら、探索なしで O(1)。これは連結リスト構造の素直な恩恵です。

一方 min-heap では事情が変わります。ヒープ内のノードは siftUp / siftDown で位置が動くので、外部にノード参照を渡したとしても「いま配列のどの index にいるか」までは追跡できません。各ノードに「自分が今ヒープ配列のどの index にいるか」を持たせ、siftUp / siftDown のたびに更新する実装にすれば外部参照経由の O(log n) 削除も可能ですが、実装は煩雑になります。Scheduler は その煩雑さを払わず、別のアプローチ（論理削除 + 遅延物理削除）で cancelCallback を成立させて います（詳細は記事末尾のコラムで扱います）。

連結リストはタスク数が少ない時代に peek O(1) / pop O(1) / ノード参照ありの cancel O(1) が揃う構造でしたが、タスクが多くなると挿入の O(n) がそのまま全体のボトルネックになります。一方 min-heap は、挿入が最悪でも O(log n)、peek と pop はそれぞれ O(1) と O(log n) で揃っており、タスク数が増えてもバランスが崩れにくい。Scheduler の「次に実行すべき最小値だけが欲しい」というユースケースとも噛み合います。代わりに「ノード参照ありの O(1) cancel」という性質は失われ、論理削除パターンへの設計変更が必要になった、というのが移行に伴うトレードオフです。

min-heap の中身を読む — SchedulerMinHeap.js

ファイル全体は 90 行ほどで、エクスポートされているのは push / peek / pop の 3 つだけです。それぞれを順に見ていきます。

push: 末尾に追加して、浮上させる

// packages/scheduler/src/SchedulerMinHeap.js（一部抜粋）

export function push<T: Node>(heap: Heap<T>, node: T): void {
  const index = heap.length;
  heap.push(node);
  siftUp(heap, node, index);
}

配列の末尾に Array.prototype.push でくっつけて、その位置から siftUp で正しい位置まで浮上させます。

peek: 根を見るだけ

// packages/scheduler/src/SchedulerMinHeap.js（一部抜粋）

export function peek<T: Node>(heap: Heap<T>): T | null {
  return heap.length === 0 ? null : heap[0];
}

配列の先頭（根）を返すだけ。コストは O(1)。最小ヒープなので根が常に最小値、という不変条件をそのまま利用しています。

pop: 根を取り、末尾を根に置き、沈める

// packages/scheduler/src/SchedulerMinHeap.js（一部抜粋）

export function pop<T: Node>(heap: Heap<T>): T | null {
  if (heap.length === 0) return null;
  const first = heap[0];
  const last = heap.pop();
  if (last !== first) {
    heap[0] = last;
    siftDown(heap, last, 0);
  }
  return first;
}

ここで気になったのが、「先頭を取り出したい」のになぜ末尾要素をわざわざ根に持ってくるのか、という点です。

これは配列のスライド（shift()）が O(n) になってしまうから。配列の先頭を抜くと残り全要素を 1 つずつ前にずらす必要があり、ヒープ性質と関係なく遅くなります。代わりに「末尾を根に置いて、改めて適切な位置まで沈める（siftDown）」という手順を踏むことで、配列操作部分は O(1) に抑え、再構築の O(log n) だけがコストになります。

if (last !== first) のガードもさりげなく重要です。要素数が 1 のヒープで pop を呼ぶと、heap.pop() で唯一の要素が抜けて last === first の状態になります。このガードがあるおかげで「もう要素がないのに siftDown を呼ぶ」という無駄な処理を避けられます。

配列とツリーの対応

ヒープは抽象的にはツリーですが、実装は配列です。インデックスから親子関係が一意に決まります。

配列インデックス: 0    1    2    3    4    5    6
配列内容:        [ A,   B,   C,   D,   E,   F,   G ]

対応するヒープツリー:

                A (i=0)         ← 深さ 0（インデックス 0）
              /         \
          B (i=1)        C (i=2)         ← 深さ 1（インデックス 1〜2）
          /     \         /     \
       D(i=3) E(i=4)  F(i=5)  G(i=6)     ← 深さ 2（インデックス 3〜6）

なぜ配列で完全二分木が表現できるのかというと、完全二分木は「最終段以外は全ノードが埋まり、最終段は左詰めで隙間なく並ぶ」という形を持つからです。深さ 0 が 1 ノード、深さ 1 が 2 ノード、深さ 2 が 4 ノード…とレベル順（幅優先順）に並べていけば、最終段の途中まででも隙間ができずに配列に詰めていけます。「配列のインデックス」と「ツリーの深さ」が一対一に対応し、親子関係も計算で出せます。

関係	計算式	適用範囲
親インデックス	(i - 1) >>> 1	i > 0（root には親がない）
左子インデックス	i * 2 + 1	全 index
右子インデックス	i * 2 + 2	全 index

親インデックスの式は i > 0 の場合に限ることに注意してください。i = 0（root）には親がないので、そもそも親を計算する必要がありません。実際の siftUp も while (index > 0) のループ条件で root に到達した時点で抜けるので、i = 0 で親計算が呼ばれることはない作りになっています。

寄り道：>>> って何をしているのか

(i - 1) >>> 1 の >>> が何の演算か分からなかったので調べました。

>>> は「符号なし右シフト（unsigned right shift）」と呼ばれるビット演算です。やっていることは単純で、数値の 2 進数表現を右に N ビットずらすだけ。

例えば 10 >>> 1:

10 を 2進数で書くと:  1010
これを右に 1 ビットずらす:
  1010
   ↓ 右にシフト
   101    (= 5)

右端のビット（0）が押し出されて消え、左端には 0 が補充されます。結果は 101 = 10進数で 5。「右に 1 ビットシフト = 2 で割って小数切り捨て」と同じ意味になります。奇数も同様で、7 >>> 1 なら 0111 → 011 = 3、7 / 2 = 3.5 の切り捨てに一致します。

i > 0 の範囲では (i - 1) >>> 1 は Math.floor((i - 1) / 2) と同じ結果になります。前述の「親インデックス = (i - 1) / 2 を切り捨て」を、割り算ではなくビット演算で表現している、というだけの話です。

注意: i = 0 のとき両者は 一致しません。Math.floor((0 - 1) / 2) = -1 ですが、(0 - 1) >>> 1 は仕様上まず ToUint32(-1) = 4294967295（= 0xFFFFFFFF）に変換され、そこから 1bit シフトして 2147483647 という巨大な値を返します。「>>> は負数を一度 32bit 符号なし整数として読み替えてからシフトする」という挙動の影響です。現行の siftUp は while (index > 0) で root に到達した時点でループを抜けるので、この巨大値で heap[2147483647] を読みに行くことはありません。ただし PR #21147 以前は while (true) だったため、まさにこの計算が走り、heap[2147483647] の OOB read が発生していました（詳細は後段の「PR #21147 の修正と効果」で扱います）。

用語：ビット
コンピュータが扱う最小の情報単位。0 か 1 の二択。整数はこのビットを並べた 2 進数として内部に持たれている（例: 整数の 10 はメモリ上では ...00001010 という並び）。「ビット演算」は数値を 10 進数ではなく 2 進数として見て直接操作する演算で、CPU が 1 命令で実行できる軽い操作。

ではなぜ Math.floor((i - 1) / 2) ではなく >>> なのか。

ここで効くのが、JavaScript における数値の内部表現です。JS の Number 型は仕様上 64bit の浮動小数（double） ひとつしかなく、整数も小数も同じ箱で扱われます。同じ「数」を扱うのに、Math.floor と >>> では仕様上の処理が次のように違います。

• Math.floor((i - 1) / 2) — / が浮動小数の割り算、Math.floor が浮動小数を引数に取って浮動小数を返す。全工程が浮動小数のレール
• (i - 1) >>> 1 — 仕様上、左右のオペランドはまず ToUint32 で 32bit 符号なし整数に変換され、その整数に対してビット単位のシフトが行われる（ECMA-262 §6.1.6.1.11）。整数のレールで完結する経路

「同じ結果になる」と言っても、走るレールが違うわけです。

>>> を使うと、コード上で「この計算は整数の範囲で完結する」という意図が構文レベルで明示されます。実際にエンジンがどのような機械語命令に落とすか、Math.floor より必ず速いか、までは JS エンジンや状況に依存するので断定はできませんが、少なくとも仕様上は浮動小数の除算と切り捨て関数の呼び出しを通らない経路で同じ結果が得られる、と整理できます。React の SchedulerMinHeap.js でこの置換が入ったのは PR #17616 です。

用語：JIT 最適化（V8 など）
実行時にホットなコードを機械語にコンパイルして高速化する仕組み。型が安定していたり、整数演算で完結していたりするコードほど最適化が効きやすい。逆に、配列の境界外アクセスや型のブレが起きると、該当箇所のコードが最適化上不利な経路（プロトタイプチェーン確認込みの遅いパスなど）に切り替わることがある。劣化の粒度（関数全体 vs. 該当ロード単位）は条件によって異なる — 詳しくは後段「OOB read を踏むと、その配列アクセスが『遅い経路』に切り替わる」で扱う。

compare の前提 — Node 型と Task オブジェクトの関係

compare の引数の Node 型が何者なのか先に整理しておきます。SchedulerMinHeap.js の冒頭でヒープが扱う型はこう定義されています。

// packages/scheduler/src/SchedulerMinHeap.js（先頭）

type Heap<T: Node> = Array<T>;
type Node = {
  id: number,
  sortIndex: number,
  ...
};

必須フィールドは id と sortIndex の 2 つだけ。型注釈の T: Node や末尾の ... は Flow（Facebook 製の JavaScript 用静的型チェッカ。TypeScript と似た立ち位置で、React 本体のソースは Flow で書かれている）の構文です。

• 末尾の ... — 「id と sortIndex を持っていれば、それ以外のフィールドが付いていてもよい」という意味。Flow ではこれを inexact object type（open type とも）と呼ぶ。ヒープに入れる側（後述の Task オブジェクト）が callback や priorityLevel を追加で持っていても弾かれない

SchedulerMinHeap.js 側は「ヒープに入れるオブジェクトの中身は知らない、id と sortIndex さえあれば並べ替えできる」という汎用ライブラリとして書かれています。実際には別ファイル（Scheduler.js）でこの形を満たす Task オブジェクトを作って push しています。

// packages/scheduler/src/forks/Scheduler.js（unstable_scheduleCallback の中, 一部抜粋）

var newTask: Task = {
  id: taskIdCounter++,        // ★ Node が要求するフィールド
  callback,                   // 実際に走らせる関数
  priorityLevel,              // 5段階の優先度（次回扱う）
  startTime,                  // 実行可能になる時刻
  expirationTime,             // 期限切れ時刻
  sortIndex: -1,              // ★ Node が要求するフィールド（後で書き換え）
};

id と sortIndex が Node 型の必須フィールド、それ以外（callback / priorityLevel / startTime / expirationTime）は Task 固有の追加情報です。ヒープから見えるのは前者の 2 つだけで、callback などはヒープの「並び替えロジック」の関心の外にあります。

それぞれの意味を整理しておきます。

フィールド	型	値の決まり方	ヒープから見えるか
id	number	taskIdCounter++ で 1, 2, 3... と単調増加	✓ 第二の比較キー
sortIndex	number	taskQueue なら expirationTime、timerQueue なら startTime を代入	✓ 第一の比較キー
callback	関数	scheduleCallback の引数で渡される実体	✗
priorityLevel	number	1〜5（Immediate〜Idle）	✗
startTime	number	now() + delay	✗（sortIndex 経由で間接的に効くのみ）
expirationTime	number	startTime + timeout(priority)	✗（同上）

sortIndex は「キューによって何を意味するかが変わる切り替えスイッチ」として使われています。同じ Task オブジェクトでも、timerQueue に入っているときは startTime の値、taskQueue に昇格すると expirationTime の値、というふうに入れ替わります（実際の書き換えは後述の advanceTimers セクションで詳しく見ます）。

用語：構造的部分型（structural subtyping）
「型 X を満たす = X が要求するフィールドを全部持っている」という、フィールドの形だけで判定する型システム。Task は id と sortIndex を持っているので、明示的に継承を宣言しなくても自動的に Node 型の一種として扱える。TypeScript / Flow / Go のインターフェース等が採用している。

compare: sortIndex で並べ、同点なら id で決着

ここまで「親 ≤ 子」と何度も書いてきましたが、その「≤」を実際に判定しているのが compare 関数です。siftUp も siftDown も、内部ではこの関数を呼んで「どっちが小さい?」を聞いています。

// packages/scheduler/src/SchedulerMinHeap.js（一部抜粋）

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

引数 a と b は前項で見た Node 型のオブジェクト — 実体としては Task オブジェクトです。動作はこうです。

• まず sortIndex の差を取る（= 期限の早い方を「小さい」と判定）
• その差が 0 でなければそれを返す（普通はこれで決着）
• 差が 0、つまり完全に同じ sortIndex だったときに限り、id の差で決める

注目したいのは 2 段構えになっていること。なぜ sortIndex だけで終わらないのか。

「同点」が起きる現実的なケース

scheduleCallback は短い間に連続で呼ばれます。React の同じレンダリングサイクル内で複数のコールバックを登録するような場面では、こういう状況が普通に起こります。

時刻 t に、Normal 優先度のタスクを 3 つ続けて登録:
  task A: sortIndex = 5005 (= t + 5000ms)
  task B: sortIndex = 5005 (= t + 5000ms)  ← 同じ!
  task C: sortIndex = 5005 (= t + 5000ms)  ← 同じ!

Normal 優先度は timeout が 5000ms。Scheduler の現行実装は時刻取得に performance.now() を使うので時刻値はマイクロ秒オーダで返ってきます。そのぶん通常環境で複数タスクが完全に同じ時刻値を踏むのは決して頻繁ではありませんが、テスト環境で時刻をモックしている場合・タイマー解像度が粗い環境・短時間に大量の登録が起きるケースなど、同じ時刻値が返るシナリオは現実に起こりえます。同じ時刻値が getCurrentTime() から返ってきた瞬間に登録されたタスクは expirationTime も完全に一致します。これが「sortIndex の同点」が起こりうる理由です。低頻度でも起こりうる以上、比較関数としてはこれを順序づける手段を持っておく必要があります。

もし第二キーがなかったら何が起こるか

仮に compare が a.sortIndex - b.sortIndex だけを返していたとします。すると A・B・C の比較はすべて 0。ヒープから見ると「3 つは同順位」で、どれを先に取り出しても OK ということになります。

ここで困るのは、min-heap は 同順位の要素について取り出し順を保証しないデータ構造 だ、という性質です。pop のあとに末尾要素を根に移して siftDown するなど、内部の swap 経路次第で、同順位の中で誰が次に根に来るかは変わりえます。

A, B, C を順に push し、その後 pop を繰り返したとき:
  比較関数が 0 を返す要素同士は、どれが先に出てくるかが
  内部の配列操作の経路に依存する。
  登録順を保ったまま出てくる保証はない。

ユーザーから見ると「先に登録した A が先に走るだろう」と期待するのに、A が出てくるとは限らない。同順位内の取り出し順がヒープ内部の状態に依存してしまうため、登録順どおりに走るとは限らない、という曖昧さが生まれます。デバッグや再現の難しい挙動です。

補足: 一般用語で言うと、これは「安定性 (stability) がない」と表現される性質です。ソートアルゴリズムでも「安定ソート」「不安定ソート」という分け方がありますが、min-heap はそのままでは「同順位の登録順を保つ」という意味での安定性を持っていません。

id を加えるとどうなるか

id は Scheduler 内のグローバルなカウンタ taskIdCounter で 1, 2, 3... と単調に増えていきます（Scheduler.js で taskIdCounter = 1 から始まる）。先に登録されたタスクほど id が小さい、という対応です。

task A.id = 100
task B.id = 101  ← A の後に登録
task C.id = 102  ← B の後に登録

compare の第二キーがこれを使うので、A・B・C の sortIndex が同点でも、必ず A → B → C の順で出てきます。同じ sortIndex なら登録順で並ぶ という安定性が後付けされた、ということです。

ただし、これが保証するのはあくまで「同 sortIndex の中の順序」です。同じ priority のタスクでも expirationTime や startTime が違えば sortIndex も違うので、priority 単位での FIFO を意味するわけではありません。「同じレンダリングサイクル内で同 priority のタスクが連続登録され、結果的に sortIndex も一致する」というシナリオに対して安定性が効く、という限定的な保証です。

この 1 行 return diff !== 0 ? diff : a.id - b.id; で、Scheduler は「優先度ベースのキュー」に「同 sortIndex 内では登録順」という安定性を後付けしている、という構造になっています。id のような単調増加するカウンタを比較関数の第二キーに使うのは、min-heap に安定性を持たせる定番のテクニックです。

siftUp / siftDown を手で追う

3 を例にした浮上・沈降の動きはすでに見た通りです。ここからは Scheduler の実コードと突き合わせる目的で、別の例で機械的にトレースしていきます。push / pop の中で呼ばれる siftUp と siftDown こそ、ヒープが「親 ≤ 子」の不変条件を保つメカニズム。自分はコードを眺めているだけでは動きが追えなかったので、具体的な配列を書きながら値の変化を追ってみました。

siftUp の動作トレース

挿入直後の状態（末尾に追加された直後）から始まります。

初期状態 (taskQueue, sortIndex は expirationTime ms とする):
  [10, 20, 30]

push 新タスク (sortIndex = 5):
  [10, 20, 30, 5]
                ↑ index = 3

siftUp ステップ1:
  parent(3) = (3-1) >>> 1 = 1 → 値は 20
  compare(20, 5) > 0 なので swap
  [10,  5, 30, 20]
       ↑ index = 1

siftUp ステップ2:
  parent(1) = (1-1) >>> 1 = 0 → 値は 10
  compare(10, 5) > 0 なので swap
  [ 5, 10, 30, 20]
   ↑ index = 0

index = 0 になったのでループ終了。最小値 5 が根に来た。

ソースの siftUp はこれをそのまま書いた、という雰囲気です。

// packages/scheduler/src/SchedulerMinHeap.js（一部抜粋）

function siftUp<T: Node>(heap: Heap<T>, node: T, i: number): void {
  let index = i;
  while (index > 0) {
    const parentIndex = (index - 1) >>> 1;
    const 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;
    }
  }
}

siftDown の動作トレース

siftDown は siftUp の逆方向の操作です。改めて整理すると、こういう状況で呼ばれる関数になっています。

状況: pop で根の最小値を取り出した直後。
      代わりに「末尾の要素」を根の位置に移してきた。
      → 末尾要素は当然小さいとは限らないので、根の位置にいると
        「親 ≤ 子」の規則を破ってしまう。

やりたいこと: その「不当に根にいる要素」を、子と比べながら
            正しい深さまで降ろす。

降ろし方の方針:
  ・自分（親）の子 2 つを見比べて、小さい方を選ぶ
  ・自分 > 小さい方の子 なら swap して 1 段降りる
  ・自分 ≤ 両方の子 なら、もう「親 ≤ 子」を満たしているので終わり
  ・葉まで来たら終わり

siftUp が「上に這い上がる」ならこちらは「下に沈んでいく」。

siftDown という関数名がそのまま挙動を表しています。さっきの siftUp 完了後の 4 要素ヒープに対して pop を呼ぶケースで具体例を見てみます。

直前の状態（siftUp 完了後、要素数 4）:
  [5, 10, 30, 20]

pop を呼ぶと、pop 関数の内部でこういう前処理が走る:

  first = heap[0] = 5        ← これが返り値になる（最小値の取り出し）
  last  = heap.pop() = 20    ← 配列末尾を切り取る、配列は要素数 3 の [5, 10, 30]
  heap[0] = last             ← 末尾要素 20 を根に置く: [20, 10, 30]

  → このあと siftDown(heap, 20, 0) を呼ぶ

ツリーで見ると、こうなっています。

       20  ← 不当に根に居座っている末尾要素
      /  \
    10    30

20 は明らかに 10 より大きいので「親 ≤ 子」が崩れています。これを直すのが siftDown の仕事です。

siftDown ステップ1:
  今の位置: index = 0 (値 20)
  左の子: index = 0 * 2 + 1 = 1 → 値 10
  右の子: index = 0 * 2 + 2 = 2 → 値 30
  小さい方の子は左の 10。
  自分 (20) > 小さい方の子 (10) なので swap、1 段降りる。

  配列: [10, 20, 30]
              ↑ 20 が index 1 に降りた

  ツリー:
         10  ← 10 が根に浮上
        /  \
      20    30

これで根の「親 ≤ 子」は直りました（10 ≤ 20、10 ≤ 30）。20 はまだ自分の位置で「親 ≤ 子」を満たしているか確認したいところですが、20 が降りた index 1 はすでに葉なので、これ以上降りる必要はありません。

siftDown ステップ2:
  今の位置: index = 1 (値 20)
  index = 1 は概念的には葉（子の index 3, 4 はどちらも length = 3 の範囲外）。
  → 現行コードではループ条件 index < halfLength（= 1 < 1）が false になり、
    ループ本体に入らずに終了。
    つまり子の heap[3] / heap[4] を読みに行くこと自体が起きない。

「子の index を計算してから範囲外と判定する」のではなく、「そもそもループに入らない」というのが現行コードの挙動。halfLength がこの早期終了を実現していることは、次節「halfLength の意味と V8 最適化」で詳しく見ます。

最終状態:

配列: [10, 20, 30]
ツリー:
       10
      /  \
    20    30

pop の返り値は最初に取り出した 5。配列は「親 ≤ 子」が成り立った min-heap に戻っています。

ソースの siftDown がこの動きをそのまま書いたもの、と読めるか確かめてみます。

// packages/scheduler/src/SchedulerMinHeap.js（一部抜粋）

function siftDown<T: Node>(heap: Heap<T>, node: T, i: number): void {
  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];

    // The left child is less than its parent.
    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;
    }
  }
}

トレースの「子 2 つを見比べて小さい方を選ぶ」は if (compare(left, node) < 0) 以下の分岐、「自分 ≤ 両方の子なら終わり」は末尾の return に対応している、と読み取れます。

一方で、自分が読んだときに意味が掴めなかった行が 2 つ残りました。

• ループ条件の index < halfLength
• const halfLength = length >>> 1

ここは次の「halfLength の意味と V8 最適化」で掘り下げます。

siftUp と並べてみると対称性がよく見えます。

項目	siftUp	siftDown
いつ呼ばれるか	push の最後	pop の最後
始点	末尾（新規追加先）	根（index 0）
動く方向	上へ（根に向かう）	下へ（葉に向かう）
比較相手	親 1 つ	子 2 つのうち小さい方
終了条件	根に到達 or 親 ≤ 自分	葉に到達 or 自分 ≤ 両方の子

halfLength の意味と V8 最適化

ここからは、先ほどの siftDown コードで予告した 2 行 — const halfLength = length >>> 1 と while (index < halfLength) — に焦点を絞ります。halfLength という名前は何を表していて、なぜループ条件にこれが使われているのか。この 2 行を解きほぐすと React のコードがなぜここまでこだわっているかが見えてきます。

halfLength は「子を持つ最後の親インデックス + 1」

計算内容だけ見ると、halfLength = length >>> 1 は要素数 n を 2 で割って切り捨てた値。例えば要素数 7 のヒープなら halfLength = 3 です。

意味は「index 0 〜 (halfLength - 1) のノードだけが子を持っている」。

要素数 n = 7 のヒープ:
  配列インデックス: 0  1  2  3  4  5  6
                   [A, B, C, D, E, F, G]
  halfLength = 7 >>> 1 = 3

ツリー:
              A (i=0)
            /         \
        B (i=1)        C (i=2)
        /     \        /     \
     D(i=3) E(i=4)  F(i=5) G(i=6)
     ↑      ↑       ↑       ↑
     葉     葉      葉       葉  ← どれも子を持たない

• 子を持つノード（親）: index 0, 1, 2 ← halfLength = 3 未満
• 子を持たないノード（葉）: index 3, 4, 5, 6 ← halfLength = 3 以上

ループ条件 index < halfLength は「自分がまだ親なら、子を見比べる必要があるからループを続ける。葉になったらやることはないから抜ける」を表現しています。

なぜ境界がちょうど length >>> 1 になるのか — 手で導く

halfLength = length >>> 1 の >>> 1 は 2 で割って切り捨て、つまり Math.floor(length / 2) と同じです。問題は「なぜ 割って切り捨てる だけで、ぴったり親と葉の境目になるのか」。

ステップ 1: 「最後の親」のインデックスを直接求める

ヒントは 子から親を逆算する公式 です。配列インデックスの完全二分木では、子と親の関係は次のように対応しています。

ノード i の左子: leftIndex  = i * 2 + 1
ノード i の右子: rightIndex = i * 2 + 2

  ↓ ひっくり返すと

ノード c の親:   parentIndex = Math.floor((c - 1) / 2)

子インデックス c を 2 で割って切り捨てると親に戻る、というのが配列で表現した完全二分木の性質です。

ここで考えたいのは「配列の一番最後の要素（index = length - 1）の親は誰か?」ということ。length ≥ 2 なら配列末尾の要素は必ず誰かの子になっているので、その親が「最後の親」になります。length = 1 のときは root しか存在せず親も子もありませんが、その場合 halfLength = 1 >>> 1 = 0 となり、while (index < halfLength) のループは一度も入らないので siftDown は何もせず終わります。以下の導出は length ≥ 2 を前提に進めます。

末尾のインデックス: length - 1
その親のインデックス: Math.floor(((length - 1) - 1) / 2)
                   = Math.floor((length - 2) / 2)  ← これが「最後の親」

インデックスは整数なので、ここでは必ず切り捨て（floor）が入ります。

親と判定したい範囲は index 0 から「最後の親」まで。ループ条件 index < halfLength は「葉に到達したら止まる」なので、halfLength には 「最後の親」+ 1 = Math.floor((length - 2) / 2) + 1 を入れたい。これを整理します。

halfLength = Math.floor((length - 2) / 2) + 1
           = Math.floor(length / 2)

Math.floor((length - 2) / 2) + 1 がなぜ Math.floor(length / 2) になるかは、length の偶奇で分けて確かめれば見えてきます。

• length が偶数（= 2k）のとき: Math.floor((2k - 2) / 2) + 1 = (k - 1) + 1 = k = Math.floor(2k / 2)
• length が奇数（= 2k + 1）のとき: Math.floor((2k - 1) / 2) + 1 = (k - 1) + 1 = k = Math.floor((2k + 1) / 2)

どちらも Math.floor(length / 2) に一致。そして JS の length >>> 1 は 非負整数の length に対して Math.floor(length / 2) と同じ結果 を返します。これが length >>> 1 の正体です。

ステップ 2: 偶奇で具体的に確かめる

数式だけだと不安なので、実際の値で見ます。

length = 7（奇数、index 0〜6）:
  末尾 index = 6
  最後の親 = (6 - 1) / 2 切り捨て = 2
  halfLength = 2 + 1 = 3  ←  7 >>> 1 = 3 と一致 ✓
  親: index 0, 1, 2 / 葉: index 3, 4, 5, 6

length = 8（偶数、index 0〜7）:
  末尾 index = 7
  最後の親 = (7 - 1) / 2 切り捨て = 3
  halfLength = 3 + 1 = 4  ←  8 >>> 1 = 4 と一致 ✓
  親: index 0, 1, 2, 3 / 葉: index 4, 5, 6, 7

偶数のときの「最後の親」（index 3）は左子（index 7）しか持たない片足の親ですが、それでも左子との比較は必要なので親として扱いたい。length >>> 1 はこの片足の親もちゃんと境界の内側に取り込んでくれます。

ポイント: halfLength は「親の個数」と一致する値であると同時に、「最初に登場する葉のインデックス」でもあります。だから index < halfLength は「まだ親なら続ける、葉に着いたら止まる」をひとつの不等式で書けています。

ただし注意点があります。完全二分木では「最後の親」が右子を持つかどうかは要素数の偶奇で変わります。

要素数 n = 7（奇数）の場合:
  halfLength = 3。最後の親は index 2。
  → 左子 index 5、右子 index 6。どちらも配列内に存在する。

要素数 n = 8（偶数）の場合:
  halfLength = 4。最後の親は index 3。
  → 左子 index 7 は配列内に存在するが、
    右子 index 8 は配列の範囲外（length = 8 のため）。

halfLength が保証してくれるのは左子の存在だけで、右子は依然として「あるかないか」を確認する必要があります。これが、現行 siftDown で右子側にだけ if (rightIndex < length && ...) のガードが残っている理由です。なお、コードを読むと const right = heap[rightIndex] の read 自体はガードより前 に実行されているので、ガードが防いでいるのは「右子の値を実際に compare で使うこと」であって、配列 read 自体ではありません（read 側に残った OOB の話は後段「右子側の OOB は残っている」で扱います）。

旧コードの形を見てみる

PR #21147 以前の siftDown は、ループ条件として index < length を使い、子の存在は 値が undefined かどうか で判定する作りでした。

// PR #21147 以前の siftDown（実差分から該当部分を抜粋）
while (index < length) {
  const leftIndex = (index + 1) * 2 - 1;
  const left = heap[leftIndex];           // ← 先に読んでしまう
  const rightIndex = leftIndex + 1;
  const right = heap[rightIndex];         // ← 同じく先に読んでしまう

  if (left !== undefined && compare(left, node) < 0) {
    if (right !== undefined && compare(right, left) < 0) {
      // ...右子と swap...
    } else {
      // ...左子と swap...
    }
  } else if (right !== undefined && compare(right, node) < 0) {
    // ...右子と swap...
  } else {
    return;
  }
}

ポイントは 2 つ。

1. ループ条件は index < length だが、index が 配列内に収まっていること と その index のノードが子を持つこと はイコールではない。葉ノード（子を持たない）でも index < length なら成立してしまう
2. 子の存在判定は left !== undefined / right !== undefined という 値チェック で行っており、heap[leftIndex] / heap[rightIndex] の 読み取りは判定より先 に走る

OOB read がいつ起きるか

要素数 4 のヒープ（index 0〜3）で、ルート（index = 0）から siftDown が始まるケースを追ってみます。

[1 ループ目] index = 0
  leftIndex  = 1, rightIndex = 2  → どちらも範囲内、セーフ
  仮に左子と swap、index = 1 に降りる

[2 ループ目] index = 1
  ループ条件 1 < 4 → 通過
  leftIndex  = 3                  → 範囲内、heap[3] は普通に読める
  rightIndex = 4                  → 配列の範囲外（length = 4）!
  const right = heap[4]           ← ★ OOB read 発生
  → right は undefined になる
  → 後続の分岐では right は undefined として扱われる
    （左子が小さければ左子と swap して続行、左子も小さくなければ return）

問題は const right = heap[4] の行です。配列の長さは 4 なので、index 4 は範囲外。それでも JavaScript では例外を投げず、undefined が返ってきます。その後の分岐は right を undefined として扱うので機能上は問題なく動く。動いてしまうからこそ気づきにくい、というのが厄介な点です。

なお、葉ノード（子なし）まで降りた場合も同様です。例えば index = 3 まで降りたら leftIndex = 7、rightIndex = 8 で、どちらも範囲外。heap[7] / heap[8] を読みに行って両方 undefined、最終的に return で抜ける、という流れになります。

この「動いてしまう OOB read」が、次節で見る「該当配列アクセスが遅い経路に切り替わる」という罠につながります。

OOB read を踏むと何が起きるか — 「遅い経路」への切り替わり

PR #21147（2021-04）はこの OOB read を消すための修正で、PR description では「de-optimization を避ける」と説明されています。

ただし V8 周辺の用語整理を先にしておく必要があります。V8 にはいくつか段階のあるパフォーマンス劣化があって、よく混同されます。

• 関数全体の de-optimize（脱最適化） — V8 が機械語にコンパイル済みの関数を「想定外のことが起きたので安全な経路に戻す」と差し戻す処理。一段重いペナルティ
• 個別ロードの slow path 化 — 配列アクセス 1 行（= 1 つの load 命令）の挙動学習メモが切り替わり、以後そのアクセスだけが「特殊ケースも扱う遅い経路」を通るようになる現象

PR description の「de-optimization」が前者を厳密に指しているかは PR 本文だけでは断定できませんが、V8 公式ブログ Elements kinds in V8 が OOB read について直接書いているのは後者の挙動です。本記事では V8 ブログが直接根拠にできる後者を主軸に扱い、PR 用語との対応関係を補足する形で進めます。

用語：de-optimize（脱最適化）
厳密には「最適化された関数を機械語版からインタプリタ実行に差し戻す」ことを指す V8 用語。本節で扱うのはより局所的な「配列アクセス 1 行が以後遅い経路を通るようになる」現象（V8 内部では inline cache の状態遷移として実装されている）で、関数全体の de-opt とは区別すると正確。

V8 公式ブログが指している「load 単体の slow path 化」が具体的にどういう現象なのかを見ていきます。前提として、配列の範囲外を読んだとき JavaScript は裏で面倒な処理をしています。表面的には「範囲外なら undefined が返るだけ」に見えますが、エンジン側ではそれを実現するために重い処理が走ります。

範囲内と範囲外でアクセス処理がどれくらい違うか見ます。

heap[3] にアクセス（length = 4 の配列）:
  → メモリ上の連続領域から 4 番目を読む。1 命令で終わり。

heap[5] にアクセス（length = 4 の配列）:
  → 「heap 配列自身は 5 番目を持っていない」と判定
  → 持っていないなら「heap の親（= Array.prototype）に 5 番目はあるか?」を確認
  → そこにも無い → 「さらにその親（= Object.prototype）に 5 番目はあるか?」を確認
  → そこにも無い → 親がもういない → ようやく undefined を返す

なぜわざわざ親まで見に行くのか? JS のオブジェクトは「自分が持っていないプロパティは親に聞きに行く」というルール（プロトタイプチェーンと呼びます）で動いていて、配列もその例外ではないからです。

補足: heap[5] が undefined を返すのは「範囲外だから」ではなく、親までずっと聞いて回った結果どこにも無かったから、というのが内部の動き。試しに Array.prototype[5] = 'foo' を実行すると、heap[5] は undefined ではなく 'foo' を返してきます。範囲外アクセスは仕様レベルで親探索を必須としています。

範囲内なら 1 命令で終わるアクセスが、範囲外になった瞬間に親探索を伴う処理に切り替わる。これだけでも重いですが、本当の問題はここからです。

V8 は同じコードが何回も呼ばれるとそれを高速な機械語にコンパイルする際、配列アクセス 1 行ごとに「これまでに観測したアクセスパターン」を覚えるメモ（inline cache）を持っています。最初のうち全ての観測が「普通の範囲内アクセス」で済んでいれば、その load 命令は「親探索なしの速い経路」を選びます。問題は、ここに 1 回でも範囲外アクセスが混ざったとき。V8 公式ブログ Elements kinds in V8 はこう書いています。

"Once a load has run into this situation, V8 remembers that 'this load needs to deal with special cases', and it will never be as fast again."

拙訳: ある配列読み取り処理が一度でもこの状況（範囲外アクセス）に遭遇すると、V8 は「この読み取りは特殊ケースを扱う必要がある」と覚え込み、それ以降そのアクセスは二度と元の速さには戻らない。

ここでブログが言っている "this load" は 「その配列アクセス 1 行」 であって、関数全体ではないことに注目してください。一度範囲外を踏むとそのメモが「範囲外もあり得る」に書き換わり、それ以降、その配列アクセスの行は「範囲内なら速いパス、範囲外なら親探索を含む遅いパス」の両対応コードに差し替わります。毎回チェックが入るぶんずっと遅くなる、というわけです。

つまり OOB read は「1 回親を辿る分だけ遅い」のではなく、そのコード行の配列アクセスが以後ずっと両対応モードに切り替わる恒久的なペナルティ です。たった 1 行の範囲外アクセスが踏まれるだけで、siftDown のホットなループ内の該当 load が以後ずっと遅く動き続ける、というのはこのためです。

PR #21147 の修正と効果

ここまで siftDown の halfLength 導入に絞って見てきましたが、PR #21147 の中身はそれだけではありません。OOB read による slow path 化（PR description の言葉では「de-optimization」）を避ける、という同じ目的のもとで、ヒープ実装の複数箇所に手が入っています。

// peek: undefined 判定 → length 判定
- const first = heap[0];
- return first === undefined ? null : first;
+ return heap.length === 0 ? null : heap[0];

// pop: undefined 判定 → length 判定 + 早期 return
// （省略、本質は peek と同じ）

// siftUp: while (true) → while (index > 0)
- while (true) {
+ while (index > 0) {
    const parentIndex = (index - 1) >>> 1;
    const parent = heap[parentIndex];
-   if (parent !== undefined && compare(parent, node) > 0) {
+   if (compare(parent, node) > 0) {

// siftDown: while (index < length) → halfLength 導入
+ const halfLength = length >>> 1;
+ while (index < halfLength) {

それぞれの変更が何を消しているのか整理します。

関数	旧コードの問題	修正内容
peek	空配列で heap[0] を read（範囲外）	length === 0 を先にチェック
pop	同上、空配列で heap[0] を read	length === 0 を先にチェック
siftUp	while (true) で root 到達後も次の周回に入り、(0 - 1) >>> 1 = 2147483647 で heap[2147483647] を read	while (index > 0) で root の親計算を打ち切り
siftDown	while (index < length) で葉ノードでもループ本体に入り、子の heap[...] を OOB read	while (index < halfLength) で「子を持つ親」だけ処理

siftDown の halfLength がよく取り上げられますが、siftUp 側の (0 - 1) >>> 1 で生まれる巨大 index も同じ「最適化上不利な経路」を踏みうる構造でした（>>> が符号なし右シフトなので、負数になる引き算結果が 32bit 整数の上限近くに化ける挙動については、本記事の >>> 解説節を参照）。

右子側の OOB は残っている

修正後の現行コードを見ると、左子側は halfLength で抑え込まれていますが、右子側は素朴に書かれています。

// packages/scheduler/src/SchedulerMinHeap.js（一部抜粋）
while (index < halfLength) {
  const leftIndex = (index + 1) * 2 - 1;
  const left = heap[leftIndex];
  const rightIndex = leftIndex + 1;
  const right = heap[rightIndex]; // ← rightIndex < length のチェックより前!

  if (compare(left, node) < 0) {
    if (rightIndex < length && compare(right, left) < 0) {
      // ...
    }
  }
}

ここで疑問が湧きます。

const right = heap[rightIndex]; を rightIndex < length の判定より前にやっているなら、OOB read が起きうる。さっきの「一度 OOB を踏むと永久に遅くなる」というルールに照らすと、ここもダメなのでは?

確かにこの 1 行は範囲外アクセスを踏みうる経路です。範囲外が起きる条件は限定的で、rightIndex === length になるのは「length が偶数」かつ「index がいま最後の親（左子しか持たない片足の親）に降りてきている」ときに限られます。siftDown の途中で swap が止まれば return で抜けるため、最後の親まで毎回到達するわけではありません。

ただし、V8 公式ブログが言っているのは "that load will never be as fast again"（そのロード は二度と元の速さに戻らない）です。劣化するのは「OOB を踏んだ配列アクセス行」であって、その行が一度でも OOB を踏めば、その後はループ内で毎回その行を通るたびに「遅いパス」を経由することになります。OOB が起きる頻度が限定的でも、いったん起きてしまえば以後そのロードは恒久的に劣化しうる、というのが厳密な読み方です。

補足: V8 にはさらに「Array.prototype や Object.prototype に何も追加されていない限り、範囲外アクセスは即 undefined を返してよい」という近道のしくみ（V8 ブログ内では "no elements" protector と呼ばれています）もあって、右子側の OOB read の実コストはこれでも薄められている可能性があります。

ここからは記事側の推測になります。PR #21147 の本文が明示しているのは「out-of-bounds access の改善」と「ベンチ結果」までで、右子 read を残した理由までは説明されていません。コード構造を見ると左子側ほどの hot path ではなさそうですが、PR とベンチ結果だけから「だから影響は十分小さい」と断定はできません。同じ修正を if (rightIndex < length) { const right = ...; ... } の形でも書けたはず、というのは事実として残しておきます。

ベンチ結果

PR に添付されたベンチマーク結果は次の通りです。

データ規模	修正前	修正後	改善倍率
100 タスク	17,740 ops/sec	441,482 ops/sec	約 25 倍
10,000 タスク	1,430 ops/sec	14,038 ops/sec	約 10 倍

この数字は PR #21147 全体（peek / pop / siftUp / siftDown の 4 箇所の変更）の効果 であって、halfLength 1 つに帰属させられるものではない、という点に注意です。ただし siftDown は pop のたびに呼ばれる hot path で、その中の左子 read は葉ノードに降りるたびに毎回踏む構造だったので、寄与が最も大きい変更だったと推測できます。

halfLength 単体としては、「アルゴリズムの早期終了」と「V8 の最適化を維持するための境界制御」を兼ねており、データ構造の正しさだけでなく JS エンジンの実装上の癖まで踏み込んで設計されています。

なぜキューを 2 つに分けるのか — taskQueue vs timerQueue

ここまで「ヒープが 2 つある」と話してきましたが、なぜ 1 つにまとめなかったのか? 答えは unstable_scheduleCallback の振り分け処理を見ると見えてきます。

// packages/scheduler/src/forks/Scheduler.js（unstable_scheduleCallback 一部抜粋）

if (startTime > currentTime) {
  // ---- 遅延タスク → timerQueue ----
  newTask.sortIndex = startTime;
  push(timerQueue, newTask);
  // ...
} else {
  // ---- 即時タスク → taskQueue ----
  newTask.sortIndex = expirationTime;
  push(taskQueue, newTask);
  // ...
}

startTime > currentTime（= まだ実行できない delay 付きタスク）と、それ以外で格納先のキューと sortIndex の値が両方変わります。

キュー	格納条件	sortIndex	並べる軸の意味
taskQueue	startTime <= currentTime（即時実行可）	expirationTime	「いつ期限切れになるか」
timerQueue	startTime > currentTime（delay 中）	startTime	「いつ実行可能になるか」

なぜ別キューにしないと困るのか

結論を先に言ってしまうと、1 本のキューに混ぜると peek で返ってきたタスクが「今すぐ実行できる」とは限らなくなる 、これが問題の本質です。順序がぐちゃぐちゃになる、という話ではありません。expirationTime で並べたヒープの根は、確かに「最も期限が迫っているタスク」を返してくれます。でも workLoop が欲しいのは「今すぐ動かせるタスク」。この 2 つは別物 だ、という話です。

ヒープが約束してくれるのは「ある 1 つの軸での最小値」だけです。複数条件を同時に満たす最小値を返す機能はない。具体例で見てみます。

前提: Normal 優先度（timeout = 5000ms）のタスクを 2 つ用意します。

時刻 0ms に B が登録された（delay = 2000ms 付き）:
  B.startTime      = 2000ms
  B.expirationTime = 7000ms

時刻 1000ms に A が登録された（即時実行）:
  A.startTime      = 1000ms （即時実行可）
  A.expirationTime = 6000ms

これを 1 本のキューにまとめ、expirationTime で並べたとします。

1 本キュー内（expirationTime 順、小さい方が根）:

         A (expirationTime = 6000ms, startTime = 1000ms)
        / \
       B (7000ms, 2000ms)   ...

まず A が根に来るので peek は A を返す。A は実行可能なのでこれは問題なし。A を処理して pop した後、workLoop が次の peek を呼ぶと、今度は B が返ってきます。

問題はここです。仮に現在時刻が 1100ms だとすると、B の startTime = 2000ms はまだ未来。peek した結果が「まだ動かせないタスク」になっています。

ヒープの並び自体は壊れていません。expirationTime の小さい順に正しく並んでいる。ただ、workLoop が暗黙に期待していた「peek の結果は実行可能」という前提が、expirationTime という基準では成立しないだけです。

ポイント: startTime の順序と expirationTime の順序は無関係。delay 付きタスクは登録が早い分 expirationTime も小さくなりがちで、即時タスクより「期限切れには近い」が「まだ動かせない」という逆転が普通に起きる。

この状態に陥ったとき、workLoop の選択肢は 2 つしかありません。

1. B をスキップして次を見る — でも peek は状態を変えない以上、また同じ B が返ってくる。pop で取り除いて後で戻すなら、push で O(log n) のコストが追加でかかる
2. B を待つ — その間に他の即時タスクが入ってきても気付けない

どちらも、ヒープの「O(1) で peek できる」「peek の結果はそのまま処理すべきもの」という単純さが崩れる。

これを避けるために、Scheduler は「キューに入っている時点で startTime が到来済み」という 不変条件 を taskQueue に持たせています。実行可能になるまでは timerQueue で待機させ、時刻が来たら taskQueue に移し替える。この設計なら peek(taskQueue) の結果は 時刻の意味で 実行可能なタスクであることが保証されます。

補足: 「callback が non-null」までは保証されません。cancelCallback で論理削除された task は taskQueue 内に tombstone として残るので、peek(taskQueue) が callback === null の task を返すケースがあります。workLoop 側はこれを見て pop(taskQueue) で物理削除する流れになっています（詳細は後段のコラム「cancelCallback と論理削除」を参照）。

この「移し替え」を担うのが advanceTimers です。

// packages/scheduler/src/forks/Scheduler.js（advanceTimers 一部抜粋。コメントは説明用に和訳）

function advanceTimers(currentTime: number) {
  let timer = peek(timerQueue);
  while (timer !== null) {
    if (timer.callback === null) {
      pop(timerQueue);                       // キャンセル済み
    } else if (timer.startTime <= currentTime) {
      pop(timerQueue);
      timer.sortIndex = timer.expirationTime; // ★ ここで sortIndex を書き換える
      push(taskQueue, timer);
    } else {
      return;                                // 残りも全て pending（heap 性質より）
    }
    timer = peek(timerQueue);
  }
}

ここで見るべき点は 2 つあります。

1. 昇格時に sortIndex を書き換える — timerQueue では startTime だった値を、taskQueue に入れる前に expirationTime に差し替えています。同じ Task オブジェクトを使い回し、キューへ入れるタイミングで比較キーだけを切り替えている形です
2. else の return の効率性 — timerQueue は min-heap なので、peek した先頭が「最も早く動き出すタスク」。それが currentTime より未来なら、残りも全て未来であることが構造的に保証される

特に 2 点目は、peek が O(1) であることに続く ヒープを採用したことのもう一つの恩恵 です。線形リストや任意の配列だったら「まだチェックしていない要素に startTime が小さいものがあるかも」と疑い続ける必要があり、即 return できません。「根が最小値」というヒープの不変条件が、ループの早期終了を保証してくれているわけです。

コラム — cancelCallback と論理削除

連結リスト時代の cancel が O(1) だったのに対し、min-heap への移行で「途中要素の効率的な削除手段」が失われた、という話は「連結リストからの移行」セクションで触れました。ここでは Scheduler がその穴をどう埋めているか、実装を具体的に見ます。

採用されているのは 論理削除 + 遅延物理削除（tombstone パターン） です。

// 概念コード
function unstable_cancelCallback(task) {
  task.callback = null; // 論理削除：callback を null にするだけ
}

ヒープからの物理削除はしません。代わりに workLoop が peek でその task を参照したとき、callback === null を見てその時点で初めて pop（物理削除）します。

// packages/scheduler/src/forks/Scheduler.js（workLoop 一部抜粋）

const callback = currentTask.callback;
if (typeof callback === "function") {
  // ...通常実行...
} else {
  pop(taskQueue); // ← null だったので物理削除
}

まとめ — 第1回で押さえたこと

第1回で見えたのは、Scheduler の「キュー」が次の特徴を持つことです。

• データ構造はミニヒープ。taskQueue と timerQueue の 2 本が並走している
• 2 本ある理由は並べる軸の違い。taskQueue は expirationTime 順、timerQueue は startTime 順
• 昇格は advanceTimers が担い、sortIndex を書き換えて taskQueue に push する
• 連結リストから min-heap への移行は PR #16245。タスク数増加への対応
• siftUp / siftDown は配列ベースで実装され、>>> や halfLength は V8 最適化を意識した書き方
• cancelCallback は論理削除 + 遅延物理削除（tombstone）で対処

ここまでで「タスクキューの実体がミニヒープであり、sortIndex という比較キーで動いている」という土台ができました。

次回（第2回）は「ではその sortIndex に入る expirationTime はどう決まるのか」を扱います。React の 5 段階の優先度（Immediate / UserBlocking / Normal / Low / Idle）が、なぜそれぞれ -1 / 250ms / 5000ms / 10000ms / 事実上無限という timeout を持つのか。starvation（飢餓）はどう防がれるのか。優先度設計の Why を掘っていきます。

参考

• packages/scheduler/src/SchedulerMinHeap.js（main ブランチ） — 本記事で読み解いたヒープ実装本体
• packages/scheduler/src/forks/Scheduler.js（main ブランチ） — taskQueue / timerQueue の宣言、unstable_scheduleCallback、advanceTimers、workLoop
• PR #16245: [Scheduler] Store Tasks on a Min Binary Heap — 連結リストから min-heap への移行（2019-08-08）
• PR #21147: [perf] Improve SchedulerMinHeap implementation — out-of-bounds access に起因する V8 最適化上の不利な経路の回避（PR description の表現では「de-optimization の回避」）を主眼に、peek / pop / siftUp / siftDown を改修（2021-04）
• PR #17616 — Math.floor から >>> への置換
• v16.8.6 時代の Scheduler.js — 連結リスト時代の実装（比較用）
• SchedulerMinHeap.js のコミット履歴 — 変更履歴の追跡
• V8 公式: Elements kinds in V8 — 配列境界外アクセスが V8 の最適化上不利になる理由（PR #21147 の根拠）。本文中「a load that has run into this situation... will never be as fast again」「operations on holey arrays require ... expensive lookups on the prototype chain」を引用
• ECMA-262 §10.1.8.1 OrdinaryGet — obj[key] の [[Get]] 内部処理。プロパティが見つからない場合に親プロトタイプの [[Get]] を呼び出すと規定（範囲外配列アクセスがプロトタイプチェーンを辿る仕様根拠）
• MDN: Number — JS の数値が IEEE 754 倍精度 64bit 浮動小数として扱われることの説明（>>> 採用の前提）
• ECMA-262 §6.1.6.1.11 Number::unsignedRightShift — >>> が両オペランドを ToUint32 で変換してから動作する旨の仕様本文
• ECMA-262 §7.1.8 ToUint32 — 32bit 符号なし整数への変換抽象操作の定義