Home Design SylFS Aura Setup TechNote TODO Walkthrough API (rustdoc) Graphs

計算量注記の規約

目的

関数ごとに計算量をコメントで明記する。 下層ライブラリから積み上げれば、上層の計算量は呼び出し回数との掛け算で見積もれる。

実際、この方針が無かったために描画の性能問題では仮説を 5 つ立てて 4 つ外した（spec/resource_loading.md）。「重そう」という直感はあてにならない。

表記

各関数のドキュメントコメントに以下の 1 行を入れる。

/// 計算量: O(...) — 記号の意味

記号は必ずその場で定義する。O(n) だけでは何の n か分からない
呼び出す下位関数の計算量を含めた合計を書く
支配項だけでなく、実測で効く定数倍（毎ピクセルの浮動小数演算など）も短く添える
呼び出し頻度が問題になる関数（毎フレーム／毎ノード）はそれも書く

例

/// 計算量: O(W×H) — W,H は矩形の幅・高さ（ピクセル）。
/// 半透明（アルファが 1〜254）のときは 1 ピクセルずつ合成するため
/// 定数倍が重い。不透明・完全透明なら行単位の一括書き込みで済む。

積み上げの例

draw_pixel_alpha        O(1)
  ↓ W×H 回
boxfill                 O(W×H)
  ↓ 要素ごとに 1 回
要素ループ              O(Σ W_i×H_i) — 要素 i の面積の総和
  ↓ 毎フレーム
draw                    O(Σ W_i×H_i) / フレーム

面積の総和で効くので、画面を覆う大きな要素が支配的になる。実測でグラデーション（ヒーロー全面）が paint の 23% を占めたのはこの構造から予測できた。

適用順序

下層から上へ。上層だけ書いても積み上がらない。

kernel/draw.rs の描画プリミティブ
web_engine/draw_helpers.rs
css/（セレクタ照合・カスケード）
os_lib/layout/
上層（web_engine/render.rs, layout.rs）

【2026-08-04】実行して確かめていたものを、静的に確かめられるようにした

「この要素は画面に出るはずなのに出ない」を調べるのに、ビルド（約 10 分）＋ QEMU 実行（約 6 分）を何度も回していた。

しかし座標変換と可視判定は入力と出力が決まっている純粋な計算であり、本来は単体試験で答えが出る。実行して確かめる対象ではなかった。

web_engine/paint_cull.rs として切り出した:

pub fn viewport_y(y_offset, scroll_y, top_offset) -> i32;   // ドキュメント→ビューポート
pub fn buffer_y(el_y, win_y) -> i32;                        // ビューポート→描画バッファ
pub fn is_in_viewport(el_y, height, top_offset, win_h) -> bool;
pub fn is_in_clip(draw_x, draw_y, w, h, clip) -> bool;

単体試験には実測で観測した実際の値をそのまま入れてある（test_paint_cull.rs 17 件）。

これで静的に確定したこと

#93「主な研究テーマ」  y_offset=1349 → el_y=120 → draw_y=151  （画面に出る）
#100「スマートホーム・HEMS」y_offset=1627 → el_y=398 → draw_y=429（画面に出ない）

どちらも - is_in_viewport(el_y, h, 40, 549) が true - is_in_clip(draw_x, draw_y, w, h, (100,31,924,580)) が true

つまり可視判定でもクリップでもない。 これをビルドせずに言えるようになった。

教訓

純粋な計算（座標・判定・パース）は、実行環境を回して確かめない。先に純粋モジュールへ切り出して単体試験にすれば、 1 回 15 分の往復が 20 秒の make test になる。

【2026-08-05】ノードに依存しない判定をノードごとに計算しない

cascade.rs は「候補ルールのどれかが :hover を使うか」を ノードごとに候補ルール全部へ問い合わせていた。

しかし「そのルールが :hover を使うか」はノードに依存しない。同じ答えを N×C 回計算し直していたことになる。

