Re^2: Best way to sum an array?

> The recursive approach is not a good solution, as I had to disable warnings on deep recursion and as the array gets longer it really blows up... only for short arrays does it outperform the eval version.

The beauty of recursions come into play if you can split into several branches.

Deep recursion becomes very unlikely and eval is outperformed.

Perl Version: 5.016003
Array Length: 10000
Expected result: 50005000
              Rate recursive recursive3       eval rec_split iterative
+  listutil
recursive   7.44/s        --       -19%       -89%      -91%     -100%
+     -100%
recursive3  9.16/s       23%         --       -86%      -89%     -100%
+     -100%
eval        67.6/s      808%       638%         --      -19%      -97%
+     -100%
rec_split   83.8/s     1026%       815%        24%        --      -96%
+     -100%
iterative   2145/s    28722%     23322%      3073%     2461%        --
+      -94%
listutil   36669/s   492642%    400327%     54142%    43678%     1610%
+        --
[download]

Even that the total number of additions is still the same, this shows how sub-calls and copying arrays are braking in Perl.

There is still room for more tuning:

don't copy arrays just indices
replace sub-calls with goto's/loop constructs and a result-stack
replace division by 2 with bit-shift

But of course it's impossible to achieve the performance of the C version in this particular case!

use warnings;
use strict;
use Benchmark qw/cmpthese/;
use List::Util::XS;
use List::Util qw/sum/;

my @array = 1.. 10000;
my $expect = sum(@array);

{
   use feature 'current_sub';
   no warnings 'recursion';
   sub SumArryRcs
     {
        1==@_?$_[0]:1>@_?die:shift(@_)+__SUB__->(@_);
     }
   sub SumArryRcs2
     {
        @_ ? shift(@_) + __SUB__->(@_) : 0;
     }

}


{
   my $agg = 0;
   sub SumArryRcs3 {
      if (@_) {
         $agg += pop;
         goto &SumArryRcs3
      } else {
         my $res = $agg;
         $agg = 0;                      # reset
         return $res;
      }
   }
}


sub SumArrySplit {
   if (@_ >2) {
      return
        SumArrySplit( @_[ 0 .. $#_/2 ] )
          +SumArrySplit(@_[ $#_/2+1 .. $#_ ] );
   } elsif (@_ == 2) {
      return $_[0]+$_[1]
   } else {
      return $_[0];
   }
}



# warn SumArryRcs3(@array);
# warn SumArrySplit(@array);

warn "Perl Version: $]\n";
warn "Array Length: ", scalar @array,"\n";
warn "Expected result: $expect\n";

#__END__


cmpthese(-1, {
              iterative => sub {
                 my $agg = 0;
                 $agg += $_ for @array;
                 $agg == $expect or die;
              },
              recursive =>
              sub { SumArryRcs(@array) == $expect or die },

              # recursive2 =>
              # sub { SumArryRcs2(@array) == $expect or die },

              recursive3 =>
              sub { SumArryRcs3(@array) == $expect or die },

              rec_split =>
              sub { SumArrySplit(@array) == $expect or die },


              eval =>
              sub { eval(join "+", @array) == $expect or die },
              listutil =>
              sub { sum(@array) == $expect or die },
             }
        );
[download]

Cheers Rolf
_{(addicted to the Perl Programming Language and ☆☆☆☆ :)

Je suis Charlie!}

Comment on Re^2: Best way to sum an array? Select or Download Code