tips: sort は LANG=C で4倍速くなる

LANG=C sortは、LANG=en_US.UTF-8 sortと比べて 1/4 の時間で処理が終わることを確認しました。

同じ処理にかかる時間を、LANG=C の場合とLANG=en_US.UTF-8とで比べると、以下のようになりました。

locale	平均時間[sec]	標準偏差
C	0.2028	0.0103
en_US.UTF-8	0.8831	0.0191

どういうこと?

環境変数 LANG を適切に設定することで、エラーメッセージが母国語になったり、日付の書式が日頃から使い慣れた様式に変わったり…と、locale によるネイティブ言語対応は素晴らしいものです。

locale は、いろいろなところに影響を及ぼします。例えば ls の出力順も変わります。

$ touch a b c A B C
$
$ LANG=C export LANG
$ ls
A  B  C  a  b  c
$
$ LANG=en_US.UTF-8 export LANG
$ ls
a  A  b  B  c  C
$

LANG=C の場合は、ファイル名が ASCII コード順に A→Z→a→z で出力されています。
ファイル名を表すバイト列の大小で並べ替えている、とも言えます。

LANG=en_US.UTF-8 の場合は、アルファベット順に [aA]→[bB]→[cC]→…となっています。また大文字は小文字より後にならぶ規則も見えます。
すなわち、バイト列の大小とは異なる(人間の文化に沿った)特別な規則を当てはめて文字を並べ替えています。

逆に言うと、LANG=C とは「locale 処理の無い状態」にあたります。
C 以外の locale を設定する、とは「この文字はあの文字より先か後か、を決めるためにいちいち locale の処理が必要になる」ことを意味しています。

ならば、LANG=C を設定するだけで locale 処理が省略されるわけで、処理終了までにかかる時間も短縮できるハズです。コの世界において「速いは正義」です。夢のような話です。

ここでは「ランダムな文字列 10万件を sort するのにかかる時間」を、locale (＝環境変数 LANG)を切り替えて計測し比較してみました。

環境

VPS 環境の CentOS 6.5 で確認しました。
OS 標準の bash、time、および sort コマンドを使用ました。

手法

「ランダムな文字列 10万件を sort するのにかかる時間」を、LANG を切り替えて計測することで比較しました。

まず、並べ替え対象となるランダムな文字列を10万件生成し、ファイルに保存しておきます。
※Vit-Symtyさんの記事「ランダム文字列をたくさん生成する」を参考にしました。

$ cat /dev/urandom | tr -dc 'a-zA-Z0-9' | fold -w 16 | head -n 100000 > ./a.a

cf. ランダム文字列をたくさん生成する / Vit-Symty

で、ファイルの中身を sort コマンドで並べ替え、その時間を計測します。
その際、事前に環境変数 LANG を C ならびに en_US.UTF-8 に設定しておきます。
つまり以下のようなことをします。

$ LANG=C export LANG
$ /bin/cat ./a.a | /usr/bin/time /bin/sort >/dev/null
$ LANG=en_US.UTF-8 export LANG
$ /bin/cat ./a.a | /usr/bin/time /bin/sort >/dev/null

並べ替えの結果は標準出力に出ます。
並べ替えにかかった時間の計測結果(＝timeコマンドの出力)は、標準エラー出力に出ます。
ここでは並べ替えにかかった時間のデータが欲しいので、標準出力は /dev/null に捨てています。

これを繰り返し実行し、データを採取します。

結果

各試行の結果から、処理終了までにかかった時間(＝elapse)の平均を出しました。サンプル数 N=30 です。

locale	平均時間[sec]	標準偏差
C	0.2028	0.0103
en_US.UTF-8	0.8831	0.0191

LANG=en_US.UTF-8 sortで平均 0.88秒かかる処理が、LANG=C sortでは平均 0.20秒で終了しました。

time コマンドではほかにもいろいろな情報がとれます。比較して差の大きかった項目をも併せてグラフにしました。
※グラフの作成には LibreOffice を使用しました。

コマンド終了までにかかった user / system/ elapsle の時間:

コマンド実行中の CPU 使用率:

これらを見ると、以下のような傾向が見て取れました。ただしこれは試験環境の特性によるものかもしれません。

• system の時間が、locale を問わずとても小さい。
• CPU 使用率は、locale C の方が高くなる傾向にある。

考察

sort | uniq -c など、順番にあまり意味は無く数の方が大切な場合があります。
そのようなときは、LANG=C 下で sort することで時間を短縮できるでしょう。

CentOS 6 の shell 環境は、標準インストールで LANG=en_US.UTF-8 になるようです。
これをそのまま使用すると、必要のない処理に意図せず貴重な時間を搾取されてしまう恐れがあります。
CentOS 6 のシステム標準 locale は、/etc/sysconfig/i18n で設定します。ここで LANG=C を指定すれば、OS 内の各所で処理を高速化できる可能性があります(未検証)。

もちろん、処によっては locale 処理が重要な意味を持つ場合もあります(ex. アルファベット順の並べ替え、日本語のエラーメッセージ出力、等々)。
その場合は

• プロセスの標準 locale は LANG=C としておく。当該処理の部分だけ適切な LANG を指定し、終わったら C に戻す。

とか、

• 日本語のエラーメッセージが必要なアカウントにだけ、~/.bashrc に LANG=C export LANG と書いておく。

とかすれば、利便性を損なわず locale C の恩恵を享受出来るでしょう。

結論

LANG=C を設定することで、locale 制御のある状態(＝LANG=en_US.UTF-8 sort)と比較して、文字列の並べ替え処理が 1/4 の時間で終わることを確認した。

資料

time コマンドの出力サンプル

$ cat ./a.a | LANG=C time sort >/dev/null
0.09user 0.00system 0:00.22elapsed 44%CPU (0avgtext+0avgdata 7128maxresident)k
0inputs+0outputs (0major+1832minor)pagefaults 0swaps
$

$ cat ./a.a | LANG=en_US.UTF-8 time sort >/dev/null
0.35user 0.00system 0:00.84elapsed 42%CPU (0avgtext+0avgdata 7260maxresident)k
0inputs+0outputs (0major+1864minor)pagefaults 0swaps
$

データ採取に使用したスクリプト

以下のスクリプトを実行した後、適当な時間放置し、Ctrl-C で停止しました。

#!/bin/sh

while /bin/true
do
    /bin/sleep 1
    LANG=C export LANG
    /bin/cat ./a.a | /usr/bin/time /bin/sort >/dev/null 2>>C.out

    /bin/sleep 1
    LANG=en_US.UTF-8 export LANG
    /bin/cat ./a.a | /usr/bin/time /bin/sort >/dev/null 2>>en_US.UTF-8.out
done

並べ替え処理の間に 1秒間の sleep を挟んであります。先行実施した並べ替え処理が、後の並べ替え処理に影響を及ぼさないように意図したものですが、おまじないかもしれません。

結果はそれぞれファイル C.out、en_US.UTF-8.out に溜まっているので、適当に加工してデータを抽出しました。

抽出には以下のスクリプトを使用しました。

sed -e 's/[^0-9\.]/ /g' | \
awk -v 'ORS=' '
BEGIN {
    print "user system : elapsed %CPU avgtext avgdata maxresident inputs outputs pf-major pf-minor swaps\n";
}
{ sub(/[\n\r]*$/, " "); print; getline; print; print "\n"; }
'

• 数字以外の文字を SPC に置き換える。
• 1回の試行でレコードが2行出来るので、それを1行にまとめる。
• 出力の1行目に、各項目のタイトルを出力する。

ということをしています。
出力は 1行1レコード、SPC 区切りになります。
LibreOffice Calc に貼り付けて取り込み、グラフにしました。

参考文献

• ロケール（locale）まとめ / aosho235, 2017 http://qiita.com/aosho235/items/58e2e7acd5c2ee3641ff
• ランダム文字列をたくさん生成する / Vit-Symty, 2014 http://qiita.com/Vit-Symty/items/5be5326c9db9de755184
• ASCII文字コード / IT用語辞典 e-Words http://e-words.jp/p/r-ascii.html