はじめに

　処理の内容は「任意の文字列について、その文字列を必ず一つの a から始まるようにする」というものです。例として、URL でもいいんですが、その場合だと「URL の末尾は必ず一つのスラッシュで終わっている」ということ。この処理を考えた場合、二つの方法を思いつきました。

case 1

　正規表現式で一行なので高速のはず。0 個以上の文字を 1 個に置き換えるという発想。

• 文字列先頭の連続する 0 個以上の a を、一つの a に置き換える

case 2a

　文字列先頭に a がある場合とない場合を考えて処理を行うタイプ。

• 文字列先頭に a が無ければ、文字列先頭に a を付加する
• 更に、文字列先頭の連続する 2 個以上の a を、一つの a に置き換える

case 2b

　case 2a とほとんど同じだけれど、条件分岐で処理が排他になっているタイプ。

• 文字列先頭に a が無ければ、文字列先頭に a を付加する
• そうでなければ、文字列先頭の連続する 2 個以上の a を、一つの a に置き換える

ベンチマーク プログラム

#!/usr/bin/perl

sub test {
    my ($code, $str) = @_; print $str, ' -> ' , $code->($str), "
";
}

sub case1 {
    my $str = shift;
    # 先頭の 0 個以上の a を一つの a に置き換える
    $str =~ s/^a*/a/;
    $str;
}
test (&case1, 'bc');
test (&case1, 'abc');
test (&case1, 'aaabc');

sub case2a {
    my $str = shift;
    # a で始まっていなければ先頭に a を追加する
    $str = 'a'. $str if $str !~ /^a/;
    # a が二個以上連続していたら一つの a にする
    $str =~ s/^aa+/a/;
    $str;
}
test (&case2a, 'bc');
test (&case2a, 'abc');
test (&case2a, 'aaabc');

sub case2b {
    my $str = shift;
    if ($str !~ /^a/) {
        $str = 'a'. $str
    } else {
        $str =~ s/^aa+/a/;
    }
    $str;
}
test (&case2b, 'bc');
test (&case2b, 'abc');
test (&case2b, 'aaabc');



use Benchmark qw( :all );
cmpthese (1_000_000, {
    case1_0 => qq{ case1 ('bc') },
    case1_1 => qq{ case1 ('abc') },
    case1_2 => qq{ case1 ('aaabc') },
    case2a_0 => qq{ case2a ('bc') },
    case2a_1 => qq{ case2a ('abc') },
    case2a_2 => qq{ case2a ('aaabc') },
    case2b_0 => qq{ case2b ('bc') },
    case2b_1 => qq{ case2b ('abc') },
    case2b_2 => qq{ case2b ('aaabc') },
});

結果

# Intel Core 2 Duo 3.16GHz, Windows XP, ActivePerl 5.8.8
case1_2   830565/s      --
case1_1  1015228/s     22%
case1_0  1031992/s     24%
case2a_0 1102536/s     33%
case2b_0 1184834/s     43%
case2b_2 1231527/s     48%
case2a_2 1333333/s     61%
case2b_1 1560062/s     88%
case2a_1 1776199/s    114%

# Intel Core 2 Duo 2.4GHz, MacBook Pro, Perl 5.10.0
case1_2   781250/s      --
case1_1   787402/s      1%
case1_0   806452/s      3%
case2b_2  813008/s      4%
case2a_2  909091/s     16%
case2a_0  925926/s     19%
case2b_1 1098901/s     41%
case2b_0 1136364/s     45%
case2a_1 1250000/s     60%

　スマートに正規表現式一発で書いた方が速いと予想したものの、反対に、ベタに処理を分岐して書いた方が速いという結果になりました。また、条件分岐をする場合でも、排他処理をして、余計な処理を通らないように工夫した方が、遅いという結果にもなりました。うーん、謎です。
　最近の CPU では、分岐予測やパイプライン処理などの高速化技術が当たり前のように使われていて、分岐予測が失敗した場合、ロールバックするコストの方が高く付いたりすることがあるようです。あくまで機械語レベルでの話だと思うのですが、Perl のようなインタプリタ言語でもこのような機構が働いているのかはわかりません。