高速検索 the_silver_searcher を使ってみる - インゲージ開発者ブログ

こんにちは、masm11 です。たまには新しいツールでも導入して快適になってみましょう。

今回ご紹介するのは、高速検索ツール the_silver_searcher です。

検索の仕方の変遷

以前は grep を使ってましたよね。

grep foo *.rb

これだとカレントディレクトリしか探してくれないので、

grep foo *.rb */*.rb

なんてしてみたり、もしくは grep に -r オプションができたので

grep -r foo .

ってのもありかもしれません。

ずっと私は find, xargs, grep を使っていました。

find . -name \*.rb -print0 | xargs -0 grep foo

こんなのですね。この程度ならさらさらと打てます。いつも同じパターンなので。

しかし、遅いのです。もっとズババッッ! と検索して欲しいです。

the_silver_searcher とは

そこで、the_silver_searcher の登場です。速いです! 速さの秘訣を本家 github サイトから超訳すると、

pthread を使って並列処理している
バッファに読み込まず mmap() を使っている
Boyer-Moore の検索アルゴリズムを使っている
正規表現の検索には JIT コンパイラを使っている
同じ正規表現を使う時には正規表現コンパイラのキャッシュが効いている
.gitignore の処理も配列とバイナリサーチを駆使

さて、ではまずはインストールしてみます。

macOS の場合は Homebrew が使えます。Homebrew がインストールされているなら、

brew install the_silver_searcher

これだけです。

CentOS の場合は、

sudo yum install the_silver_searcher

ArchLinux の場合は、

sudo pacman -S the_silver_searcher

です。

では使ってみましょう。

the_silver_searcher というのは、ソフトウェアの名前です。これが即ちコマンド名なわけではありません。コマンド名は ag です。 silver → 銀 → ag ですね。

ざっと実行してみた感じ、↓こんな出力です。

luna:emacs % ag pgtk_menu_show
src/pgtkterm.indent
4793:  terminal->menu_show_hook = pgtk_menu_show;

src/pgtkterm.c
4650:  terminal->menu_show_hook = pgtk_menu_show;

src/menu.h
63:extern Lisp_Object pgtk_menu_show (struct frame *, int, int, int,

src/pgtkmenu.c
619:pgtk_menu_show (struct frame *f, int x, int y, int menuflags,
luna:emacs %

実際には色が付いていてそこそこ見やすくなっています。

f:id:masm11:20200817172509p:plain

さて、検索時間を比べてみましょう。一体どのくらい速いのでしょうか?

まずは find, xargs, grep でやってみます。できるだけキャッシュに載せるため、連続で実行しています。

luna:emacs % for i in `seq 10`; do time bash -c '(find . -type f -print0 | xargs -0 grep pgtk_menu_show) > /dev/null 2>&1'; sleep 1; done
bash -c   0.98s user 0.70s system 51% cpu 3.259 total
bash -c   1.39s user 1.03s system 47% cpu 5.137 total
bash -c   1.27s user 1.13s system 46% cpu 5.183 total
bash -c   1.26s user 1.18s system 47% cpu 5.148 total
bash -c   1.30s user 1.17s system 47% cpu 5.197 total
bash -c   1.27s user 1.01s system 44% cpu 5.051 total
bash -c   1.39s user 1.09s system 47% cpu 5.165 total
bash -c   1.33s user 1.16s system 47% cpu 5.239 total
bash -c   1.10s user 1.02s system 45% cpu 4.624 total
bash -c   0.92s user 0.96s system 47% cpu 3.942 total
luna:emacs %

1回5秒程かかっています。次に ag を使って検索してみます。

luna:emacs % for i in `seq 10`; do time ag pgtk_menu_show > /dev/null; sleep 1; done
ag pgtk_menu_show > /dev/null  0.10s user 0.16s system 361% cpu 0.071 total
ag pgtk_menu_show > /dev/null  0.14s user 0.14s system 406% cpu 0.067 total
ag pgtk_menu_show > /dev/null  0.11s user 0.16s system 407% cpu 0.065 total
ag pgtk_menu_show > /dev/null  0.13s user 0.14s system 401% cpu 0.066 total
ag pgtk_menu_show > /dev/null  0.14s user 0.13s system 400% cpu 0.067 total
ag pgtk_menu_show > /dev/null  0.11s user 0.13s system 385% cpu 0.061 total
ag pgtk_menu_show > /dev/null  0.11s user 0.15s system 401% cpu 0.065 total
ag pgtk_menu_show > /dev/null  0.10s user 0.16s system 401% cpu 0.066 total
ag pgtk_menu_show > /dev/null  0.08s user 0.20s system 362% cpu 0.077 total
ag pgtk_menu_show > /dev/null  0.12s user 0.16s system 400% cpu 0.068 total
luna:emacs %

1回 0.1 秒未満!? 素晴らしいスピードです。

the_silver_searcher を Emacs で使う

dumb-jump

Emacs でタグジャンプと言えば、TAGS ファイルでしょうか。私はほとんどお世話になったことがありません。ずっと find, xargs, grep でやってました。

上で見た通り、ag がこれだけのスピードで返答を返せるなら、 TAGS なんてなくても、その場で力任せに検索してやればいいですよね? そのためのパッケージが Emacs にあります。dumb-jump といいます (dumb-jump は grep にも対応しています)。

このパッケージは主に「このメソッドの実体はどこにあるのかな～」と探すためにあるようです。

M-x package-list-packages で dumb-jump を探してインストールします。
ついでに ivy, posframe, ivy-posframe も使うことにするのでインストールします。
~/.emacs (または ~/.emacs.d/init.el ですかね?) に以下のように設定して Emacs を再起動します。 ivy と ivy-posframe の設定もしてるので長いですが、dumb-jump の設定自体は最後の段落のみです。

(require 'ivy)
(ivy-mode 1)
(setq ivy-use-virtual-buffers t)
(setq enable-recursive-minibuffers t)
(setq ivy-height 15)
(setq ivy-extra-directories nil)
(setq ivy-re-builders-alist
      '((t . ivy--regex-plus)))
(define-key ivy-minibuffer-map "\C-t" 'ivy-scroll-down-command)

(require 'ivy-posframe)
(setq ivy-posframe-display-functions-alist
      '((t . ivy-posframe-display-at-frame-center)))
(ivy-posframe-mode 1)

(require 'dumb-jump)
(setq dumb-jump-mode t)
(setq dumb-jump-selector 'ivy)
(setq dumb-jump-use-visible-window nil)

さて、何らかのソースコードを開き、メソッドを呼び出しているところにテキストカーソルを合わせ、おもむろに M-C-g を押してみてください。 1秒かからないくらいで、メソッド定義位置の候補が childframe に表示されたと思います。「これが定義のはず」と思う行を選択して Enter を押せば、その行にジャンプします。

「ジャンプ前の行どこだっけ?」と思ったら、M-C-p で戻れます。

また、M-C-q を使うと、そのメソッドを使っている箇所がいくつか childframe に表示されます。メソッドが他の箇所で具体的にどう呼ばれているかを見たい時に便利... なのでしょうか、これは便利さがまだよく解りません。

そして、言語によっては、カーソルのある位置からメソッド名をうまく取り出せないことがあるようです。そういう時は、メソッド名を範囲指定してから M-C-g を押すと、うまく検索してくれます。

ag

dumb-jump はタグジャンプしくれますが、もっと単純に grep みたいに検索して欲しいことがあります。つまり M-x grep の代わりです。

その名も ag というパッケージがあります。

M-x package-list-packages で ag を探してインストールします。
~/.emacs に以下のように設定して Emacs を再起動します。

(eval-after-load 'ag
  (lambda ()
    (setq ag-arguments '("--nobreak" "--smart-case" "--stats"))
    (fset 'masm11:ag (symbol-function 'ag))
    (fset 'masm11:ag-project (symbol-function 'ag-project))
    (defun ag (arg)
      (interactive "P")
      (if arg
          (masm11:ag (ag/read-from-minibuffer "Search string")
                     (read-directory-name "Directory: "))
        (masm11:ag-project (ag/read-from-minibuffer "Search string"))))
    (define-key ag-mode-map "n" 'next-error-no-select)
    (define-key ag-mode-map "p" 'previous-error-no-select)
    ))

本来 M-x ag が文字列とディレクトリを指定するバージョンで、 M-x ag-project が文字列だけを指定するバージョンです。 M-x ag-project の方はプロジェクト配下のディレクトリ全てにわたって検索してくれます。

が、どちらかというと、M-x ag-project の方をよく使うと思うので、そちらを M-x ag として使うようにしました。元々の M-x ag は C-u M-x ag で使えるようにしてあります。

そして、結果を表示しているバッファでは、n, p で次のヒットと前のヒットを移動できますが、M-x grep のように該当ファイルの該当行を表示してはくれません。Enter を押せば表示してくれるのですが。そこで、keymap をいじって M-x grep と同様の動作になるようにしてみました。

あと、ag-arguments については、元々は、マッチを含むファイルごとに空行が挿入されているのですが、見づらいので入れないようにしました。元々しっかり色が付いているので、空行がなくても全然問題はありません。

おまけ

ag の出力は上記の通り、デフォルトではツールに食わせるのには向いていません。しかし、実はそれは端末に出力する場合のみで、パイプに出力させると、以下のようにツール向きの出力になります。

luna:emacs % ag pgtk_menu_show | cat
src/pgtkterm.indent:4793:  terminal->menu_show_hook = pgtk_menu_show;
src/pgtkterm.c:4650:  terminal->menu_show_hook = pgtk_menu_show;
src/menu.h:63:extern Lisp_Object pgtk_menu_show (struct frame *, int, int, int,
src/pgtkmenu.c:619:pgtk_menu_show (struct frame *f, int x, int y, int menuflags,
luna:emacs %

また、ag は .gitignore を参照します。.gitignore に書かれているファイルは検索対象外です。 .gitignore に書かれているファイルも対象にするには、-t などを指定するのが良いでしょう。

(いまさらですが、実は先述のスピード差は、.gitignore に書いてあるファイルを対象外にしてるから、というのが最も大きいです)