索引の構築時（ルールにつき 1 回、O(R×Sel)）にビットで求めておき、カスケードは OR で引くだけにした（O(C)）。 rule_index::state_masks / active_states_of。

一般則

C-1: ループの中で計算している値の引数に、ループ変数が入っていなければ外へ出せる。これは「ループ不変式の巻き上げ」そのもので、木の走査でも同じことが言える。

効果測定について

style_tree の実測は 184〜356 tick と回ごとに倍近く振れ、 この変更の効果は QEMU の計測ノイズに埋もれて見えない。無駄な計算が減ったことは計算量から確実だが、「速くなった」と数字で主張はできない。正直に書いておく。

C-2: ノイズより小さい改善は、計算量で正しさを示し、挙動不変を試験で担保する。実測の倍率を作文しない。

【2026-08-05】描画 1 フレームの内訳を測った

draw() は毎フレーム呼ばれるが、その中でリソース到着を検知して 再レイアウトも起こすため、「描画が重い」のか「再レイアウトが重い」のかが混ざって見えなかった。分けて測った。

[PERF][DRAW] frames=100 total=13576tick max=4336tick relayout=5972tick

内訳	値
1 フレーム平均	136 tick（約 1.4 秒）
うち再レイアウト	5972 tick（44%）
純粋な描画	7604 tick ÷ 100 = 76 tick/枚
フレームレート	約 0.5 fps（200 秒で 100 フレーム）

再レイアウトは 1 回あたり実測 4.6 秒。

対処: 到着をまとめて 1 回にする

フォントは 4 並列でそれぞれ数秒かけて届くため、到着のたびに再レイアウトするとそのたびに 4.6 秒を払っていた。実ブラウザと同じくリフローをまとめる。

到着が QUIET（2 秒）途切れたらまとめて 1 回
ただし最初の到着から MAX_WAIT（6 秒）を超えたら待たずに実行（届き続ける限り画面が更新されない事態を防ぐ）

最初 QUIET を 0.3 秒にしたがまったくまとまらなかった （relayout 5972 → 6418 tick）。到着間隔は 0.3 秒よりずっと長い。再レイアウト 1 回が 4.6 秒なのだから、2 秒待って 2 回を 1 回にできれば元が取れる、という計算で 2 秒にした。

結果

	修正前	修正後
1 ページ読み込みのレイアウト回数	9 回	6〜7 回（3 回計測）
`relayout` tick	5972	6234（有意差なし）

レイアウト回数は一貫して減ったが、tick では有意差が出なかった。残った再レイアウトが重い側に偏っている可能性が高い。「回数を減らす」より「1 回を軽くする」方が本命だと分かった。

次に見るべき場所

再レイアウト 1 回の 4.6 秒の内訳。 style_tree は実測 24〜200 tick なので主役ではない。 parse_and_layout の残り（HTML 解析・CSS 解析・レイアウト木構築）を区間に割って測ること。外側の回数をいじる前に中身を測る （spec/l1_l2_usb.md U-3 と同じ手順）。

【2026-08-05・続】「再レイアウト 1 回が 4.6 秒」も誤りだった

前節で「再レイアウト 1 回が実測 4.6 秒」と書いたが、 これは 5972 tick ÷ レイアウト回数 で割り出した推定値であって実測ではなかった。段ごとに測ったら違った。

[PERF][LAYOUT] html=1  css=4  style=40  layout=5  flatten=7  合計=57tick  要素=369
[PERF][LAYOUT] html=0  css=12 style=135 layout=29 flatten=7  合計=183tick 要素=369
[PERF][LAYOUT] html=2  css=21 style=29  layout=5  flatten=6  合計=63tick  要素=369

HTML 解析・CSS 解析・レイアウト木の構築はどれも軽い。 style_tree が一番重いが、それでも 26〜270 tick。

