RubyとGo言語を組み合わせて高速なgrepを作りました

Milkode 1.7で新しく入ったGomilkの技術解説です。ここ数ヶ月Go言語の勉強をしていましたが、Rubyで書かれたMilkodeとのよい組み合わせを思いつき、一ヶ月ほどかけて作ってみました。

Gmilkの問題

MilkodeにはGmilkというGrep感覚で使えるコマンドラインツールが付属しているのですがもう少し高速に検索したいという欲求がずっとありました。

Gmilkが遅い原因としては

• 関連するライブラリがたくさんあってアプリケーションの起動が遅い
• 検索候補のファイル一覧を回すループ処理が遅い

というのが主な理由でした。

これらの問題を解決するために新しいプログラムを書きました。 名前はGo言語で作るのでGomilkとしました(偶然ゴロがよかった)。

作戦

以下のような作戦で高速化を図りました。

1. あらかじめWebアプリを立ち上げておく
2. Gomilkを実行
3. Gomilkは引数から検索クエリを作ってhttp経由でWebアプリに渡す
4. Webアプリはもらったクエリーを元にGroongaで全文検索して検索候補のファイル一覧を返す
5. 受け取ったファイル一覧を元にGomilk側でファイル内容の検索を行う

実際の処理と照らし合わせると以下のようになります。

1. あらかじめWebアプリを立ち上げておく

$ milk web -g

2. Gomilkを実行

$ gomilk test

3. Gomilkは引数から検索クエリを作りhttp通信経由でWebアプリに渡す

GET http://127.0.0.1:9292/gomilk?dir=%2Fpath%2Fto%2Fdir&query=test

4. Webアプリはもらったクエリーを元にGroongaで全文検索して検索候補のファイル一覧を返す

/path/to/dir/Gemfile
/path/to/dir/app.rb

5. 受け取ったファイル一覧を元にGomilk側でファイル内容の検索を行う

`path/to/dir/Gemfile`の中から`test`を探す・・
`/path/to/dir/app.rb`の中から`test`を探す・・

主要ライブラリの初期化処理はあらかじめWebアプリ側で済ませておくことでアプリケーションの起動時間の短縮化につながります。

2, 3, 5に相当するhttp通信とファイル一覧を元にした検索処理はGo言語で書きます(ここがGomilk)。バイナリに変換出来るのでプログラムの基本速度自体が高速になり、並列処理を使って複数のファイルを同時に検索することも可能になります。ファイル一覧を回すループはずいぶんと高速になるはずです。

Groongaとの通信やwebアプリ自体の制御はすでにRubyで書かれているものを再利用出来るためGoで書き直す量を最小限に絞ることも出来ました。(割と重要)

結果

OSX 10.7.5, Core2 Duo 3.06 GHz, 8 GB RAM, 500GB HDD.

それぞれのルートディレクトリから"performance test"を検索しました。(例: grep -r "performance test")

Ruby-2.1.2 (4722 files)

	検索1回目(sec)	2回目以降(sec)
grep 2.14 (-r)	11.510	0.191
ag 0.22 pre	7.024	0.159
Gmilk 1.7.0	10.783	2.198
Gomilk 0.1	4.110	0.228

linux-3.10-rc4 (45752 files)

	検索1回目(sec)	2回目以降(sec)
grep 2.14 (-r)	40.135	1.747
ag 0.22 pre	35.923	1.459
Gmilk 1.7.0	※3.196	2.315
Gomilk 0.1	11.400	0.539

• (おそらく)ファイル内容がHDDのキャッシュに載っているかどうかで検索速度が変わるため、1回目と2回目以降で分けて計測しました
• HDDのキャッシュクリアはマシンを再起動すれば多分クリアされるだろう、という前提で行っています。
• ※について : よく理由が分からなかったのですが妙に早かったです・・。Rubyを検索した後にLinuxを検索してデータを取っていたためGroongaデータベースの内容が事前にキャッシュされ高速になったのかもしれません。(でもそれならGomilkももっと早くなっていいよなぁ)

特にキャッシュに載る前の最初の検索において、全てのファイルの中身を調べる必要のあるgrepやagと比べて、全文検索エンジンであらかじめ検索対象を絞り込めるGmilk, Gomilk の方が有利な印象です。

