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.