[Israel.pm] unshift vs push&reverse

sawyer x xsawyerx at gmail.com
Fri Mar 27 04:22:34 PDT 2009


These are the following results that I have from Shlomi's first test:
Benchmark: timing 50000 iterations of push, unshift...
      push: 23 wallclock secs (21.02 usr +  0.03 sys = 21.05 CPU) @
2375.30/s (n=50000)
   unshift: 27 wallclock secs (24.27 usr +  0.04 sys = 24.31 CPU) @
2056.77/s (n=50000)


Apparently here, push is faster. This is Perl 5.10.0 so there might be
push optimizations...

On Fri, Mar 27, 2009 at 12:35 PM, Shlomi Fish <shlomif at iglu.org.il> wrote:
>
> 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.
>
> _______________________________________________
> Perl mailing list
> Perl at perl.org.il
> http://mail.perl.org.il/mailman/listinfo/perl


More information about the Perl mailing list