2010.08.29

Fast Duff’s Device

This week I’ve sent some links about common techniques to improve code performance to the FlashCodersNY mailing list and after sending a link about the Duff’s Device and the Fast Duff’s Device I got really curious if the performance could be improved with simple changes so I decided to do some benchmarks…

To check the benchmark and my implementations: http://jsperf.com/duffs-device
In my opinion the results are pretty much inconclusive since they vary depending on browser/os/version and is also affected by external influences… but usually my 3 implementations runs a little bit faster… (but you have to mind that the original ones are pretty old) – Unfortunately I’ve changed the test names and the implementations after publishing the benchmark so the browserscope data is hard to analyze, but now at least I understand how jsPerf works.

I was expecting that the last version would be always faster since it uses bitwise operation for rounding the value and also uses multiplication instead of division, but bitwise operations have a really strange behavior in JS, sometimes they are really fast and other times they run slower than the native Math methods – I think it happens because the JavaScript engines does a lot of optimizations and maybe the bitwise operations can’t and/or aren’t easily optimized specially since variables aren’t strong typed in JS, but that is just my assumptions, don’t have any technical reference about that or did any other kind of tests, I’m just guessing…

My Implementation


var iterations = 9999; //Number of iterations
var testVal = 0; //Used to test loop speed

/*
 * Fast Duff's Device
 * based on Jeff Greenberg implementation: http://home.earthlink.net/~kendrasg/info/js_opt/jsOptMain.html#fastDuffsdevice
 * @author Miller Medeiros (http://millermedeiros.com/)
 * @version 0.3 (2010/08/25)
 */
var n = iterations % 8;
while(n--){
	testVal++;
}

n = (iterations * 0.125) ^ 0; //multiplication is faster than division in some cases and `XOR 0` removes decimal digits
while(n--){
	testVal++;
	testVal++;
	testVal++;
	testVal++;
	testVal++;
	testVal++;
	testVal++;
	testVal++;
}

Just to quick explain what the bitwise ^ (XOR) 0 does:

alert( 5.25 ^ 0 ); //5
alert( 5.75 ^ 0 ); //5
alert( -5.25 ^ 0 ); //-5
alert( -5.75 ^ 0 ); //-5

And I’ve used multiplication since it is supposed to be faster than division.

Important

Don’t use this kind of optimization unless you really need it!

The gain in performance in some browsers is so small (and some cases even null) that I don’t think it worth using the bitwise operations and division since it makes the code less readable than approach #2 (that uses Math.floor and simple division) is way more readable and have similar performance…

Make sure you confirm that the Duff’s device really improves the performance, even the benchmark demonstrating huge performance gains from normal loops in some cases the performance can be worse, specially since modern JavaScript engines does many optimizations automatically and this kind of technique can potentially “cancel” some of them.

Learn More

A good introduction to Bitwise Operations and a good book about JavaScript performance.

Related

That’s it!


Comments

make sure you confirm that the Duff's device really improves the performance, even the benchmark demonstrating huge performance gains from normal loops in some cases the performance can be worse, specially since modern JavaScript engines does many optimizations automatically and this kind of technique can potentially "cancel" some of them.

Leave a Comment

Please post only comments that will add value to the content of this page. Please read the about page to understand the objective of this blog and the way I think about it. Thanks.

Comments are parsed as Markdown and you can use basic HTML tags (a, blockquote, cite, code, del, em, strong) but some code may be striped if not escaped (specially PHP and HTML tags that aren't on the list). Line and paragraph breaks automatic. Code blocks should be indented with 4 spaces.