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

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)

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

Replies are listed 'Best First'.
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]

Replies are listed 'Best First'.

RE (tilly) 5 (less?): A Not so Simple Append
by tilly (Archbishop) on Oct 03, 2000 at 06:37 UTC

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]

*sigh*