in reply to Re: shift vs @_
in thread shift vs @_

Besides style, is there any performance penalty paid by shift? In the docs I see: "Shifts the first value of the array off and returns it, shortening the array by 1 and moving everything down." My reading of this makes me think that shift is potentially an expensive operation, because it has to "shift" the front of the area off, and then copy the remaining elements all back one position.

Replies are listed 'Best First'.
Re^3: shift vs @_
by Tanktalus (Canon) on Oct 02, 2006 at 23:24 UTC

    This has been covered a few times. Check out:

    The bottom line? Perl implements arrays by creating a block of memory, and then pointing the beginning of the array as an offset into that block. When you try to unshift too much onto the beginning of the array such that we run out of room at that end of the chunk of memory, perl goes to allocate more memory, and, again, keeps a chunk free at the beginning. However, if you're shifting off the array until it's empty, perl just keeps incrementing the "beginning" pointer until the beginning and end point at the same place, meaning a length of zero. There is no copying here whatsoever.

[reply]
      Thankyou. The statement in that second link about it being an O(1) operation is exactly what I was looking for--I was afraid it might be O(n).
[reply]
Re^3: shift vs @_
by sgifford (Prior) on Oct 02, 2006 at 22:14 UTC
    They seem to be about the same. shift comes out slightly ahead in this test, perhaps because it simplifies the loop. 
    #!/usr/bin/perl

use warnings;
use strict;

use Benchmark;

timethese(1_000_000, {
  'use_shift' => sub { sub_with_shift(0..9) },
  'use_list' => sub { sub_with_list(0..9) },
  'use_direct' => sub { sub_with_direct(0..9) },
});

sub sub_with_shift
{
  my $sum = 0;
  while (@_)
  {
    $sum += shift;
  }
  $sum;
}

sub sub_with_list
{
  my(@a)=@_;
  my $sum = 0;
  $sum += $_
    for @a;
  $sum;
}

sub sub_with_direct
{
  my $sum = 0;
  $sum += $_
    for @_;
  $sum;
}

    [download]
    Benchmark: timing 1000000 iterations of use_direct, use_list, use_shift...
use_direct:  7 wallclock secs ( 6.48 usr + -0.01 sys =  6.47 CPU) @ 154559.51/s (n=1000000)
  use_list: 10 wallclock secs ( 9.85 usr +  0.06 sys =  9.91 CPU) @ 100908.17/s (n=1000000)
 use_shift:  6 wallclock secs ( 6.48 usr +  0.01 sys =  6.49 CPU) @ 154083.20/s (n=1000000)

    --
    sgifford's Web page
[reply]
[d/l]
[select]
      #!/usr/bin/perl

use warnings;
use strict;

use Benchmark;

timethese(1_000_000, {
  'use_shift' => sub { sub_with_shift(0..2) },
  'use_list' => sub { sub_with_list(0..2) },
  'use_direct' => sub { sub_with_direct(0..2) },
});

sub sub_with_shift
{
  my ($one, $two, $three) = (shift, shift, shift);
  my $sum = $one+$two+$three;
}

sub sub_with_list
{
  my ($one, $two, $three) = @_;
  my $sum = $one+$two+$three;
}

sub sub_with_direct
{
  my $sum = $_[0] + $_[1] + $_[2];
}

      [download]
      i think my example better reflects the core of the problem
[reply]
[d/l]
      Sorry i forgot result 
Benchmark: timing 1000000 iterations of use_direct, use_list, use_shif
+t...
use_direct:  0 wallclock secs ( 0.57 usr +  0.00 sys =  0.57 CPU) @ 17
+54385.96/s (n=1000000)
  use_list:  1 wallclock secs ( 0.86 usr +  0.00 sys =  0.86 CPU) @ 11
+62790.70/s (n=1000000)
 use_shift:  2 wallclock secs ( 0.96 usr +  0.00 sys =  0.96 CPU) @ 10
+41666.67/s (n=1000000)

      [download]
[reply]
[d/l]
Re^3: shift vs @_
by chromatic (Archbishop) on Oct 03, 2006 at 02:03 UTC
    Besides style, is there any performance penalty paid by shift?

    Yes; if you do it repeatedly hundreds of thousands of times in a tight loop, you might slow down your program as much as performing one IO operation. In other words, none that you will ever notice.

[reply]
Re^3: shift vs @_
by Anonymous Monk on Nov 12, 2010 at 02:47 UTC
    Interesting point, but it would be a lot easier to shift the zeroth index point up one element, presuming that the array members are themselves string descriptors or other pointers. That plus decrementing the array size would be pretty cheap.
[reply]

In Section Seekers of Perl Wisdom