I was looking at the Fisher-Yates Shuffle and I noticed that there is a branch in the while loop. This got me thinking, "Is it a big deal to swap two locations in an array when the locations are the same?"

Well it occured to me that there would be some overhead... but how much? Is that overhead more then or less then the overhead of a branch? Well, honestly I don't know. But I ran a benchmark, and it came out close... Here is the code, followed by the results: 

use strict;
use Benchmark;
use vars '@array';

# The Fisher-Yates Shuffle 
#
#    my $arrayref = shift;
#    my $index = @$arrayref;
#    while ( $index-- ) 
#    {
#        my $newloc = int rand (1+$i);
#        next if $index == $newloc;
#        @$arrayref[$index, $newloc] = @$arrayref[$newloc, $index];
#    }

@array = (1..100_000); # An array to be shuffled. 

# Rather then pass in a ref to the array, just shuffle the array in pl
+ace.
timethese( 100, {
    'BRANCH'  => sub {
            my $i=@array; 
            while($i--){
                my $j=int rand(1+$i);
                next if $i==$j;  ### This is the line being tested.
                @array[$i, $j]=@array[$j, $i]
            }},
    'WITHOUT' => sub {
            my $i=@array; 
            while($i--){
                my $j=int rand(1+$i); 
                @array[$i, $j]=@array[$j, $i]
            }},
    } );

# Benchmark: timing 100 iterations of BRANCH, WITHOUT...
#  BRANCH: 73 wallclock secs (73.43 usr +  0.00 sys = 73.43 CPU) @  1.
+36/s (n=100)
# WITHOUT: 67 wallclock secs (67.02 usr +  0.00 sys = 67.02 CPU) @  1.
+49/s (n=100)

# Benchmark: timing 1000 iterations of BRANCH, WITHOUT...
#  BRANCH: 727 wallclock secs (726.67 usr +  0.00 sys = 726.67 CPU) @ 
+ 1.38/s (n=1000)
# WITHOUT: 668 wallclock secs (667.78 usr +  0.02 sys = 667.80 CPU) @ 
+ 1.50/s (n=1000)

[download]
It looks to me like the branch is not needed.

In reply to Fisher-Yates Shuffle by Adam

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.