スタックとキュー — call stack size exceeded の正体

スタックとキュー。積み重ねたカードと一列に並んだカード、処理する小さな機械。

call stack size exceeded は、スタックが積み上がりすぎた合図です。スタックとキューを自作して、その正体を確かめます。

前回: 配列と連結リスト — 先頭への追加が数百倍遅い

これは【深掘り】の記事です。本線の順路ではありません。 本線のデータ構造を自作する回で「配列は先頭への挿入が遅い」ところまでやった人が、「では、その遅さを避けるために毎日使っている道具は何なのか」を知るための記事です。飛ばしても本線は進みます。

この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。 Windows の PowerShell ではありません。 VM に Node.js が入っている必要があります。 入れ方は本線のnpmの回にあります。node -v で v20 以上が出れば大丈夫です。 作業場所は ~/cslab/sq/ です。 この記事のためだけに新しく作り、最後に全部消します。 既存のプロジェクトには触りません。 記事に出てくる測定値は私のVMの数字です。 皆さんの数字とは違います。見てほしいのは絶対値ではなく、件数を10倍にしたときに何倍になるかです。


対象レベル: 中級〜上級 / 区分: 発展

目次

「スタック」を私は2回、別の意味で覚えていた

はじめに、恥ずかしい話をします。

私は「スタック」という言葉を、まったく別の2つのタイミングで、別のものとして覚えました。

1回目は、データ構造の説明を読んだときです。

スタックは後入れ先出し(LIFO)のデータ構造です。皿を積み重ねるように、最後に置いたものを最初に取ります。

「はい、分かりました」と思いました。皿の絵も見ました。 そして、その日から一度も使いませんでした。

2回目は、その半年後です。再帰の書き方を間違えて、これが出ました。

RangeError: Maximum call stack size exceeded

私はこれを検索して、「無限ループになっている」という説明を読み、if を1行足して直しました。直りました。

そして私は、この2つが同じ「スタック」だと、まったく気づいていませんでした。

「call stack」の「stack」は、技術用語によくある比喩だと思っていました。 「処理が積み重なるイメージ」みたいな、雰囲気の話だと。

違いました。

Maximum call stack size exceeded の「stack」は比喩ではありません。 皿を積み重ねる、あのスタックが、本当にメモリの上に積み重なっていて、本当に溢れているのです。 しかも段数は数えられます。 この記事で数えます。

だから、この記事は「LIFO と FIFO という2つの言葉を覚える記事」ではありません。

すでに毎日使っているものの正体を確かめる記事です。

  • Ctrl+Z(元に戻す)
  • ブラウザの「戻る」ボタン
  • エラーの下に並ぶ、あの行の羅列(スタックトレース)
  • setTimeout に書いた処理が、なぜ後回しになるのか

この4つは全部、スタックかキューの話です。 そして4つとも、この記事で自分の手で書きます。 30行くらいで書けます。書いてしまえば、二度と「言葉を覚える」対象には戻りません。

この記事でわかること

  • Maximum call stack size exceeded の「スタック」は比喩ではないこと。自分が push と pop で作るのと同じものが、言語の内側にあって、それが溢れている
  • スタックの段数の上限は「回数」ではなく「バイト数」で決まること。同じ回数でも、関数の中身が重いと先に溢れる(実測で 12530段 と 5961段 になります)
  • スタックトレースを下から読むと呼び出し順になるのは、あれが本当にスタックを上から順に書き出したものだから、ということ。しかも既定では上10段しか出ていない
  • JavaScript の配列で作ったキューは、shift() を使うと遅いこと。20万件を取り出すだけで 4050ミリ秒(件数2倍で時間5倍。O(n²) の形です)。先頭の位置を数字で持つだけで、100万件が 4.1ミリ秒になる
  • JavaScript のイベントループも「タスクキュー」という名前のキュー(それも2本)であること。setTimeout が後回しになるのは、別の行列に並び直しているから
  • 「優先度付きキュー」はキューではないこと。名前に反して追い越しが起きる。そして順番に関する問題は、「最後にやったことから片づけたいか」の1問でほぼ決まる

この記事でやること

  1. ~/cslab/sq/ を作り、スタックを自分で書く(push / pop / peek / isEmpty)。400万件でも1件あたりの時間が増えないことを実測する
  2. わざと Maximum call stack size exceeded を出し、何段積めたかを数える。--stack-size を変えて、上限がバイト数で決まることを確かめる
  3. スタックトレースを実際に出力し、下から読むと呼び出し順になる理由を見る
  4. スタックが解いている実際の問題を3つ書く(括弧の対応・元に戻す・ブラウザの戻る)。おまけで電卓も書く
  5. キューを配列の shift() で書いて測り、先頭の位置を持つ形に直して、同じ測定で速くなることを確かめる
  6. setTimeout と Promise の実行順を出力してイベントループがキューであることを確かめ、亜種と判断基準を表にまとめて ~/cslab/ を消す

先に知る言葉

この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。

言葉意味
スタック(stack)最後に入れたものを最初に取り出す入れ物。積んだ皿。入れるのが push、取るのが pop
キュー(queue)最初に入れたものを最初に取り出す入れ物。レジの行列。入れるのが enqueue、取るのが dequeue
LIFO / FIFO上の2つの英語での呼び方。Last In First Out / First In First Out。言葉を覚えても何も分からないので、この記事では使いません
コールスタック(call stack)いま呼び出し中の関数を積んでおく、言語処理系が持っているスタック。関数を呼ぶと1段積み、return すると1段降りる
スタックフレームコールスタックの1段分。その関数の引数・ローカル変数・戻り先が入っている。中身が多いほど1段が太る
スタックトレースエラーが出た瞬間のコールスタックを、上から順に文字にしたもの。e.stack に入っている
O(1) / O(n)件数が増えたときに時間がどう増えるか。O(1) は増えない、O(n) は比例して増える。本線の計算量の回でやりました
リングバッファ決まった長さの配列を輪のように使い回すキュー。先頭と末尾の位置を数字で持ち、端まで行ったら 0 に戻る
両端キュー(deque)前と後ろの両方から入れられて、両方から取れる入れ物。スタックとしてもキューとしても使える
イベントループJavaScript が「次に何を実行するか」を決めている仕組み。実体はキュー。本線の非同期処理の回の裏側です

① スタックを自分で書く

まず作業場所を作ります。

bash
$ mkdir -p ~/cslab/sq
$ cd ~/cslab/sq
$ node -v
v22.14.0

v20 以上なら大丈夫です。 出ない場合は本線のnpmの回に戻ってください。

この記事では npm install を1回もしません。ライブラリは使いません。 使ったら、正体を確かめるという目的が消えます。

package.json だけ置きます。これは import を使うためです。

bash
$ cat > package.json <<'EOF'
  { "name": "sq", "type": "module" }
  EOF

"type": "module" の意味は「このフォルダの .js は ESM(import / export が使える形式)として読む」です。これが無いと import が構文エラーになります。あとで、この設定のせいで実行順が変わる場面が出てきます(⑥で扱います)。

スタックを書く

stack.js を作ります。

bash
$ cat > stack.js <<'EOF'
  export class Stack {
    #items = [];
  
    push(value) {
      this.#items.push(value);
      return this;
    }
  
    pop() {
      return this.#items.pop();
    }
  
    peek() {
      return this.#items[this.#items.length - 1];
    }
  
    isEmpty() {
      return this.#items.length === 0;
    }
  
    get size() {
      return this.#items.length;
    }
  }
  EOF

これで全部です。 20行もありません。

中身の説明を、1個ずつします。

