タグジャンプ高速化

[7-rate]

要望機能

tagsファイルを検索するタグジャンプが遅いです。
これを高速化したいです。

具体的な現象

tagsファイルのキーがソートされている前提で、
sakura_core以下ディレクトリでtagsで最も上に登録されるキー(ADDTAIL_INTERVAL_MILLISEC)と
最も下に登録されるキー(wfd)を比較した結果、私の環境では

キー	時間
ADDTAIL_INTERVAL_MILLISEC	4ms
wfd	29ms

のようになり、顕著に差が出ます。これがさらに大きなtagsファイルだと秒単位で時間がかかってしまいます。

原因

CDlgTagJumpList::find_key_core()にてキーにマッチするデータ抽出を行っているが、
tagsファイルからキーワードの抽出の処理にて上から1ラインずつなめているため。

対策案

対策案1

tagsファイルがソートされている場合は2分探索でキーの検索を行うようにする。

対策案2

マルチスレッドで検索を行う。

対策案3

ほかに何かあればご意見ください。

開発はゆっくりにはなりますが対策案1を検討中です。

[KENCHjp]

@7-rate さん、Issue立てありがとうございます。
また対策案につきましても提案ありがとうございます。
内部をほとんどわかってないadminですが、対策案は１の方がよいように思います。
なにかありましたらまた発言等気軽にお願いいたします。
取り急ぎ返信。

[berryzplus]

なんかしらの方法でドキュメント全体を舐める必要がある気がしていますが、可能な限りフルスキャンの回数は少なくしたいです。

ドキュメント内の検索開始位置候補を正規表現でピックアップするとか、入り口を絞る方法も考えられるかな、と。

wfdに一致する単語は、単語の先頭がwです。
単語の先頭がaで始まる単語とはマッチしませんし、gwfdにマッチさせたらいかんです。

[7-rate]

前置き
初issue立てでちょっとドキドキしてます。エンジニアとしてもペーペーなので的外れな事を言ってたらガツンと言ってもらって構いません！

berryzplusさん、前半の話がよく分かりません。
ここで言うドキュメントとはtagsファイルを指していますか？であればファイルアクセスを少なくしたいという認識であっていますか？

後半についてですが、tagsファイルのキーはソートされている前提ですので正規表現で検索よりは二分探索の方が速いのでは？と思っています。

[berryzplus]

@7-rate さん
あらためて初めまして。

berryzplusさん、前半の話がよく分かりません。
ここで言うドキュメントとはtagsファイルを指していますか？
であればファイルアクセスを少なくしたいという認識であっていますか？

ドキュメントは編集ウインドウで開いているファイルデータを指しています。

てっきり、tagsの中身は初回に一括で読み込んで、ジャンプ要求のときにジャンプ先を探すためにメモリサーチしてるんだと思っていました。マップ使ってないのかぁ・・・。（注：コードは見てないです。

tagsファイルを行単位で読み込むのが遅い、という話だとは思ってなかったです。
ひょっとして、ジャンプ要求のたびにファイル読んでる？それは遅くなりそうですね。

後半についてですが、tagsファイルのキーはソートされている前提ですので正規表現で検索よりは二分探索の方が速いのでは？と思っています。

tagsファイルを勘違いしてたようです。
「キーワード」の羅列じゃなくて、「キーワード＋出現位置(群)」の羅列ですよね。
・・・であるなら、2分探索は有効だと思います。
https://qiita.com/ofutonfuton/items/d7e449d35b17a3bcf399#%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2

ただ、こういうときこそ std::map<std::wstring,std::list<size_t>> を使えばいいような気もします。
https://qiita.com/sileader/items/a40f9acf90fbda16af51

[7-rate]

berryzplusさん、こちらこそ改めましてはじめまして。

