Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

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

by blazar (Canon)
on Jul 11, 2007 at 10:11 UTC ( #625977=perlmeditation: print w/ replies, xml ) Need Help??

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]; } @_; }

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__

The results are as follows:

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

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
Re: About List::Util's pure Perl shuffle()
by BrowserUk (Pope) 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% --

    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.

      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/ }; }

      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% --

      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!

      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 ], @_; }
      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% --
      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% --

      blokhead

        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% --

        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.
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; } @_; }
    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.

      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 }
      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% --

      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/ };
      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% --

      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.

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

      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], @_; }

      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% --

      So that seems the best both speed and possibly memory wise.

        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.

        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 ], @_; }

        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.
        Ah, but the fix is easy. It's in my reply (which was posted and updated with the fix before you posted yours).
Re: About List::Util's pure Perl shuffle()
by ambrus (Abbot) on Jul 11, 2007 at 20:18 UTC
Re: About List::Util's pure Perl shuffle()
by aufflick (Deacon) on Jul 12, 2007 at 01:40 UTC
    ++ for putting me onto perltex!!

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (11)
As of 2014-08-20 12:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (113 votes), past polls