mandelbrot/docs/PERFORMANCE_PLAN.md

# 未確定画素を減らしながら軽量化する案

作成日：2026-09-05。精査・追記：2026-09-06。以下はBLA除去後のコードを調査した時点の計画。承認後の変更と測定結果は [実装結果](IMPLEMENTATION_RESULTS.md) を参照。

実装時の状態遷移・処理量上限・手順・確認ケースは [実装設計](PERFORMANCE_IMPLEMENTATION.md) にまとめた。

## 推奨方針

まず **計算済みの状態を使い続けること、GPUとの往復を減らすこと、失敗した画素だけを適切な精度で補修すること** に集中する。反復回数や誤差判定を一律に削って軽くする方針は採らない。

現状はBLAを除去しても、未脱出画素の全件継続、補修後のやり直し、細かいGPU完了待ち、各画素のBigInt再計算が残っている。ここを直す方が、別の近似加速器を追加するより先である。

最初の実装単位は次の3つを推奨する。

1. 未脱出画素の到達反復数・誤差を正しく記録し、未確定の分類を揃える。
2. 継続計算のGPU投入を小さなまとまりにし、まとまりごとの読戻しにする。
3. 補修が必要な画素だけを別キューへ移し、正常な画素の状態と参照軌道を保持する。

P0の判定修正は正しい結果へ直す変更であり、従来と結果が変わる可能性がある。P0後の結果を基準として、P1では最終反復数の方針を維持し、同じ計算結果を少ない再計算・同期で得る。その後に、内点の早期確定と画素ごとの反復予算を導入する。

## 1. 「計算不能」を分けて扱う

ここでいうセルは画素を指す。現在の `FIELD_UNKNOWN` は複数の状態を含むため、総数だけを最小化すると誤判定を増やしやすい。

| 状態 | 現行の表現 | 目指す扱い |
| --- | --- | --- |
| まだ計算していない | reason 0 | 最終画像で0。タイルの被覆漏れを防ぐ |
| 精度・参照軌道の都合で結果を採用できない | reason 1～5 | 最優先で減らす。局所参照・精度昇格・高精度補修へ回す |
| 現在の反復数まで脱出していない | reason 6、または `FIELD_INTERIOR_LIKELY` | 数値故障とは分ける。到達反復数を記録し、継続または内点判定へ回す |
| DS感度を表す予約名 | reason 7（名前のみ。現行シェーダーに出力経路なし） | 現在の失敗原因とは数えない。将来出力するなら補修対象・集計まで同時に定義する |
| 内点と確認できた | `FIELD_INTERIOR_PROVEN` | 継続キューから安全に除く |

**有限回の未脱出だけで集合内と証明したことにはならない。** また、異なる2精度で結果が一致したことは有用な確認だが、一般の境界画素について数学的な証明そのものではない。Direct DSとDeep DS補修も、全丸め誤差の区間を伝播して脱出を証明する実装ではない。全座標で「厳密分類・未確定0・短時間」を保証する目標は置かない。

reason 4の `rebase-gap` も、定義と集計は残るが現行シェーダーに失敗を書き込む経路は見当たらない。rangeやreference-endの実測件数と、予約理由を区別する。現在の統計配列の要素7は `corrected` 用なので、reason 7をそこへ足す変更はできない。

目標は、同じ表示精度・反復方針での数値失敗を可能な限り0へ近づけ、残った未脱出画素には正直な状態と継続手段を持たせること。UNKNOWNを黒や周囲の色へ置き換えるだけでは改善と数えない。

## 2. 現状から分かった負荷

根拠は [index.html](../index.html) のコードと [前回の確認結果](CLEANUP.md)。今回、追加のEdge起動や速度測定は行っていない。2026-09-06の精査では、参照サービスの実コードを使ったキャッシュ更新確認と、小さなCPU計算で数値例を確認した。以下のボトルネック順位はコードからの推定で、GPU時間・同期時間・CPU時間の内訳は未計測である。

