|
in reply to About List::Util's pure Perl shuffle()
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.
|
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 ], @_;
}
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% --
| [reply]
[d/l]
[select] |
|
|
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.
| [reply]
[d/l] |
|
|
sub bukNew (@) {
my @x = 0 .. $#_;
@_[ map splice( @x, rand @x, 1 ), @x ];
}
However some random tests with various string and list lengths seem to show that it could be considerably slower than buk(), by even as much as 40% or so. Thus... are you sure your benchmark is not flawed? | [reply]
[d/l]
[select] |
|
|
|
|
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/ };
}
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!
| [reply]
[d/l]
[select] |
|
|
