findコマンドが遅いからgoで書き直してみた件

findって時間かかるよね。

特に以下のように「このサーバのどっかには存在するはずのclientって名前のつくファイル名のファイルを探す」時にfindをかますと、特に多くのファイルの乗ったファイルサーバ等では少し時間がかかるのは皆さんも御存知の通りかと思われます。

$ sudo time find / -name "*client*" > /dev/null

real    0m1.503s
user    0m0.980s
sys     0m1.068s

単純に指定したファイルシステム配下を全てなめてる訳ですから、
まぁ分からんでもない速度です。
ではこのfindをGoで書いてみるとどれくらい速く出来るかというのがこの記事の趣旨です。まぁ勉強がてら見てみましょうや。

※ちなみに本記事のtime、つまり計測時間については、10回平均を書いています。

やる前に。

単純にgoでフォルダを再帰させるだけだとどれくらいの速度かみてみます。こちらを参考にさせていただきました。

package main

import (
    "fmt"
    "io/ioutil"
    "path/filepath"
    "strings"
)

func main() {
    fmt.Println(dirwalk("/"))
}

func dirwalk(dir string) []string {
    files, err := ioutil.ReadDir(dir)
    if err != nil {
        fmt.Println(err)
    }

    var paths []string
    for _, file := range files {
        if file.IsDir() {
            paths = append(paths, dirwalk(filepath.Join(dir, file.Name()))...)
            continue
        }
        if strings.Contains(file.Name(), "README"){
        paths = append(paths, filepath.Join(dir, file.Name()))
        }
    }

    return paths
}

このスペックでやってみる

CPU: Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz x 2個
メモリ: 8GB

#普通のfind
$ time find / -name "*README*" 

real    0m1.273s
user    0m0.516s
sys     0m0.680s

#goで書いたfind
$ time ./cmd

real    0m2.167s
user    0m1.000s
sys     0m1.184s

ま、まぁこんなもんか（こっから速くなるのか・・・？）
頑張ってやっていこー！

速さの為にコードを書く時意識したこと。