一方で関数全体を測ると 92〜944 tick（後の計測では 2176 tick も）。つまり重いのは flatten より後だった。

flatten 後で見つけたもの: 要素ごとの線形検索

矩形を DOM ブリッジへ反映する箇所が、要素 1 個ごとに get_element_by_id を呼んでいた。これは全ノードの線形走査で、しかも各ノードで is_attached が親を辿る。

O(要素 × ノード × 深さ)   実測で要素 369・ノードも同程度

さらに id を持たない要素では毎回 format!("_ta_{}", idx) で 文字列を確保してから、まず一致しない検索を走らせていた。

id → ノード添字の対応表を走査 1 回で作る（dom_bridge::build_id_index）ようにした。 O(要素 × ノード) → O(要素 + ノード)。

残る大きな値の正体

関数全体が 1000 tick を超える回があるが、これは fetch_script_text / fetch_binary_bytes が同期でネットワークを叩くため。 spec/resource_loading.md に「CSS / JS は同期（未対応・残る本丸）」と書いてあるとおりで、レイアウトの計算コストではない。

レイアウトの計算そのものは既に軽い。 数字を軽くしたいなら CSS/JS の非同期化であって、レイアウトの最適化ではない。

教訓

C-3: 「合計 ÷ 回数」で 1 回あたりを推定して、それを実測と呼ばない。今回それで「4.6 秒」という存在しない数字を 2 回の報告で使った。段ごとに測れば 57〜183 tick だった。

【2026-08-05・確定】ページ読み込みの最大コストは CSS の同期取得

段を細かく割って、ようやく単一の数字にたどり着いた。

上から順に割った結果

[PERF][DRAW] 最長更新 5030tick（うち再レイアウト 4249tick, 要素=369）
  └ [PERF][LAYOUT] html=0 css=2315 style=280 layout=79 flatten=53 合計=2728
      └ font_face登録 = 22〜124tick（14 件）
      └ 残り ≒ 2130tick ← **CSS/JS の同期取得**

1 回の draw() が 50 秒かかり、その 85% が再レイアウト、再レイアウトの大半が CSS の同期取得（約 21 秒）。

分かったこと

区間	実測
HTML 解析	0〜13 tick
CSS 区間（取得＋font-face 登録）	最大 2315 tick
うち font-face 登録	22〜124 tick
カスケード	235〜291 tick
レイアウト木	55〜79 tick
flatten	53〜71 tick

計算はどれも軽い。重いのは通信だけ。

なぜここまで測るのに時間がかかったか

最初は [PERF][LAYOUT] 関数全体 の tail を見て「30〜500 tick、軽い」と判断していた。だが分布を取ると最大は 4220 tick で、平均や末尾では見えなかった。

C-4: 時間の分布は tail ではなく sort -n | tail で見る。 1 回だけ極端に重い処理は、平均にも末尾にも現れない。「最大を更新した回だけ出す」計装が要る。

非同期化の位置づけ（再確認）

この 21 秒を消すのが CSS 非同期化の目的で、動機は数字で裏づけられた。ただし 9 回試して未達（spec/resource_loading.md の総括を参照）。 動機は正しい。実装がまだ噛み合っていない。

【2026-08-05】計測は「一斉に」置いて 1 回で読む

何が問題だったか

1 箇所ずつ計装 → 実機で確認 → 外す → また 1 箇所……を繰り返していた。 実機 1 回が数分かかるので、これでは終わらない。ユーザから「一発一気に計測したらいい」と指摘を受けた。そのとおり。

道具: `web_engine/perf.rs`

固定スロット（enum Slot）と固定長の AtomicU32 配列。確保しない
加算は fetch_add 1 回。熱経路に置いても影響が小さい
dump() が全スロットを 1 行で出す

計測点を増やすときは Slot に 1 行、NAMES に 1 行足すだけ。 名前と実体が 1 箇所に並んでいるのでずれない。

