Kosshi が大規模でも高速な理由

Kosshi は すべてを 1 つのアウトラインに まとめる設計を採っています。 ファイルを分けず、プロジェクトも日記もタスクも同じアウトラインに置く。 この使い方をしていると、中身は数千行、数万行と育っていきます。

キー入力や描画そのものの速さはネイティブアプリとして作ることで確保していますが、 行数が数十万、数百万になるとそれだけでは足りません。 1 回の描画や編集の裏で動く処理そのものを、行数に応じて増えないように設計する必要があります。

この記事では、アウトラインが大きくなっても反応速度が落ちないよう、 Kosshi が内部で何をしているかを説明します。

行数に比例するコスト

アウトライナーの内部では、 1 つの操作に対していくつもの処理が走っています。 画面に表示する行の取り出し、折りたたみによる表示の切り替え、 検索語に一致する行の抽出、編集後のレイアウト更新。 これらが描画の締め切りに間に合えば、画面はカクつきません。

問題になるのは、行数に比例して時間がかかる処理が混ざっている場合です。

たとえば「画面の上から 3 行目はどれか」を求めるのに、 素朴に作るとアウトラインの先頭から 「これは折りたたまれているから飛ばす」「次は見える、1 行目」「次も見える、2 行目」 と順番に数えることになります。 行数が 2 倍になれば時間も 2 倍、10 倍なら 10 倍かかる。 プログラミングではこの性質を O(n) と書きます（n は行数）。

1 行あたりの処理がどれだけ軽くても、 O(n) の処理は行数が増えればいつか描画の締め切りに間に合わなくなります。 こうした処理が各所にある設計でまともに動くのは、 数万行まで。 10 万行で操作のたびに間が空き始め、 100 万行では使いものになりません。

1 つのアウトラインにすべてを置く使い方では、 1 年で数万行、数年で数十万行に到達する可能性があります。 Kosshi は 100 万行のベンチマークを基準に開発しています。

アウトラインの性質と効率化

アウトラインにはいくつかの性質があります。

• ズームインして、興味のある部分だけを表示することが多い
• 折りたたみで、関係ない子孫を非表示にできる
• 画面には一度に 30〜50 行しか表示できない

100 万行のアウトラインを開いていても、 画面に映っているのはごく一部です。 残りは折りたたまれているか、スクロール位置から外れているか、ズームの外にある。 描画や編集のコストは、画面に映っている分にだけ払う。 アウトラインの総行数が増えても、 画面に映る行数は変わらないので、反応速度も変わりません。

この方針が、大規模なアウトラインを扱えることの基盤になります。 以降は、この方針を実現するための仕組みを説明します。

SumTree を利用した高速化

ひとつ問題があります。 画面を描くには、スクロール位置から画面下端までに 今どの行が並んでいるのかを毎回求める必要があります。 検索で飛んだとき、折りたたみを切り替えたとき、スクロールしたとき。 そのたびに「この位置には何行目がくるのか」を計算し直します。

これを素朴にやると、結局アウトラインの先頭から 「この行は折りたたみで隠れているから飛ばす」 「この行は見える、1 行目」と 1 行ずつ数え直すことになり、 O(n) に戻ってしまう。 この割り出しを高速にできなければ、先の方針は成り立ちません。

Kosshi は内部のデータ構造に SumTree (augmented B+Tree) を使っています。 B+Tree はデータベースやファイルシステムで大量のデータを索引付きで扱うために広く使われている構造で、 木のノードをたどることで目的の要素に素早く到達できます。 SumTree はその拡張版で、各ノードが「このサブツリーに何が含まれているか」の集計値を持ちます。

SumTree という呼び方は、Rust 製の高速なコードエディタ Zed にならっています¹。 Zed では大きなファイルでもキー入力が即座に反映される裏側で動いており、 Kosshi はこの考え方をアウトライナー向けに仕立て直しました。

集計値による位置特定

なお、SumTree のツリー構造はアウトラインの階層構造とは別物です。 アウトラインの階層（親の下に子、子の下に孫）はユーザーが見ているもの、 SumTree のツリーはその全行を効率よく扱うための内部構造で、 ユーザーからは見えません。

図で示すと以下の通りです。

各ノードが持つ集計値は、たとえば次のような情報です。

• 自分の下に何行あるか
• そのうち何行が完了済みか
• 合計の高さは何ピクセルか

500,000 行目を探したいとき、 ルートから木を降りていくだけで目的地に絞り込めます。 「左の子は 200,000 行、通過。次の子は 200,000 行、通過。 その次の子は 150,000 行、ここに含まれる。この中の 100,000 行目を探せばいい」。 中の行を 1 つずつ数えることはありません。

ノードの数は行数よりずっと少ないので、 100 万行のアウトラインでも数回の判断で目的地に到達します。

折りたたみとズームへの応用

アウトライナーに特徴的な操作として、折りたたみとズームがあります。 どちらも、画面に映る行が一度に大きく変わる操作です。

親の下に 10,000 行ぶら下がっていたとします。 素朴な作りだと、 折りたたみの瞬間に 10,000 行を 1 行ずつ「見えない」状態にする処理が走ります。 ズームも同じで、範囲外に置かれる行すべてに印をつけて回ることになる。 行数に比例した遅延です。

SumTree では、その 10,000 行を束ねているサブツリーをまとめて扱えます。 折りたたみなら「このサブツリーの表示行数は 0」、 ズームなら「このサブツリーは表示範囲外」とするだけです。 内部の 10,000 行を個別に処理する必要はありません。

描画時も同じ仕組みで、 「このノードの配下は見えている行が 0 だから丸ごと飛ばす」 という判断がノード 1 つ分のコストでできます。 ズームで外に置いた部分、折りたたんだ部分、画面外の部分は、 すべてこのレベルで枝刈りされます。

集計値の応用

集計値の仕組みには副次的な効果があります。集計を伴う機能が追加しやすくなることです。

たとえば「この親の下に未完了のタスクが何件あるか」を 親の行の横に表示する機能を考えます。 素朴に実装すると、 親を開くたびに子孫を数える処理が走り、 編集のたびに古いカウントを無効化する必要があり、 それなりの実装量になります。

SumTree では、内部ノードが持つ集計値に「未完了タスクの数」というフィールドを 1 つ足すだけです。 子ノードの集計値を足し上げれば親ノードの集計値になる、という性質によって自動的に最新に保たれ、 行を編集してもずれることがありません。 アウトライン側から見ると、ある行配下の未完了タスク数は、 その範囲を束ねている SumTree ノードの集計値を読むだけで得られます。

同じ発想で実現できる機能がいくつかあります。

• ある範囲の文字数カウント
• 完了したタスクの割合
• 画像を含む行の数
• 最終更新時刻
• ブックマークが付いた行の数

いずれも、集計値にフィールドを足すだけで成立します。