Gomilkはag等の高速なgrepと比べても安定してよいパフォーマンスを出せている事が分かります。Gmilkと比べると圧倒的に高速です。ファイル数が増えてくるとGroongaで事前に絞り込めるためGomilkの効率はさらに良くなります。

milk web 側の実装

milk web に -g オプションを付けた時に GET /gomilk を受け取れるようにします。例えば検索ディレクリ: /path/to/dir、検索文字列: testの場合は以下のようなURLを受け付けます。

GET http://127.0.0.1:9292/gomilk?dir=%2Fpath%2Fto%2Fdir&query=test

受け取ったWebアプリはディレクトリと検索文字列を使ってGroongaデータベースを検索します。検索結果のファイル一覧をテキスト形式で返します。

/path/to/dir/Gemfile
/path/to/dir/app.rb

後はGomilk側にお任せです。

GET /gmilk の結果例。検索候補となるファイル一覧が表示される。

Gomilkの実装

pt(monochromegane/the_platinum_searcher)のコードを大分参考にしました。というかptが無かったらGomilkを作る気にもならなかったと思います。枕に足を向けて寝られません。

私の場合はよく検索するコード群はMilkodeに登録してgomilkで検索し、それ以外はptを使って検索するように使い分けています。ptはWindows版があるのと日本語ファイルに強いのが嬉しい所です。

Gomilkが独自に実装した部分としては、ptがディレクトリ内を検索してファイルリストを作る部分を、http経由でmilk webと通信する処理に置き換えたことです。

まとめ

RubyとGoの組み合わせが上手くいって満足する検索スピードを得ることが出来ました。

私自身は今後は主にGomilkを使っていきますがGmilkも引き続きメンテナンスを続ける予定です。Rubyだけで動かせるGmilkの手軽さはやはり便利です。またGomilkやGmilkの最大のメリットは「いちいち検索先ディレクトリを指定しないで検索出来る」ことだと思っていて、agやgrepが高速でもGomilkを使えない環境であれば、Gmilkを使う価値は充分にあると思っています。

既存のアプリケーションをWebアプリとしてあらかじめ立ち上げておく事で、全てをGo言語に置き換える必要が無くなる、というのは色々と使えるアプローチではないかと思いました。

前も似たようなことを書いた気がしますがGo言語とRubyのようなLL言語の相性はとてもよいと思っていて、まずはRubyでさくさくと作り、後で速度が必要になってきた部分をGo言語で置き換えていくとなかなかいいです。Webアプリ等のバックエンドを置き換える例はすでに色々な所で紹介されていますが、Gomilkの場合はフロントエンドを置き換える一つの例になったのではないでしょうか。

Gomilkは「検索先ディレクトリの指定が不要で、かつgrepやagよりも高速に検索出来る」私にとって理想のツールになりました、是非一度お試し下さい。まだ出来たばかりなので随時機能は追加していく予定です。

Milkode 1.7 をリリース - gomilk

• Go言語で作ったgmilkの高速版、gomilkに対応
• gmilk --expand-path に対応
• README, ヘルプの国際化強化

インストール

$ gem install milkode

ダウンロード, Gems

Go言語で作ったgmilkの高速版、gomilkに対応

ongaeshi/gomilk

Go言語で書かれた高速なgmilkです。

Rubyで書かれたWebアプリと通信して(Groongaを使って)検索候補となるファイルを見つけ出し、Go言語でファイル内検索するのでめちゃ早いです。

試しにRubyのソースコード全体(4722 files)から検索すると0.2秒位で結果が返ってきます。Linux(45752 files)でも0.5秒位でした。- 詳しく

ファイル内検索部分は monochromegane/the_platinum_searcher を大分参考にさせて頂きました。私の場合はよく検索するコード群はMilkodeに登録してgomilkで検索し、それ以外はptを使って検索するように使い分けています。

簡単な使い方

1. gomilkのバイナリをダウンロードして(またはソースからgo build)、PATHの通った場所に置きます。
2. mil web -gでWebアプリを起動します
3. 後はgmilkと同じように使って下さい。

# 現在パッケージで検索
$ gomilk search_keyword

# 全体パッケージで検索
$ gomilk -a search_keyword

詳しくはongaeshi/gomilkをどうぞ。

emacs-milkodeで使う時は--nogroup --nocolor --smart-caseオプションを追加するといいです。