• 最後に標準出力する結果以外は参照渡しやgolang で string を []byte にキャストしてもメモリコピーが走らない方法を使用し、string型のままで文字列連結等せずに[]byte型でのやり取りを徹底する。
• フォルダを再帰的に掘る、という動作をする際、一つのフォルダを再帰的に掘っている時の待機がfindをする上での最大の無駄だと思うのでここを並列化する。この際、なんでもかんでも全部並列化すればよいわけではないので、最初に指定したフォルダ配下のフォルダのみ並列化してやる事にする。
• 謎のプライドやマルチプラットフォームで動くよう、cgoは使いません。ってか使っていいならCでfind書き直した方が(ry

コードはこれ。

goのバージョン:1.9.1

fingp.gp

package fingo

import (
    "fmt"
    "io/ioutil"
    "os"
    "path/filepath"
    "runtime"
    "strings"
    "sync"
    "unsafe"
)

func para(root, word string, d os.FileInfo, buff *[]byte, wg *sync.WaitGroup) {
    *buff = append(*buff, dirwalk(word, filepath.Join(root, d.Name()))...)
    defer wg.Done()
}

func FindFile(root, word string) string {
    dir, err := ioutil.ReadDir(root)
    if err != nil {
        fmt.Println(err)
    }

    runtime.GOMAXPROCS(runtime.NumCPU())
    wg := new(sync.WaitGroup)
    buff := make([]byte, 0, 1000)

    for _, d := range dir {
        if !d.IsDir() {
            dirwalk(word, filepath.Join(root, d.Name()))
            continue
        }
        wg.Add(1)
        go para(root, word, d, &buff, wg)
    }
    wg.Wait()
    return string(buff)
}


func dirwalk(word, dir string) []byte {
    files, err := ioutil.ReadDir(dir)
    if err != nil {
        fmt.Println(err)
    }

    paths := make([]byte, 0, 200)

    for _, file := range files {
        if file.IsDir() {
            paths = append(paths, dirwalk(word, filepath.Join(dir, file.Name()))...)
            continue
        }
        if strings.Contains(file.Name(), word) {
            path := filepath.Join(dir, file.Name()) + "\n"
            bp := *(*[]byte)(unsafe.Pointer(&path))
            paths = append(paths, bp...)
        }
    }
    return paths
}

main.go

package main

import (
    "fmt"
    "github.com/nao4arale/fingo"
    "os"
    "runtime"
)

func main() {
  /* os.Args[1]...Dirctory, os.Args[2]...To find Words. */
    fmt.Printf("%s", fingo.FindFile(os.Args[1], os.Args[2]))
}

結果

結論から言うと、CPU数の暴力で殴ればfindに勝てます
（findは、速かった笑）

検証環境①

CPU: Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz x 2個
メモリ: 8GB

#普通のfind
$ time find / -name "*README*" | wc -l
3354

real    0m1.273s
user    0m0.516s
sys     0m0.680s

#goで書いたfind
$ time ./cmd / README | wc -l
3361

real    0m1.648s
user    0m0.952s
sys     0m1.240s

負けてんじゃねーかｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
※wcの結果ですが、エラーの行数の分で違うだけです。

検証環境②

CPU: Intel(R) Xeon(R) CPU E5620 @ 2.40GHz × 6個
メモリ: 16GB

#普通のfind
$ time find / -name "*README*" | wc -l
416

real    0m0.921s
user    0m0.236s
sys     0m0.308s

#goで書いたfind
$ time ./cmd / README | wc -l
419

real    0m0.595s
user    0m0.572s
sys     0m0.536s

良かった勝てたみたいね
とりあえず並列させまくればCにでも勝てる事がなんとなくわかりました。
ま、環境下でいくらでも変わってくるとは思いますが、Cのコードであるfindに張り合えるくらいの書き方は出来た気がするので、まぁ良しとしようかしら。最大限リソースを利用すれば、C相手でさえ勝てるのがGoの魅力ですね。
あ、ご指摘お待ちしております。

オマケ：CPU6個でやった時のmpstatの様子も見てみる

#普通のfind
0時58分14秒  CPU    %usr   %nice    %sys %iowait    %irq   %soft  %steal  %guest  %gnice   %idle
10時58分15秒  all    5.53    0.00    9.55    0.00    0.00    0.17    0.00    0.00    0.00   84.76
10時58分15秒    0    3.03    0.00   10.10    0.00    0.00    1.01    0.00    0.00    0.00   85.86
10時58分15秒    1   14.85    0.00   27.72    0.00    0.00    0.99    0.00    0.00    0.00   56.44
10時58分15秒    2   15.46    0.00   18.56    0.00    0.00    0.00    0.00    0.00    0.00   65.98
10時58分15秒    3    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00  100.00
10時58分15秒    4    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00  100.00
10時58分15秒    5    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00  100.00

#goで書いたfind
10時58分42秒  CPU    %usr   %nice    %sys %iowait    %irq   %soft  %steal  %guest  %gnice   %idle
10時58分43秒  all   10.89    0.00   15.58    0.00    0.00    0.00    0.00    0.00    0.00   73.53
10時58分43秒    0   12.00    0.00   14.00    0.00    0.00    0.00    0.00    0.00    0.00   74.00
10時58分43秒    1   10.00    0.00   16.00    0.00    0.00    0.00    0.00    0.00    0.00   74.00
10時58分43秒    2   12.00    0.00   17.00    0.00    0.00    0.00    0.00    0.00    0.00   71.00
10時58分43秒    3    9.00    0.00   14.00    0.00    0.00    0.00    0.00    0.00    0.00   77.00
10時58分43秒    4   10.42    0.00   13.54    0.00    0.00    0.00    0.00    0.00    0.00   76.04
10時58分43秒    5   11.88    0.00   18.81    0.00    0.00    0.00    0.00    0.00    0.00   69.31

goのコードではruntime.GOMAXPROCS(runtime.NumCPU())と書いてます。
が、ここまで綺麗に全て均等に使われているとは驚きというか、芸術的です。
これが見れただけでも今回やって良かったと思います。