tagsファイルを行単位で読み込むのが遅い、という話だとは思ってなかったです。
ひょっとして、ジャンプ要求のたびにファイル読んでる？それは遅くなりそうですね。
そうです。ジャンプ要求のたびにtagsファイルを読みに行き、キーの探索も線形探索のため遅いです。

初回起動時にtagsファイルを解析してキーワード+出現位置(群)をmap等で持っていれば確実に高速化できるでしょうが、それは難しいです。
・開いている編集対象のファイルによって参照するtagsファイルが異なる
→各編集対象のファイルが参照するtagsファイル毎にmapを作らなくてはいけなくなる。
　→起動も遅くなります。

・tagsファイルのサイズが巨大なとき、それがそのままメモリ使用量となる
→例えば私が本業でやっているプロジェクトのソースコードでtagsを作ると50MBにもなります。(sakura_coreディレクトリだと140KBほど)
　→さらに規模が大きい環境の場合下手すれば数百MB以上も考えられる。
　　→このメモリ使用量を許容できるか？(できないと思ってます。)

上記の懸念があるため、キーワード+出現位置(群)をmap等で持っておくのは厳しいと思っています。
ただ、berryzplus案を少し工夫して一度タグジャンプしたキーワード+出現位置の組み合わせをキャッシュし、二度目以降のタグジャンプをキャッシュに問いあわせて高速化などの応用には使えそうですね。

[berryzplus]

う～む。色々ありますねぇ。

ちらっと思ったこと：
数百MBもの巨大なtagsインデックスが作られるケースがあるなら、いっそのことメモリ内mapではなく本物のデータベースを使ってしまう手もあります。visual studioはintellisenseのバックエンドにsqliteを使っています。テーブル構造とか真面目に設計しないとアレですが、作りようによってはDB使ったほうが速度も保守性も高くなるかも知れません。

あとぼんやりですが、tagsファイル読込の非同期化はなんとかしたほうが良さそうに思いました。

[beru]

実際に実験していないので速くなるか分かりませんがメモリマップトファイルを使うのはどうだろうか？と教えて頂いた CDlgTagJumpList::find_key_core() を眺めていて思いました。

[7-rate]

sqliteなどのデータベースを使う案はいいかもしれませんね。
私自身あまり触ったことがないのですぐに実装というわけにはいきませんが、、
それに懸念もあります。
今まで使っていたtagsファイルからフォーマットが変わるわけなのでユーザーとしても困惑するのではないかな？と思います。tagsファイルはvimなどの他エディタでも使われているフォーマットのものなので個人的にも変えたくはないですね。。両方(tagsとsqlite等DB)使えるようにすればその辺は解決しますが。

beruさん、ご意見ありがとうございます。
メモリマップトファイルについての知識があまりないのですが、ディスク上のファイルを仮想メモリに割り当てる機能だとざっくり認識しています。
tagsファイルを仮想メモリに割り当てても実態はディスクにあるため高速化にはつながらないのでは？と考えています。(ファイルポインタをもとにfgets()で読み込んでいたものを、仮想メモリに割り当てることで配列のように添え字参照できるという旨味はありますが)

[7-rate]

vimでもtagsファイルを二分探索でキー探索しているようです。
下記参考に細々と実装してます。
https://github.com/vim/vim/blob/493fbe4abee660d30b4f2aef87b754b0a720213c/src/tag.c#L1248

[berryzplus]

データベースをバックエンドにしたら、検索を高速化するコードを自作しなくてもイケるかな？って感想なので、tagsファイルは何も変わらんです。将来的にやってみたい実装ですが、とりあえず普通に二分探索がいいのかな？と思ってます。

メモリマップトファイルは、ファイルデータを仮想メモリに割り当てる技術です。必要な時に必要な部分だけコミット(=実メモリに割り当て)する使い方が出来ます。GBオーダーの巨大ファイルを扱う方策として何度か話題に上がってました。

tagsに応用した場合、二度目以降のアクセスの高速化に役立つのかな？と思います、マップを突っ込んで退避しとくってのもあるかな。