gmilk --expand-path に対応

gmilkでの検索結果のファイルのパス · Issue #66 · ongaeshi/milkode

README, ヘルプの国際化強化

READMEに基本的な使い方を(英語で)追加しました。 英語版のヘルプも書きました。これでWebアプリで日本語しか無い所は無くなったはず・・。

リリースノート

• milk web

  • Support gomilk option (milk web -g)
    • https://github.com/ongaeshi/gomilk
  • Support i18n in the help.haml

• gmilk

  • gmilkでの検索結果のファイルのパス (thanks kazuna)

• etc

  • Improve README
  • Add a badge of gem version
  • Change the setting of TravisCI [groonga-dev,02268]
  • Change to Bundler a method of generating a gem
    • Jeweler, Thanks for long support

関連記事

• Milkode 1.6.1 をリリースしました
• Milkode1.4リリース - ドリルダウンによるマウスクリックの絞り込み機能を追加！
• Milkode1.3リリース - GitHubボタンを追加、キーワードのマッチ箇所をハイライト
• Milkode 1.2 リリース : ファイル名のマッチ個所に色づけ、ctags連携、~/.gitignoreのサポート

A Tour of Go を一通りやってみて、 Go言語の印象に残った機能や特徴などの感想

はじめてのGo言語 - ブログのおんがえし に続いて A Tour of Go を最後までやってみました。

コードを実際に実行させながら基本的なGoの使い方を学ぶことで出来るのでおすすめです。日本語版もあります。

英語の勉強にもなるので私は英語版を使いました。どうしても意味が分からない時だけ日本語版を読むようにしたのですが、コードもあるし全体の80%くらいは英語だけでなんとか分かりました。プログラマはコード例などが付いているものの方が英語学習が捗ると思っています。

解答例

以下を大分参考にさせてもらいました。

• A Tour of Go で Go に入門した - ゆううきブログ

私の解答は GitHub に。

• ongaeshi/tour-of-go

演習問題は少し難しいけどGo言語の得意分野がなんとなく分かるのでおすすめです。どうしても分からない時は解答を読んで理解してみるといいです。

印象に残ったトピック

#8 Functions continued

link

func add(x, y int) int {
   ….
}

ローカル変数、引数、戻り値、どれも Go は後ろに付けます。よく考えられていて色々な恩恵があります。例えば同じ型種類の引数が連続している時は一つだけ指定すればよいです。

#13 Short variable declarations

link

