Rustでvim/neovim用finderプラグインをつくり軽快になっている話
100万ファイルあるホームディレクトリでファイル一覧を出すのに私の環境で2秒、vimのバッファ[1]に書き込んだり開いたりするのに10秒以上かかります。これはwebの文脈でさえ遅い[2]といえる数値です。こうした状況下で速さを求めたことについて書きます。
この記事を読まずともREADMEのコピペでプラグインを試すことができます。
導入
人間は横着なので頭を使いタイピングするより限られた選択肢から選ぶことを望みます。多くの人が使うwebページはそのように最適化されています。テキスト入力を目的とするテキストエディタにおいても、多くの人にはこのことが当てはまるでしょう。テキスト入力における入力補完もセレクタの一種ですが、今回は[3]プログラミング中におけるファイルを選択して開いたりといった操作に焦点をあてます。
こうした動作を行うファインダは数多くあり戦国時代呼ばれるほど選択肢があります[4]。この記事はVim Advent Calendar 2021の記事ですが、2020年にも2つのプラグイン記事がありました[5][6]。2022年も補完プラグイン作者2人がそれぞれつくるらしいです。これほど増えた理由について私が考えるには、候補を出してフィルタしてソートして表示するというモデルが簡単であること、それからUIの好みが多岐に渡ることです。
私の好み「セレクタとしてvimのバッファがそこにありいつもどおりの操作を行うことができ、かつfzfの応答速度を持つもの」はありませんでした。
gifでは100万のファイルに対して"ファイル名 ディレクトリ名 プロジェクトのディレクトリ名"の順で問い合わせたところで目当てのファイルが見つかったので開いています。入力中もクエリに対して瞬時に結果が表示されています。
人間が候補を吟味するには機械以上の時間がかかるため表示される候補が多いほど実行時間の猶予があります。ゆえにこのファーストビューを速くすることが応答速度に必要な第一目標になります。
設計
トップダウンにUIの検討
昨年のプラグイン[5:1]は、スクロールのキーバインドを上書きすることで描画範囲を検出しその範囲だけGoから取得し描画するという方法で、vimへの書き込みの遅さに対応しています。全候補を表示できる優れた方法ですがバッファの扱いが些か特殊です。
これを踏まえ、gifのようにファインダを起動しクエリを入力しある程度絞り込めたところで候補を吟味するという操作について、ファーストビューに注目して考えると一つの戦略が思い浮かびます。
- 入力されたクエリについてファーストビューを描画する。
- クエリが変更されるまでは3以降の動作を行い変更されたら1に戻る
- ソースフィルタソートが終わるまではファーストビューの範囲を更新しつづける
- ソースフィルタソートが終わったら全ての候補を書き込む
この方法なら、全候補の表示をソースが完了するまでは待つという妥協をすることでファーストビューの応答速度をvimのバッファで実現できます。人間の吟味には時間がかかるのでこのトレードオフはそれほど悪い選択ではないはずです。並行してこれを実現するモデルを考えると、ソースには全候補一括でなく候補のストリームないしチャンクが求められ、ソート済み候補から
応答速度と並びUIの好みは多岐に渡るという問題があります。UIは見た目の装飾やキーバインドにはじまりpreviewを重視したものやresume機能をもつものなどあります。ちなみに私の好みは視線の移動が少ないものresumeを持つものfloat windowでほぼ全画面のものです。UIモジュールとしてまるごと交換可能とすることで、計算を持つ設定として自由度が上がると考えられます。
ユーザが行う設定もUIの一つです。ツールを初めて使う人は、そのツールについて何も知らないため設定について考えることなく使えることを求めます。時が経ちツールの挙動に気に入らない部分があったときには、直感的操作で変更可能だと嬉しいはずです。この需要を満たす方法の一つは、コピペすれば動く設定を用意しユーザ自身にコピペさせることで変更したくなったときに変更箇所, 変更方法の検討がつくようにすることです。
vim/neovimにおける技術選定
まず以下の記事もあわせてお読みいただくとvimに利用可能なプログラミング言語について説明が得られます。
実行速度を目標とするのにvim scriptは適しません。速くて静的型付け言語で書き心地がマシなrustが好ましいです。vimからrustを使うには3通りの方法があります。
- libcallを使う
- vimから実行ファイルをサブプロセスとして呼びRPC
- luaやpython等から動的ライブラリとして呼ぶ
つくるものの性質上、大量の文字列をvimとやりとりする必要があります。中にはファイル名も扱うためutf-8が求められるjson(RFC8259)は適しません。他にもrustでStringはutf-8であるのに対し、vim scriptやlua, python等は任意のバイナリを持つc文字列であるということに気をつけて設計する必要があります。またデータ移動コストは小さいに越したことはありません。
- 文字列しかやりとりできないので、生の文字列を扱うかjsonシリアライズ
- neovimには今年の9月msgpackでencodeする方法が追加されました[9]がvimにはないのでc言語の速さでシリアライズできるのはjsonしかない。共有メモリはOSごとの実装が必要
- vimとlua, luaとffiのメモリやりとりで済む luajitからlua54まで対応してるffiライブラリがあるkhvzak/mlua
スクリプト言語の中でluaは速くneovimによる優遇もあります。luaから動的ライブラリとして利用する方法が手軽に速いという結論になります。
luaとrustでvimプラグインをつくると使用の際必要になるものは、rustのパッケージマネージャ兼ビルドツールであるcargoとluajitを使えるneovimかluaで動的ライブラリを読み込むことができる機能(+lua/dyn)を持つvimがです。rustの標準インストーラであるrustupは必要に応じコンパイラのバージョン指定まで行えるため、asdfや**envを使う必要がなく公式の手順[10]通り行っても後で困ることがありません[11]。
プラグインに求められることは、ユーザの実行に対しvimから情報を取得し候補を出してフィルタしてソートしてvimへ書き込むことです。速度の面からvimからの情報取得, vimへの書き込みを除いたソースフィルタソート全てをrust側でやることが好ましいとなります。
モデル
vimの情報とクエリでソースフィルタソートを起動し、範囲取得を高速に行えるようにというインターフェイスだけが決まっています。"フィルタ"はろ過する(traversalに対するfilter操作), 加工する(unixコマンド)双方の意味で用いられうるため、ソートのための候補の重み(スコア)を計算するものをMatcherと呼ぶことにします。
- ソースおよびMatcherはvimからの情報を入力として外との情報取得が必要になります。例えばファイルソースはディレクトリを入力としてディレクトリ内のファイルを取得します。ディレクトリが変わるかファイルが変わると結果が変わります。
- 計算しないことは何よりも速いのでキャッシュも並行して考えます[12]。ディレクトリが一致すれば"キャッシュ時刻が新しければ結果を使いまわしても良"く、反対に一致しない場合"異なる結果"です。また仮にディレクトリのタイムスタンプまで見れば"完全に同じ結果"/"異なる結果"の判断ができるとみなせるでしょう。入力に対してキャッシュとして結果を使い回せるかはソース自身だけが知っていることです。
従ってソースとMatcherには候補ストリームとキャッシュ可能性の最低2つのインターフェイスが必要になります。
モデルはソースフィルタソートを、UI側が行う範囲取得とは非同期的に行う必要があります。非同期を実現する方法としてvimはtimerにより実行スレッド内でタスクを細切れにすることで実現します。luaもcoroutineで同様にシングルスレッドで非同期を実現します。rustを採用したのでデータ競合に煩わされる心配なくマルチスレッドで行うことができます。
トップダウンと言っていますがフロント, バック, 技術の間を言ったり来たりして矛盾や局所最適化のないよう練り合わせるものです。フロントより裏側のが気合入っていますがベンチや試行錯誤の結果ですので設計段階で言えることは多くありません。そういった意味でモデルはシンプルです。
実装
ビルドと自動ビルド
実行速度を第一としたためソースの追加にはコンパイルが必要になります。動的なリンク方法も考えましたが、cargoの力を借りて静的にリンクしてしまうのがシンプルかつ型システムの恩恵も受けることができお得です[13][14]。自前のビルドツールがCargo.tomlおよびグルーコードを生成することで実現しています。こうした仕組みについて知らなくても動くことが望ましいので自動ビルドが必要になります。ビルドが必要になるタイミングは2つ考えられます
- プラグインの初回利用時など動的ライブラリが存在せず読み込まれていないとき
- 使用しようとしたソースが動的ライブラリに含まれていないとき
rustではResultでエラーを自前で管理し、try-catch構文を持つ言語のように使用するライブラリがエラーを吐きっぱなしにしたりしないため、2のようなエラーハンドリングで人権があります。
自動ビルドの実装はluaが必要なタイミングでコンパイルを走らせるだけです。ただし、今の実装ではvimの操作をブロックしてコンパイルが走り体験が最悪なのでおすすめしません
ビルドができたら新しい動的ライブラリを読み込みなおす必要がありますが、共有ライブラリとも呼ばれるとおり閉じることは考えられていないため、メモリを片付けて別名として読み込むことで実現しています。
Resume機能
Resume機能は候補が表示されていた状態をカーソル位置まで含めて復元する機能です。この機能によりvim本来のlocation/quickfix listの使い心地を再現できます。私はpreviewよりもよく使う機能です。人間は間違えるので投機的に実行して後から修正可能であると良いという言説がwebデザインの文脈で使われます。
まず呼称を準備します。ソースおよびフィルタを起動してクエリを入力するという操作について、クエリ含むvimからの情報に応じて変化するソート結果にIDを振りフローと呼ぶことにしました。resumeする際はフローIDを選択するよりも、ソースごとの最後のフローを復元したいはずです。このソースごとのフローの集まりにもIDを振りセッションと呼ぶことにしました。直近の結果を保持するだけでなく、キャッシュのためどの道、多くのソート結果を保持する必要があります。後は指定されたセッションIDに紐づく保持しているソート結果を引き出し表示するだけです。
現在、モデルはセッションIDを指定するresumeのためのインターフェイスを持っていますが、セッション一覧のソースやluaから全セッションを取得するapiがなくセッションIDを得る方法がないためまだ使えません
マルチスレッドチャンネルソートチャンクキャッシュ
応答速度を実現するための核となる部分です。これらは同時に考える必要があるため一つのsectionになりました。
まず非同期ランタイムにはデファクトスタンダードであるtokioを使います。ioなど必要なものが揃っていることは知っていたのでasync-stdとの比較などは行っていません。モデルはソースフィルタソートを、UI側が行う範囲取得とは非同期的に行う必要があるため、クエリが変更されるごとにソースフィルタソートを行うため最低でも1つtokioスレッドが必要になります。ここでソースは非同期の恩恵を受けやすく、Matcherやソートは重い計算処理であるので、tokioスレッドはworkerスレッドかブロッキングスレッドどちらも指しうるふわっとした呼称です
はじめに検討するのはソースやフィルタが候補を返すインターフェイスをストリームとするかチャンクとするかです。
- std::iter::Iterator
- futures::stream::Stream
-
tokio::syncが提供するチャンネル
で候補単体またはその配列を流すことが考えられます。こちらの記事が大変有用でした。
100万ファイルを一つの指標としていたので10^6個の文字列で回してみるとこの数値でした。
- 250ms
let mut it = (0i32..1000000).map(|x| x.to_string());
while let Some(_) = it.next() {}
- 500ms
let mut it = futures::stream::unfold(0i32..1000000, |mut it| async move {
it.next().map(|x| (x.to_string(), it))
});
futures::pin_mut!(it);
while let Some(_) = it.next().await {}
実際にはファイルソースの例のようにソースは非同期処理を行うため、イテレータは適しません。その上で非同期処理をたくさん行うのであればworkerスレッドにspawnしてチャンネルで受け渡ししても良さそうですが、こちらはチャンネルのオーバーヘッドと関数がストリームを返さずチャンネルを返すことになり直感的から一歩遠ざかることが気になったので見送りました。それからもう一点、ソースは候補の配列でなく候補単体を流すべきと判断しました。生成が非同期であること以降のMatcherをとめることをなく行いため粒度が細かいほうがいいためです。フィルタも同様に候補単体のストリームとしました。
次にこのMatcherの結果である候補とスコアの組のストリームStream<Item = (Item, Score)>をソートすることを考えます。全候補一括ではないためインクリメンタルにソート結果を更新し続けるオンラインアルゴリズムが必要です。fzfにならいチャンクごとにソートしソート済み同士をマージすることにしました。チャンクによりメモリなどをまとめて計算することによる計算量削減は効果があります。
ソート済み候補[15]にソート済みのチャンクをマージします。愚直な方法としてはstableなソートを使うことです。仮実装ではそうしました。計測してみるとこれが遅くさらに溜まるにつれ露骨に遅くなっていきました。linearfの名前を掲げるのにこれはイケてません。
rt.spawn(async move {
pin_mut!(chunks);
while let Some(mut chunk) = chunks.next().await {
// +50ms desc
let orig_size = chunk.len();
let mut chunk = chunk
.drain_filter(|(_, s)| !s.should_be_excluded())
.collect::<Vec<_>>();
// +1ms
chunk.sort_unstable_by(|a, b| a.1.cmp(&b.1));
// +0~1ms
let sorted = &mut sorted.write().await;
sorted.source_count += orig_size;
sorted.items.append(&mut chunk);
sorted.items.sort_by(|a, b| a.1.cmp(&b.1));
// +10ms asc 200ms
}
let sorted = &mut sorted.write().await;
sorted.done = true;
})
ソート済み候補に対してチャンクは十分に小さく10^6の配列にstableソートを行うことがそもそも無駄で、マージソートを考えるなら1回のマージでよく、挿入ソートの亜種ライブラリソートを考えるならin-placeで済むことが当然思いつきます。
キャッシュチャンク
フィルタとソートの間にはストリームをバッファリングしてチャンクにする処理とキャッシュのため配列に保存する処理が必要になります。チャンクにするにはfutures::stream::Chunksが使えます。キャッシュと新しい値を同様に扱いたいのでストリームないし配列から値を返すストリームCacheStream<Item=(Item, Score)>の形になります。rustではStreamの非同期における1タスクを同期関数poll_nextとして書くことができます。100万候補をソースするのに対してクエリの変更は高速であるため、オリジナルがキャッシュに書き込むのと並行して読み出す利用者がいるので配列のRwLockが必要になります。
CacheStreamの初期案は配列を読み続け、次がない場合にwriteロックを取りオリジナルストリームを読み配列に書き込むという愚直なものでした。
次の案は書き込むのをオリジナルだけとしスレッドを立てることでした。オリジナルだけとすることによりCacheStream自身に一旦候補を保持しキャッシュへの書き込みを遅らせソースを動かし続けることが期待できます。
ベンチをとってみると初期案よりも遅くなりました。
- 初期案 time: [2.2397 s 2.3155 s 2.3874 s]
- 失敗案 time: [3.0025 s 3.2543 s 3.5057 s]
失敗案の結果と比較してみると初期案はオリジナルとキャッシュでread, writeロックのタイミングがよく衝突が少なくまたwriteロックを取得した際には書き込みが行われるのでスループットが悪くありませんでした。失敗案はwriteロックがreadを妨げ遅くなっていたようですが、書き込みをオリジナルだけとすることで一旦候補を保持する案は悪くないように思えます。
そして現状の案、CacheStreamとfutures::stream::Chunksを組み合わせてしまいオリジナルでチャンクをつくってからキャッシュ配列に書き込む案です。まずそもそもの書き込む回数が減るので衝突などが減ります。読む回数が大幅に減るのでwakerで読む側を起こしたりといった非同期ならではのことが効果的に利用できます。
ベンチをとると半分以下になりました。
- 初期案 time: [2.2397 s 2.3155 s 2.3874 s]
- 現状案 time: [820.39 ms 841.62 ms 863.00 ms]
現状案やベンチはこちらから見ることができます
ここまでの実装でgifのfzf相当の応答速度を持つfinderができました。計測を行いながら進めていますが、Matcherであったり同条件がなかなか用意できないので数値をのせることができません。マサカリ大歓迎です
おまけ vim/neovimにおけるlua
小さくまとまっているいい言語です。vim scriptと比べると関数をオブジェクトとして自在に扱える点、メタテーブルという抽象が優れています。一方で小さい故のクセを持ち辞書と配列の区別が曖昧です。
luaは辞書と配列の区別が曖昧で、vim scriptはboolを持たず整数と区別がつきません。この2つの表現力不足によりデータのやりとりには手心が必要なります。
- luaからvim scriptへ辞書を渡すにはvimでは
vim.dictという関数で明示的に変換してから渡す、neovimでは要素数を見て判断される - vim scriptからluaへは渡された整数の解釈には関数の返り値型などそのデータが持つ意味が必要
また、配列は古いvimとの互換も壊れているのでそこも気をつける必要があります。
以上を踏まえこれらを吸収する層を用意すると必要な関数だけ増えますが100行程度で済みました。
まとめ
この記事は弊プラグインおよびrustの布教であると共に、動いているから
UIの機能はまだまだ乏しいですが、安定して軽快に動作し、rust-lang/rustやneovim/neovimのような巨大リポジトリでインクリメンタルにgrepしたり、プログラミング中にノイズにならないことはそれだけで気持ち良いのでぜひ一度体験してみてください
-
Website Response Times, Response Time Limits: Article by Jakob Nielsen ↩︎
-
ソースがstreamとしてフィルタソートされるコアの部分は転用は可能だがフロントまわりをつくっていない ↩︎
-
他にも、ヒープ等ソート途中の構造で持つと範囲取得時のコストが増えるが、ストリームについてオンラインにソートしやすい ↩︎
-
直前のクエリでヒットした候補は次のクエリでもヒットする可能性が高くファーストビューにつながるので優先してフィルタソートという工夫が考えられる ↩︎
-
rustup自体の更新のためOSのパッケージマネージャを介していれるのが好ましいですが ↩︎
-
キャシュするからには正しい結果でなければなりません。副作用の使用に注意を払っているとキャッシュが効いたり、デバッグしやすかったり(そもそも必要がなかったり)する利点があります。 ↩︎
-
ソースが受け取るパラメータをソースの関連型として静的に定義できます ↩︎
-
気をつけてかけば静的ディスパッチ, インライン化できる ↩︎
-
rustはデフォルトがprivateでimmutableなのでソート済みであることの安全確認がしやすい ↩︎
Discussion