新・日々録 by TRASH BOX@Eel このページをアンテナに追加 RSSフィード

2016-12-10

正規表現を使ったテキストフィルタとC/C++による自作ツールではどちらが高速か?

改行区切りのテキストレコードを舐めて、特定の形式に当てはまるものを除外するツールが欲しくなった。形式の判定には正規表現が使えそうだった。

Unix環境で動かすなら、既存のテキストフィルタを使えばよい。だが残念なことに動作環境はWindowsで、しかもスクリプトではなく単体で動作する実行ファイルに仕立て上げる必要があった。

そこで、初めてC++11の正規表現ライブラリを使って、即席のツールを書いた。

で、ふと思ったのだが、Unix環境では、標準のテキストフィルタとCやC++正規表現ライブラリを使って作った即席のツールでは、どちらが高速なのだろうか?

grep(1)などのテキストフィルタは高速に動作するように実装されているはずなので、素人が何も考えずにCやC++で作ったツールより速そうだが、実際はどんな感じなのか、ちょっと実験してみた。

テスト条件

実験はUbuntu 16.04.1 LTS 64bitで行った。テキストフィルタUbuntuリポジトリから入れた(もしくはインストール時に入ってきた)ものを使った。

UbuntuMSI 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としては、どちらかと言えば低スペックに該当する環境だろう。

テストデータは、以下のRubyスクリプトで作成した。

#!/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
$ _

grep(1)の2倍弱。sed(1)より高速だ――が、GNU awkだったらそうはいかない気がしないでもない。

C言語の場合

Unix環境なので、POSIXregex(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(&regex,
	                  "^ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789$",
	                  REG_EXTENDED | REG_NEWLINE | REG_NOSUB);
	if (errcode != 0) {
		regex_perror(&regex, errcode);
		return EXIT_FAILURE;
	}

	line = NULL;
	len = 0;

	while (getline(&line, &len, stdin) != -1) {
		if (regexec(&regex, line, 0, NULL, 0) != 0) {
			(void) fputs(line, stdout);
		}
	}

	free(line);
	regfree(&regex);

	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は十中八九テンプレートライブラリとして提供されているので、POSIXregex(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++で実装するよりも、テキストフィルタを使った方がよさそうな雰囲気だ。実装が楽な上に、動作も高速だ。

ところで、POSIXregex(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ユーザランドで作業するのなら、テキストフィルタは十分に高速だ。なので、安心して素直にテキストフィルタを使っておけば、大抵は問題ない。

POSIXregex(3)は、素の状態でそこそこ高速なようだが、regex(3)そのものを高速化することは難しい。C++11のstd::regexは、(少なくともgcc付属のものは)最適化オプションの併用を検討した方がよさそうだ。

あえてCやC++正規表現する場合は、正規表現エンジンよりも先に、入出力のコストに注意を払うほうがよいだろう。

flex(1)は……字句解析器が欲しくなるようなケースで使うべき(≒他のケースでは、少なくとも性能面のメリットはない)かな?

Y.IY.I 2018/04/15 10:27 flex のその使い方には異議を申し立てたいです。あまりにも遅いやりかたです。
高速化を試みました。環境は Debian jessie です。
実行ファイルを 2 個用意しました。

filter0 : 元のままのコード。cc -O3 のみ。
filterf : 最高速で動くように flex 側で調整。

実行結果

$for prog in filter0 filterf ; do time "./$prog" < data.txt | wc -l ; done
9838709

real 0m14.874s
user 0m14.680s
sys 0m0.620s
9838709

real 0m2.708s
user 0m2.500s
sys 0m0.452s
$

filterf.l の内容はこうです。(変更部分のみ)

%}

REGEX ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n
%%
{REGEX}
[^\n]*\n fputs( yytext,stdout);
%%

flex のオプションは -f です。でもやっぱり flex の出番はそこじゃない……

eel3eel3 2018/04/15 17:36 >Y.I さん
ありがとうございます。何となく理解できました。今回の場合、正規表現(REGEXの中身)にマッチしなかった場合の処理を記述するのが肝要なのですね。

マッチしなかった場合の処理を付け加えたコードにて、最適化なしで「real 0m8.936s」、最適化O3で「real 0m3.211s」ぐらいで動作することを確認しました。

なおflexのオプションは -CFr です(manを読む限り -f と同等のはず)。

Y.IY.I 2018/04/16 06:37 ありがとうございます。この記事は大変勉強になります。本当は別の目的でググってたまたまたどりついたのですが。
flex のオプションで -f と同じなのは -Cfr で、 -CFr と同じなのは -F みたいです。
-F はキーワードが多い場合に効果があるそうです。
それから、パターンで ^ を使うと少し遅くなるそうです。
実際に -F でコンパイルした場合、パターンに ^ を使った場合を試してみましたが、あまり差はありませんでした。
やはり、マッチしなかった場合の長さを 1 行にしているのが大幅な高速化になっていると思われます。
マニュアルには書かれていることですが、実際に比べてみたのは初めてです。
そういう意味でも勉強になりました。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/eel3/20161210/1481360920