XP is just a number PerlMonks

### Best way to sum an array?

 on May 24, 2017 at 15:06 UTC Need Help??

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

How do I pick the "best way" to do something? In particular, I want the fastest way, using the fewest resources, to sum up the values in an array of arbitrary length. I could do it in a loop with a bucket, I could do it recursively, I could do it with a join and an eval, etc. What's the "best" way? Is there a "better" way? How do I measure? How do I pick?
```# Iterative
sub SumArryItr { my \$agg = 0; \$agg += \$_ for @_;  return \$agg }

# Recursive
use feature 'current_sub';
sub SumArryRcs { 1==@_?\$_[0]:1>@_?die:shift(@_)+__SUB__->(@_) }

# Eval Trick
sub SumArryEvl { eval join "+", @_ }

# Test
my @array = ( -249, 0,  74, 65, 80, 72 );
print "Sum: ", join( ", ", @array ), "\n";
print "Itr: ", SumArryItr( @array ), "\n";
print "Rcs: ", SumArryRcs( @array ), "\n";
print "Evl: ", SumArryEvl( @array ), "\n";
merci

Replies are listed 'Best First'.
Re: Best way to sum an array?
by haukex (Archbishop) on May 24, 2017 at 15:45 UTC

List::Util (the XS version) beats them all:

```               Rate  recursive recursive2       eval  iterative   list
+util
recursive    1244/s         --        -4%       -68%       -97%      -
+100%
recursive2   1297/s         4%         --       -67%       -97%      -
+100%
eval         3930/s       216%       203%         --       -91%
+-99%
iterative   42708/s      3332%      3192%       987%         --
+-85%
listutil   281788/s     22544%     21622%      7071%       560%
+  --

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.

> as I had to disable warnings on deep recursion and as the array gets longer it really blows up...

FWIW tailcall with goto &sub

it's also 30% faster than normal recursion

```
Rate recursive recursive2 recursive3      eval iterativ
+e listutil
recursive     184/s        --        -4%       -24%      -46%      -98
+%    -100%
recursive2    192/s        5%         --       -20%      -43%      -98
+%    -100%
recursive3    240/s       31%        25%         --      -29%      -98
+%    -100%
eval          339/s       84%        76%        41%        --      -97
+%    -100%
iterative   10240/s     5472%      5225%      4159%     2923%        -
+-     -95%
listutil   205922/s   111960%    106979%     85548%    60701%     1911
+%       --

I had a version which used \$_[0] instead of aggregating in a closure, but it destroyed the aliased array and made the cmpthese() impossible.

Cheers Rolf
(addicted to the Perl Programming Language and ☆☆☆☆ :)
Je suis Charlie!

Nice. That module does the work in native compiled code, so of course it's fastest. I didn't know about that module. This is clearly best.
#1053
merci

Then you should immediately familiarise yourself with it, and its sister module Scalar::Util. They are two of the most useful modules included in the Perl core.

A module is almost always a good solution, if not the best, for any problem. This is especially true if you consider your own time as one of the resources you want to minimize.
Bill
> 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%
+        --

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!

Cheers Rolf
(addicted to the Perl Programming Language and ☆☆☆☆ :)
Je suis Charlie!

Re: Best way to sum an array?
by karlgoethebier (Abbot) on May 24, 2017 at 15:14 UTC

How do I measure?

«The Crux of the Biscuit is the Apostrophe»

Furthermore I consider that Donald Trump must be impeached as soon as possible

Nice. This gets me the following chart, but I'm not sure I understand what it means.
```         Rate   Evl   Rcs   Itr
Evl  115745/s    --  -84%  -93%
Rcs  729138/s  530%    --  -55%
Itr 1612898/s 1293%  121%    --
```

I think that means the Itr version is an order of magnitude (16x) better than the Rcs version, right? And that the Rcs version is 7 times better than the Evl version. If so, then the answer is clear.
merci

Left column sorted from slow to fast. It shows the number of iterations.

«The Crux of the Biscuit is the Apostrophe»

Furthermore I consider that Donald Trump must be impeached as soon as possible

Re: Best way to sum an array?
by karlgoethebier (Abbot) on May 24, 2017 at 16:01 UTC

Or just say:

```use Time::HiRes qw( time );