1 回の実行で出る内訳（実測）

[PERF][ALL] https取得=23356/12 送信待ち=9524/40 受信待ち=19929/24496
            cache読=73/95 cache書=470/13 css/js取得=4380/24
            fontface=329/12 font解析=2/10 img復号=1833/1

これでページ読み込み全体の内訳が一度に分かる。

効果測定も往復が要らなくなった

「変更の効果を端から端の数字で推し量る」のをやめ、 変えた当人を直接測る。A/B のために戻して測り直す必要が消えた。

例: 送信待ちの上限を 3 通り試した比較は、それぞれ1 回ずつの実行で判定できた（成功率 ok/total も同じ行に出るので副作用も同時に見える）。

設定	送信待ち	再送	ok/total
600ms × 4	9667tick / 39回	52	13/13
1.5s × 3	9540tick / 39回	52	13/13
300ms × 1	11087tick / 41回	52	13/13

上限を 1/5 にしても合計が動かない → パラメータは効かない、と 3 回で確定できた。以前なら戻して測り直して倍の回数を使っていた。

規準

C-5: 実機が遅い環境では、計測点は関連する関数へ一斉に置く。 1 箇所ずつ確かめるのは、実機が速い環境でだけ許される贅沢。

C-6: 変更の効果は変更した当人を直接測る。端から端の数字はホスト負荷に埋もれ、A/B の往復を招く。

【2026-08-05】計測スロット一覧（`web_engine/perf.rs`）

1 回の実行で出る内訳。増やすときは Slot と NAMES に 1 行ずつ足す。

スロット	何を測るか
`https取得`	HTTPS 取得の全体（接続〜本文）
`送信待ち`	送信後の応答待ち（`retry_write` 経路）
`受信待ち`	TLS 受信ループ
`cache読` / `cache書`	ディスクキャッシュ
`css/js取得`	`fetch_script_text`
`fontface`	`@font-face` の登録
`font解析`	フォント解析（WOFF2 展開含む）
`img復号`	画像デコード
`sleep実測`	送信待ちループの `sleep` 実経過
`応答確認` / `eth poll`	同ループ内の内訳
`初回応答待ち`	要求送出後の最初の 1 バイト待ち
`受信sleep` / `recv呼出`	受信ループの内訳

使い方の型

まず [PERF][ALL] で全体を 1 回見る
最大の項目を選び、その中身を割るスロットを足してまた 1 回見る
直したら、直した当人のスロットで確認する（1 回）

実機 1 回が数分かかる環境では、この 3 回で原因特定まで行ける。 1 箇所ずつ入れては外す進め方だと同じ結論に十数回かかっていた。

【2026-08-05】空きセクタ探索の O(n²) を潰した

見つけ方（実機 1 回）

ネットワーク経路を洗い終えたあと、[PERF][ALL] の残る大きな項目は

cache書=3636/14   ← 1 回 260 tick（2.6 秒）

キャッシュへの保存 1 回に 2.6 秒。5.3MB のフォントで allocate_sector を 1 万回以上呼ぶので、そこを疑った。

原因

allocate_sector は毎回ビットマップの先頭から空きを探していた。

1 個目: 先頭から 1 セクタ目を見て終わり
1000 個目: 先頭から 1000 個ぶん埋まった領域を読み飛ばしてから見つける

前の方はもう埋まっているので、確保が進むほど走査が伸びる。O(n²)。しかもビットマップセクタは 1 つずつ read_sector（SDCard/SSD 等の外部記憶ではミラー付き）で読む。

対処

見つけた位置を next_bitmap_hint に覚え、次回はそこから探す。見つからなければ 0 へ戻って一巡するので取りこぼしは無い。