| 箇所 | 確認できた処理 | 問題・軽量化の方向 |
| --- | --- | --- |
| `refinePixelFrontier()`、`operationLimitIndices()` | reason 6の全画素を候補にする。8近傍だけを選ぶ `operationLimitFrontier()` は本経路から呼ばれていない | 名前に反して境界だけの計算ではない。内点判定と優先順位が必要 |
| `pixelFrontierIterationFloor()` | 画素幅のビット数×256を最低反復予算とする | 空間精度と必要脱出反復数を強く結び付けたヒューリスティック。深部では大きな追加計算になる |
| `DEEP_ACTIVE_RESUME_INIT_WGSL` | `w=0, n=0, m=0` から開始する | 初期描画で計算した反復を、継続経路で再び計算する |
| `refinePixelFrontier()` の `restart` | 数値補修があると、次の周回で残存候補全体のsessionを作り直すことがある | 少数の失敗で正常な画素まで再計算する |
| `continueOperationLimitActive()` | 原則1 dispatchごとにsubmit、全queue完了待ち、4 byte件数のmapを行う | GPUとCPUの細かい往復。GPUに次の仕事が届くまで空く可能性がある |
| `ReferenceService.requestFixed()`、参照Worker | 反復目標が変わりキャッシュにない場合、参照を再生成して検証する | 同一原点・同一精度なら末尾延長で済ませられる余地がある |
| `recoverNumericalUnknownTiles()` | 局所参照のバッチごとに全画面metaを読戻し、CPUで所属画素を抽出 | 失敗が疎でも全画面転送・走査が発生する |
| `precisionFallbackWorkerSource()` | 最大4試行で2精度ずつ、各画素を反復0から計算する | 高精度計算が重複する。同じ精度の計算結果を再利用できる |
| `recoverResidualPrecision()` | 残件をWorker数で割り、実質全残件を一度に投入して `Promise.all` で待つ | 小さな費用上限で区切られておらず、長いCPU負荷になり得る |
| `applyPrecisionFallback()` | Workerの結果ごとに反映と全画面統計を実行 | 細切れのアップロード・統計・完了待ちをまとめられる |
| `qualityStages()`、`renderQualityStage()` | 深部は原則1回の最終描画。補修と継続が完了するまで新規frameの公開を待つ | 完了時間がそのまま初回表示待ちになる。履歴のない座標ジャンプで特に目立つ |

### 具体的な規模

前回の320×240、Seahorse、span `3.4e-13`、初期512反復では、FASTは32768反復まで進んで約36.7秒かかった。FASTとDeepの最終meta・smoothは一致したが、これは両者共通の停止条件・数値判定まで正しいという証明ではない。

この条件の画素幅は約49.74 bit相当で、現在の最低反復予算は12736。目標を倍増するため最低予算を初めて越えるのは16384で、さらに安定判定によって32768などへ進む。512から32768は反復目標で64倍であり、実際の総演算量が常に64倍という意味ではない。

現在のchunkは、残り反復数による切り詰めを除くと `max(1, min(256, floor(4,000,000 / activeCount)))`。全画素が継続対象のまま32768反復まで進む仮定では、320×240で少なくとも約631 dispatch、800×600で4096 dispatchになる。各目標境界、補修、参照生成の追加費用は含まない。実際には脱出によって対象が減るため、この例を実測dispatch数として扱わない。ここでいうdispatch数は反復カーネルの回数で、別にindirect引数を準備する小さなdispatchが各回にある。

## 3. 最初に直すべき判定上の問題

### 継続経路の終端誤差検査が通常の目標で実行されない

`DEEP_ACTIVE_CONTINUE_WGSL` の未脱出時の終端処理は `p.targetIter >= p.maxIter` を条件とする。一方、呼び出し側は `p.maxIter=150001`、通常の目標は最大150000である。そのため、この分岐の誤差検査と反復数のmeta更新には通常到達しない。脱出・range等の他の検査は別途存在する。

