eduardo has asked for the wisdom of the Perl Monks concerning the following question:

one of the most basic operations you can do in a program is the swapping of two variables. who here can't remember sitting in their first programming class and being taught that the proper algorithm for swapping two variables was:
#define 3 variables, 2 for storage, one for temp...
my ($a, $b, $c);

#set the two variables to some value
$a = 5;
$b = 6;

#use the temp value to swap them
$c = $a;
$a = $b;
$b = $c;

#now, $a has $b and $b has what $a had

[download]
and then, you left feeling pretty good about yourself, until you encountered perl (and languages like it...) that alowed you to do this wonderful thing: 
($b, $a) = ($a, $b);   #swap two variables

[download]
well, i was thinking about this, and questioned, i wonder what the great oracle of benchmark would say about this... and the results were quite suprising:
#!/usr/bin/perl -w

use strict;
use Benchmark;

my $a = rand(10);
my $b = rand(10);

sub traditional {
   my $c = $a;
   $a = $b;
   $b = $c;
}

sub non_trad {
   ($b, $a) = ($a, $b);
}

timethese (-10, { "traditional" => \&traditional,
                  "not traditional" => \&non_trad,
                  });


[ed@darkness ed]$ perl swap.pl
Benchmark: running not traditional, traditional, 
   each for at least 10 CPU seconds...

not traditional: 11 wallclock secs (10.25 usr +  0.00 sys = 10.25 CPU)
+ @ 302846.15/s (n=3104173)
traditional: 11 wallclock secs (10.83 usr +  0.00 sys = 10.83 CPU) @ 4
+91714.04/s (n=5325263)

[download]
which basically says, in a nutshell... the traditional 3 value approach is faster... anyone care to explain to me why?

Replies are listed 'Best First'.
RE: simple swap...
by Russ (Deacon) on Jul 22, 2000 at 00:21 UTC
    Let me start with a lesson I learned recently: with your code, you are not using the $a and $b you declared at the top. The code executes without warning because $a and $b are "reserved" variables in Perl (used in sorting). If you change the variables to something else (capitalize them), you get: 
    sub traditional {
    my $C = $A;
    $A = $B;
    $B = $C;
}

sub non_trad {
    ($B, $A) = ($A, $B);
}

Global symbol "$A" requires explicit package name at ./bench.perl line
+ 12.
Global symbol "$B" requires explicit package name at ./bench.perl line
+ 13.

    [download]
    You should "use vars" to allow Benchmark to use the variables you want it to use.

    This doesn't change the results, though, since you were (unknowingly) using "real" variables, anyway.

    Here are some more possibilities, just to play around: 

    #!/usr/bin/perl -w

use vars qw/$A $B @Arr/;

use strict;
use Benchmark;

$A = rand(10);
$B = rand(10);
@Arr = ($A, $B);

sub traditional {
    my $C = $A;
    $A = $B;
    $B = $C;
}

sub non_trad {
    ($B, $A) = ($A, $B);
}

sub array_slice1 {
    @Arr = @Arr[1,0];
}

sub array_slice2 {
    @Arr[1,0] = @Arr;
}

timethese (100000, {
    "traditional" => \&traditional,
    "not traditional" => \&non_trad,
    "array1" => \&array_slice1,
    "array2" => \&array_slice2,
});

Results:
Benchmark: timing 100000 iterations of array1, array2, not traditional
+, traditional...
         array1:  4 wallclock secs ( 3.98 usr +  0.00 sys =  3.98 CPU)
         array2:  3 wallclock secs ( 3.27 usr +  0.00 sys =  3.27 CPU)
not traditional:  2 wallclock secs ( 2.72 usr +  0.00 sys =  2.72 CPU)
    traditional:  2 wallclock secs ( 1.81 usr +  0.00 sys =  1.81 CPU)

    [download]

    Russ
    Brainbench 'Most Valuable Professional' for Perl

[reply]
[d/l]
[select]
      Your array slicing is unfair, since you create the array beforehand.

      $_="goto+F.print+chop;\n=yhpaj";F1:eval
