Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

To push and pop or not to push and pop?

by GrandFather (Cardinal)
on Nov 05, 2005 at 22:24 UTC ( #506033=perlmeditation: print w/ replies, xml ) Need Help??

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. :)


Perl is Huffman encoded by design.

Comment on To push and pop or not to push and pop?
Select or Download Code
Re: To push and pop or not to push and pop?
by rnahi (Curate) on Nov 05, 2005 at 22:34 UTC
Re: To push and pop or not to push and pop?
by robin (Chaplain) on Nov 05, 2005 at 23:47 UTC
    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.

Re: To push and pop or not to push and pop?
by Aristotle (Chancellor) on Nov 06, 2005 at 00:21 UTC

    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.

    Makeshifts last the longest.

Re: To push and pop or not to push and pop?
by pg (Canon) on Nov 06, 2005 at 03:02 UTC

    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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://506033]
Approved by rnahi
Front-paged by dbwiz
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (14)
As of 2014-07-31 19:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (251 votes), past polls