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*