Best way to sum an array?

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

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% + --` [download] Read more... (1030 Bytes) 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.	[reply] [d/l] [select]
Re^2: Best way to sum an array? by LanX (Saint) on May 24, 2017 at 18:14 UTC
> as I had to disable warnings on deep recursion and as the array gets longer it really blows up... FWIW tailcall with `goto` `&sub` Read more... (2 kB) 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 +% --` [download] 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!}	[reply] [d/l] [select]
Re^2: Best way to sum an array? by Anonymous Monk on May 24, 2017 at 15:55 UTC
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	[reply]
Re^3: Best way to sum an array? by tobyink (Canon) on May 24, 2017 at 17:12 UTC
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.	[reply]
Re^3: Best way to sum an array? by BillKSmith (Monsignor) on May 24, 2017 at 17:59 UTC
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	[reply]
Re^2: Best way to sum an array? by LanX (Saint) on May 25, 2017 at 14:21 UTC
> 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! Read more... (2 kB) Cheers Rolf _{(addicted to the Perl Programming Language and ☆☆☆☆ :) Je suis Charlie!}	[reply] [d/l] [select]
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	[reply]
Re^2: Best way to sum an array? by Anonymous Monk on May 24, 2017 at 15:43 UTC
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	[reply]
Re^3: Best way to sum an array? by karlgoethebier (Abbot) on May 24, 2017 at 15:48 UTC
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	[reply]
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; # your code here printf "Took %.3f seconds\n", time - $start;` [download] For deeper insights see Devel::NYTProf Good advice was given above. Regards, Karl �The Crux of the Biscuit is the Apostrophe� Furthermore I consider that Donald Trump must be impeached as soon as possible	[reply] [d/l]
Re: Best way to sum an array? by thanos1983 (Parson) on May 24, 2017 at 15:59 UTC
Hello Anonymous Monk I assume you want to measure based on speed, then your friend is Benchmark. But there are also alternatives ways to do it, take a look here (How can I add all the numbers in an array with out doing a foreach loop?). Seeking for Perl wisdom...on the process of learning...not there...yet!	[reply] [d/l]
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...	[reply]
Re^2: Best way to sum an array? by BrowserUk (Patriarch) on May 25, 2017 at 12:43 UTC
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	[reply] [d/l]
Re^3: Best way to sum an array? by hippo (Bishop) on May 25, 2017 at 12:54 UTC
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.	[reply]
Re^4: Best way to sum an array? by BrowserUk (Patriarch) on May 25, 2017 at 15:44 UTC
Re^5: Best way to sum an array? by hippo (Bishop) on May 25, 2017 at 16:08 UTC
Some notes below your chosen depth have not been shown here
Re^4: Best way to sum an array? by LanX (Saint) on May 25, 2017 at 13:01 UTC
Re: Best way to sum an array? by karlgoethebier (Abbot) on May 24, 2017 at 16:12 UTC
See also Re^6: Question on Regex about the output of Benchmark. �The Crux of the Biscuit is the Apostrophe� Furthermore I consider that Donald Trump must be impeached as soon as possible	[reply]
Re: Best way to sum an array? by Anonymous Monk on May 24, 2017 at 16:32 UTC
Also check out the Kahan summation algorithm, implemented in Math::Utils::fsum.	[reply]
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 }` [download]	[reply] [d/l]
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.	[reply]
Re^2: Best way to sum an array? by karlgoethebier (Abbot) on May 24, 2017 at 19:22 UTC
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	[reply]


Perl-Sensitive Sunglasses
	PerlMonks