メソッドやることなぜそう書けるか
push(v)一番上に置く配列の末尾に足す。末尾なら他の要素を動かさなくていい
pop()一番上を取り出して、消す配列の末尾を抜く。同じく他は動かない
peek()一番上を見るが、消さない末尾を読むだけ。これが無いと「見てから決める」が書けない
isEmpty()空かどうかpop() の戻りが undefined かで判断してはいけない。undefined を push した場合と区別がつかない

#items の # は「プライベートフィールド」です。 クラスの外から s.#items と書くと構文エラーになります。

これは飾りではありません。 スタックの本質は「上からしか触れないこと」です。中の配列に外から s.#items[3] で触れられるなら、それはただの配列です。試すと SyntaxError: Private field '#items' must be declared in an enclosing class が出て、実行される前に止まります。 制約が本物であることは、こうして確かめられます。

動かす

bash
$ cat > use-stack.js <<'EOF'
  import { Stack } from './stack.js';
  
  const s = new Stack();
  console.log('空か:', s.isEmpty());
  
  s.push('皿1').push('皿2').push('皿3');
  console.log('段数:', s.size);
  console.log('一番上を見る:', s.peek(), '(段数は', s.size, 'のまま)');
  
  console.log('取る:', s.pop());
  console.log('取る:', s.pop());
  console.log('残り:', s.size, '一番上:', s.peek());
  console.log('取る:', s.pop());
  console.log('空か:', s.isEmpty());
  console.log('空から取る:', s.pop());
  EOF
$ node use-stack.js
空か: true
段数: 3
一番上を見る: 皿3 (段数は 3 のまま)
取る: 皿3
取る: 皿2
残り: 1 一番上: 皿1
取る: 皿1
空か: true
空から取る: undefined

入れた順は 皿1・皿2・皿3、出てきた順は 皿3・皿2・皿1 です。 逆さになりました。

「逆さになる」を欠点だと思わないでください。 これがスタックを使う理由です。「最後にやったことを、最初に取り消したい」 ときには、逆さでないと困ります。

本当に O(1) か測る

「push も pop も O(1) です」と本には書いてあります。信じる前に測ります。

bash
$ cat > bench-stack.js <<'EOF'
  import { Stack } from './stack.js';
  
  for (const n of [10_000, 100_000, 1_000_000, 4_000_000]) {
    const s = new Stack();
  
    let t = performance.now();
    for (let i = 0; i < n; i++) s.push(i);
    const tPush = performance.now() - t;
  
    t = performance.now();
    while (!s.isEmpty()) s.pop();
    const tPop = performance.now() - t;
  
    console.log(
      String(n).padStart(9),
      'push', tPush.toFixed(1) + 'ms',
      'pop', tPop.toFixed(1) + 'ms',
      '→ push 1件あたり', (tPush / n * 1e6).toFixed(3) + 'ns'
    );
  }
  EOF
$ node bench-stack.js

私のVMではこうなりました。

    10000 push 1.2ms pop 1.4ms → push 1件あたり 117.420ns
   100000 push 6.0ms pop 3.5ms → push 1件あたり 60.257ns
  1000000 push 36.0ms pop 3.9ms → push 1件あたり 35.977ns
  4000000 push 60.4ms pop 13.9ms → push 1件あたり 15.089ns

読み方です。

見るところ数字意味
件数1万 → 400万(400倍)
push の合計1.2ms → 60.4ms(約50倍)400倍にしたのに50倍。比例していない
1件あたり117ns → 15ns件数を増やしたのに、1件あたりは減っている

1件あたりが増えていません。 これが O(1) の意味です。件数がいくら増えても、1回の操作にかかる時間は変わらない。

1件あたりが「減っている」のは、O(1) より速いという話ではありません。 小さいループでは、JITコンパイラが最適化を始める前の遅い時間や、計測そのものの誤差が全体に対して大きく見えます。件数が増えると、それが薄まって本来の速さが見えます。 測るときは、小さいほうの数字を信じすぎない、という教訓でもあります。

④で、これと同じ形の測定を、キューでやります。 そのときに、同じ形なのに結果がまったく違うのを見ます。


② あのエラーの正体

ここが本題です。

わざと落とす

bash
$ cat > overflow.js <<'EOF'
  let depth = 0;
  
  function dive() {
    depth++;
    dive();
  }
  
  try {
    dive();
  } catch (e) {
    console.log(e.constructor.name + ': ' + e.message);
    console.log('depth =', depth);
  }
  EOF
$ node overflow.js
RangeError: Maximum call stack size exceeded
depth = 12530

出ました。 そして、12530 という数字が出ました。

この数字が、この記事で一番大事です。

dive() は return を1回もしていません。だから dive が dive を呼び、その dive が dive を呼び、誰も降りてこない。 積むだけです。

そして 12530段目で、積む場所が無くなりました。

これは無限ループではありません。 無限ループ(while (true) {})は、何も溢れません。 CPUを使い続けるだけで、エラーは出ません。 このエラーが出るのは、呼び出しごとに場所を取る何かが、本当に積み上がっているからです。 積み上がっているものが、コールスタックです。①で自分が書いた #items と、役割は同じです。

何が1段に入っているのか

dive() は引数もローカル変数もありません。それでも1段は場所を取ります。「どこに戻るか」を覚えておく必要があるからです。

では、中身を増やしたら段数はどうなるか。 測ります。

bash
$ cat > frame-size.js <<'EOF'
  let d1 = 0;
  function light() {
    d1++;
    light();
  }
  
  let d2 = 0;
  function heavy(a, b, c, d, e) {
    d2++;
    const arr = [a, b, c, d, e];
    heavy(a, b, c, d, arr.length);
  }
  
  try { light(); } catch { console.log('引数なし        :', d1, '段');}
  try { heavy(1, 2, 3, 4, 5); } catch { console.log('引数5つ+ローカル:', d2, '段');}
  EOF
$ node frame-size.js
引数なし        : 12530 段
引数5つ+ローカル: 5961 段

半分以下になりました。

ここが誤解のもとです。 「JavaScriptは1万回くらいまでしか関数を呼べない」ではありません。 限界は「回数」ではなく「バイト数」です。 1段が太ると、積める段数が減ります。 だから、同じ再帰の書き方でも、関数の中身によって落ちる深さが変わります。 「手元では通ったのに本番で落ちた」の原因になりえます。

上限そのものを動かす

バイト数で決まっているなら、バイト数を変えれば段数が変わるはずです。 Node.js には V8 に渡すオプションがあります。

bash
$ node --stack-size=2000 overflow.js
$ node --stack-size=4000 overflow.js
RangeError: Maximum call stack size exceeded
depth = 25535
RangeError: Maximum call stack size exceeded
depth = 51135
--stack-size段数
指定なし(既定・約1MB相当)12530
2000(KB)25535
4000(KB)51135

2倍にしたら、ほぼ2倍になりました。 段数はバイト数に比例しています。推測ではなく、測って確かめられました。

だからといって --stack-size を大きくして解決してはいけません。 これは「深く積んでも大丈夫にする」オプションではなく「溢れる場所を先送りする」オプションです。設定を大きくしすぎると、このエラーが出る代わりにプロセスが異常終了することがあります。エラーで止まるほうが、まだ扱えます。 直し方は、上限を上げることではなく、積むのをやめることです。⑦の直前で扱います。

[スクリーンショット: 01_段数が変わる.png] — overflow.js の既定・2000・4000 の3回の実行結果が並んで写るように撮ります。段数がバイト数に比例していることが1枚で分かります。

スタックトレースは「上から書き出したもの」

エラーメッセージの下に並ぶ、あの行の羅列を見ます。