func main() {
    var i, j int = 1, 2
    k := 3

基本は var でローカル変数を宣言するのですが、最初の初期化の時だけ:=で初期化することが出来ます。結果としてほとんどのローカル変数は:=で初期化することになり、コードの見通しがよくなります。どうしても初期化が後回しになる時だけ var を使うのがよさそうです。

この機能は本当によいので、 C# や C++ でも var や auto と一緒に使えるようにして欲しいなぁ。

#20 For is Go's "while"

link

func main() {
    sum := 1
    for sum < 1000 {
         ...
    }

ループ用の構文は for しかないです。while っぽいループも for で書きます。

func main() {
    for {
    }
}

引数無しだと無限ループになります。

#33 Slicing slices

link

特定範囲のサブ配列を取得することが標準で出来ます。

func main() {
    p := []int{2, 3, 5, 7, 11, 13}

    fmt.Println("p[1:4] ==", p[1:4])
    fmt.Println("p[:3] ==", p[:3])
    fmt.Println("p[4:] ==", p[4:])

#36 Range

link

foreach は for + range で表現します。for 1つでループ関連を全て表現しようと頑張っている印象です。

func main() {
    for i, v := range pow {
        fmt.Printf("2**%d = %d\n", i, v)
}

#41 Map literals continued

link

Map型(数値以外をインデックスに取れる配列、RubyのHash)も標準搭載です。リテラル表記もあるのがありがたいです。

type Vertex struct {
    Lat, Long float64
}

var m = map[string]Vertex{
    "Bell Labs": {40.68433, -74.39967},
    "Google":    {37.42202, -122.08408},
}

#44 Function values

link

関数も値としてとれます。クロージャにも対応しているので JavaScript で出来ることもある程度出来るのではないかと思います。

func main() {
    hypot := func(x, y float64) float64 {
        return math.Sqrt(x*x + y*y)
    }

#52 Methods

link

メソッドの書き方はなかなかに個性的で struct の横に書きます。C# や C++ が struct の下に直接関数を定義する事で (v *Vertex) を省略出来るのでここだけ見ると面倒なのですが・・

type Vertex struct {
    X, Y float64
}

func (v *Vertex) Abs() float64 {
    return math.Sqrt(v.X*v.X + v.Y*v.Y)
}

#53 Methods continued

link

float64 を typedef してそこに独自のメソッドを定義するようなことがあっさりと出来ます。

C# や C++ ではメソッドはクラスの所有物なのに対して、Go では構造体とメソッドが対等な関係になります。一長一短ですが基本型にもメソッドが定義出来る事、コンパイラの内部構造をよりすっきりと表現出来ていることは Go のメリットだと考えます。

type MyFloat float64

func (f MyFloat) Abs() float64 {
    if f < 0 {
        return float64(-f)
    }
    return float64(f)
}

#57 Interfaces are satisfied implicitly

link

個人的に一番面白かったのはインターフェース周りでした。継承関係を明示しなくても関数定義が条件を満たしていればそのインターフェースに属していることになります。

分かりにくいですが、独自に定義した Writer インターフェースに標準ライブラリの os.Stdout を代入することが出来ます。(Write関数を持っているから) さらに、 fmt.FPprintf(w io.Writer ..) の第1引数に独自に定義した Writer インターフェースを渡す事も出来ます。

type Writer interface {
    Write(b []byte) (n int, err error)
}

func main() {
    var w Writer

    // os.Stdout implements Writer
    w = os.Stdout

    fmt.Fprintf(w, "hello, writer\n")
}

標準ライブラリもこの機能をフルに使っていて、ユーザーがカスタマイズしたものを渡したいようなものはあらかじめインターフェースで定義されているので、条件を満たす関数を定義すれば簡単に標準ライブラリに渡すことが出来るようになります。詳しくは以下にたくさん載っているので読んでみるとよいです。

• Big Sky :: Golang のオフィシャルが提供するインタフェースまとめ

#65 Goroutines

link

並列化が簡単に書けるのでいいですね。

func main() {
    go say("world")
    say("hello")
}

まとめ

Rebuild: 42 でも Go言語が紹介されていたし、よいタイミングで勉強出来たような気がします。

どこかで「色々な言語を触っているとGo言語のよさが分かる」というのを見ましたが、まさにその通りだと思います。C/C++/Objective-C/D/C#/Java といった C系の言語と Ruby/Perl/Python/PHP といった LL系の言語を両方触ったことがある人が Go を触ると、両者のよい所を上手く取り入れた言語になっているのが良く分かるのではないでしょうか。

go runでコンパイル無しで実行出来たり、ヘッダが不要で記述量が少ないこともあって初見でスクリプトに近い印象も受けるのですが、スクリプトの良さを取り入れたC言語だという理解をしています。さくっと書く時のスピード感はやはりスクリプトの方が早いです。が、C と比べたら Go の快適さは素晴らしいです。

C で書く領域を全て Go で書けるような未来はまだ先でしょうが、今までなら C で書くようなケースで Go で書ける環境が整っているのであれば、試してみる価値は充分にあるのではないのかと思いました。はこべブログでも言及されていましたが LL から使うミドルウェア部分なんかはまさにそういう所だと思います。

ハッシュ、文字コード変換、http とのやり取り、並列処理などが標準として用意されているのも大きいです。この辺を C で書こうとすると Windows, OSX, Linux で分岐するコード書く必要がどうしても出てしまうので。Go ならこの辺りの機能を含んだバイナリを簡単に作る事が出来ます。

他の人の見解もたくさんあるので是非。私の感想よりおすすめです。

• Go言語の気に入ったところ/気に入らなかったところ - はこべブログ ♨
• Rebuild.fm ep42の補足等 : D-7
• 規模の大きい本番システムをGo言語で書き直した感想 - ワザノバ | wazanova

はじめてのGo言語

pt(monochromegane/the_platinum_searcher)を改造してみたくなり(つまりはWindowsでも動くagが欲しくて)、久しぶりに新しい言語が覚えたくなったのでGo言語をはじめてみました。

以下、最初にひっかかった所を含めてメモ。

インストール

$ sudo port install go (or brew install go)

続いてGOPATHの設定。ソースコードやライブラリが置かれる場所だと理解している。

$ export GOPATH=$HOME/Documents/gocode

定まったら.bashrcに追記しておく。

Mercurial のインストール

go get (ライブラリをインストールするコマンド) は Git や Svn や Mercurial 等をライブラリ提供者側が選択出来るらしい。で、Google製のライブラリは Mercurial で提供されているようなので Git しか入っていない人はここで Mercurial をインストールしておく。

$ sudo port install mercurial

go get でトラブル

一番引っかかった所。

$ go get github.com/PuerkitoBio/goquery

に失敗する。エラーが起きない人は次に進んでよい。 curl-ca-bundle を再インストールすることで動くようになった。

$ sudo port install curl-ca-bundle
$ sudo port -f activate curl-ca-bundle @7.36.0_0
--->  Activating curl-ca-bundle @7.36.0_0
Warning: File /opt/local/etc/openssl/cert.pem already exists.  Moving to: /opt/local/etc/openssl/cert.pem.mp_1397399953.
--->  Cleaning curl-ca-bundle

Emacs用のgo-modeをインストール

とりあえずどんな言語でもメジャーモードが用意されているのは Emacs のよい所。

M-x package-install go-mode

Goは基本インデントがタブなので、タブ幅を4に設定しておく。

(setq default-tab-width 4)

Emacs は go-mode が良く出来ていて特に気にせずタブに変換してくれるのでそんなに困らないけど、普段タブを使わないエディタ設定を使っている人は注意。(空白でもとりあえず書けるようではある。)

チュートリアルをやってみる

A Tour of Go (日本語版)

を少しづつ進めるとよい。

例えば#3 The Go Playgroundを3.goに保存したら、

package main

import (
    "fmt"
    "net"
    "os"
    "time"
)

func main() {
    fmt.Println("Welcome to the playground!")

    fmt.Println("The time is", time.Now())

    fmt.Println("And if you try to open a file:")
    fmt.Println(os.Open("filename"))

    fmt.Println("Or access the network:")
    fmt.Println(net.Dial("tcp", "google.com"))
}

go runで実行出来る。

$ go run 3.go
Welcome to the playground!
The time is 2014-04-20 15:49:47.334389539 +0900 JST
And if you try to open a file:
<nil> open filename: no such file or directory
Or access the network:
<nil> dial tcp: missing port in address google.com

go buildでバイナリを作成。

$ go build 3.go
$ ./3            # 実行
Welcome to the playground!
The time is 2014-04-20 15:51:22.174033453 +0900 JST
And if you try to open a file:
<nil> open filename: no such file or directory
Or access the network:
<nil> dial tcp: missing port in address google.com

普段 の開発中はほとんどgo runしか使わなくてよい、スクリプトっぽく動かせて便利。

the_platinum_searcher をビルドする

monochromegane/the_platinum_searcher の通りなのだけど、go getして、cdして、go buildする。

$ go get github.com/monochromegane/the_platinum_searcher
$ cd $GOPATH/src/github.com/monochromegane/the_platinum_searcher
$ go build -o ~/tmp/pt

最後だけ~/tmp/ptに変えてるけど要はバイナリの出力先なので好きな所に。

ここからptを改造していくのだけどそれはまた次の機会に。

Go言語初感

触って一週間位の人の感想です。

• Windows, OSX, Linux で動くバイナリを簡単に作れるのはかなりよい
• CやC++に比べると記述量を減らそうとかなり努力している
  • C/C++ > D, C#, Go > Ruby, Python の印象
  • なによりヘッダを書かずにネイティブコードが吐けるのは嬉しい (Dもだけど)
• 静的型なので型チェックによってテストを書かなくてもある程度の安全性が保証される
• go runを使えば実行まで1ステップなので開発中のターンアラウンドはスクリプト言語のそれに近い
  • もっと規模の大きなコードを書くと印象が変わるかもしれないけど
• 本当のウリはgoルーチンを中心とする並列化処理だったりするのだろうけどその辺はまだ触ってないです、すいません
• :=の初期値代入が好き

まずは、他言語のライブラリに余り依存していなくて(もしくはGo言語向けのライブラリがすでに存在していて)、最終的にバイナリ形式で配布したいものに使ってみようかと思います。