Zenn
🚤

CtrlP に出戻りした

2020/09/24に公開
Vim
tech

はじめに

Vim でファジーファインダといっても沢山ある訳ですが、皆さんはどれを使ってるでしょうか。

  • CtrlP
  • fzf.vim
  • denite
  • vim-fz
  • そもそもファジーファインダ使わず netrw
  • そもそもファジーファインダ使わず NERDTree
  • そもそもファジーファインダ使わず dirvish
  • そもそもファジーファインダ使わず fern
  • その他

いろいろあります。それぞれに特徴があり、自分の好きな物を使っておられると思います。個々の特徴を知りたい方は @yutakatay さんが良い記事を書いてくれているのでそちらをご覧ください。

https://zenn.dev/yutakatay/articles/vim-fuzzy-finder

まず昔話を聞いて欲しい

僕はもともと CtrlP を使っていました。CtrlP は kien 氏が開発した Vim プラグインで、Vim script のみで実装された高速なファジーファインダです。

意外と知られていない便利なvimプラグイン「ctrlp.vim」

出会い

当時 CtrlP はとても軽快で、一目惚れしてしまいました。パフォーマンスを出す為の細かいハックが沢山入っていました。特徴的なハックとしては、最短キーワードを使うという物がありました。Vim script は命令の予約語を省略する事ができます。例えば関数定義をする為の命令 function の最短キーワードは fu です。Vim script は逐次でスクリプトをパースするので少しでも文字が短いと、それだけでパースがごく微量ですが速くなるのです。

kien 氏は、この他にも色々なハックを取り入れており、遅くなるコードは入れないというスタンスにもとても感銘を受けました。GitHub リポジトリの kien/ctlrp.vim にも沢山パッチを送りました。当時は kien 氏も活発に活動しており、ユーザがグングン増えていきました。

別れ

しかしあまりにアクティブな issue に疲れてしまったのか、kien 氏の活動は徐々に無くなり、最後には開発をリタイヤしてしまいました。

多くのファンを抱えた CtrlP には他のメンテナがいる訳でもなく、そこにはただ単に動きのない開発リポジトリがあるだけでした。そしてそれを不安に思った CtrlP ユーザの方が kien/ctrlp.vim を fork し、kien/ctrlp.vim に活発にパッチを送っていた数名にメンテナの権利を与えました。それが ctrlpvim/ctrlp.vim です。

そして僕もそのメンテナに選ばれたのです。

独立

kien 氏がいなくなった ctrlp.vim を動かすのは自分しかいない、そう思ってメンテナンスを続けました。

なるべく kien 氏のスタイルを保つ事を心掛けました。もちろん前述の最短キーワードも。

しかし Vim script だけでファジーファインダを実装するという事が意味する物が、時には苦行になる事もありました。

超えられない壁

繰り返しますが、CtrlP は Vim script だけで実装されています。ただでさえ遅いスクリプト処理系なのですが、特に以下の様な問題がありました。

  • 大量のファイルがあるとファイル一覧を出すのに時間が掛かる
  • 大量のファイルがあると絞り込みが遅くなる

後者に関しては特に深刻で、酷い時には1文字タイプしただけで数秒待たされてしまう状況でした。

この超えられない壁を見て、競合するプラグインにスイッチしてしまうユーザも幾らかいました。

そして、僕自身もスイッチしてしまいました。

vim-fz

大量のファイルがあるとなぜ遅くなるのか、それはC言語で実装されている Vim と、ユーザが書いた Vim script の間を何度も行き来するからなのです。ファイルを一覧する為に外部コマンドを使う方法も CtrlP は提供していますが、一度起動するとその大量のファイル一覧を全て得るまで応答を得られません。

そこで僕が考えたのが Vim の :terminal を使う方法です。

ファイル一覧を非同期でリストアップしつつ、選択したファイル名を標準出力する端末向けコマンドを使い、それを Vim の :terminal で起動、そのコマンドの出力を使って CtrlP と同じインタフェースを提供するという物です。

https://github.com/mattn/vim-fz

似たプラグインとして fzf.vim 等があります。この方法は確かに機嫌良く動きました。数万個ファイルが存在していたとしても非同期で実行されるのですから、ユーザは何も気にする必要がないのです。おそらく今後、自分は vim-fz を使い続ける、そう思っていました。

人間が感じる数ミリ秒

しかし vim-fz を常用したり、fzf.vim に浮気したりした中で、どうしても納得がいかない部分がありました。それは外部コマンドの起動速度です。

vim-fz は gof というコマンドを、fzf.vim は fzf というコマンドを起動します。コマンドを起動する為には :terminal を使います。仮想端末を用意し、そこでシェルを起動し、さらにそのシェル上で外部コマンドを起動します。

これに掛かる時間はおそらく数ミリ秒程度だと思います。この数ミリ秒の遅れが僕にはどうしても許せませんでした。

ファジーファインダを起動するという事は、おおよそ今から開こうとしているファイル名が決まっているはずです。欲しいのはそのファイル名への最短キーシーケンスです。ファイル名にマッチする文字を今すぐタイプしたいはずなのです。

