RE (tilly) 3 (less?): A Not so Simple Append

Conceptually push and unshift are exactly symmetrical, along with pop and shift. Is there really a performance difference?

I tried it and wow:

use strict;
use Benchmark;
use vars qw(%test);

%test = (
  push => sub {
    my @tmp;
    push @tmp, "bar" foreach 1..10000;
  },
  unshift => sub {
    my @tmp;
    unshift @tmp, "bar" foreach 1..10000;
  },
);

timethese (-5, \%test);

__END__
Benchmark: running push, unshift, each for at least 5 CPU seconds...
      push:  5 wallclock secs ( 5.46 usr +  0.05 sys =  5.51 CPU) @ 17
+.42/s (n=96)
   unshift:  8 wallclock secs ( 8.08 usr +  0.11 sys =  8.19 CPU) @  0
+.73/s (n=6)
[download]

Why is the one so much faster than the other?

Comment on RE (tilly) 3 (less?): A Not so Simple Append Download Code

Replies are listed 'Best First'.
RE: RE (tilly) 3 (less?): A Not so Simple Append by extremely (Priest) on Oct 03, 2000 at 05:25 UTC
benefits of the array structure... you just make a new scalar and add a pointer to the end of the array with push. With unshift, you make a scalar, copy every pointer in the array over one, and stick the new pointer at the beginning. PerlGuts Illustrated may help you see that. See Arrays. -- $you = new YOU; honk() if $you->love(perl)	[reply]
RE (tilly) 5 (less?): A Not so Simple Append by tilly (Archbishop) on Oct 03, 2000 at 06:37 UTC
I know all that. I just had not realized that they place the array right at the beginning of the space allocated. I guess I shouldn't be surprised, after all that is the same algorithmic mistake they made on map. Look at the following: use strict; use Benchmark; use vars qw(%hash %test); %test = ( shift => sub { my @tmp = map "foo", 1..10000; foreach (@tmp) { my $val = shift @tmp; unshift @tmp, $val; } }, pop => sub { my @tmp = map "foo", 1..10000; foreach (@tmp) { my $val = pop @tmp; push @tmp, $val; } }, ); timethese (-5, \%test); __END__ Benchmark: running pop, shift, each for at least 5 CPU seconds... pop: 7 wallclock secs ( 6.60 usr + 0.00 sys = 6.60 CPU) @ 6 +.67/s (n=44) shift: 7 wallclock secs ( 6.27 usr + 0.00 sys = 6.27 CPU) @ 6 +.70/s (n=42) [download] When you have the space available, unshift is not appreciably slower. Just place the new array 1/16 of the way off from whichever way it is being moved. The memory wastage is insignificant, push is also pretty much the same speed, and unshift will become fast. *sigh*	[reply] [d/l]