提案は、「次へ継続するための状態保存」と「今の目標まで計算した結果の判定」を分離すること。各目標境界で実際の `n` と誤差を記録し、必要な画素だけを補修へ回す。既存の終端分岐を単に有効化すると `return` によって継続キューから画素が脱落するため、state保存と再投入を含めて設計する。

さらにloop先頭で `s.n>=stop` を先に判定するため、最後の更新で到達した `z_target` の脱出判定は次の継続まで遅れる。表示をその目標で確定するなら、最終stateを評価してから未脱出として採用する必要がある。中間chunkではなく、結果を採用する目標境界で確認する。

この修正で今まで見えていなかった数値UNKNOWNが一時的に増える可能性がある。改善の評価は、その増加を隠さず、正しい判定後の補修コストと残件数で行う。

### 未脱出の表現と停止条件を揃える

Direct DSは未脱出を `FIELD_INTERIOR_LIKELY` として返す一方、別経路ではreason 6となり、継続対象が異なる。同じ予算で比較するには、数値的に判定できたこと、集合内であること、追加反復を待っていることを別々に扱う必要がある。

また、`pixelEscapeAdvance()` の「新しい脱出が既存の脱出画素の近傍内に収まる」という条件と2回の安定周回は、将来の孤立した脱出や1画素未満の誤差を保証しない。現行の実用的な停止条件として記録し、厳密な内点証明とは呼ばない。

### 処理量上限は全経路で統一されていない

400万pixel-iterationsは現行の継続・疎補修の設計値であり、すべてのdispatchに適用できている保証ではない。`computeAccurateDirectHybrid()` のDS queueは初期batchを上限から決めるが、時間による拡大後に同じ上限でclampしていない。12000反復では333画素から500画素へ増えるだけで600万になる。

`initialNumericRows()` は最小1行なので、`幅×反復数` が予算より大きい場合は1行でも超える。既存の `regression.mjs` はこの例外を許容する検査で、全経路400万以下の証拠にはならない。重いDS／Deep経路は必要なら横方向も分割し、どの適応処理でも最終的に上限へ戻す。FASTの4800万等とは別のカーネル別予算として管理する。GPUの経過時間は演算内容にも依存するので、画素×反復数だけで停止防止を保証しない。

## 4. 軽量化案と優先順位

| 優先 | 案 | 期待する効果 | 未確定を増やさない条件 |
| --- | --- | --- | --- |
| P0 | 上記の状態・誤差判定と処理量上限を整理 | 評価基準と分割の前提を正す | 未検査の画素を確定扱いせず、上限超過時はさらに分割する |
| P1 | GPU投入をまとめ、読戻しを間引く | 同期・submit・JS呼び出しを削減 | 各dispatchの上限と投入総量を維持 |
| P1 | 正常画素のstateと参照軌道を保持 | 反復0からの重複計算を削減 | 参照原点・精度・計算式が同一であること |
| P1 | 数値失敗キューをGPU上で作る | 全画面readback・CPU走査を削減 | キュー被覆とoverflow時の処理を保証 |
| P2 | 失敗理由別に補修を選ぶ | 回収できない補修の反復を削減 | 失敗した画素には次の補修手段を残す |
| P2 | BigIntの重複計算と一括投入を減らす | CPU負荷・最長待ち時間を削減 | 2精度比較と未採用画素の追跡を維持 |
| P3 | 安全な内点判定を加える | 未脱出キュー自体を縮小 | 判定に失敗した点は通常計算へ戻す |
| P3 | 画素・タイルごとに反復予算を配分 | 一律の深い反復を削減 | 優先度の低い未確定画素を捨てない |
| P4 | 同一視点の段階表示とメモリ上限 | 初回待ち・メモリ圧迫を軽減 | 暫定表示を完成履歴へ昇格させない |

### P1-A：GPU主導の継続と小さなまとめ投入