ファイル数が多くても少なくても、この起動時間は掛かってきてしまいます。

出戻り

この方法でも駄目だ。そう感じた僕は他のプラグインを試してみたりもしました。しかしどうしても納得が行きません。そしてふと思い起こしてみました。

CtrlP は文字をタイプした時の絞り込みこそは遅かったけど、少量のファイル数なら一瞬で画面が表示されたなぁ

それは当然です。なにせ Vim というプロセスは既に起動していて、Vim というユーザインタフェースも用意されていて、ファイル一覧を画面として表示したら後はユーザからのキーを待ち受けすれば良いだけなのですから。

CtrlP を速くする

じゃぁ絞り込みを速くしたらいんじゃない？

そう思った僕は、久しぶりに CtrlP のソースファイルを開いてみました。遅いのはコマンドを使わないケースのファイル一覧です。ディレクトリを再帰的に検索し、ファイル一覧を作ります。偶然かどうか、以前僕は Vim 本体に readdir という関数を入れていたので、それを使ってみる事にしました。

https://github.com/ctrlpvim/ctrlp.vim/pull/552

初回の実装には色々とぬけがあり、リンク先のキャプチャほど速くはならなかったのですが、ファイルを一覧する処理 GlobPath は既存の物よりも数パーセントほど速くなりました。

master (d93d978): 8.49551 sec
readdir (8857c17): 7.33068 sec

この pull-request には実は GlobPath 以外の修正も含まれています。CtrlP がファイル一覧を作ったあと、入力された文字に従ってリストを作り直す処理。ここに重たい処理がいました。それが mixedsort という関数です。

fu! s:mixedsort(...)
	let ct = s:curtype()
	if ct == 'buf'
		let pat = '[\/]\?\[\d\+\*No Name\]$'
		if a:1 =~# pat && a:2 =~# pat | retu 0
		elsei a:1 =~# pat | retu 1
		elsei a:2 =~# pat | retu -1 | en
	en
	let [cln, cml] = [ctrlp#complen(a:1, a:2), s:compmatlen(a:1, a:2)]
	if s:ispath
		let ms = []
		if s:res_count < 21
			let ms += [s:compfnlen(a:1, a:2)]
			if ct !~ '^\(buf\|mru\)$' | let ms += [s:comptime(a:1, a:2)] | en
			if !s:itemtype | let ms += [s:comparent(a:1, a:2)] | en
		en
		if ct =~ '^\(buf\|mru\)$'
			let ms += [s:compmref(a:1, a:2)]
			let cln = cml ? cln : 0
		en
		let ms += [cml, 0, 0, 0]
		let mp = call('s:multipliers', ms[:3])
		retu cln + ms[0] * mp[0] + ms[1] * mp[1] + ms[2] * mp[2] + ms[3] * mp[3]
	en
	retu cln + cml * 2
endf

mixedsort は sort 関数に渡す比較関数です。つまり数万のファイル数があれば、数万回呼び出される関数です。この関数の中で呼びだしている関数 s:curtype() これが数十ミリ秒掛かっている事に気付きました。

そこで Vim8 から入った部分適用(partial)という機能を使って、予め呼び出した s:curtype() を関数に渡しつつ利用するという方法に変更しました。

https://github.com/ctrlpvim/ctrlp.vim/pull/552/files#diff-c9de02bff2ec6d5e66b2f5f71beb595dR1587

これにより例え数万個ファイルがあったとしても、遅くならない程度に改良できました。

ctrlp-matchfuzzy

CtrlP には matcher という仕組みがもともと用意されています。これはファイルの一覧を絞り込む部分を Python や他の外部コマンドを使い高速化できる仕組みです。要はファジーマッチする部分だけを Vim script じゃない物に委ねたという事になります。

これはこれで良い物だったのですが、これも Python をロードしたり外部コマンドを利用します。この matcher を起動する際に起きる数ミリ秒の遅延が、やはり僕には納得できませんでした。

そしてまた運が良いことにちょうど同じ頃、Vim 本体に matchfuzzy() という組み込み関数が入りました。この関数は文字列配列とパターン文字列を渡すと、ファジーマッチした結果の配列を返すという物です。

これまるで CtrlP の為に用意された関数やん

そう思った僕はこの matchfuzzy() を matcher として使うプラグインを作りました。

https://github.com/mattn/ctrlp-matchfuzzy

そしたらなんと、めちゃくちゃ速いんです。そりゃそうです。外部コマンドも使いませんし、そもそも Vim の組み込み関数なのですから速くて当然です。遅延もありません。

既に10日ほど使い続けていますが、特に問題も起きていません。

おわりに

CtrlP に出会い、CtrlP と別れ、そしてまた CtrlP に戻ってきました。しばらくはまた CtrlP を使い続けます。そしてまた、ぼちぼちと CtrlP のメンテナも再開しようと思っています。kien 氏の CtrlP を壊さない為に。

Discussion