[reply]
        I'm not sure I understand what you mean. The variables being swapped are created beforehand in both methods. In the first examples, they are separate variables. In my second example, they are members of an array. Each of the subs swap the values in two variables.

        I mainly included them to point out:

        • TMTOWTDI
        • My benchmarks show arrays are even slower than the lists in the first example.
        :-)

        Russ
        Brainbench 'Most Valuable Professional' for Perl

[reply]
Re: simple swap...
by japhy (Canon) on Jul 21, 2000 at 23:07 UTC
    Possibly because the ($a,$b) = ($b,$a) requires that $a and $b get pushed onto the stack, and then do a list assignment.

    However, in Perl 5.6 on my machine here, I get these results: 
    jeffp@hut [3:04pm] ~ #103> perl -MBenchmark
timethese(1_000_000, {
  'swap' => q{ ($a,$b) = ($b,$a) },
  'three' => q{ { my $c = $a; $a = $b; $b = $c } },
});
Benchmark: timing 1000000 iterations of swap, three...
      swap: 17 wallclock secs ( 5.04 usr +  0.00 sys =  5.04 CPU) @ 19
+8449.61/s (n=1000000)
     three: 29 wallclock secs ( 5.96 usr +  0.01 sys =  5.97 CPU) @ 16
+7539.27/s (n=1000000)

    [download]
    $_="goto+F.print+chop;\n=yhpaj";F1:eval
[reply]
[d/l]

      What about testing the number of iterations for a specified amount of runtime, as was done in the original test, as opposed to timing a set number of iterations and checking the time as you did? The first method seems more likely to be accurate to me, and anyway you can't compare the tests unless they are the same, due to the vagaries of benchmark.

      I'd be interested to see the results, but don't have Perl 5.6. Both methods of testing show the traditional method to be faster on 5.005_03.

[reply]
(Ovid) Re: simple swap...
by Ovid (Cardinal) on Jul 21, 2000 at 23:21 UTC
    I'm using Perl 5.005_03 by Active State and my results clearly match what eduardo is getting. In fact, to make the test more of a fair match, I realized that I should probably declare $c outside of the "traditional" sub (though I acknowledge that in the real world, a temp variable should not be declared like that.) When I did that to $c, the traditional swap was even faster than the Perl swap.

    I can't help but wonder if japhy's results stem from a 5.6 optimization that's not found in older versions of $^X.

[reply]
Re: simple swap...
by athomason (Curate) on Jul 22, 2000 at 00:19 UTC
    I don't think it's a 5.6 thing: I ran eduardo's code on ActiveState 5.6 with these results: 
    Benchmark: running not traditional, traditional, each for at least 10 
+CPU seconds...
not traditional: 11 wallclock secs (10.68 usr +  0.02 sys = 10.70 CPU)
+ @ 364259.16/s (n=3899030)
traditional: 11 wallclock secs (10.85 usr +  0.00 sys = 10.85 CPU) @ 4
+74001.38/s (n=5141493)

    [download]
    Judging by the difference, the compiler doesn't seem optimize that kind of switch.
[reply]
[d/l]
RE: simple swap...
by jlistf (Monk) on Jul 21, 2000 at 23:34 UTC
    running on v5.6.0 
    Benchmark: timing 1000000 iterations of not traditional, traditional..
+.
not traditional: 4 wallclock secs ( 3.48 usr + 0.00 sys = 3.48 CPU ) @
+ 287687.00/s (n=1000000)
traditional: 3 wallclock secs ( 2.74 usr + 0.00 sys = 2.74 CPU ) @ 364
+431.49/s (n=1000000)

    [download]
    dunno what it means though...
[reply]
[d/l]
RE: simple swap...
by steveAZ98 (Monk) on Jul 22, 2000 at 23:46 UTC
    This is what I got using perl 5.004_04

    use Benchmark;
    timethese(10000000, {
    'swap' => q{ ($d,$e) = ($e,$d) },
    'three' => q{ { my $f = $d; $d = $e; $e = $f } },
    });


    Benchmark: timing 10000000 iterations of swap, three...
    swap: 13 secs (13.29 usr 0.00 sys = 13.29 cpu)
    three: 20 secs (19.45 usr 0.00 sys = 19.45 cpu)

[reply]

Back to Seekers of Perl Wisdom