先読みとautovivificationの話，あるいはマイクロオプティマイゼーションの話

Perlの話です．~~が，先読みの辺りはどの言語でも共通なのでは，という感じです．~~

追記

なんか先読み関係ない感じになってるのでコメント見ると良いです．この記事の情報は誤っているので後で書き直す．

ここから先は読まなくても良い

さて，配列を走査するような処理を書く時，「1個後のアイテムと現在のアイテムを比較したい」というようなニーズから，1個後のアイテムを読んでおきたいというような事があると思います．

ナイーブに実装するとしたら以下のようになるでしょう (C-Style Loopで書いている理由は以降の比較のためなので深く考えないで下さい)．

my @array = (1..100);
for (my $i = 0; my $item = $array[$i]; $i++) {
    my $next_item = $array[$i+1];
    # do something...
}

このコードは，先読みした値を変数に格納しておいて，それを使いまわすというような効率的な書き方に変形する事が出来ます．

my @array = (1..100);
for (my $i = 0, my $next_item; my $item = $next_item || $array[$i]; $i++) {
    $next_item = $array[$i+1];
    # do something...
}

さてこの両者でベンチマークを取ってみると以下の様な感じになります．

use Benchmarks sub {
    my @array = (1..100);

    my $normal = sub {
        for (my $i = 0; my $item = $array[$i]; $i++) {
            my $next_item = $array[$i+1];
            # do something...
        }
    };

    my $read_ahead = sub {
        for (my $i = 0, my $next_item; my $item = $next_item || $array[$i]; $i++) {
            $next_item = $array[$i+1];
            # do something...
        }
    };

    +{
        normal     => $normal,
        read_ahead => $read_ahead,
    };
};
__END__
              Rate     normal read_ahead
normal     39711/s         --       -25%
read_ahead 52609/s        32%         --

速いですね！　めでたしめでたし！

めでたくない場合

しかしながら走査するオブジェクトの構造が変わるとそうは問屋がおろしません．
以下の様なコードの場合を考えてみましょう．

use Data::Faker;
my $faker = Data::Faker->new;
my @array;
for (1..100) {
    push @array, +{
        name => $faker->name,
        age  => int rand(80),
    };
}

for (my $i = 0, my $next_item; my $item = $next_item || $array[$i]; $i++) {
    $next_item = $array[$i+1];
    $next_item->{name};
}

このコードは永遠に終わりません．無限ループします．

このコードで配列の最後の要素にアクセスしている時，$next_itemはundefとなりますが，このundefに対してハッシュリファレンスのようにアクセスすると，undefは{}という風に空のハッシュリファレンスに変化してしまいます (もちろん配列リファレンスで同じようなことを行なった場合も同様です)．以下の様な感じ．

my $foo = undef;
$foo->{not_exists}; # <= この時点で$fooは{}になっている！

Perlでは空のハッシュリファレンスは真値であるので，論理和の評価は空ハッシュである$next_itemが返ってきてしまい，for文の条件が常に真として扱われてしまい無限ループしてしまうという訳ですね．

このように，走査対象の配列の中身がハッシュリファレンスで，なおかつ1個次の要素を見る必要がある場合，上手くいかずにハマる場合があるわけです．

そこで我々はどうすべきか

1. ローカル変数を1個作って，そこに$next_itemをコピーしてそっちにアクセスする

for (my $i = 0, my $next_item; my $item = $next_item || $array[$i]; $i++) {
    $next_item = $array[$i+1];
    my $_next_item = $next_item;
                                                                            
    # do something...
    $_next_item->{name};
}

このようにすると無限ループは起きないものの……

use Data::Faker;
use Benchmarks sub {
    my $faker = Data::Faker->new;
    my @array;
    for (1..100) {
        push @array, +{
            name => $faker->name,
            age  => int rand(80),
        };
    }

    my $normal = sub {
        for (my $i = 0; my $item = $array[$i]; $i++) {
            my $next_item = $array[$i+1];

            # do something...
            $next_item->{name};
        }
    };

    my $read_ahead = sub {
        for (my $i = 0, my $next_item; my $item = $next_item || $array[$i]; $i++) {
            $next_item = $array[$i+1];
            my $_next_item = $next_item;

            # do something...
            $_next_item->{name};
        }
    };

    +{
        normal     => $normal,
        read_ahead => $read_ahead,
    };
};
__END__
              Rate read_ahead     normal
read_ahead 19855/s         --       -11%
normal     22399/s        13%         --

先読みしたほうが遅い！！！！　意味無いじゃん！！！！
……まあそりゃそうですよねという感じ．

2. no autovivificationする

undefに->{something}や->[42]のようにアクセスするとそれぞれ空の{}や[]という風になってしまうのが問題なので，その挙動を潰してやれば良い！

ということでautovivificationの出番です．
https://metacpan.org/pod/autovivification

no autovivificationという風に宣言してやると，そのレキシカルスコープでvivification，つまりundefを自動で空のハッシュリファレンスや配列リファレンスに変換する処理を無効にすることが出来ます．

no autovivification;
for (my $i = 0, my $next_item; my $item = $next_item || $array[$i]; $i++) {
    $next_item = $array[$i+1];
    # do something...
    $next_item->{name}; # <= ここでundefが変換されない！
}

ベンチマークの結果は以下のとおり

no autovivification;
use Data::Faker;
use Benchmarks sub {
    my $faker = Data::Faker->new;
    my @array;
    for (1..100) {
        push @array, +{
            name => $faker->name,
            age  => int rand(80),
        };
    }

    my $normal = sub {
        for (my $i = 0; my $item = $array[$i]; $i++) {
            my $next_item = $array[$i+1];
            # do something...
        }
    };

    my $read_ahead = sub {
        for (my $i = 0, my $next_item; my $item = $next_item || $array[$i]; $i++) {
            $next_item = $array[$i+1];
            # do something...
        }
    };

    +{
        normal     => $normal,
        read_ahead => $read_ahead,
    };
};
__END__
              Rate     normal read_ahead
normal     36885/s         --       -18%
read_ahead 44776/s        21%         --

おっ，速い！

まとめ

undefにリファレンスアクセスするといつの間にかundefが別のものになる
うかつに先読みしない
とは言え先読みしたい，なおかつ少しでもパフォーマンスが気になる場合はno autovivificationを使うのが良いのでは無いか．

という感じです

その手の平は尻もつかめるさ

ギジュツ的な事をメーンで書く予定です