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問でほぼ決まる
この記事でやること
~/cslab/sq/を作り、スタックを自分で書く(push/pop/peek/isEmpty)。400万件でも1件あたりの時間が増えないことを実測する- わざと
Maximum call stack size exceededを出し、何段積めたかを数える。--stack-sizeを変えて、上限がバイト数で決まることを確かめる - スタックトレースを実際に出力し、下から読むと呼び出し順になる理由を見る
- スタックが解いている実際の問題を3つ書く(括弧の対応・元に戻す・ブラウザの戻る)。おまけで電卓も書く
- キューを配列の
shift()で書いて測り、先頭の位置を持つ形に直して、同じ測定で速くなることを確かめる 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 が「次に何を実行するか」を決めている仕組み。実体はキュー。本線の非同期処理の回の裏側です |
① スタックを自分で書く
まず作業場所を作ります。
v22.14.0
v20 以上なら大丈夫です。 出ない場合は本線のnpmの回に戻ってください。
この記事では npm install を1回もしません。ライブラリは使いません。 使ったら、正体を確かめるという目的が消えます。
package.json だけ置きます。これは import を使うためです。
"type": "module"の意味は「このフォルダの.jsは ESM(import/exportが使える形式)として読む」です。これが無いとimportが構文エラーになります。あとで、この設定のせいで実行順が変わる場面が出てきます(⑥で扱います)。
スタックを書く
stack.js を作ります。
これで全部です。 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 が出て、実行される前に止まります。 制約が本物であることは、こうして確かめられます。
動かす
空か: true
段数: 3
一番上を見る: 皿3 (段数は 3 のまま)
取る: 皿3
取る: 皿2
残り: 1 一番上: 皿1
取る: 皿1
空か: true
空から取る: undefined
入れた順は 皿1・皿2・皿3、出てきた順は 皿3・皿2・皿1 です。 逆さになりました。
「逆さになる」を欠点だと思わないでください。 これがスタックを使う理由です。「最後にやったことを、最初に取り消したい」 ときには、逆さでないと困ります。
本当に O(1) か測る
「push も pop も O(1) です」と本には書いてあります。信じる前に測ります。
私の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コンパイラが最適化を始める前の遅い時間や、計測そのものの誤差が全体に対して大きく見えます。件数が増えると、それが薄まって本来の速さが見えます。 測るときは、小さいほうの数字を信じすぎない、という教訓でもあります。
④で、これと同じ形の測定を、キューでやります。 そのときに、同じ形なのに結果がまったく違うのを見ます。
② あのエラーの正体
ここが本題です。
わざと落とす
RangeError: Maximum call stack size exceeded
depth = 12530
出ました。 そして、12530 という数字が出ました。
この数字が、この記事で一番大事です。
dive() は return を1回もしていません。だから dive が dive を呼び、その dive が dive を呼び、誰も降りてこない。 積むだけです。
そして 12530段目で、積む場所が無くなりました。
これは無限ループではありません。 無限ループ(
while (true) {})は、何も溢れません。 CPUを使い続けるだけで、エラーは出ません。 このエラーが出るのは、呼び出しごとに場所を取る何かが、本当に積み上がっているからです。 積み上がっているものが、コールスタックです。①で自分が書いた#itemsと、役割は同じです。
何が1段に入っているのか
dive() は引数もローカル変数もありません。それでも1段は場所を取ります。「どこに戻るか」を覚えておく必要があるからです。
では、中身を増やしたら段数はどうなるか。 測ります。
引数なし : 12530 段
引数5つ+ローカル: 5961 段
半分以下になりました。
ここが誤解のもとです。 「JavaScriptは1万回くらいまでしか関数を呼べない」ではありません。 限界は「回数」ではなく「バイト数」です。 1段が太ると、積める段数が減ります。 だから、同じ再帰の書き方でも、関数の中身によって落ちる深さが変わります。 「手元では通ったのに本番で落ちた」の原因になりえます。
上限そのものを動かす
バイト数で決まっているなら、バイト数を変えれば段数が変わるはずです。 Node.js には V8 に渡すオプションがあります。
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枚で分かります。
スタックトレースは「上から書き出したもの」
エラーメッセージの下に並ぶ、あの行の羅列を見ます。
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 自身の中身です。
そして、深い再帰で落ちたときは、この逆の問題が起きます。
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)] は数だけなら合っています。
必要なのは「いま開いている中で、一番内側のもの」を覚えることです。 そして閉じ括弧が来たら、一番内側から順に閉じていく。
「一番最後に開いたものを、最初に閉じる」 — スタックです。
(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 には落とし穴があります。 それも一緒に確かめます。
入力 "こんにち" 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本。
/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本で計算できます。
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は上から順にしか実行しない」と、繋がっている話です。
④ キューを自分で書く(そして遅さを実測する)
キューに切り替えます。 「来た順に処理したい」ほうです。
まず素直に書く
人数: 3 次に呼ぶ人: 客1
呼ぶ: 客1
呼ぶ: 客2
呼ぶ: 客3
空か: true
入れた順に出てきました。 スタックとの違いは、pop() が shift() に、peek が [0] に変わっただけです。
書き換えた場所は2箇所だけ。 それだけで、性能がまったく別のものになります。
測る
①と同じ形の測定を、そのままやります。
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秒という数字が読めることが大事です。
直す:先頭の位置を数字で持つ
問題は「ずらすこと」です。 では、ずらさなければいい。
取り出したら、配列を詰めるのではなく「もう取り出した」という位置を数字で覚えておきます。
変わったのは、この考え方だけです。
| 遅いほう | 速いほう | |
|---|---|---|
| 取り出したあとの配列 | 詰める(全部ずらす) | そのまま。読んだ位置を #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)」と呼びます)。
同じ測定をやる
10000 件を全部取り出す: 1.5 ms
100000 件を全部取り出す: 3.8 ms
200000 件を全部取り出す: 0.8 ms
1000000 件を全部取り出す: 4.1 ms
並べます。
| 件数 | shift() 版 | #head 版 |
|---|---|---|
| 1万 | 1.6 ms | 1.5 ms |
| 10万 | 816.9 ms | 3.8 ms |
| 20万 | 4050.5 ms | 0.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 版には、まだ引っかかる点があります。配列が伸び続けることです。 掃除で回収はしますが、一時的には大きくなります。
入る数の上限が決まっている場合は、もっと素直な形があります。 決まった長さの配列を、輪のように使い回すやり方です。
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つは毎日踏んでいる)
順番待ちの行列とジョブキュー
分かりやすいほうから片づけます。
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) を書いても即座には実行されない、という話をしました。「イベントループがあるので」で済ませました。
その中身を見ます。
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つ |
動きを、もう少し細かく見ます。
--- 開始 ---
--- 同期の最後 ---
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件、通信や音声のバッファ |
| 優先度付きキュー | 優先度の高いものから取れる | 並んだ順序が守られない(下で詳しく) | 緊急のジョブ、経路探索、タスクの締切順 |
| 二重終端優先度付きキュー | 最大も最小も取れる | 上のさらに変種。名前だけ知っていれば十分 | ほぼ出てこない |
「優先度付きキュー」はキューではない
名前に騙されました。 私は「キューの一種で、ちょっと融通が利くもの」だと思っていました。
違います。
取り出し: パスワード再発行
取り出し: 通常のメール
取り出し: 通常のメール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本でした。新しい道具を覚える話にはなりませんでした。
おまけ:②のエラーの直し方
「積むのをやめる」と書いたので、実際にやります。 深い再帰は、自分でスタックを持てば消えます。
再帰 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 も混ぜて出力しようとして、こうなりました。
同期
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 のような、桁の違いでした。
後片づけ
この記事で作ったものを、全部消します。
まず、何があるか確認します。
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回もしていないので、消すものは自分で書いたファイルだけです。
消す前に、場所を確かめます。
/home/user/cslab/sq
pwd で必ず確認してください。 これから rm -rf を打ちます。別の場所で打つと、消してはいけないものが消えます。 rm で消したものは戻りません(本線の基本コマンドの回で扱いました)。
cslab が消えていれば終わりです。
何も入れていないので、これで完全に元通りです。 Node.js のグローバル設定も、apt で入れたものも、この記事では触っていません。
残しておきたい場合は、
stack.jsqueue-fast.jsring.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つを何本組み合わせるかだけ。新しい道具を覚える話にはならなかった
参考リンク
- roadmap.sh — Computer Science — このコースがどの項目を扱っているかの地図
- roadmap.sh — JavaScript — ⑤のイベントループが置かれている位置
- MDN — Array.prototype.push — ①で使った末尾への追加の仕様
- MDN — Array.prototype.shift — ④で 4050ミリ秒かかった原因の一次情報
- MDN — RangeError: too much recursion / Maximum call stack size exceeded — ②で出したエラーの公式の説明
- MDN — Error.prototype.stack — ②で読んだスタックトレースの中身
- MDN — JavaScript の実行モデル — スタックとキューが実行の順番をどう決めているか
- MDN — History API — ③で真似したブラウザ履歴の、本物の仕様
- Node.js 公式 — The Node.js Event Loop, Timers, and process.nextTick — つまずき6で混乱した
nextTickの位置 - Node.js 公式 — コマンドラインオプション — ②で使った
--stack-sizeの説明
次に読む
この記事は 【深掘り】コンピュータ科学 の 6 / 25 本目です。
| 記事 | |
|---|---|
| ← 前の記事 | 配列と連結リスト — 先頭への追加が数百倍遅い |
| → 次の記事 | ハッシュテーブル — 10万件のincludesで止まる |
上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
- コールスタックは比喩ではない
- shift は O(n)。リングバッファで直す
この記事は、上の項目を実際に手を動かして確かめる回です。

コメント