for step in 0..total {
    let i = (self.next_bitmap_hint + step) % total.max(1);
    ...
    self.next_bitmap_hint = i;   // 見つけた位置を覚える

連続確保が O(1) 近くになる。

効果

	cache書	回数	FS 異常
修正前	3636 tick	14	0
修正後	2115 tick	14	0

42% 短縮（約 1520 tick）。単体試験 858 件パス、描画に回帰なし。

付随して直したこと

内部状態を持つようになったので、構造体リテラルでの生成をやめて SylFS::from_parts(device, superblock) に一本化した。試験も同じ経路で作る。フィールドを増やしても生成箇所が壊れない。

教訓

C-7: 「先頭から探す」実装は、要素が増えるほど遅くなる。 前回の位置を覚えるだけで O(n²) が消えることが多い。確保・探索を繰り返すコードを見たら、開始位置を確認する。

【2026-08-05】要約はフレーム数ではなく時間で出す

[PERF][ALL] を「25 フレームごと」に出していたが、 重い回は 1 ページ読み込みで 25 回も描かない（実測 10 回未満）。結果、実機を数分回したのに計測が取れずに終わる実行が 2 回あった。

時間基準（5 秒ごと）に変えた。描画回数によらず必ず出る。

C-8: 実機が遅い環境では、計測の出力条件を「何回起きたか」に依存させない。時間で出す。 1 回の実行が数分かかるのに、条件を満たさず何も取れないのは最悪。

【2026-08-05】CSS の再解析は疑ったほど重くなかった

css/js取得=4760/16 に対し、実際の CSS/JS は 3 本程度。到着のたびにキャッシュを捨てるので何度も読み直しており、 再解析が重いのではと疑って測った。

CSS解析=478/6   ← 1 回 80 tick
鍵比較=4/11     ← ほぼ 0（124KB の文字列比較は速い）

6 回の解析で 478 tick。大きくない。 cached_css_key == inline_css（124KB の比較）も 4 tick で無視できる。

疑いは外れたが、外れたことが 1 回で分かったのが収穫。ここは触らない。

ネットワーク経路の最終状態

https取得=27027/13  送信待ち=4223/39  受信待ち=12649/25827
cache読=69/65  cache書=2573/14  css/js取得=3798/16
DNS=67/15  TCP接続=204/14  TLS握手=4118/14
CSS解析=478/6  鍵比較=4/11

DNS・TCP 接続・CSS 解析・鍵比較はいずれも軽い。残るのは受信待ち（正当なネットワーク遅延）と TLS ハンドシェイク 14 回。

次の一手（feature 相当）

13 リソースに対しハンドシェイクが 14 回。接続を使い回せば（HTTP keep-alive / TLS セッション再開）ここは大きく減るが、これは最適化ではなく機能追加。今の Connection: close 前提の実装を変える必要がある。

【2026-08-05】描画の内訳を分解した（進行中）

draw() は total=14249 relayout=8584 で、 再レイアウトを除いた描画は 5665 tick。その内訳を測った。

原始操作はどれも軽い

[PERF][PAINT]  背景画像=247/7 グラデ=0/0 img描画=0/0 文字描画=260/400
[PERF][PAINT2] 境界=0 大面積塗り=0 線形グラデ=136 矩形塗り=46
               文字(低)=17 影=0 角丸=0 画素背景=185

合計しても 891 tick（重複を含む）。 5665 のうち 4770 tick が原始操作の外にある。

つまり「何を描くか」ではなく、要素ループの管理コストが本体。

既存カウンタを合流させた

draw_helpers.rs と kernel/draw.rs には 2026-07-31 の計測で入れたカウンタが 9 本あったが、それぞれ別に出していた。 [PERF][PAINT2] として [PERF][ALL] と同じ節目で出すようにした。

別々に出すと突き合わせに実機をもう 1 回回すことになる。 既にある計測は、新しく作らず同じ行へ合流させる。

次に測っているもの

画像収集 … 描画前に可視要素の URL を集めるパス（毎フレーム String を複製している）
要素ループ … 並べ替えと本体の描画ループ