`encodeDeepActiveChunks()` は既に複数passを符号化できる。最初は2～4回程度の有界dispatchをまとめ、件数を読むのはまとまりの最後だけにする。GPU上の件数からindirect dispatchを構築し、対象0の後続passは何も処理しないようにする。

補修画素の再投入がないまとまりの中ではactive数は増えない。その入口の件数を保守的な上限に使えば、毎回CPUへ戻らず各dispatchの処理量を制限できる。再投入するときはこの前提を更新する。

4 byteの読戻し自体のために `mapAsync()` の前で全queueの完了を重ねて待つ必要はない。対象バッファのGPU使用完了はmapの成立で扱える。ただし、mapの成立は他バッファや別のpromiseの完了を意味しない。投入量の制御や別用途の完了待ちは分けて残す。[WebGPU仕様のbuffer mapping](https://gpuweb.github.io/gpuweb/#buffer-mapping)

継続・高コスト補修の各dispatchを400万pixel-iterations以内へ実際に制限したうえで、GPUへ先行投入する時間・総仕事量にも上限を置く。まとめる回数を増やしてWindowsのGPU停止やキャンセル遅延を再発させない。uniformの値がpassごとに変わる場合は専用offsetや別バッファで保持し、submit前の同じuniform領域への上書きで全passが最後の値を見る構成にしない。[WebGPU開発者による複数passのuniform書き込みの説明](https://github.com/gpuweb/gpuweb/discussions/2509)

### P1-B：正常なstateと参照軌道を使い続ける

最初に補修キューと継続キューを分離する。数値失敗した画素だけを継続キューから外し、正常画素の `d, w, scaleExp, n, m, errScaled` を保持する。補修した画素は、その結果と参照に対応したstateで再参加させる。stateを復元できない画素に限って再計算する。

次に、同一原点・同一精度の参照Workerに末尾stateを保持し、目標増加時は軌道の末尾を延長する。既に検査したprefixは同じ条件のまま保持し、新しく追加した部分を検査する。精度変更や原点変更時は別の参照として扱う。

初期Deep描画からの継続state保存はその次に行う。FAST・Direct・DSのstateをDeepへそのまま移植しない。実装を共通化する場合も、丸め順・誤差・参照の契約を揃えてから採用する。

参照が短い場合の `refs.request(..., true)` は、現行の第5引数 `fresh` によって該当キャッシュを削除する。旧案の「引数がなく無効」という記述は誤りだった。ただし同じ入力の処理中promiseは再利用され、再生成しても決定的な候補探索は同じ原点を選び得る。改善対象はfreshの追加ではなく、試した原点の記録、失敗分布に基づく別候補の選択、十分な長さを得られない場合の処理である。

### P1-C：GPU内で失敗画素を集める

reason別・タイル別の件数、prefix sum、画素indexのscatterをGPU上で作り、局所参照ごとの範囲をそのまま補修へ渡す。既存の疎キューを拡張する形を優先し、別の監査基盤は追加しない。

CPUへ必要なのは参照を選ぶための小さなタイル要約と、最終的にBigIntへ渡す少数の失敗indexである。全画面metaの読戻しは通常の補修ループから外し、任意の検証や例外処理に限定する。

overflowや被覆漏れの検査はGPUで集計してまとまりの最後に確認する。件数確認を減らすことと、未処理画素を黙って捨てることを混同しない。

### P2-A：失敗理由ごとの補修

| 理由・分布 | 最初に試す処理 | 次の処理 |
| --- | --- | --- |
| reference-end | 同一原点の軌道延長。実際に脱出する参照なら失敗領域内で参照を再選択 | 局所参照で再計算 |
| error-boundが局所に集中 | 既存参照でのDS補修か、回収実績のある局所参照を選ぶ | 改善しなければ高精度補修 |
| escape-uncertain | 該当画素だけ精度を上げる | 必要な画素だけBigInt |
| range | スケーリングと座標差の表現を確認 | 指数を持つ表現または高精度補修 |
| 広く密集した失敗 | タイル単位で参照・精度を選び直す | 大量の画素別BigInt投入を避ける |

現在も `readNumericalFailureTiles()` はタイル内の最小indexの失敗画素を代表点に使っている。`sumX/sumY` という名前だが重心の総和ではなく、その代表点×件数である。改善は、この既存代表点を基準に失敗の密集度・到達反復・過去の回収費用から少数の代替候補を選ぶこと。単に「中心から失敗画素へ変更する」という新規機能ではない。参照変更でグリッチを減らせる一方、近い参照を選ぶだけで誤差を保証できるわけではない。[摂動法のグリッチと参照選択](https://mathr.co.uk/blog/2014-03-31_perturbation_glitches.html)

reason 4・7を将来使う場合の経路は予約設計として別途定義する。発生していない理由に専用の常時計算を追加しない。

補修1回で回収できた画素数、残件数、費用を少数の集計値で保持する。回収の止まった手段を同じ条件で繰り返さず、次の手段へ送る。時間切れの画素は保留として残し、補修完了数へ加算しない。

### P2-B：BigInt補修を小さくする

現在の精度比較は `P/P+32 → P+32/P+64 → …` で、隣り合う試行が同じ精度の軌道を再計算する。前回の高精度側の結果を次の低精度側へ使えば、最大4試行の8軌道を5軌道に減らせる。最初の比較で成功する画素にはこの削減は発生しない。

Workerへの仕事は全残件の等分ではなく、小さな画素数・推定pixel-iterationsで区切る。まず1～2 Workerを基本にして空いたWorkerへ次のバッチを渡し、端末の余裕がある場合だけ増やす。入力が来たら追加投入を止め、長い処理は必要に応じてWorker終了で取り消す。

同時期に返った結果のindex・meta・smoothをまとめて転送し、GPU scatterで反映する。全画面統計はWorker結果ごとではなく適用バッチごとに1回。2精度で採用できない画素は失敗キューに残す。

### P3-A：継続が不要な内点を安全に除く

Directにある主カージオイド・周期2円の判定を、適用可能なタイル・参照表現へ広げる。深い座標を単純にf32へ丸めて判定せず、高精度座標または誤差を含む区間で領域内と確認できた場合だけ採用する。領域から遠いタイルでは判定自体を省ける。[Cardioid and bulb checking](https://mathr.co.uk/blog/2022-11-19_cardioid_and_bulb_checking.html)

さらに一般の周期成分を対象とするなら、周期候補の検出と内点の確認を分ける。有限精度で同じ値になった、近い位置へ戻った、という理由だけでは確定しない。包含・収縮等を確認できる方式は後段の研究候補とし、全画素で毎反復行わず長く残る画素に絞る。

主カージオイドと周期2円だけでは、Seahorseや小さなコピー内部の問題を全部解決できない。効果の対象範囲を区別する。

### P3-B：反復予算を空間精度と切り離す

画素幅は座標の必要精度を決める。一方、外部の点が何回で脱出するかは軌道に依存するため、`pixelBits × 256` は必要反復数の証明ではない。

一律の倍増を置き換える候補は、境界近傍、孤立した未脱出成分、長時間残る画素を別キューで管理し、変化の多い部分を優先する方式。低優先度の未確定画素にも一定量を配り、孤立した遅い脱出を永久に取り残さない。8近傍だけへ対象を限定する変更は行わない。

この変更は従来と最終反復数・停止条件が変わり得る。P1の純粋な実行効率改善と分けて評価する。通常閲覧の有限予算と、明示的な高品質計算の扱いを決め、到達予算と未確定数を内部状態に残す。

### P4：表示待ちとメモリ負荷を抑える

最終的な未確定を減らす処理を継続しつつ、現在の視点で計算した暫定結果を段階表示する案を検討する。全体の低解像度計算を単純に追加すると二重計算になるため、同一画素格子のタイル完成表示か、最終計算へ再利用できる段階処理を優先する。暫定画像は完成履歴にしない。

現在のactive用stateは全画面に32 byte/画素、2本のqueueは合計8 byte/画素。800×600ならこの部分だけで約18.3 MiBあり、meta・smooth・texture・参照は別に必要になる。候補数が少ないときは密なslot配列、候補が多いときは上限付きタイルworkspaceを使い分ける。ただし画素indexとslotの対応、世代、queue境界を明確にする。slot方式でindex対応表を追加すれば、その分のメモリも増える。タイル処理でも生存stateを破棄して毎回0から計算してはならない。

## 5. 実装・確認の進め方

| 段階 | 変更範囲 | 確認すること |
| --- | --- | --- |
| 0 | 終端判定・未確定分類・処理量上限・最低限の集計 | 正常画素と未検査画素を区別できる。継続画素がqueueから消えず、適応batchも上限内 |
| 1 | 同期のまとめ、BigIntの同精度結果再利用 | 同じ予算で脱出分類・反復数・smoothが一致。同期数と重複軌道数が減る |
| 2 | 失敗キュー分離、正常state保持、参照末尾延長 | 補修後も正常画素の進捗が戻らない。数値UNKNOWNが減るか増えない |
| 3 | GPUでのタイル別queueと補修選択 | 全画面読戻しbyte数、BigInt対象数、補修失敗の再試行が減る |
| 4 | 内点判定と反復予算・段階表示 | 内点の誤確定を防ぐ。遅い脱出・孤立成分・操作往復で破綻しない |

自動監査を描画ループへ戻さない。計測は `?test` の明示実行で、初回表示までの時間、数値補修完了までの時間、未確定の理由別件数、仕事量上界、再初期化数、GPU読戻し回数・byte数、CPU補修数を1ケース1レコードへ集約する。現在の `activeCount×chunk` は早期脱出分も含む上界で、実行した反復数そのものではない。実反復を測るならテスト時のみGPU内で集約し、区別して記録する。

テストは既存の `regression.mjs` と `browser_smoke.mjs` を必要な分だけ拡張する。初期表示、同じSeahorse座標のFAST／Deep、実軸付近、既知の黒領域問題の座標を小さな代表セットとする。最初は同じadapter・解像度・予算でウォームアップ1回＋計測3回。少数回の測定からp95は主張しない。

GPU制御は **検証用Edgeを1インスタンス、タブを1つ** に限定し、ケースを直列実行する。Edge内部の複数プロセスはあり得るが、ケースごとにブラウザーやプロファイルを増やさない。終了時に今回の検証用ブラウザーを閉じ、通常利用のブラウザーは終了対象にしない。

採用条件は、同条件での数値失敗の減少または非増加、計測した時間・仕事量の削減、既知の表示破綻がないこと。P0で従来未検査の失敗を可視化した直後は、修正後の正しい状態を比較基準とする。速度改善率・任意座標での未確定0は実装前に約束しない。

既存テストはこの案の採用条件をまだすべて検査しない。特に `numericalFailures=0` とFAST／Deep一致だけではP0の終端検査や共通する誤りを検出できない。既存の比較関数は不一致箇所だけを高精度で確認するため、一致した画素の独立確認も少数必要である。追加する確認ケースと、現行テストが未対応の範囲は実装設計に明記した。

## 6. 後回しにする案

- BLA、series approximation等の別の近似加速器の再導入。まず既存計算の重複・同期・補修を直す。
- 全画面を常にDS／BigIntにする変更。高精度が必要な画素へ限定する。
- Worker・Edge・GPU投入数の無制限な増加。
- 誤差guardの緩和、未確定画素の着色だけで件数を減らす変更。
- 常時shadow比較、フレームごとの全面ハッシュ、新しい多段階昇格ゲート。

未使用の `encodeDeepBucketHistogramStats()` や旧背景補修経路などの追加整理は可能だが、実行されていないコードの削除だけで数十秒の描画時間は解消しない。次の実装では、上記の実際に実行される仕事量と待ち合わせを優先する。