bash
$ cat > trace.js <<'EOF'
  function a() { b(); }
  function b() { c(); }
  function c() { throw new Error('ここで落ちた'); }
  
  try { a(); } catch (e) { console.log(e.stack); }
  EOF
$ node trace.js
Error: ここで落ちた
    at c (file:///home/user/cslab/sq/trace.js:3:22)
    at b (file:///home/user/cslab/sq/trace.js:2:16)
    at a (file:///home/user/cslab/sq/trace.js:1:16)
    at file:///home/user/cslab/sq/trace.js:5:7
    at ModuleJob.run (node:internal/modules/esm/module_job:271:25)
    at async onImport.tracePromise.__proto__ (node:internal/modules/esm/loader:578:26)
    at async asyncRunEntryPointWithESMLoader (node:internal/modules/run_main:116:5)

私が呼んだ順は a → b → c です。 表示されている順は c → b → a です。

逆さです。 ①で見た pop の順番と、同じ逆さ方です。

当たり前でした。 エラーが起きた瞬間、コールスタックはこうなっていました。

(上)  c   ← いまここ。throw した
        b
        a
        トップレベル
(下)

スタックトレースは、これを上から順に読み上げただけです。上から読み上げれば、当然「いま落ちた場所」が先に来ます。

本線のエラーの読み方の回で「エラーは下から読む」と書きました。 理由はこれです。 気合いや慣れの話ではありません。下が呼び出しの始まり、上が落ちた場所という構造だからです。 上の行は「どこで落ちたか」、下の行は「なぜそこに来たか」。 知りたいのが後者なら、下から読むのが正しい向きです。

もうひとつ、実務的な話です。 上の出力には ModuleJob.run のような、自分が書いていない行が混ざっています。これは Node.js 自身の中身です。

そして、深い再帰で落ちたときは、この逆の問題が起きます。

bash
$ node -e 'function d(){d()} d()' 2>&1 | head -8
RangeError: Maximum call stack size exceeded
    at d ([eval]:1:14)
    at d ([eval]:1:14)
    at d ([eval]:1:14)

同じ行が並ぶだけで、それも数行で終わります。

Error.stackTraceLimit は既定で 10 です。 つまりスタックトレースは、常に上から10段しか出ていません。

12530段積んで落ちたとき、見えているのは上の10段だけです。だから、深い再帰のトレースは「同じ関数名が10行並ぶ」だけで、原因が書いていません。

これを知らないと、「トレースが役に立たない」と思って読むのをやめてしまいます。 役に立たないのではなく、そういう種類のエラーだというだけです。深い再帰の原因は、トレースではなく自分の書いた終了条件を見ます。


③ スタックが実際に解いている問題

「後入れ先出し」という言葉から離れます。具体的な問題を3つ解きます。

括弧の対応が取れているか

(a[b]{c}) は正しく、(a[b)] は間違いです。これを判定します。

なぜスタックなのかを、先に考えます。 「開き括弧の数と閉じ括弧の数が同じか」では駄目です。(a[b)] は数だけなら合っています。

必要なのは「いま開いている中で、一番内側のもの」を覚えることです。 そして閉じ括弧が来たら、一番内側から順に閉じていく。

「一番最後に開いたものを、最初に閉じる」 — スタックです。

bash
$ cat > brackets.js <<'EOF'
  const PAIRS = { ')': '(', ']': '[', '}': '{' };
  const OPENS = new Set(Object.values(PAIRS));
  
  export function check(text) {
    const stack = [];
  
    for (let i = 0; i < text.length; i++) {
      const ch = text[i];
  
      if (OPENS.has(ch)) {
        stack.push({ ch, i });
        continue;
      }
      if (!(ch in PAIRS)) continue;
  
      const top = stack.pop();
      if (!top) {
        return { ok: false, why: `${i}文字目の ${ch} に対応する開き括弧が無い` };
      }
      if (top.ch !== PAIRS[ch]) {
        return { ok: false, why: `${top.i}文字目の ${top.ch} を ${i}文字目の ${ch} で閉じている` };
      }
    }
  
    if (stack.length > 0) {
      const last = stack[stack.length - 1];
      return { ok: false, why: `${last.i}文字目の ${last.ch} が閉じていない` };
    }
    return { ok: true };
  }
  EOF
$ cat > use-brackets.js <<'EOF'
  import { check } from './brackets.js';
  
  for (const s of ['(a[b]{c})', '(a[b)]', '((a)', 'a)b', '{[()]}']) {
    const r = check(s);
    console.log(s.padEnd(10), r.ok ? 'OK' : 'NG: ' + r.why);
  }
  EOF
$ node use-brackets.js
(a[b]{c})  OK
(a[b)]     NG: 2文字目の [ を 4文字目の ) で閉じている
((a)       NG: 0文字目の ( が閉じていない
a)b        NG: 1文字目の ) に対応する開き括弧が無い
{[()]}     OK

間違いの種類が3つに分かれました。

種類いつ分かるか
種類が違う括弧で閉じたpop した中身と照合したとき
開いたまま終わった最後にスタックが空でなかったとき
閉じ括弧が余っているpop が空だったとき

場所(何文字目)まで言えているのは、push するときに位置も一緒に積んだからです。 これは「エディタが ) に赤線を引く」の、いちばん素朴な版です。

エディタやコンパイラの括弧チェックは、大きくなってもこの発想のままです。 HTMLタグの閉じ忘れの検出も、同じ形です。<div> を積んで </div> で降ろす。種類が合わないとその場で分かります。

元に戻す(undo)

Ctrl+Z です。なぜスタックなのかは、もう分かるはずです。 「最後にやったことを最初に取り消す」。

ただし、undo には落とし穴があります。 それも一緒に確かめます。

bash
$ cat > editor.js <<'EOF'
  export class Editor {
    constructor() {
      this.text = '';
      this.undoStack = [];
      this.redoStack = [];
    }
  
    #apply(op) {
      this.undoStack.push(this.text);
      this.redoStack.length = 0;
      this.text = op(this.text);
    }
  
    type(s) { this.#apply((t) => t + s); }
    clear() { this.#apply(() => ''); }
  
    undo() {
      if (this.undoStack.length === 0) return console.log('  → 戻せません');
      this.redoStack.push(this.text);
      this.text = this.undoStack.pop();
    }
  
    redo() {
      if (this.redoStack.length === 0) return console.log('  → 進めません');
      this.undoStack.push(this.text);
      this.text = this.redoStack.pop();
    }
  
    show(label) {
      console.log(
        label.padEnd(10),
        JSON.stringify(this.text).padEnd(10),
        'undo:' + this.undoStack.length,
        'redo:' + this.redoStack.length
      );
    }
  }
  EOF
$ cat > use-editor.js <<'EOF'
  import { Editor } from './editor.js';
  
  const e = new Editor();
  e.type('こんにち'); e.show('入力');
  e.type('は');       e.show('入力');
  e.clear();          e.show('全消し');
  e.undo();           e.show('戻す');
  e.undo();           e.show('戻す');
  e.redo();           e.show('進む');
  e.type('!');       e.show('入力');
  e.redo();           e.show('進む');
  EOF
$ node use-editor.js
入力       "こんにち"    undo:1 redo:0
入力       "こんにちは"   undo:2 redo:0
全消し      ""         undo:3 redo:0
戻す       "こんにちは"   undo:2 redo:1
戻す       "こんにち"    undo:1 redo:2
進む       "こんにちは"   undo:2 redo:1
入力       "こんにちは!"  undo:3 redo:0
  → 進めません
進む       "こんにちは!"  undo:3 redo:0

最後の3行を見てください。

redo:1 があった状態で ! と入力したら、redo:0 になりました。 そして「進む」が効きません。

これはバグではありません。 #apply の中の this.redoStack.length = 0; が、意図的にやっています。 戻したあとに別のことをしたら、進む先は消えるのが正しい動きです。 消さないと、「こんにち」の続きに「!」を付けたのに、「こんにちは」に進めるという、あり得ない状態になります。 皆さんが使っているエディタも、必ずこうなっています。 試してみてください。

undo は「スタック1本」ではなく「スタック2本」です。 これは実際に書かないと気づけない部分でした。redo の存在が、必ずもう1本を要求します。

ブラウザの「戻る」ボタン

undo が分かれば、これは同じ形です。 「戻る」用のスタックと「進む」用のスタック、2本。

bash
$ cat > history.js <<'EOF'
  export class History {
    constructor(url) {
      this.current = url;
      this.backStack = [];
      this.forwardStack = [];
    }
  
    visit(url) {
      this.backStack.push(this.current);
      this.forwardStack.length = 0;
      this.current = url;
    }
  
    goBack() {
      if (this.backStack.length === 0) return console.log('  → 「戻る」ボタンは灰色');
      this.forwardStack.push(this.current);
      this.current = this.backStack.pop();
    }
  
    goForward() {
      if (this.forwardStack.length === 0) return console.log('  → 「進む」ボタンは灰色');
      this.backStack.push(this.current);
      this.current = this.forwardStack.pop();
    }
  
    show(label) {
      console.log(
        label.padEnd(12),
        ('いま: ' + this.current).padEnd(14),
        'back[' + this.backStack.join(' ') + ']',
        'forward[' + this.forwardStack.join(' ') + ']'
      );
    }
  }
  EOF
$ cat > use-history.js <<'EOF'
  import { History } from './history.js';
  
  const h = new History('/');
  h.visit('/a');   h.show('/a を開く');
  h.visit('/b');   h.show('/b を開く');
  h.goBack();      h.show('戻る');
  h.goBack();      h.show('戻る');
  h.goForward();   h.show('進む');
  h.visit('/z');   h.show('/z を開く');
  h.goForward();   h.show('進む');
  EOF
$ node use-history.js
/a を開く      いま: /a       back[/] forward[]
/b を開く      いま: /b       back[/ /a] forward[]
戻る          いま: /a       back[/] forward[/b]
戻る          いま: /        back[] forward[/b /a]
進む          いま: /a       back[/] forward[/b]
/z を開く      いま: /z       back[/ /a] forward[]
  → 「進む」ボタンは灰色
進む          いま: /z       back[/ /a] forward[]

最後を見てください。 2回戻ってから /z を開いたら、「進む」ボタンが灰色になりました。

これで「戻るボタンが灰色になる条件」が、感覚ではなく構造で説明できます。

ボタンの状態条件
「戻る」が灰色backStack が空。つまり、そのタブで最初に開いたページにいる
「進む」が灰色forwardStack が空。戻っていない、または戻ったあとに別のページを開いた

「新しいタブで開いたページは、戻るボタンが押せない」 のも同じ理由です。そのタブの backStack は空だからです。

本物のブラウザは、これに加えてページの状態やスクロール位置も一緒に積んでいます。 ですが、押せるか押せないかを決めているのは、この2本のスタックの長さです。

おまけ:逆ポーランド記法の電卓

余裕があればの項目です。 飛ばしても後半に影響しません。

3 + 4 を 3 4 + と書く記法です。この形なら、括弧が1つも要りません。 そしてスタック1本で計算できます。

bash
$ cat > rpn.js <<'EOF'
  const OPS = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => a / b,
  };
  
  export function calc(expr, verbose = false) {
    const stack = [];
  
    for (const token of expr.trim().split(/\s+/)) {
      if (/^-?\d+(\.\d+)?$/.test(token)) {
        stack.push(Number(token));
        continue;
      }
      const op = OPS[token];
      if (!op) throw new Error(`知らない記号: ${token}`);
  
      const b = stack.pop();
      const a = stack.pop();
      if (a === undefined || b === undefined) {
        throw new Error(`${token} に必要な数が足りない`);
      }
      stack.push(op(a, b));
      if (verbose) console.log(`  ${token} → スタック [${stack.join(', ')}]`);
    }
  
    if (stack.length !== 1) throw new Error(`式が余っている: [${stack.join(', ')}]`);
    return stack[0];
  }
  EOF
$ cat > use-rpn.js <<'EOF'
  import { calc } from './rpn.js';
  
  for (const expr of ['3 4 + 2 *', '5 1 2 + 4 * + 3 -']) {
    console.log(expr);
    console.log('  = ' + calc(expr, true));
  }
  try { calc('1 +'); } catch (e) { console.log('エラー:', e.message); }
  try { calc('1 2 3 +'); } catch (e) { console.log('エラー:', e.message); }
  EOF
$ node use-rpn.js
3 4 + 2 *
  + → スタック [7]
  * → スタック [14]
  = 14
5 1 2 + 4 * + 3 -
  + → スタック [5, 3]
  * → スタック [5, 12]
  + → スタック [17]
  - → スタック [14]
  = 14
エラー: 1 + に必要な数が足りない
エラー: 式が余っている: [1, 2, 5]

b = stack.pop() が先で a = stack.pop() が後なのが大事です。逆にすると 5 1 - が -4 になります。後から積んだほうが、引き算の右側です。

これは「変わった書き方の紹介」ではありません。 プログラムを実行する側の都合を見ています。 (1 + 2) * 3 のような形は、そのままでは順番に処理できません。括弧があるからです。 多くの処理系は、式を一度この形に直してから実行します。そして実行する部分は、いま書いた20行と同じ構造をしています。 本線のブートセクタの回で見た「CPUは上から順にしか実行しない」と、繋がっている話です。


④ キューを自分で書く(そして遅さを実測する)

キューに切り替えます。 「来た順に処理したい」ほうです。

まず素直に書く

bash
$ cat > queue-slow.js <<'EOF'
  export class SlowQueue {
    #items = [];
  
    enqueue(value) {
      this.#items.push(value);
      return this;
    }
  
    dequeue() {
      return this.#items.shift();
    }
  
    peek() {
      return this.#items[0];
    }
  
    isEmpty() {
      return this.#items.length === 0;
    }
  
    get size() {
      return this.#items.length;
    }
  }
  EOF
$ cat > use-queue.js <<'EOF'
  import { SlowQueue } from './queue-slow.js';
  
  const q = new SlowQueue();
  q.enqueue('客1').enqueue('客2').enqueue('客3');
  console.log('人数:', q.size, '次に呼ぶ人:', q.peek());
  console.log('呼ぶ:', q.dequeue());
  console.log('呼ぶ:', q.dequeue());
  console.log('呼ぶ:', q.dequeue());
  console.log('空か:', q.isEmpty());
  EOF
$ node use-queue.js
人数: 3 次に呼ぶ人: 客1
呼ぶ: 客1
呼ぶ: 客2
呼ぶ: 客3
空か: true

入れた順に出てきました。 スタックとの違いは、pop() が shift() に、peek が [0] に変わっただけです。

書き換えた場所は2箇所だけ。 それだけで、性能がまったく別のものになります。

測る

①と同じ形の測定を、そのままやります。

bash
$ cat > bench-queue.js <<'EOF'
  import { SlowQueue } from './queue-slow.js';
  
  for (const n of [10_000, 100_000, 200_000]) {
    const q = new SlowQueue();
    for (let i = 0; i < n; i++) q.enqueue(i);
  
    const t = performance.now();
    while (!q.isEmpty()) q.dequeue();
    const ms = performance.now() - t;
  
    console.log(String(n).padStart(7), '件を全部取り出す:', ms.toFixed(1) + ' ms');
  }
  EOF
$ node bench-queue.js
  10000 件を全部取り出す: 1.6 ms
 100000 件を全部取り出す: 816.9 ms
 200000 件を全部取り出す: 4050.5 ms

手が止まりました。

件数時間前の行からの倍率
1万1.6 ms—
10万816.9 ms件数10倍 → 時間510倍
20万4050.5 ms件数2倍 → 時間5倍

20万件を取り出すだけで4秒です。 計算は1つもしていません。取り出しただけです。

そして「件数2倍で時間5倍」 という形。これは比例ではありません。

原因は shift() です。 shift() は配列の先頭を抜きます。 抜いたら、残り全部を1つずつ前にずらす必要があります。 20万件のキューで1回 shift() すると、19万9999件が動きます。 それを20万回。 1回が O(n) なので、全部取り出すと O(n²) です。件数2倍で時間4倍前後になるのは、この形です。

①のスタックでは、pop() は末尾を抜くだけなので、他は1つも動きませんでした。 同じ「1件取り出す」なのに、先頭か末尾かで、これだけ違います。

これが、本線のデータ構造を自作する回で見た「配列は先頭への挿入が遅い」の、取り出し側の顔です。 あのときは「遅いらしい」で終わっていました。今回は4秒として体験できました。

[スクリーンショット: 02_shiftが遅い.png] — bench-queue.js の3行の出力が写るように撮ります。20万件で4秒という数字が読めることが大事です。

直す:先頭の位置を数字で持つ

問題は「ずらすこと」です。 では、ずらさなければいい。

取り出したら、配列を詰めるのではなく「もう取り出した」という位置を数字で覚えておきます。

bash
$ cat > queue-fast.js <<'EOF'
  export class Queue {
    #items = [];
    #head = 0;
  
    enqueue(value) {
      this.#items.push(value);
      return this;
    }
  
    dequeue() {
      if (this.#head >= this.#items.length) return undefined;
  
      const value = this.#items[this.#head];
      this.#items[this.#head] = undefined;
      this.#head++;
  
      if (this.#head > 1024 && this.#head * 2 >= this.#items.length) {
        this.#items = this.#items.slice(this.#head);
        this.#head = 0;
      }
      return value;
    }
  
    peek() {
      return this.#items[this.#head];
    }
  
    isEmpty() {
      return this.size === 0;
    }
  
    get size() {
      return this.#items.length - this.#head;
    }
  }
  EOF

変わったのは、この考え方だけです。

遅いほう速いほう
取り出したあとの配列詰める(全部ずらす)そのまま。読んだ位置を #head に足す
1回の作業量残っている件数に比例(O(n))数字を1増やすだけ(O(1))
先頭の場所いつも [0][#head]

this.#items[this.#head] = undefined; の1行を入れている理由があります。

これを書かないと、取り出したはずの値が配列の中に残り続けます。 100万件流したら、100万件分が解放されません。「動くけれどメモリが減らない」タイプの不具合になります。

そして slice の3行は「掃除」です。

#head を増やすだけだと、配列の前半が空のまま伸び続けます。半分以上が空になったら、そこで一度詰め直します。 詰め直しは O(n) ですが、n件取り出すごとに1回なので、1件あたりに割ると増えません(これを「ならし O(1)」と呼びます)。

同じ測定をやる

bash
$ cat > bench-queue2.js <<'EOF'
  import { Queue } from './queue-fast.js';
  
  for (const n of [10_000, 100_000, 200_000, 1_000_000]) {
    const q = new Queue();
    for (let i = 0; i < n; i++) q.enqueue(i);
  
    const t = performance.now();
    while (!q.isEmpty()) q.dequeue();
    const ms = performance.now() - t;
  
    console.log(String(n).padStart(9), '件を全部取り出す:', ms.toFixed(1) + ' ms');
  }
  EOF
$ node bench-queue2.js
    10000 件を全部取り出す: 1.5 ms
   100000 件を全部取り出す: 3.8 ms
   200000 件を全部取り出す: 0.8 ms
  1000000 件を全部取り出す: 4.1 ms

並べます。

件数shift() 版#head 版
1万1.6 ms1.5 ms
10万816.9 ms3.8 ms
20万4050.5 ms0.8 ms
100万(測っていません)4.1 ms

20万件で 4050ms が 0.8ms になりました。 そして100万件でも 4.1ms です。5倍の件数で、時間はほぼ同じ。

20万件が10万件より速く出ているのは誤差です。 この範囲の時間は、slice の掃除がどこで入ったか、JITの状態、他のプロセスの影響で簡単に前後します。 見るべきは「1万件と100万件が、どちらも数ミリ秒である」ことです。100倍にしても増えていない。それが O(1) です。

アルゴリズムを変えたわけではありません。 データ構造も配列のままです。 「取り出したら詰める」という、頼まれてもいない作業をやめただけで、5000倍になりました。

真のリングバッファ(長さを決めてしまう)

#head 版には、まだ引っかかる点があります。配列が伸び続けることです。 掃除で回収はしますが、一時的には大きくなります。

入る数の上限が決まっている場合は、もっと素直な形があります。 決まった長さの配列を、輪のように使い回すやり方です。

bash
$ cat > ring.js <<'EOF'
  export class RingQueue {
    constructor(capacity) {
      this.buf = new Array(capacity).fill(null);
      this.cap = capacity;
      this.head = 0;
      this.tail = 0;
      this.size = 0;
    }
  
    enqueue(value) {
      if (this.size === this.cap) throw new Error(`満杯です(capacity=${this.cap})`);
      this.buf[this.tail] = value;
      this.tail = (this.tail + 1) % this.cap;
      this.size++;
    }
  
    dequeue() {
      if (this.size === 0) return undefined;
      const value = this.buf[this.head];
      this.buf[this.head] = null;
      this.head = (this.head + 1) % this.cap;
      this.size--;
      return value;
    }
  
    show() {
      const cells = this.buf.map((v) => (v === null ? '_' : v)).join(',');
      console.log(`  buf=[${cells}] head=${this.head} tail=${this.tail} size=${this.size}`);
    }
  }
  EOF
$ cat > use-ring.js <<'EOF'
  import { RingQueue } from './ring.js';
  
  const q = new RingQueue(4);
  q.enqueue('A'); q.enqueue('B'); q.enqueue('C'); q.show();
  console.log('dequeue →', q.dequeue()); q.show();
  console.log('dequeue →', q.dequeue()); q.show();
  q.enqueue('D'); q.enqueue('E'); q.show();
  try { q.enqueue('F'); } catch (e) { console.log('  ' + e.message); }
  EOF
$ node use-ring.js
  buf=[A,B,C,_] head=0 tail=3 size=3
dequeue → A
  buf=[_,B,C,_] head=1 tail=3 size=2
dequeue → B
  buf=[_,_,C,_] head=2 tail=3 size=1
  buf=[E,_,C,D] head=2 tail=1 size=3
  満杯です(capacity=4)

最後から2行目を見てください。

  buf=[E,_,C,D] head=2 tail=1 size=3

E が、配列の先頭(0番)に入っています。 D は3番。3番の次が0番に回りました。 % this.cap がやっています。これが「輪」です。

そして head=2, tail=1 で、head が tail より後ろにいます。 配列の順番と、キューの順番が一致していません。 並んでいるのは C(2番)→ D(3番)→ E(0番)です。

配列は絶対に伸びません。 new Array(4) のまま、永久に4マスです。 その代わり、満杯になったら入れられません。 これは欠点にも見えますが、入る量に上限があると分かっている場合は、むしろ利点です。 「詰まったら、待たせるか、捨てるか、その場で決めろ」と強制されるからです。上限の無いキューは、上限が無いのではなく、メモリが尽きるまでという上限です。

この形は、あちこちに実物があります。 一定件数だけ残すログ、直近の入力を覚えておく履歴、音声や通信のデータの受け渡し。「古いものから捨てていい、決まった量のバッファ」は、たいていこの形です。


⑤ キューが実際に解いている問題(そのうち1つは毎日踏んでいる)

順番待ちの行列とジョブキュー

分かりやすいほうから片づけます。

bash
$ cat > jobs.js <<'EOF'
  import { Queue } from './queue-fast.js';
  
  const jobs = new Queue();
  jobs.enqueue({ id: 1, kind: 'メール送信' });
  jobs.enqueue({ id: 2, kind: '画像の縮小' });
  jobs.enqueue({ id: 3, kind: 'メール送信' });
  
  let tick = 0;
  while (!jobs.isEmpty()) {
    const job = jobs.dequeue();
    tick++;
    console.log(`${tick}番目に処理: #${job.id} ${job.kind}(残り ${jobs.size} 件)`);
  
    if (job.id === 2) {
      jobs.enqueue({ id: 4, kind: '縮小結果の通知' });
      console.log('   → 途中で仕事が増えた。#4 は最後尾に並ぶ');
    }
  }
  EOF
$ node jobs.js
1番目に処理: #1 メール送信(残り 2 件)
2番目に処理: #2 画像の縮小(残り 1 件)
   → 途中で仕事が増えた。#4 は最後尾に並ぶ
3番目に処理: #3 メール送信(残り 1 件)
4番目に処理: #4 縮小結果の通知(残り 0 件)

処理の途中で増えた #4 は、#3 を抜かしませんでした。 最後尾です。

これがキューの一番大事な性質です。 「あとから来たものが、先に来たものを抜かさない」。追い越されないことが保証されているから、待っている側は「いつか自分の番が来る」と言えます。 スタックでこれをやると、先に来たものが永久に処理されないことがあります。 忙しいときに一番古い仕事が放置される、という形で表に出ます。

この形は、本線のメッセージキューの回で扱った道具の、いちばん素朴な版です。 RabbitMQ が何をしてくれるのかというと、この Queue をプロセスの外に出して、落ちても消えないようにしてくれます。 キューという発想自体は、いま書いた30行と同じです。

幅優先探索(名前だけ)

キューが解いているもう1つの有名な問題が「幅優先探索」です。 迷路の最短経路や、SNSの「共通の友人」を探すときに出てきます。

この記事では扱いません。 ただ、覚えておいてほしい対応があります。

探索の種類使う入れ物
幅優先探索(近いところから全部見る)キュー
深さ優先探索(1本道を行き止まりまで進む)スタック(または再帰=コールスタック)

この2つのコードの違いは、dequeue() と pop() の1文字レベルだけです。同じループで、入れ物を変えると探索の順番が変わる。別のアルゴリズムを覚える話ではありません。

setTimeout が後回しになる本当の理由

ここが、この章の山です。

本線の非同期処理の回で、setTimeout(fn, 0) を書いても即座には実行されない、という話をしました。「イベントループがあるので」で済ませました。

その中身を見ます。

bash
$ cat > loop.js <<'EOF'
  console.log('1: 同期');
  
  setTimeout(() => console.log('4: setTimeout 0ms'), 0);
  
  Promise.resolve().then(() => console.log('3: Promise.then'));
  
  console.log('2: 同期');
  EOF
$ node loop.js
1: 同期
2: 同期
3: Promise.then
4: setTimeout 0ms

書いた順は 1 → 4 → 3 → 2 です。 出た順は 1 → 2 → 3 → 4 です。

「0ミリ秒」と書いた setTimeout が、最後に出ました。

これは「0ミリ秒が守られていない」のではありません。 setTimeout は「0ミリ秒後に実行する」という意味ではなく「0ミリ秒後に行列に並ばせる」という意味です。 並んだあと、自分の番が来るまで実行されません。

そして、その行列が2本あります。

行列の名前何が並ぶかいつ処理されるか
マイクロタスクキューPromise.then の中身など同期のコードが終わった直後、空になるまで全部
マクロタスクキュー(タスクキュー)setTimeout / setInterval / I/O などマイクロタスクが全部終わってから、1つ

動きを、もう少し細かく見ます。

bash
$ cat > loop2.js <<'EOF'
  console.log('--- 開始 ---');
  
  setTimeout(() => {
    console.log('timeout 1');
    Promise.resolve().then(() => console.log('  timeout 1 の中の micro'));
  }, 0);
  
  setTimeout(() => console.log('timeout 2'), 0);
  
  Promise.resolve()
    .then(() => { console.log('micro 1'); return Promise.resolve(); })
    .then(() => console.log('micro 2'));
  
  console.log('--- 同期の最後 ---');
  EOF
$ node loop2.js
--- 開始 ---
--- 同期の最後 ---
micro 1
micro 2
timeout 1
  timeout 1 の中の micro
timeout 2

注目してほしいのは、下の3行です。

timeout 1
  timeout 1 の中の micro     ← ここ
timeout 2

timeout 1 の中で作った Promise が、timeout 2 より先に実行されています。

マクロタスクを1つ処理したら、次のマクロタスクに行く前に、マイクロタスクの行列を空にするからです。だから timeout 1 と timeout 2 の間に割り込みます。

ここから、実務で効く結論が2つ出ます。

1. Promise を無限に生み続けると、setTimeout が永久に実行されません。 マイクロタスクの行列が空にならないので、マクロタスクの番が来ないからです。ブラウザでは、これで画面が固まります。 2. await の直後は「同期の続き」ではなく「マイクロタスクの行列に並び直した後」です。 だから、await を挟むと、その間に他のコードが動きます。

「イベントループ」という抽象的な名前のせいで、私はこれを長く「JavaScriptの神秘」だと思っていました。 実体は、④で自分が書いた Queue が2本あるだけです。並ばせる行列が違うから、順番が違う。それだけでした。

[スクリーンショット: 03_イベントループの順番.png] — node loop2.js の出力全体を撮ります。timeout 1 の中の micro が timeout 2 より前にあることが読めることが大事です。


⑥ 亜種を表で整理する

ここまでで、素直なスタックとキューは書きました。 実務で名前を見る亜種を、「何が違うのか」だけで並べます。

名前何ができるか素直な版との違いどこで見るか
スタック上から入れて上から取る—コールスタック、undo、括弧の対応
キュー後ろから入れて前から取る—ジョブキュー、イベントループ
両端キュー(deque)前後どちらからも入れられて、どちらからも取れる操作が2倍。スタックとしてもキューとしても使えるので、これ1つで足りる場面が多い直近N件の履歴、スライディングウィンドウ
循環キュー(リングバッファ)決まった長さを使い回す長さが固定。満杯だと入らない(または古いものを捨てる)ログの直近N件、通信や音声のバッファ
優先度付きキュー優先度の高いものから取れる並んだ順序が守られない(下で詳しく)緊急のジョブ、経路探索、タスクの締切順
二重終端優先度付きキュー最大も最小も取れる上のさらに変種。名前だけ知っていれば十分ほぼ出てこない

「優先度付きキュー」はキューではない

名前に騙されました。 私は「キューの一種で、ちょっと融通が利くもの」だと思っていました。

違います。

bash
$ cat > priority.js <<'EOF'
  class NaivePriorityQueue {
    #items = [];
  
    enqueue(value, priority) {
      this.#items.push({ value, priority });
      this.#items.sort((a, b) => a.priority - b.priority);
    }
  
    dequeue() {
      return this.#items.shift()?.value;
    }
  
    get size() { return this.#items.length; }
  }
  
  const pq = new NaivePriorityQueue();
  pq.enqueue('通常のメール', 5);
  pq.enqueue('日次バッチ', 9);
  pq.enqueue('パスワード再発行', 1);
  pq.enqueue('通常のメール2', 5);
  
  while (pq.size > 0) console.log('取り出し:', pq.dequeue());
  EOF
$ node priority.js
取り出し: パスワード再発行
取り出し: 通常のメール
取り出し: 通常のメール2
取り出し: 日次バッチ

入れた順と、出てきた順を比べてください。

パスワード再発行(優先度1)は3番目に入れたのに、最初に出ています。日次バッチ(優先度9)は2番目に入れたのに、最後です。優先度の順にはなっていますが、来た順にはなっていません。

これは壊れているのではなく、優先度付きキューとして正しい動きです。 後から来たものが、前に割り込みます。

気をつけたいのは、同じ優先度5の2件です。 3件目を入れた時点で並びは [1, 5, 9] になり、4件目(優先度5)を追加してから sort します。通常のメール と 通常のメール2 が入れた順で出たのは、Array.prototype.sort が安定ソート(同じ値どうしの並びを変えない)だと決まっている(ES2019 以降)からです。

つまり、同じ優先度の順番を守っているのはキューではなく、sort の性質です。 並べ方を変えれば崩れます。もう1つの問題は速さです。 enqueue のたびに配列全体を sort し直す(O(n log n))ので、件数が増えるほど1件あたりの手間が増え、大量のジョブには向きません。

要点はこれです。

この例は優先度順には出ますが、正しく速く書けているわけではありません。 同じ優先度の順番を何が決めているのか、件数が増えたらどうなるのか。見えない前提が多いことが、「優先度付きキューは自分で書くと事故る」理由です。 正しく書くには「ヒープ」という別のデータ構造が要ります。この記事では扱いません。

そして、名前についての結論です。

質問キュー優先度付きキュー
先に入れたものが先に出る?必ずいいえ
あとから来たものに抜かされる?絶対にないされる
同じ優先度のもの同士の順番は?(優先度が無い)実装次第。保証されないことが多い

つまり、キューの一番大事な性質(追い越されない)を、優先度付きキューは持っていません。 名前が似ているだけの、別の道具です。

実務でこれが問題になる形が決まっています。

「急ぎのジョブを先に処理したい」と思って優先度付きキューにすると、優先度の低いジョブが永久に処理されなくなります。 高いものが流れ込み続ける限り、順番が来ません。これを「飢餓」と呼びます。

避け方は、優先度を細かくすることではなく、行列を分けることです。 急ぎ用のキューと通常用のキューを別に持ち、それぞれの中では追い越しを起こさない。 キューの性質を捨てないための設計です。


⑦ 判断表:この2つで、ほとんど片づく

ここまで、いろいろ書きました。 実際に使うときの判断は、1つの質問です。

迷ったときに見る表

状況・やりたいこと使うものなぜ
最後にやったことを取り消したいスタック取り消す順は、やった順の逆
来た順に、公平にさばきたいキュー追い越しが起きない
一番内側の対応を探したい(括弧・タグ)スタック最後に開いたものが、最初に閉じる
ブラウザの「戻る」「進む」スタック2本戻る先と進む先で別
重い処理を後回しにしたいキュー並ばせて、順に処理する
迷路の最短経路キュー(幅優先)近い場所から全部調べる
行き止まりまで試して戻るスタック(または再帰)戻る先を積んでおく
直近N件だけ残したいリングバッファ(または両端キュー)長さが固定で、古いものが自動で消える
急ぎを先に処理したいキューを2本に分ける優先度付きキューにすると、低いほうが飢える
真ん中の要素を取りたいどちらでもない端しか触らないのが、この2つの前提。配列やマップを使う

最後の行が大事です。 「真ん中を見たい」「途中に挿入したい」が出てきた時点で、それはスタックでもキューでもありません。 無理に当てはめると、#items に外から触るコードが生えて、制約が消えます。

質問は1つ

その仕事は「最後にやったこと」から片づけたいか?
  → はい  : スタック
  → いいえ: キュー(来た順)

順番に関する問題は、ほとんどこれで決まります。 決め方が2択だから、「順番の決め方は2つしかない」 と言えます。

残りは、この2つをどう組み合わせるかです。undo はスタック2本、ブラウザの履歴もスタック2本、イベントループはキュー2本でした。新しい道具を覚える話にはなりませんでした。

おまけ:②のエラーの直し方

「積むのをやめる」と書いたので、実際にやります。 深い再帰は、自分でスタックを持てば消えます。

bash
$ cat > no-recursion.js <<'EOF'
  function sumRecursive(n) {
    if (n === 0) return 0;
    return n + sumRecursive(n - 1);
  }
  
  function sumWithStack(n) {
    const stack = [];
    for (let i = n; i > 0; i--) stack.push(i);
  
    let total = 0;
    while (stack.length > 0) total += stack.pop();
    return total;
  }
  
  try {
    console.log('再帰 100000  :', sumRecursive(100_000));
  } catch (e) {
    console.log('再帰 100000  :', e.message);
  }
  console.log('自作スタック 100000:', sumWithStack(100_000));
  console.log('自作スタック 5000000:', sumWithStack(5_000_000));
  EOF
$ node no-recursion.js
再帰 100000  : Maximum call stack size exceeded
自作スタック 100000: 5000050000
自作スタック 5000000: 12500002500000

500万件でも落ちません。

やっていることは同じです。 積んで、逆から降ろす。 違うのは、積む場所が「コールスタック」か「自分の配列」かだけです。 コールスタックには上限があり、自分の配列には(ほぼ)ありません。 ②で見たとおり、コールスタックは1MB程度の固定領域です。 再帰を「自分でスタックを持つループ」に書き換えられるのは、②の理解があって初めて出てくる発想でした。エラーメッセージが本当のスタックの話をしていると分かっていないと、この直し方は思いつきません。


つまずいたところ

遠回りした部分を、消さずに残します。

1. isEmpty() を pop() === undefined で書いて壊した

最初、isEmpty() を書かず、while (q.pop() !== undefined) でループしていました。undefined を1件 push したら、そこで止まりました。

「値が無い」と「値として undefined が入っている」は別です。空かどうかは、件数で判断するしかありません。 isEmpty() は飾りではなく必須でした。

2. --stack-size を大きくして解決したと思った

②で --stack-size=4000 にしたら深い再帰が通ったので、「直った」と思いました。直っていません。

入力が少し増えたら、また落ちます。 そして大きくしすぎると、RangeError の代わりにプロセスが黙って死ぬことがあります。エラーで止まるほうが、まだ扱えます。 直すべきは終了条件か、⑦のように積み方でした。

3. スタックトレースが10行しか出ず、「壊れている」と思った

深い再帰で落ちたとき、同じ関数名が10行並ぶだけで、原因が書いてありませんでした。Node.js の不親切だと思っていました。

Error.stackTraceLimit が既定で 10 だからです。 12530段のうち10段しか出ていません。トレースが役に立たない種類のエラーだと知っていれば、無駄に読み込まずに済みました。

4. #head 版で「値を消す1行」を忘れ、メモリが減らなかった

this.#items[this.#head] = undefined; を書かずに100万件流したら、動くのにメモリが減りませんでした。

#head を進めても、配列の中身は消えていません。 「もう読んだ」と自分は思っているだけで、参照は生きています。 「速いが、参照を持ち続ける」は、性能の話ではなく不具合です。

5. #head を進めるだけにして、配列が伸び続けた

値を undefined にしても、配列の長さは縮みません。 長時間動かすと、空マスだけの巨大な配列になります。

slice で詰め直す3行を足しました。 「O(1) にした」で終わらせず、node --expose-gc などで実際のメモリを見るのが本当です。 ここは測りきれておらず、宿題として残しています。

6. .mjs と .cjs で process.nextTick の順番が変わって混乱した

⑤で process.nextTick も混ぜて出力しようとして、こうなりました。

bash
$ cat > tick.js <<'EOF'
  process.nextTick(() => console.log('nextTick'));
  Promise.resolve().then(() => console.log('micro'));
  console.log('同期');
  EOF
$ node tick.js
$ cp tick.js tick.cjs
$ node tick.cjs
同期
micro
nextTick
同期
nextTick
micro

同じコードで、順番が逆になりました。

package.json に "type": "module" を書いたので、.js は ESM として読まれます。 ESM のトップレベルは、それ自体がすでにマイクロタスクの中で動いているため、nextTick の割り込み位置が変わります。

記事では nextTick を扱わないことにしました。 「実行順を確かめる実験は、ファイルの形式まで含めて条件を書かないと再現しない」 という教訓が残りました。

7. 優先度付きキューの「同じ優先度の順番」を、キューが守っていると思い込みやすい

⑥のコードです。通常のメール と 通常のメール2 が入れた順で出たのは、キューの工夫ではなく、sort が安定ソートだからです。

例はそのまま残しています。 「優先度付きキューは、思っているより自分で正しく書けない」ことが、正しいコードを写経するより伝わると判断したためです。正しくやるにはヒープが要りますが、一般的なヒープは同じ優先度の順番(来た順)を保証しません。 来た順も守りたいなら、優先度に加えて投入の番号も比べます。

8. 測定値が実行ごとにばらついて、どれを信じるか分からなくなった

#head 版で、20万件が10万件より速く出ました。「バグでは」と3回測り直しました。

数ミリ秒の範囲は、JITの状態や他のプロセスの影響で簡単に前後します。 数ミリ秒どうしを比べる意味はありません。 見るべきは 4050ms と 0.8ms のような、桁の違いでした。


後片づけ

この記事で作ったものを、全部消します。

まず、何があるか確認します。

bash
$ cd ~/cslab/sq
$ ls
bench-queue.js   editor.js        loop.js          priority.js      stack.js         use-history.js
bench-queue2.js  frame-size.js    loop2.js         queue-fast.js    tick.cjs         use-queue.js
bench-stack.js   history.js       no-recursion.js  queue-slow.js    tick.js          use-ring.js
brackets.js      jobs.js          overflow.js      ring.js          trace.js         use-rpn.js
package.json     rpn.js           use-brackets.js  use-editor.js    use-stack.js

node_modules はありません。 この記事では npm install を1回もしていないので、消すものは自分で書いたファイルだけです。

消す前に、場所を確かめます。

bash
$ pwd
/home/user/cslab/sq

pwd で必ず確認してください。 これから rm -rf を打ちます。別の場所で打つと、消してはいけないものが消えます。 rm で消したものは戻りません(本線の基本コマンドの回で扱いました)。

bash
$ cd ~
$ rm -rf ~/cslab
$ ls ~

cslab が消えていれば終わりです。

何も入れていないので、これで完全に元通りです。 Node.js のグローバル設定も、apt で入れたものも、この記事では触っていません。

残しておきたい場合は、stack.js queue-fast.js ring.js の3つだけコピーしておくと使い回せます。 実務ではライブラリを使うことが多いですが、中身を1度書いた3ファイルは、詰まったときに読み返す価値があります。


まとめ — 理解できたこと

  • Maximum call stack size exceeded の「スタック」は比喩ではない。 自分が push / pop で書いたのと同じものが言語処理系の中にあり、それが本当に溢れている。別々に覚えていた2つの「スタック」は、同じものだった
  • 積める段数の上限は「回数」ではなく「バイト数」で決まる。 引数もローカル変数も無い関数は 12530段、引数5つとローカル配列がある関数は 5961段。同じ書き方でも、中身が太ると先に落ちる
  • --stack-size を 2000 / 4000 にしたら 25535段 / 51135段になった。 比例している。だが、これは直し方ではない。溢れる場所を先送りしているだけ
  • スタックトレースを下から読むと呼び出し順になるのは、あれがコールスタックを上から書き出したものだから。 気合いの話ではなく構造の話。Error.stackTraceLimit が既定 10 なので、常に上10段しか見えていない
  • peek() と isEmpty() は飾りではない。 pop() の戻りが undefined かで空を判定すると、undefined を入れた瞬間に壊れる。測定も、数ミリ秒どうしを比べても意味が無く、見るのは桁の差と件数10倍あたりの倍率
  • 括弧の対応・undo・ブラウザの「戻る」は、全部スタックだった。 undo とブラウザ履歴は「スタック2本」で、redo の存在が必ずもう1本を要求する。戻ったあとに別のことをすると進む先が消えるのは、正しい動き
  • 配列の shift() でキューを作ると、20万件を取り出すだけで 4050ミリ秒かかる。 「件数2倍で時間5倍」の形は、1回が O(n) で全体が O(n²) の顔
  • 先頭の位置を数字で持つだけで、100万件が 4.1ミリ秒になった。 アルゴリズムもデータ構造も変えていない。「取り出したら詰める」という頼まれていない作業をやめただけ
  • #head 版では、読んだマスに undefined を入れる1行と、半分空いたら slice する3行が必須。 速いが参照を持ち続けるのは、性能の話ではなく不具合
  • リングバッファは配列が絶対に伸びない代わりに、満杯になったら入らない。 上限があることは欠点ではなく、「詰まったらどうするか」をその場で決めさせる利点
  • JavaScript のイベントループも、キュー(それも2本)だった。 マイクロタスクを空になるまで全部、それからマクロタスクを1つ。setTimeout(fn, 0) は「0ミリ秒後に実行」ではなく「0ミリ秒後に行列に並ばせる」
  • Promise を生み続けると setTimeout が永久に来ない。 マイクロタスクの行列が空にならないから。ブラウザでは、これで画面が固まる
  • 「優先度付きキュー」はキューではない。 キューの一番大事な性質(追い越されない)を持っていない。急ぎを先に、をやりたいなら行列を2本に分ける。優先度を付けると低いほうが飢える
  • 深い再帰は「自分でスタックを持つループ」に書き換えれば消える。 500万件でも落ちなかった。積む場所をコールスタックから自分の配列に移しただけ。この発想は、エラーメッセージが本当のスタックの話をしていると分かって初めて出てくる
  • 順番に関する問題は「最後にやったことから片づけたいか」の1問でほぼ決まる。 残りは、この2つを何本組み合わせるかだけ。新しい道具を覚える話にはならなかった

参考リンク


次に読む

この記事は 【深掘り】コンピュータ科学 の 6 / 25 本目です。

記事
← 前の記事配列と連結リスト — 先頭への追加が数百倍遅い
→ 次の記事ハッシュテーブル — 10万件のincludesで止まる

上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。

全体の順路は はじめに にあります。

roadmap.sh のどこをやっているか

›CS — Stack & Queue
  • コールスタックは比喩ではない
  • shift は O(n)。リングバッファで直す

この記事は、上の項目を実際に手を動かして確かめる回です。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次