最近、文字列検索ライブラリを作成して気づいたのだが、C++ の標準ライブラリ cctype で定義されているグローバルな文字分類関数は、 はっきりいって使ってはいけない。非常に遅いのである。
とにかく、次の実行例を見ていただこう。
% cat ctypetest.cpp
#include <iostream>
#include <cctype>
int main()
{
size_t a = 0;
for (size_t i = 0; i < 1000000000; ++i) {
if (std::isalpha(i & 0xff)) ++a;
}
std::cout << a << std::endl;
}
% g++ -O ctypetest.cpp -o ctypetest
% time ctypetest
203125000
29.430u 0.020s 0:29.72 99.0% 0+0k 0+0io 161pf+0w
一方、従来の C のやり方だと、
% cat ctypetest.c
#include <stdio.h>
#include <ctype.h>
int main()
{
size_t a = 0;
size_t i;
for (i = 0; i < 1000000000; ++i) {
if (isalpha(i & 0xff)) ++a;
}
printf("%d\n", a);
}
% gcc -O ctypetest.c -o ctypetest
% time ctypetest
203125000
3.590u 0.000s 0:03.60 99.7% 0+0k 0+0io 82pf+0w
実に 8 倍以上の開きがある。なぜこんなことになっているのだろうか。
C++ の標準ライブラリでは、国際化対応のために、ロケールに従って ファセットと呼ばれるオブジェクトを生成して、 そいつが持っているメンバ関数を利用することになっている。 で、従来の C で提供されていた isalpha などのマクロは、どうやら、 このファセットのメンバ関数を使用する グローバルな関数として定義されているようなのだ。 かたやマクロを展開したテーブル参照、 かたやグローバルな関数呼び出し。勝負は明らかであろう。
だが、それでも腑に落ちない点がある。文字の分類を扱うファセットは、
ctype というクラステンプレートだ。これは、文字型をパラメータとし、
文字の分類や大文字・小文字変換などを行う仮想メンバ関数を定義している。
ところが、char型を扱う ctype<char> は
ctype テンプレートの特別バージョンであり、分類のためのメンバ関数
is は、インラインで実装されているのだ。
試しに is を使ってみると、
% cat ctypetest.cpp
#include <iostream>
#include <cctype>
class Foo : public std::ctype<char> { };
int main()
{
Foo foo;
size_t a = 0;
for (size_t i = 0; i < 1000000000; ++i) {
if (foo.is(std::ctype_base::alpha, i)) ++a;
}
std::cout << a << std::endl;
}
% g++ -O ctypetest.cpp -o ctypetest
% time ctypetest
203125000
4.620u 0.010s 0:04.62 100.2% 0+0k 0+0io 161pf+0w
このとおり、C 版に迫る速度になっている。
上のコードでは、
std::ctype<char>から派生させたクラスFooを使っているが、これは、std::ctype<char>のデストラクタがprotectedになっているためである。 …でも、VC++ 6.0 では、直接生成できるなあ。これは、VC++ 付属のライブラリの バグ?また、C 版より若干遅いのは、関数 is の戻値が bool になっているためだと思う。 テーブルから参照した整数値を bool に変換するのに時間がかかっているのだろう。 inline で定義されている関数なんだから、コンパイラが がんばって最適化してくれたりしないのかなぁ。
だから、標準ライブラリで定義されている isalpha などのグローバル関数も inline で定義されていればかなり速くなると思うのだが、実体のある関数で 実装しているのは何か理由があってのことだろうか。
ところで、同じコードを VC++ 6.0 でコンパイルして走らせてみた。 実行結果だけを並べる。
TimeThis : Elapsed Time : 00:00:51.053 TimeThis : Elapsed Time : 00:00:31.154 TimeThis : Elapsed Time : 00:00:29.442
先ほどとはマシン環境が異なるので、時間の絶対値には意味がないが、
VC++ では、グローバル関数の isalpha とマクロ展開されたものとの間で、
gcc で得られた結果ほどの差はない。これもまた理由がよくわからないのだが、
isalpah(i&0xff) のところのマクロ展開されたソースを見ると、
(__mb_cur_max > 1
? _isctype((int)(i&0xff),(0x0100|0x1|0x2))
: _pctype[(int)(i&0xff)] & (0x0100|0x1|0x2))
のようになっている。__mb_cur_max > 1 が真となって、結局、
実体のある関数 _isctype を呼び出しているようだ。
これは、変数名からして、
Windows 特有のマルチバイト関係の処理が絡んでいるのかもしれない。
最後に、VC++ で最速だったコードを示しておこう。これは、
ctype<char> が保持している分類テーブルを取得して、
それを直接参照している。
C:\Work>type ctypetest.cpp
#include <iostream>
#include <cctype>
class Foo : public std::ctype<char> {
public:
Foo() : table( classic_table() ) { }
inline int isalpha( unsigned char ch ) const {
return table[ch] & std::ctype_base::alpha;
}
private:
const mask *table;
};
int main()
{
Foo foo;
size_t a = 0;
for (size_t i = 0; i < 1000000000; ++i) {
if (foo.isalpha(i)) ++a;
}
std::cout << a << std::endl;
return 0;
}
C:\Work>cl -O2 foo.cpp -GX -o foo.exe
[略]
C:\Work>timethis foo
[略]
TimeThis : Elapsed Time : 00:00:12.507
初出: 2001年10月25日