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
> [email protected]
> 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
[email protected]
http://mail.perl.org.il/mailman/listinfo/perl
