Perl日記

PerlとかRubyとかPHPとかPythonとか

ベンチマーク・無限ループと再帰呼び出し

ある条件に満たない場合、それを中でもう一度再帰的に呼ぶのがいいのか、
あるいは最初から無限ループにして、条件が満たされたら脱出するのがいいのか、
分からなかったのでベンチマークしてみた。


ただ、サブルーチン呼び出しのコストは高いとどこかで見た気がするので、無限ループの方が早そうではある。

bench.pl
use strict;
use warnings;
use Benchmark qw/ cmpthese timethese /;

my $DEPTH = 50;

cmpthese(timethese(
  100_000,
  {
    recursive => \&recursive,
    infinite_loop => \&infinite_loop,
  },
));

sub recursive {
  my $w = shift || 0;
  if ($w < $DEPTH) {
    $w++;
    recursive($w);
    return;
  }
  else {
    return;
  }
}

sub infinite_loop {
  my $w = 0;
  while (1) {
    $w ||= 0;
    if ($w < $DEPTH) {
      $w++;
      redo;
    }
    else {
      return;
    }
  }
}

なるべくステップが同じになるように書いたつもりだけど。
nextではなくredoなのは、なんとなく。
実行してみる。

$ perl bench.pl
Benchmark: timing 100000 iterations of infinite_loop, recursive...
infinite_loop:  0 wallclock secs ( 1.58 usr +  0.00 sys =  1.58 CPU) @ 63291.14/s (n=100000)
 recursive:  4 wallclock secs ( 3.28 usr +  0.00 sys =  3.28 CPU) @ 30487.80/s (n=100000)
                 Rate     recursive infinite_loop
recursive     30488/s            --          -52%
infinite_loop 63291/s          108%            --

おお。
何回かやってみたが、再帰が無限ループよりも早くなることはなかった。
大体、2倍くらいは早いみたい。(CentOS, DualCore)
(母艦iMacだと2.5倍くらいだった。Core2Duo)
再帰はスタックにどんどん積まれていくからかな?

まとめ

『再帰が書ける自分カッコイイ』と思っていた時期が僕にもありましたが、これからは迷ったら無限ループ→脱出で素直に書くようにしよう。