Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re: array pre-allocation trick

by BrowserUk (Patriarch)
on Oct 31, 2002 at 07:25 UTC ( [id://209357]=note: print w/replies, xml ) Need Help??


in reply to array pre-allocation trick

The benefits of pre-assignment seem to be marginal at best.

However, the method by which you assign your values to the array is considerable more important. Unfortunately, the best method is not a simple choice either. If you are filling an array with essentially static data, then assignment to an array slice seems to be optimal, but if you need to generate your data in a loop, building a list prior to slice assignment suddenly becomes your worst option. In this case, indexed assignment in a for loop wins hands down with push beating slice assignment (pre-allocated or no) into last place. This appears to be consistant for a wide range of array size from 100, to 100_000 elements. The results below for a arrays of 10_000 elements seem typical.

Of course, this is only part of the story. If your source of data for the array is a very fast process as typified my use of rand below and your arrays large or the re-filling frequent, then the differences could be significant. On the other hand, if the source of the data was an expensive process (RDMS query or similar), then the cost of the assignment becomes insignificant relative to that process and the assignment method should be chosen as that which most closely fits the way in which you aquire the data to put in the array.

If you are receiving the data en-bloc as a list or array then using a slice assignment will probably be a win. If you are getting the values 1 at a time, then indexed assignment is probably best though some algorithms, such as where you don't know how much data you are going to receive, then the simplicity and scalability of push is the natural choice.

One final thing regarding your sample code. You show the array being declared and filled within a subroutine but you don't indicate how you are intending to return this to the calling code. If efficiency is in anyway important, ensuring that you return a reference to the array and not return the array as a list will probably save you more time than any difference you might achieve through pre-allocation or assignment method combined.

Update: Bah! Humbug. Don't

#! perl -sw use vars '$size $cpu'; use strict; use Benchmark 'cmpthese'; $::size ||= 1000; $::cpu ||= 1; my @empty; my @prealloc; $#prealloc = $::size; cmpthese( -$::cpu, { push => 'push @empty, q{data} for 0 .. $::s +ize-1', assign => '$empty[$_] = q{data} for 0 .. $::s +ize-1', assignpre => '$prealloc[$_] = q{data} for 0 .. $::s +ize-1', slice => '@empty[0 .. $::size-1] = (q{data} x $::size)', slicepre => '@prealloc[0 .. $::size-1] = (q{data} x $::size)', }); cmpthese( -1, { push => 'push @empty, rand $::size for +0 .. $::size-1', assign => '$empty[$_] = rand $::size for +0 .. $::size-1', assignpre => '$prealloc[$_] = rand $::size for +0 .. $::size-1', slice => '@empty[0 .. $::size-1] = (map{rand $::size}1 .. + $::size)', slicepre => '@prealloc[0 .. $::size-1] = (map{rand $::size}1..$ +::size)', }); __END__ C:\test>arraybench -size=10000 -cpu=1 Benchmark: running assign, assignpre, push, slice, slicepre, each for +at least 1 CPU seconds... assign: 2 wallclock secs ( 1.01 usr + 0.00 sys = 1.01 CPU) @ 18 +.77/s (n=19) assignpre: 1 wallclock secs ( 1.01 usr + 0.00 sys = 1.01 CPU) @ 18 +.77/s (n=19) push: 1 wallclock secs ( 1.05 usr + 0.05 sys = 1.10 CPU) @ 13 +.61/s (n=15) slice: 2 wallclock secs ( 1.10 usr + 0.00 sys = 1.10 CPU) @ 26 +.32/s (n=29) slicepre: 1 wallclock secs ( 1.15 usr + 0.00 sys = 1.15 CPU) @ 26 +.04/s (n=30) Rate push assign assignpre slicepre slice push 13.6/s -- -28% -28% -48% -48% assign 18.8/s 38% -- -0% -28% -29% assignpre 18.8/s 38% 0% -- -28% -29% slicepre 26.0/s 91% 39% 39% -- -1% slice 26.3/s 93% 40% 40% 1% -- Benchmark: running assign, assignpre, push, slice, slicepre, each for +at least 1 CPU seconds... assign: 1 wallclock secs ( 1.06 usr + 0.00 sys = 1.06 CPU) @ 20 +.74/s (n=22) assignpre: 1 wallclock secs ( 1.15 usr + 0.00 sys = 1.15 CPU) @ 20 +.85/s (n=24) push: 1 wallclock secs ( 0.98 usr + 0.03 sys = 1.01 CPU) @ 15 +.83/s (n=16) slice: 1 wallclock secs ( 1.00 usr + 0.00 sys = 1.00 CPU) @ 6 +.99/s (n=7) slicepre: 1 wallclock secs ( 1.13 usr + 0.00 sys = 1.13 CPU) @ 7 +.07/s (n=8) Rate slice slicepre push assign assignpre slice 6.99/s -- -1% -56% -66% -66% slicepre 7.07/s 1% -- -55% -66% -66% push 15.8/s 127% 124% -- -24% -24% assign 20.7/s 197% 193% 31% -- -1% assignpre 20.9/s 198% 195% 32% 1% -- C:\test>

Update: See Abigail-II's following post for the real gen on pre-allocation and assignment method.

My benchmark was garbage it seems.


Nah! Your thinking of Simon Templar, originally played by Roger Moore and later by Ian Ogilvy

Replies are listed 'Best First'.
Re: array pre-allocation trick
by Abigail-II (Bishop) on Oct 31, 2002 at 11:10 UTC
    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% --

    Abigail

      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% + --
      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
        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

        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

        1. building a list
        2. breaking the list down to feed it to the map element by element
        3. 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
        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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://209357]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others having a coffee break in the Monastery: (7)
As of 2024-03-28 20:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found