my \$start = time;

printf "Took %.3f seconds\n", time - \$start;

For deeper insights see Devel::NYTProf

Regards, Karl

«The Crux of the Biscuit is the Apostrophe»

Furthermore I consider that Donald Trump must be impeached as soon as possible

Re: Best way to sum an array?
by thanos1983 (Parson) on May 24, 2017 at 15:59 UTC
Re: Best way to sum an array?
by vrk (Chaplain) on May 25, 2017 at 12:34 UTC

There's a great discussion about summation algorithms in Accuracy and Stability of Numerical Algorithms by Nicholas Higham (2002), chapter 4. The focus is naturally on numerical accuracy, but there are lots of ideas and references for recursive, parallel and distributed summation algorithms. Or have a look at some of the CUDA resources by nVidia on speedy summation algorithms on GPUs.

I would say you really don't need to worry about either speed or accuracy of summation in "normal" circumstances. It becomes an issue only in a few special cases: 1) very large volumes of data (say array size of gigabytes or terabytes) typical in supercomputing and high-performance scientific or financial computing; 2) very strict numerical accuracy requirements (accuracy and speed are often opposites); 3) very resource limited computing environment (like a microcontroller). Of course, if you're summing four billion floating point numbers subject to relative error of the order of machine epsilon on a microcontroller, then you need to worry about these things...

I would say you really don't need to worry about either speed or accuracy of summation in "normal" circumstances.

Often the question "Which is the fastest way" can be translated into "The way I doing it now is really slow; how can I improve it."

With List::Util::sum() running 100x faster than the best pure perl equivalent, why wouldn't you use it even if you don't need the speed; and for some of the methods attempted by beginners and even experienced programmers new to Perl -- eg. the recursive solution in the OP -- sum() can be almost 1000 times faster. Perl sucks at recursion.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
In the absence of evidence, opinion is indistinguishable from prejudice. Suck that fhit
With List::Util::sum() running 100x faster than the best pure perl equivalent, why wouldn't you use it even if you don't need the speed

It's a good question. The only answer which springs to mind is that you want to avoid loading List::Util in the first place because:

• You're in a constrained environment and don't have the RAM to spare
• You are actually concerned about speed but it's faster to run a short script without loading List::Util if the arrays being summed are tiny
• You are in some environment where XS isn't feasible so you're stuck with the PP version (although this still isn't really a reason not to use it on its own)

They are all edge cases anyway. And of course if you are one of the 99% who do have enough RAM etc. to load List::Util you get all the other good stuff in that module other than sum() essentially for free.

In summary: yes, I'd use it everywhere unless there's a demonstrable penalty.

Re: Best way to sum an array?
by karlgoethebier (Abbot) on May 24, 2017 at 16:12 UTC

«The Crux of the Biscuit is the Apostrophe»

Furthermore I consider that Donald Trump must be impeached as soon as possible

Re: Best way to sum an array?
by Anonymous Monk on May 24, 2017 at 16:32 UTC
Re: Best way to sum an array?
by Anonymous Monk on May 24, 2017 at 15:21 UTC
That recursive sub is ugly. Could be cleaner:
```sub SumArryRcs { @_ ? shift(@_) + __SUB__->(@_) : 0 }
Re: Best way to sum an array?
by Anonymous Monk on May 24, 2017 at 17:35 UTC
'How do I pick the "best way" to do something?'

You wait until it becomes a problem. No really, this isn't a zombie invasion. Your need is part of some greater need, and that is you what you focus on. When the time comes to optimize, you Benchmark your candidates because THEN AND ONLY THEN will you have a concrete reason. Everything else is theoretical and probably will be rendered MOOT when reality rears its head at a much later date.

I'm working on Acme::GlasgowKiss.

«The Crux of the Biscuit is the Apostrophe»

Furthermore I consider that Donald Trump must be impeached as soon as possible

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://1191095]
Approved by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others having an uproarious good time at the Monastery: (8)
As of 2024-04-18 16:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found