正規表現においては、/a|b|c/(alteration)は[abc](character class)にすべし、というのは、perlに限らない常識です。

cover
Mastering Regular Expression
Jeffrey E. Friedl
[邦訳: 詳説 正規表現]
qootas.org/blog - perl regex performance
"|"(パイプ)を使った正規表現はめちゃくちゃ遅いから使わないように、ということです。確かにベンチマークを取ると32倍速いです。

どうせならPerl自身が内部で/a|b|c/を[abc]にしてくれたらと思ったことありませんか?

少なくとも、正規表現を仕事で使う人は、原著でも邦訳でもいいからこの「フクロウ本」を手元においておくべきです。邦訳が歌代さんというのもうれしいところで、これなら安心して邦訳も薦められます。

それを踏まえても、なぜか正規表現を自動最適化という話題まではさすがの本書もまだカヴァーしていない。すでにフクロウ本を隅から隅までなめるように読んだという読者も、本entryに注目です。

革命の日々！ perlって正規表現は常にNFAで扱うんだっけ？
うーん｜が遅くなるのってNFA特有の話ですよねぇ。

これはNFAかDFAかというかということだけではなく、alterationでは/foo|bar|baz/も受け入れなければならないので、compileされたコードがどうしても複雑化するということもあります。

/foo|bar|baz/も、よく見るとba[rz]|fooと書き換えることが出来ます。これが正規表現の最適化で、CPANには拙作Regexp::OptimizerおよびRegexp::Trie、そしてRegexp::Assembleなど、これをやってくれるModuleがすでにいくつか存在します。複雑な正規表現は、これらを利用するといいのですが、もしPerlが内部的にこれをやってくれたら、もっとありがたいですよね?

本題の前に、現状把握から。今回はrubyもbenchmarkしているので、いつものperlのbenchmarkの流儀とはちょっと違います。私がrubyにより不慣れということもあったのでrubyの方の流儀に会わせてます。

use strict;
use warnings;
use Benchmark ':all';

my $re_alt    = qr/s|t|u|v|w|x|y|z/;
my $re_cclass = qr/[stuvwxyz]/;
my $alphabets = 'abcdefghijklmnopqrstuvwxyz';
my $digits    = '01234567890123456789012345';

my $ntimes = 100_000;

cmpthese(
    timethese(
        0,
        {
            alt    => sub { $alphabets =~ $re_alt    for ( 1 .. $ntimes ) },
            cclass => sub { $alphabets =~ $re_cclass for ( 1 .. $ntimes ) },
        }
    )
);
cmpthese(
    timethese(
        0,
        {
         alt    => sub { $digits =~ $re_alt    for ( 1 .. $ntimes ) },
         cclass => sub { $digits =~ $re_cclass for ( 1 .. $ntimes ) },
        }
    )
);
perl 5.8.8, Mac OS X v10.4, MacBook Pro 2.0GHz の結果はこんな感じ。 
% perl alt_vs_cclass.pl 
Benchmark: running alt, cclass for at least 3 CPU seconds...
       alt:  4 wallclock secs ( 3.61 usr +  0.01 sys =  3.62 CPU) @  1.10/s (n=4)
    cclass:  3 wallclock secs ( 3.07 usr +  0.01 sys =  3.08 CPU) @ 12.99/s (n=40)
         Rate    alt cclass
alt    1.10/s     --   -91%
cclass 13.0/s  1075%     --
Benchmark: running alt, cclass for at least 3 CPU seconds...
       alt:  4 wallclock secs ( 3.68 usr +  0.02 sys =  3.70 CPU) @  0.81/s (n=3)
            (warning: too few iterations for a reliable count)
    cclass:  3 wallclock secs ( 3.05 usr +  0.01 sys =  3.06 CPU) @ 13.07/s (n=40)
         s/iter    alt cclass
alt        1.23     --   -94%
cclass 7.65e-02  1512%     --

次にruby。うーん、rubyのbenchmarkモジュールって、繰り返し指定してくれんのね。ちょっとださい。でもコードはきれいにかけるね、やっぱ。

require 'benchmark'

re_alt    = Regexp.compile('r/s|t|u|v|w|x|y|z')
re_cclass = Regexp.compile('[stuvwxyz]')
alphabets = 'abcdefghijklmnopqrstuvwxyz'
digits    = '01234567890123456789012345'

ntimes = 100_000;
Benchmark.bm(8) do |x|
    x.report('alt')    { ntimes.times{ re_alt.match(alphabets) } }
    x.report('cclass') { ntimes.times{ re_cclass.match(alphabets) } }
end
Benchmark.bm(8) do |x|
    x.report('alt')    { ntimes.times{ re_alt.match(digits) } }
    x.report('cclass') { ntimes.times{ re_cclass.match(digits) } }
end
rubyのversionは1.8.4。実行環境はperlに同じ。 
              user     system      total        real
alt       0.260000   0.000000   0.260000 (  0.269878)
cclass    0.200000   0.000000   0.200000 (  0.207589)
              user     system      total        real
alt       0.120000   0.000000   0.120000 (  0.124052)
cclass    0.080000   0.000000   0.080000 (  0.080326)

Rubyの方が遅いと言えば遅いですが、alteration|とcharacter classの差は少ないですね。特にmatchが成立する最初のケースでは、倍違わない。

と、ここまでが前ふり。

現在開発中のbleedperlでは、ついにTRIE Optimizationが実装されたのです。

試してみましょう。

% ~/bleedperl/bin/perl5.9.4 alt_vs_cclass.pl   Benchmark: running alt, cclass for at least 3 CPU seconds...
       alt:  4 wallclock secs ( 3.00 usr +  0.01 sys =  3.01 CPU) @  3.99/s (n=12)
    cclass:  4 wallclock secs ( 3.09 usr +  0.01 sys =  3.10 CPU) @ 11.61/s (n=36)
         Rate    alt cclass
alt    3.99/s     --   -66%
cclass 11.6/s   191%     --
Benchmark: running alt, cclass for at least 3 CPU seconds...
       alt:  3 wallclock secs ( 3.02 usr +  0.01 sys =  3.03 CPU) @  8.25/s (n=25)
    cclass:  3 wallclock secs ( 3.04 usr +  0.01 sys =  3.05 CPU) @ 13.11/s (n=40)
         Rate    alt cclass
alt    8.25/s     --   -37%
cclass 13.1/s    59%     --

いかがです?

Dan the Regular Expressionist