It it a requirement of the Fisher-Yates shuffle that the "randomizing window" grow smaller through each iteration? Why not just do:
sub shuffle { my $deck = shift; my $size = @$deck; my ($j, $t); for (@$deck) { $t = $deck->[$j = int rand $size]; $deck->[$j] = $_; $_ = $t; } } This is considerably faster than both versions in my tests, and sidesteps most nasty boundary cases.