改行区切りのテキストレコードを舐めて、特定の形式に当てはまるものを除外するツールが欲しくなった。形式の判定には正規表現が使えそうだった。
Unix環境で動かすなら、既存のテキストフィルタを使えばよい。だが残念なことに動作環境はWindowsで、しかもスクリプトではなく単体で動作する実行ファイルに仕立て上げる必要があった。
そこで、初めてC++11の正規表現ライブラリを使って、即席のツールを書いた。
で、ふと思ったのだが、Unix環境では、標準のテキストフィルタとCやC++で正規表現ライブラリを使って作った即席のツールでは、どちらが高速なのだろうか？
grep(1)などのテキストフィルタは高速に動作するように実装されているはずなので、素人が何も考えずにCやC++で作ったツールより速そうだが、実際はどんな感じなのか、ちょっと実験してみた。
テスト条件
実験はUbuntu 16.04.1 LTS 64bitで行った。テキストフィルタはUbuntuのリポジトリから入れた（もしくはインストール時に入ってきた）ものを使った。
UbuntuはMSI A78M-E35 V2（AMD A78）にAMD A6 7400K BEを載せた自作PCで動かしている。メモリはADATA AX3U2133W8G10-DR（PC3-17000 DDR3-2133）8GB×2枚の16GB。Ubuntu本体はSanDisk SDSSDA-120G-J25Cにインストールしているが、/homeは旧式の2.5インチHDDであるHITACHI HTS545050B9A300に配置している。テストもSSDではなくHDD上で実施している。最近のPCとしては、どちらかと言えば低スペックに該当する環境だろう。
#!/usr/bin/env ruby t = ("0".."9").to_a + ("A".."Z").to_a + ("a".."z").to_a 10000000.times do puts t.join t.rotate! end
次のような内容の62文字のテキストが1000万行。
0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz 123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0 23456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01 3456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz012 456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123 56789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234 6789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz012345 789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456 89ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01234567 9ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz012345678 ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789 BCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789A CDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789AB
およそ630MBのテキストファイルがキャッシュに載っている状態で実験した。
次のような内容の正規表現にマッチした行を取り除くことにした。
^ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789$
今考えると、あまりよくない内容の正規表現だと思うのだが、結果として意外な知見が得られた（気がする）。
よくあるテキストフィルタの場合
トップバッターはGNU grep 2.25。grep(1)にはマッチしなかった行を出力するオプション-vがあるので、それを使う。ついでに行マッチ用のオプション-xなんてのもあったので、使ってみた。
#!/bin/sh export LC_ALL=C LANG=C exec grep -v -x 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789' ${@+"$@"}
で、実験。本来は/dev/nullにリダイレクトするべきなのだろうが、正しくマッチしているか簡易判定するために、wc(1)で行数をカウントしている。
$ time sh grep/filter <data.txt | wc -l 9838709 real 0m1.122s user 0m1.228s sys 0m0.588s $ _
速い！ grep(1)はよく使われるツールなので、この値を基準とする。
次はGNU sed 4.2.2。そのものズバリなコマンドdを使い、マッチした行を削除すればよい。
#!/bin/sh export LC_ALL=C LANG=C exec sed '/^ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789$/d' ${@+"$@"}
$ time sh sed/filter <data.txt | wc -l 9838709 real 0m3.565s user 0m3.428s sys 0m0.784s $ _
ふむ、grep(1)の3倍ちょっと遅いようだ。
最後にmawk 1.3.3。GNU awkでない点がどれだけ影響するか？
#!/bin/sh export LC_ALL=C LANG=C exec awk '$0 !~ /^ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789$/' ${@+"$@"}
$ time sh awk/filter <data.txt | wc -l 9838709 real 0m2.022s user 0m1.688s sys 0m0.868s $ _
C言語の場合
Unix環境なので、POSIXのregex(3)とgetline(3)を使うことにする。コンパイラはgcc 5.4.0だ。
#ifdef __linux__ # ifndef _POSIX_C_SOURCE # define _POSIX_C_SOURCE 200809L # endif /* ndef _POSIX_C_SOURCE */ #endif /* def __linux__ */ #ifdef __FreeBSD__ # define _WITH_GETLINE #endif /* def __FreeBSD__ */ #include <assert.h> #include <stdio.h> #include <stdlib.h> #include <sys/types.h> #include <regex.h> /* ---------------------------------------------------------------------- */ /* */ /* ---------------------------------------------------------------------- */ static void regex_perror(regex_t * const re, const int errcode) { size_t len; char *msg; assert(re != NULL); if (errcode == 0) { return; /* No error */ } len = regerror(errcode, re, NULL, 0); if (len == 0) { return; /* XXX */ } msg = malloc(len); if (msg == NULL) { return; /* XXX */ } if (regerror(errcode, re, msg, len) > 0) { (void) fprintf(stderr, "%s\n", msg); } free(msg); } /* ---------------------------------------------------------------------- */ /* */ /* ---------------------------------------------------------------------- */ int main(int argc, char *argv[]) { int errcode; regex_t regex; char *line; size_t len; errcode = regcomp(®ex, "^ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789$", REG_EXTENDED | REG_NEWLINE | REG_NOSUB); if (errcode != 0) { regex_perror(®ex, errcode); return EXIT_FAILURE; } line = NULL; len = 0; while (getline(&line, &len, stdin) != -1) { if (regexec(®ex, line, 0, NULL, 0) != 0) { (void) fputs(line, stdout); } } free(line); regfree(®ex); return EXIT_SUCCESS; }
では、いざ実験。
$ time c/filter <data.txt | wc -l 9838709 real 0m3.466s user 0m3.340s sys 0m0.768s $ _
ちょっと遅い。GNU sed版のテキストフィルタと100msecほどしか違わない。
どこがボトルネックだろうか？ 思いつくポイントは入出力か正規表現エンジンぐらいだが、入力部のgetline(3)は十分高速だろうから、正規表現エンジンを疑ってみる。
試しにregex(3)ではなくstrcmp(3)を使った版を作成して、再実験。
#ifdef __linux__ # ifndef _POSIX_C_SOURCE # define _POSIX_C_SOURCE 200809L # endif /* ndef _POSIX_C_SOURCE */ #endif /* def __linux__ */ #ifdef __FreeBSD__ # define _WITH_GETLINE #endif /* def __FreeBSD__ */ #include <stdio.h> #include <stdlib.h> #include <string.h> /* ---------------------------------------------------------------------- */ /* */ /* ---------------------------------------------------------------------- */ int main(int argc, char *argv[]) { char *line = NULL; size_t len = 0; while (getline(&line, &len, stdin) != -1) { if (strcmp(line, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n") != 0) { (void) fputs(line, stdout); } } free(line); return EXIT_SUCCESS; }
$ time c/filter_strcmp <data.txt | wc -l 9838709 real 0m1.406s user 0m1.356s sys 0m0.800s $ _
元コードの半分以下の時間で済んだ。
grep(1)との速度差は、純粋な正規表現エンジンの性能差によるものなのか、それともテキストフィルタによっては正規表現の内容次第でstrcmp(3)での比較と同等の処理に切り替えたりするものなのか、気になるところだ。入出力の足回りも工夫されているかもしれない。
なお蛇足だが、regex(3)はビルド済みのライブラリとして提供されているので、コンパイラの最適化オプションは（純粋なregex(3)による処理部分に関しては）効果がない。
先に挙げたのは最適化なしバイナリでの計測結果だったので、同じgccにて-O3でビルドしたバイナリでの計測結果：
$ time c/filter_o3 <data.txt | wc -l 9838709 real 0m3.610s user 0m3.660s sys 0m0.636s $ _
最適化なしの場合とほぼ同じ。むしろ100msecちょっと遅くなった？
C++の場合
C言語版ではPOSIX由来の機能を使ったが、C++では標準ライブラリの範囲内で賄える。そこで、ひとまずC++11の範囲内で実装してみた。なおコンパイラはg++ 5.4.0だ。
#include <iostream> #include <regex> #include <string> int main() { static const std::regex re("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"); std::string line; while (std::getline(std::cin, line)) { if (!std::regex_match(line, re)) { std::cout << line << std::endl; } } }
いざ実験。
$ time cpp/filter <data.txt | wc -l 9838709 real 1m9.467s user 1m3.700s sys 0m35.220s $ _
遅い！ なんか一気に遅くなったぞ。なせだ？
試しに入力をPOSIXのgetline(3)に差し替えてみた。
#ifdef __linux__ # ifndef _POSIX_C_SOURCE # define _POSIX_C_SOURCE 200809L # endif /* ndef _POSIX_C_SOURCE */ #endif /* def __linux__ */ #ifdef __FreeBSD__ # define _WITH_GETLINE #endif /* def __FreeBSD__ */ #include <cstdio> #include <iostream> #include <regex> int main() { static const std::regex re("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"); char *line = NULL; size_t len = 0; while (getline(&line, &len, stdin) != -1) { if (!std::regex_match(line, re)) { std::cout << line; } } free(line); }
気を取り直して再実験。
$ time cpp/filter_getline <data.txt | wc -l 9838709 real 0m26.366s user 0m26.032s sys 0m0.964s $ _
40秒ちょっと短縮された。入力部分の見直しは効果があるようだ。が、それでもまだまだ結構遅い。
Ubuntu付属のg++を使っているのだが、付属の正規表現ライブラリの性能はこんなものなのか、それともまだ調整不足（なのでバージョンアップすると改善されるもの）なのか……？
std::regexは十中八九テンプレートライブラリとして提供されているので、POSIXのregex(3)とは異なり、最適化オプションは効果がある。
POSIXのgetline(3)に差し替えた版の「26秒ちょっと」という結果は、最適化なしで計測したものだ。試しに-O3でビルドした場合は：
$ time cpp/filter_getline_o3 <data.txt | wc -l 9838709 real 0m6.509s user 0m6.360s sys 0m0.812s $ _
20秒も短縮された！ すごい効果だ。まあ、正規表現を定数で渡しているので、正規表現のコンパイルまで含めてビルド時に処理されている可能性も否定できないのかもしれない。
では、元バージョンを-O3でビルドするとどうなるか？
$ time cpp/filter_o3 <data.txt | wc -l 9838709 real 0m48.178s user 0m41.868s sys 0m36.912s $ _
短縮された時間は20秒……。
少なくともstd::regexは最適化オプションが効くようだが、std::getlineにはあまり効果がないようだ。
flexを使った場合
ここまで実験した範囲では、下手にCやC++で実装するよりも、テキストフィルタを使った方がよさそうな雰囲気だ。実装が楽な上に、動作も高速だ。
ところで、POSIXのregex(3)やC++のstd::regexを使う場合、実行時に正規表現のコンパイルが発生する。コンパイルが1回だけなら影響は少なそうだが、実行時に何度もコンパイルされるケースでは、実行速度に無視できない影響がでることもあるようだ。
では、実行時ではなく、予め準備しておいたらどうか？
――ということで、本日のダークホース、flex 2.6.0の登場である。
%{ #include <stdio.h> #include <stdlib.h> %} REGEX ^ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n %% {REGEX} %% int yywrap(void) { return 1; } int main(void) { yylex(); return EXIT_SUCCESS; }
frex(1)が吐き出すソース次第だが、どうか？
$ time flex/filter <data.txt | wc -l 9838709 real 0m26.838s user 0m26.284s sys 0m0.936s $ _
うーん、遅い。
frex(1)が吐き出したソースには字句解析器のコードがガッツリ書かれているので、吐き出されたソースへの最適化オプションの適用は、それなりに効果がある。
試しに-O3でビルドした場合の計測結果：
$ time flex/filter_o3 <data.txt | wc -l 9838709 real 0m17.869s user 0m17.772s sys 0m0.660s $ _
9秒ほど速くなった。とはいえC++のstd::regexほどには、最適化オプション付与による効果は得られないようだ。
入力部分などを色々弄れば改善できるかもしれないが、肝心の弄り方がよく分からない。
結論
環境次第であるとは思うが、最近のUnixユーザランドで作業するのなら、テキストフィルタは十分に高速だ。なので、安心して素直にテキストフィルタを使っておけば、大抵は問題ない。
POSIXのregex(3)は、素の状態でそこそこ高速なようだが、regex(3)そのものを高速化することは難しい。C++11のstd::regexは、（少なくともgcc付属のものは）最適化オプションの併用を検討した方がよさそうだ。
あえてCやC++で正規表現する場合は、正規表現エンジンよりも先に、入出力のコストに注意を払うほうがよいだろう。
flex(1)は……字句解析器が欲しくなるようなケースで使うべき（≒他のケースでは、少なくとも性能面のメリットはない）かな？
