To push and pop or not to push and pop?

[GrandFather]

It's pretty easy just to assume that "it" is so. "It" may of course be any of many things, but in this case "it" is that "push and pop are obviously faster than unshift and shift". Clearly push and pop work at the growable end of the array so obviously there is an efficiency advantage. I was curious to see how much faster the push/pop pair were than the unshift/shift pair. The answer may come as something of a surprise - it did to me!

use strict;
use warnings;
use Benchmark qw(cmpthese);

my @template = (1) x 200;

cmpthese
  (
  -10,
    {
    'push pop', sub {pushPop ();},
    'push shift', sub {pushShift ();},
    'unshift pop', sub {unshiftPop ();},
    'unshift shift', sub {unshiftShift ();},
    }
  );

sub pushPop
{
my @from = @template;
my @to;
for (0..100)
  {
  push @to, pop @from for @from;
  push @from, pop @to for @to;
  }
}

sub pushShift
{
my @from = @template;
my @to;
for (0..100)
  {
  push @to, shift @from for @from;
  push @from, shift @to for @to;
  }
}

sub unshiftPop
{
my @from = @template;
my @to;
for (0..100)
  {
  unshift @to, pop @from for @from;
  unshift @from, pop @to for @to;
  }
}

sub unshiftShift
{
my @from = @template;
my @to;
for (0..100)
  {
  unshift @to, shift @from for @from;
  unshift @from, shift @to for @to;
  }
}

               Rate unshift shift      push pop   unshift pop    push 
+shift
unshift shift 129/s            --           -0%           -4%         
+  -6%
push pop      129/s            0%            --           -3%         
+  -6%
unshift pop   134/s            4%            3%            --         
+  -2%
push shift    137/s            6%            6%            2%         
+   --

There are two big surprises here, at least for me:

• The stack pairs (push/pop and unshift/shift) run at the same speed
• The queue pairs (push/shift and unshift/pop) run at close to the same speed and are both slightly faster than the stack pairs

Every now and then a problem comes up that could be solved using either of the stack pairs. In the past I would always choose push/pop. Now I'm happier thinking about the best expression of the problem and not being distracted by assumed efficiency issues.

Even more interesting though is the queue result which was quite unexpected. Note though that the fastest pair was push/shift. After a little contemplation this is not quite so surprising. After all shift is often used to pull arguments out of the list passed to a sub and push is often used to tack elements on to the end of a list. These are used much more than pop and unshift so it makes sense that there is some optimisation for them. Obvious after the benchmark anyway. :)

[rnahi]

You may be interested in this old (but always fresh) meditation on the same subject:
Shift, Pop, Unshift and Push with Impunity!.

[robin]

Clearly push and pop work at the growable end of the array so obviously there is an efficiency advantage.

As you've probably guessed by now, both ends are growable.

Unshift used to be quite a bit slower before tilly fixed it.

[Aristotle]

First, your benchmark is bogus code; shift @from for @from is not advisable. Use a while instead.

Anyway, there’s no “growable end” per se to arrays. Variables in Perl translate to multiply indirect structures in perl, which means that all of them can grow or shrink pretty seemlessly (hmm, with caveats).

---

Update: at first I claimed that the same is true of strings while I tried to work the kinks ouf my benchmark. It was a little tricky to do correctly because growing strings from the end with substr requires a length call that is not necessary when growing from the start. Now that I have, though, the final version disproves my expectations:

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

use Benchmark qw( timethese cmpthese );

my $template = 1 x 200;

cmpthese timethese -5 => {
    end_end => sub {
        my $from = $template;
        my $to = '';
        for ( 0 .. 100 ) {
            substr $to, length $to, 0, substr $from, -1, 1, '' while l
+ength $from;
            substr $from, length $from, 0, substr $to, -1, 1, '' while
+ length $to;
        }
    },
    start_end => sub {
        my $from = $template;
        my $to = '';
        for ( 0 .. 100 ) {
            substr $to, length $to && 0, 0, substr $from, -1, 1, '' wh
+ile length $from;
            substr $from, length $from && 0, 0, substr $to, -1, 1, '' 
+while length $to;
        }
    },
    end_start => sub {
        my $from = $template;
        my $to = '';
        for ( 0 .. 100 ) {
            substr $to, length $to, 0, substr $from, 0, 1, '' while le
+ngth $from;
            substr $from, length $from, 0, substr $to, 0, 1, '' while 
+length $to;
        }
    },
    start_start => sub {
        my $from = $template;
        my $to = '';
        for ( 0 .. 100 ) {
            substr $to, length $to && 0, 0, substr $from, 0, 1, '' whi
+le length $from;
            substr $from, length $from && 0, 0, substr $to, 0, 1, '' w
+hile length $to;
        }
    },
};

__END__
Benchmark: running end_end, end_start, start_end, start_start for at l
+east 5 CPU seconds...
   end_end:  6 wallclock secs ( 5.28 usr +  0.01 sys =  5.29 CPU) @ 34
+.22/s (n=181)
 end_start:  5 wallclock secs ( 5.33 usr +  0.01 sys =  5.34 CPU) @ 33
+.33/s (n=178)
 start_end:  6 wallclock secs ( 5.25 usr +  0.00 sys =  5.25 CPU) @ 25
+.90/s (n=136)
start_start:  5 wallclock secs ( 5.22 usr +  0.01 sys =  5.23 CPU) @ 2
+5.43/s (n=133)
              Rate start_start   start_end   end_start     end_end
start_start 25.4/s          --         -2%        -24%        -26%
start_end   25.9/s          2%          --        -22%        -24%
end_start   33.3/s         31%         29%          --         -3%
end_end     34.2/s         35%         32%          3%          --

So while it doesn’t matter whether you’re shrinking from the start or the end of the string (no surprise), it does matter noticably which end you grow the string from. Hmm. Perl is lower-level than with other things, here.

[pg]

Whether to use a certain data structure is not only determined by the speed, especially when the speed is close. Between queue and stack, there is also a legibility consideration there, and whichever makes more sense logically should be used.