About List::Util's pure Perl shuffle()

In a recent discussion (link @ GG) in ctt, PerlTeX was mentioned (and I'm also mentioning it here because it is not that widely known and IMHO it would deserve being) in relation to shuffling, at which point in reply to a posted piece of code I wrote about the perldoc -q shuffle FAQ entry, talking in particular about both Fisher-Yates and List::Util's shuffle(). Now, I happened to check the source code for the latter module, and since it has pure Perl code for the given function, I noticed that in particular it is as follows:

sub shuffle (@) {
  my @a=\(@_);
  my $n;
  my $i=@_;
  map {
    $n = rand($i--);
    (${$a[$n]}, $a[$n] = $a[$i])[0];
  } @_;
}
[download]

Now, at first sight it is a nice piece of Obfu, ain't it? Well, then if you look at it, it's easy to see how it works and in particular that it is still Fisher-Yates. But of course you have to think about it for a while... and I wondered why it is like that...

To be fair, I think that taking references in the first place is to avoid duplicating data in memory that could be heavy in memory usage... but then I also thought that all that playing with references would impose a performance penalty and -for once- I suppose that performance does matter. So I tried the following Benchmark, comparing a naive and fairly readable implementation of the algorithm with List::Util's:

#!/usr/bin/perl

use strict;
use warnings;
use Benchmark qw/:all :hireswallclock/;

sub naive (@) {
    my @l=@_;
    for (reverse 1..$#l) {
        my $r=int rand($_+1);
        @l[$_,$r]=@l[$r,$_];
    }
    @l;
}

sub listutil (@) {
    my @a=\(@_);
    my $n;
    my $i=@_;
    map {
        $n = rand($i--);
        (${$a[$n]}, $a[$n] = $a[$i])[0];
    } @_;
}

cmpthese -60, { map { $_ => "$_ 1..1000" } qw/naive listutil/ };

__END__
[download]

The results are as follows:

C:\temp>perl lus.pl
          Rate    naive listutil
naive    588/s       --     -14%
listutil 684/s      16%       --
[download]

So that pretty much may answer my question as to why the sub is implemented like that... but then this raises the question as to how could one come up with such an idea, because I'm sure I wouldn't have...

Any comments?

Comment on About List::Util's pure Perl shuffle() Select or Download Code

Replies are listed 'Best First'.
Re: About List::Util's pure Perl shuffle() by BrowserUk (Patriarch) on Jul 11, 2007 at 13:21 UTC
If you accept the principle that code in modules is destined to be reused in lots of situations, including performance critical ones, and should therefore do it's utmost to be as efficient as the author is comfortable maintaining, then List::Util's use of aliasing to sqeeze a little more performance seems entirely reasonable. That said, they missed a trick. Using a block form map creates a additional level of scope that they aren't using and slows performance. They can squeeze another 30%, and almost 50% over the 'naive' implementation, by avoiding it: `sub buk (@) { my @a = \( @_ ); my $n; my $i = @_; map+( $n=rand($i--), ${ $a[ $n ] }, $a[ $n ]=$a[ $i ] )[ 1 ], @_; } cmpthese -1, { map { $_ => "$_ 1..1000" } qw/naive listutil buk/ }; __END__ C:\test>junk Rate naive listutil buk naive 520/s -- -13% -32% listutil 597/s 15% -- -22% buk 769/s 48% 29% --` [download] Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. "Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."	[reply] [d/l]
Re^2: About List::Util's pure Perl shuffle() by blokhead (Monsignor) on Jul 12, 2007 at 02:03 UTC
As long as we're (micro)optimizing, why even take references to the elements of @_ at all? Just shuffle indices of @_ and grab things out of @_ as they are needed. I guess indexing an array is a tiny bit faster than following a scalar ref. `sub blokhead (@) { my @a = (0 .. $#_); my $i = @_; my $n; map+( $n=rand($i--), $_[$a[$n]], $a[$n]=$a[$i] )[ 1 ], @_; }` [download] It's clearly not a significant improvement, but does seem to be consistently a tiny bit faster... On large data: `our @data = map { 'x' x 1000 } 1..1000; cmpthese -2, { map { $_ => "$_ \@data" } qw/naive listutil buk ikegami + blokhead/ }; Rate naive ikegami listutil buk blokhead naive 76.1/s -- -26% -47% -88% -88% ikegami 103/s 36% -- -28% -84% -84% listutil 143/s 89% 39% -- -78% -78% buk 638/s 739% 518% 345% -- -1% blokhead 643/s 745% 522% 348% 1% --` [download] On small data: `our @data = ("xxx") x 1000; cmpthese -2, { map { $_ => "$_ \@data" } qw/naive listutil buk ikegami + blokhead/ }; Rate naive listutil ikegami buk blokhead naive 328/s -- -26% -44% -49% -49% listutil 445/s 36% -- -24% -30% -31% ikegami 589/s 80% 32% -- -8% -9% buk 637/s 94% 43% 8% -- -1% blokhead 646/s 97% 45% 10% 1% --` [download] blokhead	[reply] [d/l] [select]
Re^3: About List::Util's pure Perl shuffle() by BrowserUk (Patriarch) on Jul 12, 2007 at 07:11 UTC
As long as we're (micro)optimizing, ... I agree, that is a micro-optimisation :), but if you look at the bigger picture, your version is anything from 45% to 350% faster than the List::Util version--it's not so micro. Plus, your solution inspired me to come up with this, I think, rather surprising version. It's not only faster again, sometimes as much as another 25% over the earlier gains, it's also arguably the most readable: sub bukNew ($) { my( $ref ) = @_; my @x = 0 .. $#$ref; @{ $ref }[ map splice( @x, rand @x, 1 ), @x ]; } 10 strings length 1.25892541179417 Rate naive listutil blokhead buk bukNew naive 22172/s -- -41% -69% -69% -73% listutil 37867/s 71% -- -47% -47% -54% blokhead 71022/s 220% 88% -- -1% -14% buk 72090/s 225% 90% 2% -- -12% bukNew 82136/s 270% 117% 16% 14% -- 10 strings length 10 Rate naive listutil blokhead buk bukNew naive 20685/s -- -44% -70% -71% -75% listutil 36824/s 78% -- -47% -49% -55% blokhead 70065/s 239% 90% -- -3% -14% buk 72090/s 249% 96% 3% -- -12% bukNew 81717/s 295% 122% 17% 13% -- 10 strings length 1000 Rate naive listutil blokhead buk bukNew naive 1193/s -- -60% -98% -98% -99% listutil 2981/s 150% -- -96% -96% -96% blokhead 69931/s 5764% 2246% -- -2% -15% buk 71723/s 5914% 2306% 3% -- -12% bukNew 81873/s 6765% 2647% 17% 14% -- 100 strings length 1.25892541179417 Rate naive listutil buk blokhead bukNew naive 2190/s -- -45% -72% -73% -78% listutil 3989/s 82% -- -49% -51% -60% buk 7848/s 258% 97% -- -4% -21% blokhead 8144/s 272% 104% 4% -- -18% bukNew 9925/s 353% 149% 26% 22% -- 100 strings length 10 Rate naive listutil buk blokhead bukNew naive 2092/s -- -46% -73% -74% -79% listutil 3868/s 85% -- -50% -52% -61% buk 7811/s 273% 102% -- -4% -21% blokhead 8094/s 287% 109% 4% -- -18% bukNew 9873/s 372% 155% 26% 22% -- 100 strings length 1000 Rate naive listutil buk blokhead bukNew naive 96.3/s -- -58% -99% -99% -99% listutil 229/s 138% -- -97% -97% -98% buk 7811/s 8009% 3314% -- -4% -21% blokhead 8094/s 8303% 3437% 4% -- -18% bukNew 9869/s 10145% 4213% 26% 22% -- 1000 strings length 1.25892541179417 Rate naive listutil buk blokhead bukNew naive 208/s -- -41% -74% -75% -76% listutil 350/s 69% -- -56% -58% -59% buk 789/s 280% 125% -- -5% -7% blokhead 827/s 298% 136% 5% -- -3% bukNew 850/s 310% 143% 8% 3% -- 1000 strings length 10 Rate naive listutil buk blokhead bukNew naive 187/s -- -42% -76% -77% -78% listutil 319/s 71% -- -59% -61% -62% buk 777/s 316% 143% -- -5% -7% blokhead 815/s 337% 155% 5% -- -2% bukNew 834/s 347% 161% 7% 2% -- 1000 strings length 1000 Rate naive listutil buk blokhead bukNew naive 8.47/s -- -62% -99% -99% -99% listutil 22.2/s 162% -- -97% -97% -97% buk 785/s 9164% 3437% -- -3% -8% blokhead 810/s 9470% 3554% 3% -- -5% bukNew 850/s 9939% 3733% 8% 5% -- [download] It's advantage tails off as the number of strings rise, but when you start seeing numbers like 20x, 30x and even 40x faster than the List::Util PP version, it seems possible that someone might benefit. 'sides, I think of optimising as a lot like obfu, a fun intellectual challange. Plus there is the upside that the results can be useful. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. "Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."	[reply] [d/l]
Re^4: About List::Util's pure Perl shuffle() by blazar (Canon) on Jul 12, 2007 at 10:36 UTC
Re^5: About List::Util's pure Perl shuffle() by BrowserUk (Patriarch) on Jul 12, 2007 at 16:08 UTC
Some notes below your chosen depth have not been shown here
Re^2: About List::Util's pure Perl shuffle() by blazar (Canon) on Jul 11, 2007 at 16:15 UTC
If you accept the principle that code in modules is destined to be reused in lots of situations, including performance critical ones, and should therefore do it's utmost to be as efficient as the author is comfortable maintaining, then List::Util's use of aliasing to sqeeze a little more performance seems entirely reasonable. I'm not saying it isn't. (Well, except that some comments for the benefit of the occasional peeping Tom would have been nice.) In fact I'm amazed, because I wouldn't have expected it to be that efficient. The question still is: how does one come up with such code? I suspect that one critical difference is that the naive implementation, due to its de facto shuffling of an array in place, does so by taking two slices, and assigning to one of them. While L::U's doesn't really swap, and the overhead of dereferencing weights less. BTW, testing with `for my $i (map 10*$_, 1..4) { cmpthese -30, { map { $_ => "$_ 1..$i" } qw/naive buk/ }; }` [download] one seems* to get a slowly decreasing trend: `Rate naive buk naive 49811/s -- -37% buk 79547/s 60% -- Rate naive buk naive 4751/s -- -33% buk 7112/s 50% -- Rate naive buk naive 479/s -- -29% buk 677/s 41% -- Rate naive buk naive 46.9/s -- -27% buk 64.6/s 38% --` [download] That said, they missed a trick. Using a block form map creates a additional level of scope that they aren't using and slows performance. They can squeeze another 30%, and almost 50% over the 'naive' implementation, by avoiding it Cool!	[reply] [d/l] [select]
Re: About List::Util's pure Perl shuffle() by runrig (Abbot) on Jul 11, 2007 at 17:28 UTC
I suppose taking references might save memory, but it doesn't save any time over this (on small or large lists): `sub shuffle { my @a=@_; my $n; my $ret; my $i=@_; map { $n = rand($i--); $ret = $a[$n]; $a[$n] = $a[$i]; $ret; } @_; }` [download] I get about 16% better than the List::Util version (YMMV). Update: Aha. It's large data being shuffled, not large lists, that makes List::Util the better answer in some instances. Thanks ikegami.	[reply] [d/l]
Re^2: About List::Util's pure Perl shuffle() by ikegami (Patriarch) on Jul 11, 2007 at 17:47 UTC
Adding your optimization to BrowerUK's version, we get the best yet. `sub ikegami (@) { my @a=@_; my $i=@a; my $n; my $x; map +( $n=rand($i--), $x=$a[$n], $a[$n]=$a[$i] )[1], @a }` [download] `Rate naive listutil runrig broweruk ikegami naive 636/s -- -6% -19% -26% -37% listutil 675/s 6% -- -14% -21% -33% runrig 785/s 23% 16% -- -9% -22% broweruk 859/s 35% 27% 9% -- -15% ikegami 1010/s 59% 50% 29% 18% --` [download] Of course, this doesn't always help. For example, try shuffling somewhat long strings. `our @data = map { 'x' x 1000 } 1..1000; cmpthese -3, { map { $_ => "$_ \@data" } qw/naive listutil broweruk ru +nrig ikegami/ };` [download] `Rate runrig naive ikegami listutil broweruk runrig 118/s -- -10% -40% -43% -86% naive 131/s 11% -- -34% -37% -85% ikegami 197/s 68% 51% -- -5% -77% listutil 207/s 76% 58% 5% -- -76% broweruk 860/s 632% 558% 336% 315% --` [download] Update: runrig pointed out that my shuffle was broken. I changed `$a[$n]` to `$x=$a[$n]` to fix it. It slowed down my solution, but not by much.	[reply] [d/l] [select]
Re^3: About List::Util's pure Perl shuffle() by blazar (Canon) on Jul 12, 2007 at 09:58 UTC
Update: runrig pointed out that my shuffle was broken. I changed `$a[$n]` to `$x=$a[$n]` to fix it. It slowed down my solution, but not by much. Ok, that's the same trick as BrowserUk's, except that in that form it's even more elegant. Anyway... c'mon! I'm not ashamed the very least to ask why does it work. I can't understand...	[reply] [d/l] [select]
Re^4: About List::Util's pure Perl shuffle() by ikegami (Patriarch) on Jul 12, 2007 at 13:29 UTC
Re^2: About List::Util's pure Perl shuffle() by blazar (Canon) on Jul 11, 2007 at 23:13 UTC
I suppose taking references might save memory, but it doesn't save any time over this (on small or large lists): `[snip]` I get about 16% better than the List::Util version (YMMV). Indeed I was about to yell: "well, but then let's just adapt BrowserUk's version simply removing the referencing and dereferencing": `sub bzr (@) { my @a = @_; my $n; my $i = @_; map +($n=randi($i--), $a[$n], $a[$n]=$a[$i])[1], @_; }` [download] But that won't work any more! (So kids don't copy the code above, it's crap! ;-) OTOH if I compare your code (as `'run'`) with BrowserUk's, I get: `Rate run buk run 7467/s -- -12% buk 8454/s 13% --` [download] So that seems the best both speed and possibly memory wise.	[reply] [d/l] [select]
Re^3: About List::Util's pure Perl shuffle() by runrig (Abbot) on Jul 11, 2007 at 23:27 UTC
That's strange, I compared mine against BrowserUK's and get that they are very nearly equal (mine ahead by a meaningless 1 to 4%), until the list gets large (around a million), then I'm ahead by ~10%. This is for lists containing data only a few characters long, but as ikegami points out, for larger data, BrowserUK's wins by a longshot.	[reply]
Re^3: About List::Util's pure Perl shuffle() by ikegami (Patriarch) on Jul 12, 2007 at 01:12 UTC
Ah, but the fix is easy. It's in my reply (which was posted and updated with the fix before you posted yours).	[reply]
Re^3: About List::Util's pure Perl shuffle() by BrowserUk (Patriarch) on Jul 12, 2007 at 00:32 UTC
Here's a non-aliasing version that does work, but it doesn't perform very well. Why it works is left as an exercise. `sub bukNoAlias (@) { my @a = @_; my( $n, $t ); my $i = @_; map+( $t=$a[ $n=rand($i--) ], $a[ $n ]=$a[ $i ] )[ 0 ], @_; }` [download] Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. "Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."	[reply] [d/l]
Re: About List::Util's pure Perl shuffle() by ambrus (Abbot) on Jul 11, 2007 at 20:18 UTC
See also Benchmarking perfect shuffles.	[reply]
Re: About List::Util's pure Perl shuffle() by aufflick (Deacon) on Jul 12, 2007 at 01:40 UTC
++ for putting me onto perltex!!	[reply]

Back to Meditations