Re: array pre-allocation trick

in reply to Re: array pre-allocation trick
in thread array pre-allocation trick

Your benchmark is utterly flawed. You aren't measuring what you think you are measuring.

The arrays @empty and @prealloc are lexical. This means, they are known in the file, and only in the file. They cannot be accessed from Benchmark.pm. After all, you are passing in a string, not a coderef. The @empty and @prealloc in the passed strings will be evalled (in the main package) and will hence be package variables (as they aren't my'ed).
@::empty just grows and grows. Meaning you need the allocate more and more memory. Of course it will be slower! It will be enlightening to print the sizes of @::empty and @::prealloc after the benchmark was run.
You aren't measuring the influence of the pre-allocation at all. Except for the very first run of "assign", the @::empty array will contain at least $::size elements.
(q{data} x $::size) returns a single string, even in list context. This explains why "slice" appears to be much faster with strings than with numerals. The slice shouldn't be a win as you state, because that forces Perl to build two relatively large lists.

The following benchmark suggest that preallocating is actually a tad bit slower, and that using slices loses. Assigning is a little faster than pushing.

#!/usr/bin/perl
 
use strict;
use warnings;

use Benchmark qw /cmpthese timethese/;
    
our $size = 100_000;
    
cmpthese timethese (-10 =>  {
    push      =>  'my @arr; push @arr => $_ for 0 .. $::size - 1',
    assign    =>  'my @arr; $arr [$_] =  $_ for 0 .. $::size - 1',
    assignpre =>  'my @arr; $#arr = $::size - 1;
                            $arr [$_] =  $_ for 0 .. $::size - 1', 
    slice     =>  'my @arr; @arr [0 .. $::size - 1] = (0 .. $::size - 
+1)',
    slicepre  =>  'my @arr; $#arr = $::size - 1;
                            @arr [0 .. $::size - 1] = (0 .. $::size - 
+1)',
} => 'none');
__END__
            Rate  slicepre     slice      push assignpre    assign
slicepre  3.82/s        --       -1%      -37%      -40%      -41%   
slice     3.87/s        1%        --      -36%      -39%      -40%
push      6.08/s       59%       57%        --       -4%       -5%  
assignpre 6.36/s       66%       64%        5%        --       -1%
assign    6.44/s       68%       66%        6%        1%        --
[download]

Abigail

Comment on Re: array pre-allocation trick Select or Download Code

Replies are listed 'Best First'.
Re: Re: array pre-allocation trick by Anonymous Monk on Oct 31, 2002 at 16:41 UTC
Thanks everyone for the help. I tried the benchmark Abigail-II did on my machine, with a map thrown in for good measure, and got slightly different results -- strangely, the simple push won! #!/usr/bin/perl use strict; use warnings; use Benchmark qw /cmpthese timethese/; our $size = 100_000; cmpthese timethese (-10 => { push => 'my @arr; push @arr => $_ for 0 .. $::size - 1', map => 'my @arr; @arr = map {$_} (0 .. $::size - 1)', assign => 'my @arr; $arr [$_] = $_ for 0 .. $::size - 1', assignpre => 'my @arr; $#arr = $::size - 1; $arr [$_] = $_ for 0 .. $::size - 1', slice => 'my @arr; @arr [0 .. $::size - 1] = (0 .. $::size - +1)', slicepre => 'my @arr; $#arr = $::size - 1; @arr [0 .. $::size - 1] = (0 .. $::size - +1)', } => 'none'); __END__ Rate map slicepre slice assignpre assign + push map 7.68/s -- -34% -36% -45% -47% + -48% slicepre 11.7/s 52% -- -3% -17% -19% + -21% slice 12.1/s 57% 3% -- -14% -17% + -18% assignpre 14.1/s 83% 20% 16% -- -3% + -5% assign 14.5/s 89% 24% 20% 3% -- + -2% push 14.7/s 92% 26% 22% 5% 2% + -- [download] Here is what I was running: `This is perl, v5.6.1 built for i386-linux Linux cchan.acsys.com 2.4.8-26mdk #1 Sun Sep 23 17:06:39 CEST 2001 i68 +6 unknown` [download]	[reply] [d/l] [select]
Re: array pre-allocation trick by Abigail-II (Bishop) on Nov 01, 2002 at 10:59 UTC
strangely, the simple push won! No need to be so surprised. In both your and my benchmark, the difference between `"push"`, `"assign"` and `"assignpre"` is small, less than 10%. Speed rate differences as reported by Benchmark can differ drasticly not only between versions of Perl, but only if the underlaying OS differs, or the compiler used to compile Perl (even different versions of the same compiler!). That is, a benchmark can give different "winners" for the same test if the OS, Perl version or compiler differs. Abigail	[reply] [d/l] [select]
Re: Re: Re: array pre-allocation trick by BrowserUk (Patriarch) on Oct 31, 2002 at 16:56 UTC
The map in your example serves no purpose other than to slow it down. The `(0 .. $::size-1)` builds a list which is directly assignable to an array. By adding the map in there, you are building a list breaking the list down to feed it to the map element by element the reassembling a new (identical) list before assigning it to the array. Nah! Your thinking of Simon Templar, originally played by Roger Moore and later by Ian Ogilvy	[reply] [d/l]
Re: Re: Re: Re: array pre-allocation trick by Anonymous Monk on Nov 02, 2002 at 00:24 UTC
True the map doesn't do much, but it's a minimal benchmark for Aristotle's suggestion: `my @array = map { do_stuff_with($_); $_ } 1 .. 5000;` [download] I've replaced "do_stuff_with($_)" with a no-op. It didn't perform as well as the others, so that leads me to think I shouldn't pursue using map in this case.	[reply] [d/l]
Re^5: array pre-allocation trick by Aristotle (Chancellor) on Nov 02, 2002 at 06:52 UTC
Short note by Aristotle (Chancellor) on Oct 31, 2002 at 20:00 UTC
You have some newlines and `+`s in your code that suggest you copypasted the automatically linewrapped code from Abigail-II's node. Instead, click on the title of the node, then click the "d/l code" below the text to get at the source as originally formatted. Makeshifts last the longest.	[reply]

In Section Seekers of Perl Wisdom