monolithic kernel

CLI でのテキスト処理を高速化する

January 06, 2016

    最近、個人的に数百MBから数GBクラスのテキストファイルを扱う機会が増えています。これくらいのサイズだと、手元のマシンだけで十分対応可能な範囲ではあるのですが、扱いを間違えると時間が掛かってつらいことになります。結論から言うと、とにかく LC_ALL=C を指定しようというのと、OS X であれば初めから入っているコマンドではなく最新の coreutils を使おうという2点なのですが、それだけ終わってしまうとあんまりなので、手元の環境で計測した数字を出しつつ紹介したいと思います。

    なお、この記事中の速度計測はクアッドコアの Core i7 (2.2GHz) を搭載した MacBook Pro 15インチ (Mid 2014) で行いました。OS は OS X El Capitan です。テスト用のデータは以下のようなコマンドで生成しました。

    % perl -e 'for (1..2**24) { print(rand."\n"); }' > test.txt

    LC_ALL=C を指定しよう

    きっかけは、sort が異様に遅いということでした。高々数百MB程度のデータをソートするのに何分も掛かるのはおかしいと思い、調べてみたところ、ロケールの設定が原因との情報にたどり着きました。LC_ALL=C の環境変数を指定すると、ロケールを考慮した文字列比較を行わずにバイト列としてソートするようになるため、高速化されるようです。

    試してみたところ、その差は歴然。ロケールを考慮する必要が無ければ、忘れずに LC_ALL=C を指定したいですね。

    % time sort test.txt > /dev/null
    sort test.txt > /dev/null  311.11s user 0.54s system 99% cpu 5:11.68 total
    
    % time LC_ALL=C sort test.txt > /dev/null
    LC_ALL=C sort test.txt > /dev/null  18.18s user 0.55s system 99% cpu 18.782 total

    ちなみに、LC_ALL=C を指定することで comm, grep, look, uniq なんかも速くなるようです。

    coreutils を使おう

    こちらのきっかけは、tail -n+2 でファイルの2行目以降を切り出そうとすると cat でファイル全体を出力するのと比べてとんでもなく遅くなるということでした。

    % time cat test.txt > /dev/null
    cat test.txt > /dev/null  0.00s user 0.09s system 89% cpu 0.101 total
    
    % time tail -n+2 test.txt > /dev/null
    tail -n+2 test.txt > /dev/null  29.51s user 0.14s system 99% cpu 29.667 total

    意味がわからないですね。ただ、知人に相談したところどうも Linux だと cat と遜色ない速度が出るとのこと。そこで、GNU の提供するコマンド群の最新バージョンを利用できる coreutils を試してみることに。

    % brew install coreutils

    coreutilstail である gtail で試してみると、確かに cat に近い速度が出るようになりました。BSD の tail がなぜ遅いのかまでは確認していませんが、とにかく -n オプションを使ったアクセスのパターンにおいて GNU の tail は優秀だということがわかりました。

    % time gtail -n+2 test.txt > /dev/null
    gtail -n+2 test.txt > /dev/null  0.07s user 0.22s system 90% cpu 0.317 total

    そうなると、他のコマンドはどうなのかも気になるところ。他にもいくつか試してみました。

    sort

    LC_ALL=C を付けた sort よりさらに速くなりました。376% cpu という結果でわかるように、最新の coreutils に含まれる sort はマルチコア CPU を活用してソートしてくれるようです。

    % time LC_ALL=C sort test.txt > /dev/null
    LC_ALL=C sort test.txt > /dev/null  18.18s user 0.55s system 99% cpu 18.782 total
    
    % time LC_ALL=C gsort test.txt > /dev/null
    LC_ALL=C gsort test.txt > /dev/null  22.28s user 1.19s system 376% cpu 6.236 total

    ちなみに、El Capitan 付属の sortcoreutils のもののようですが、バージョンが 5.93 で、コピーライトの表記は2005年でした。今は 8.24 なのでかなり古いですね。coreutils のような地味なコマンドも、10年の間に着実に進化し続けているとも言えますね。カッコいい。

    wc

    実装する立場で考えると sort ほどは工夫の余地は無さそうな wc ですが、それでも coreutils に乗り換えるとかなり速くなります。すごい。

    % time wc -l test.txt > /dev/null
    wc -l test.txt > /dev/null  0.28s user 0.06s system 98% cpu 0.339 total
    
    % time gwc -l test.txt > /dev/null
    gwc -l test.txt > /dev/null  0.14s user 0.06s system 87% cpu 0.229 total

    なお、El Capitan 付属の wc は古い coreutils のものではなく、BSD 由来のものでした。

    エイリアスを設定する

    個人的には sort でロケールを考慮したいことはまずないですし、g のプレフィックスを意識するのも面倒なので、シェルのエイリアスを設定することにしました。$(brew --prefix coreutils)/libexec/gnubin にパスを通すことで coreutils のコマンドで sort 以外も含めてごっそり置き換えることも可能ですが、副作用がこわいので、使いたいと思ったものについて手でエイリアスを足す運用にしています。どうせ LC_ALL=C 付きのエイリアスは作るわけですし。

    alias comm='LC_ALL=C gcomm'
    alias grep='LC_ALL=C ggrep'
    alias look='LC_ALL=C look'
    alias sort='LC_ALL=C gsort'
    alias tail='gtail'
    alias uniq='LC_ALL=C guniq'
    alias wc='gwc'

    ggrepcoreutils のものではなく、以下のようにしてインストールしたものです。

    % brew install homebrew/dupes/grep