[Israel.pm] unshift vs push&reverse

Shlomi Fish shlomif at iglu.org.il
Fri Mar 27 03:35:21 PDT 2009


On Friday 27 March 2009 04:01:10 Yitzchak Scott-Thoennes wrote:
> On Thu, March 26, 2009 2:29 am, Gabor Szabo wrote:
> > ps. push should be way faster than unshift but I am quite sure it does
> > not matter in your code. If you want to check, benchmark them.
>
> No, perl is smart enough to make unshift just about as fast as push.
>
> The array of pointers that a Perl array is based on can have extra space
> at the beginning, and when an unshift needs to reallocate the array, it
> grabs extra space based on the number of elements in the array, such that
> N consecutive unshifts should require at most log(N)/log(2)+1
> reallocations.
>

Out of curiosity, I ran the following benchmark:

<<<<<<<<<<<<<<<
#!/usr/bin/perl

use strict;
use warnings;

use Benchmark qw(:all);

timethese(50_000,
    +{
        'push' => 
            sub {
                my @array;
                for my $x (1 .. 1_000)
                {
                    push @array, $x;
                } 
                return [reverse(@array)];
            },
        'unshift' =>
            sub {
                my @array;
                for my $x (1 .. 1_000)
                {
                    unshift @array, $x;
                }
                return \@array;
            },
    },
);
>>>>>>>>>>>>>>>

And the results are:

{{{{
shlomi:~/progs/perl$ perl  push-vs-unshift.pl
Benchmark: timing 50000 iterations of push, unshift...
      push: 29 wallclock secs (27.19 usr +  0.02 sys = 27.21 CPU) @ 1837.56/s 
(n=50000)
   unshift: 24 wallclock secs (23.42 usr +  0.02 sys = 23.44 CPU) @ 2133.11/s 
(n=50000)
}}}}

So unshift was somewhat faster than push for 1,000 elements.

Then I tried:

<<<<<<<<<
#!/usr/bin/perl

use strict;
use warnings;

use Benchmark qw(:all);

timethese(300,
    +{
        'push' => 
            sub {
                my @array;
                for my $x (1 .. 100_000)
                {
                    push @array, $x;
                } 
                return [reverse(@array)];
            },
        'unshift' =>
            sub {
                my @array;
                for my $x (1 .. 100_000)
                {
                    unshift @array, $x;
                }
                return \@array;
            },
    },
);
>>>>>>>>>

(With 100,000 elements).

And got:

<<<<<<
shlomi:~/progs/perl/snippets$ perl push-vs-unshift.pl
Benchmark: timing 300 iterations of push, unshift...
      push: 17 wallclock secs (16.16 usr +  0.02 sys = 16.18 CPU) @ 18.54/s 
(n=300)
   unshift: 15 wallclock secs (13.90 usr +  0.75 sys = 14.65 CPU) @ 20.48/s 
(n=300)
>>>>>>

So again unshift was faster than push+reverse.

Regards,

	Shlomi Fish

> _______________________________________________
> Perl mailing list
> Perl at perl.org.il
> http://mail.perl.org.il/mailman/listinfo/perl

-- 
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
Freecell Solver - http://fc-solve.berlios.de/

God gave us two eyes and ten fingers so we will type five times as much as we
read.



More information about the Perl mailing list