Performance confusion

[RobG]

I was playing with shuffling routines so I browsed those at
merlyn.demon.co.uk[1]. I did a bit of work and wrote what I thought
was a much faster version. According to my tests, it's 3 to 4 times
faster in Firefox and IE and about equal in Opera, Chrome and mobile
Safari.

I put some test cases on jsperf[2] only to discover that suddenly the
peformance of the "StocktonShuffle" was greatly enhanced in all
browsers except IE. The most dramatic was Firefox, where it went from
being 4 times slower to 3 times faster. I have no idea why there
should be such huge differences. The two functions are posted on
jsperf[2], unfortunately the part that stores results is broken so no
history of tests that have been run.

Here is my local test function:

function speedTest() {

var a, b = '0123456789'.split('');
var arg, args = arguments;
var result = [];
var i, s;
var n = 10000;

for (var j=0, jLen=args.length; j<jLen; j++) {
arg = args[j]
a = b.concat();
i = n;
s = new Date();
while (i--) {
window[arg](a);
}
result.push(arg + ': ' + (new Date() - s));
}
return result;
}

alert( speedTest('allInOneShuffle','StocktonShuffle').join('<br>') );

Can anyone explain the rather large differences in peformance?


1. <URL: http://www.merlyn.demon.co.uk/js-shufl.htm#FnB >

2. <URL: http://jsperf.com/shuffle110609 >

 

[Michael Haufe (\TNO\)]

...
Can anyone explain the rather large differences in peformance?
...

I'd venture a guess that it is because IE's use of "this" isn't
optimized. I think I remember reading a bug in bugzilla[*] for example
specifically aimed at not doing dynamic lookups on "this" during
runtime if it doesn't change.
[*] bug has been closed so its not

 

[Michael Haufe (\TNO\)]

[*] bug has been closed so its not

....so it is not easy to find atm

 

[RobG]

I'd venture a guess that it is because IE's use of "this" isn't
optimized.

Perhaps I wasn't clear.

I was referring to the large differences in performance when comparing
results from local testing to those from jsperf. In particular, the
one for Firefox where local testing showed the all-in-one shuffle to
be 4 times faster than the other, yet at jsperf the StocktonShuffle is
4 times faster.

 

[Michael Haufe (\TNO\)]

Perhaps I wasn't clear.

I was referring to the large differences in performance when comparing
results from local testing to those from jsperf. In particular, the
one for Firefox where local testing showed the all-in-one shuffle to
be 4 times faster than the other, yet at jsperf the StocktonShuffle is
4 times faster.

Hmm, I can't duplicate this. The ratio comes out about the same for me
(IE9 and Fx4 vs Website). Though in the source code of the site I
notice that everything is wrapped in a try...catch block.

 

[Dr J R Stockton]

In comp.lang.javascript message <3773f85b-3700-4581-a77d-8cbbd4362fea@h1
2g2000pro.googlegroups.com>, Wed, 8 Jun 2011 19:30:23, RobG

I was playing with shuffling routines so I browsed those at
merlyn.demon.co.uk[1]. I did a bit of work and wrote what I thought
was a much faster version. According to my tests, it's 3 to 4 times
faster in Firefox and IE and about equal in Opera, Chrome and mobile
Safari.

The first question must be whether, with your code, all possible
outcomes are equally probable (assuming Math.random to be perfect) and
whether you can prove that ... well, E&OE, I can.

The next observation is that "mine" is not really my shuffle. It's the
Fisher-Yates shuffle, as implemented by Durstenfeld and given by Knuth.

I put some test cases on jsperf[2] only to discover that suddenly the
peformance of the "StocktonShuffle" was greatly enhanced in all
browsers except IE. The most dramatic was Firefox, where it went from
being 4 times slower to 3 times faster. I have no idea why there
should be such huge differences. The two functions are posted on
jsperf[2], unfortunately the part that stores results is broken so no
history of tests that have been run.

It may be germane to observe that if I load, into FF 3.6.17 in WinXP
sp3, <http://www.merlyn.demon.co.uk/$tmp.htm#JaR>, and press the Test
button a few times, waiting each time for a line like
End. Time 8.693 s. Found 0 errors.
to appear in the following readonly textarea, then on the first two
occasions the times are just under 4 seconds and subsequently all times
are just under 9 seconds. But IE, Opera, Safari, Chrome all show their
own consistent speeds.

By the way, that page $tmp.htm seems to indicate that the best known
RegExps of LRN and myself are faster for validating YYYY-MM-DD than the
sort of function using a Date Object which those who have not read (and
remembered) past discussions here might be expected to write. But,
although the comparison is not on an entirely fair footing yet, an
arithmetic method by LRN is like lightning in comparison.

Here is my local test function:

function speedTest() {

var a, b = '0123456789'.split('');
var arg, args = arguments;
var result = [];
var i, s;
var n = 10000;

for (var j=0, jLen=args.length; j<jLen; j++) {
arg = args[j]
a = b.concat();
i = n;
s = new Date();
while (i--) {
window[arg](a);
}
result.push(arg + ': ' + (new Date() - s));
}
return result;
}

alert( speedTest('allInOneShuffle','StocktonShuffle').join('<br>') );

Can anyone explain the rather large differences in peformance?


1. <URL: http://www.merlyn.demon.co.uk/js-shufl.htm#FnB >

2. <URL: http://jsperf.com/shuffle110609 >

The comparison in [2] is not entirely fair. Both shuffle functions need
to swap a pair of elements, but one does so in-line while the other uses
a Swap function. It seems rather likely that one of those is faster
than the other. Also. one uses an abbreviated name for Math.random, and
generates the random integer in-line; the other calls a Random function.

I think yours might be described as equivalent to an optimised coding of
"mine", which was written more for general clarity. That could be
verified by using a repeatable Math.random and comparing the results.
But yours is clearly *meant* to be the same good algorithm.

It might help readers of [2] if you changed the variable identifiers to
correspond in the two routines.

Those who quote results should identify, with versions, the browser, the
operating system, the hardware, etc.

I see that I wrote that using a Swap method with "this" was [only
slightly] slower.

The following should be slightly faster than the Shuffle in js-shufl.htm
and appears to work; the loop index handling is changed. NOT VERIFIED :

function Shuffle(Q) { var J, K, T;
J = Q.length; do { K = Random(J--)
T = Q[J] ; Q[J] = Q[K] ; Q[K] = T } while (J)
return Q }

Nominally, it saves two operations (+1 & >0) per loop.


Just to add to the confusion, it should be possible to test a JavaScript
shuffle at the Windows Command Prompt using WSCRIPT or CSCRIPT. Or, for
that matter, in Excel and maybe Word. And I think I read that one can
run the "DOS" if Windows without running Windows - that would make
timing more reliable, of course