Home ›

Javascript algorithm performance : And the winner is ...

Christian Harms's picture
by Christian Harms on Thu, 12/02/2010 - 07:32
in

Our little programming contest was fun and we can learn something about best practices in javascript algorithm performance. I have prepared some micro benchmarks for common code sniplets to find the best variant. After the section with the micro benchmarks you can find the best-performed solution by running the JSLitmus test and browse through the javascript code. And yes - our co-author Matthias had the best solution with factor 20-35 faster than the clean code variant. No solution is close with the performance to Matthias' solution!

Knowing some javascript performance hints are importend. The different javascript interpreter with Just-In-Time-Optimizer can offer some surprise in the following basic code examples.

  • Adding Numbers to an Array
  • Using code in loop-header or Body
  • Round down a Number
  • Using linear Array or Object (=hashmap) for caching Numbers
  • Find a substring in a String


Adding Numbers to a Array

The clean code solution forced you to use the push-method to add a number to the Array. Is this the best way?

  1. benchArrayPush = function(count) {
  2.     var a = [];
  3.     while (count--) a.push(count);
  4. };
  5. benchArrayLength = function(count) {
  6.     var a = [];
  7.     while (count--) a[a.length] = count;
  8. };
  9. benchArrayLocal = function(count) {
  10.     var a=[], l=0;
  11.     while (count--) a[l++] = count;
  12. };
  13. benchArrayFixedLocal = function(count) {
  14.     var a=new Array(count), l=0;
  15.     while (count--) a[l++] = count;
  16. };

  • Array.push is only in Chrome faster than the other variants
  • Using a local variable as index instead of the Array.length attribute is in opera and FF 3.6 faster
  • Why is defining a Array with the end length slower than Array.push in Chome?

conclusion: The variant with using Array.length has good performance and dont need an extra variable. One point for clean code!


Using code in loop-header

Instead of call all operation in the body of a loop, you can put simple operation in the head of a loop. This is not clean code, but all operation can seperated by a ",". Is there an optimizer who accept this coding style as performant?

  1. benchLoopHeader = function(count) {
  2.     var i,j,i1=0,i2=0,i3=0,i4=0,i5=0,i6=0,i7=0,i8=0,i9=0, sum=0;
  3.     for (j=10;j;j--)
  4.         for (i=count; i; i1++,i2++,i3++,i4++,i5++,i6++,i7++,i8++,i9++,i--)
  5.             sum++;
  6. };
  7. benchLoopBody = function(count) {
  8.     var i,j,i1=0,i2=0,i3=0,i4=0,i5=0,i6=0,i7=0,i8=0,i9=0, sum=0;
  9.     for (j=10;j;j--)
  10.         for (i=count; i; i--) {
  11.             i1++;
  12.             i2++;
  13.             i3++;
  14.             i4++;
  15.             i5++;
  16.             i6++;
  17.             i7++;
  18.             i8++;
  19.             i9++;
  20.             sum++;
  21.         }
  22. };
  23. benchLoopLine = function(count) {
  24.     var i,j,i1=0,i2=0,i3=0,i4=0,i5=0,i6=0,i7=0,i8=0,i9=0, sum=0;
  25.     for (j=10;j;j--)
  26.         for (i=count; i; i--) {
  27.             i1++;i2++;i3++;i4++;i5++;i6++;i7++;i8++;i9++;sum++;
  28.         }
  29. };

conclusion: The loop body solution has no performance problems comparing with the other variants. You can use the clean coding style - second point !

Round down a Number

The Math.floor function is defined to round down and Math.ceil for rounding up. But are these function the best choice?

  1. benchIntegerFloor = function(count) {
  2.     var i = 7.7, r;
  3.     while (count--) r = Math.floor(i);
  4. };
  5. benchIntegerParseInt = function(count) {
  6.     var i = 7.7, r;
  7.     while(count--) r = parseInt(i);
  8. };
  9. benchIntegerParse10 = function(count) {
  10.     var i = 7.7, r;
  11.     while(count--) r = parseInt(i, 10);
  12. };
  13. benchIntegerBinaryOr = function(count) {
  14.     var i = 7.7, r;
  15.     while(count--) r = i|0;
  16. };

  • Using parseInt force the javascript interpreter to cast the Number to a String before parsing - this is slow!
  • If you use the bitwise OR all browser are very fast to convert it into an 32 bit integer. If your Number is greater than 2^32 the OR-variant will fail.

Conclusion: if your Number range use only 32-bit values (like in the contest) bitwise OR is the fast option, but not clean code. 1 point against clean-code.


Using Array or Object for caching Number results

For the pre-calculated results is an Array the right container as Cache - or is the standard JavaScript Object better?

  1. benchCacheArray = function(count) {
  2.     var a=[], i, j, c;
  3.     for (i=count/2; i; i--) a[i]=i;
  4.     for (i=count/2; i; i--) c = a[i];
  5. };
  6. benchCacheObject = function(count) {
  7.     var a={}, i, j, c;
  8.     for (i=count/2; i; i--) a[i]=i;
  9.     for (i=count/2; i; i--) c = a[i];
  10. };

  • Opera / Chrome are factor 6 faster than FF while accessing Object or Array!
  • There is no better performance from FF 3.6 to FF 4
  • Chrome has optimized the Array access with Numbers

conclusion: Using an Array for cached Number results is Ok, but the hashmap/Object variant is fast, too! Next point for clean code!


Find a substring in a String

What is the fastest method to find a substring in an given String? Many commentators used theString.indexOf-method, only one anonymous writer used the RegExp("7") constructor.

  1. benchStringMatch = function(count) {
  2.     var seven = "12734", res;
  3.     while (count--) res = seven.match(/7/);
  4. };
  5. benchStringRegExTest = function(count) {
  6.     var seven = "12734", res, hasSeven = new RegExp("7");
  7.     while (count--) res = hasSeven.test(seven);
  8. };
  9. benchStringIndexOf = function(count) {
  10.     var seven = "12734", res;
  11.     while (count--) res = seven.indexOf("7")!==1;
  12. };

  • String.match is factor 3 -10 slower than a predefined RegExp Object.
  • the String.indexOf method is in both Firefox very fast
  • to find one substring in many Strings the RegExp Object is in Opera / Chrome faster than String.indexOf

conclusion: Find the best variant for your usage. Or use browser-optimized code between FF/Chrome - one point against clean code.



Check the best solution for the game of forfeit



Tipp: Maximize your browser because the javascript code has fixed font width.

clean code in JavaScript

Good news for JavaScript number cruncher. Your performance depends on your algorithm and not on cryptic hacks in JavaScript!

AttachmentSize
beautify_min.js.txt16.52 KB

Comments

HTML all you need to know» Blog Archive &raquo's picture
Pingback
HTML all you need to know» Blog Archive &raquo (not verified) - Thu, 12/02/2010 - 21:25

[...] here to see the original: Javascript algorithm performance : And the winner is … | united … Related Posts:Symphonious » JavaScript Performance: For vs ForEachIE9's amazing Javascript [...]

Javascript algorithm performance : And the winner is &#'s picture
Pingback
Javascript algorithm performance : And the winner is &# (not verified) - Thu, 12/02/2010 - 21:31

[...] Czytaj więcej: Javascript algorithm performance : And the winner is … | united … [...]

Jon Hohle's picture
Error in the benchLoopLine function
Jon Hohle (not verified) - Thu, 12/02/2010 - 23:23

The `benchLoopLine` implementation performs a different calculation than the rest of the functions in that test. The expressions in the body of the loop should be separated by commas, not semicolons for an equivalent computation.

Christian Harms's picture
Copy/Paste Error
Christian Harms - Fri, 12/03/2010 - 09:38

Very attentive! A look im my source it was only a copy/paste error from emacs to the blog editor. I correct the code example - the benchmark doen't changes.

Anonymous's picture
benchStringRegExSearch =
Anonymous (not verified) - Fri, 12/03/2010 - 08:43

  1. benchStringRegExSearch = function(count) {  
  2.   var seven = "12734", res, hasSeven = /7/;    while (count--) res = seven.search(hasSeven)!==-1;
  3. };

Performed faster for me in FF 4.0b7 than using .test when finding a substring.

Anonymous's picture
Substring .match
Anonymous (not verified) - Fri, 12/03/2010 - 08:49

Oh and

  1. benchStringMatch = function(count) {
  2.     var seven = "12734", res;
  3.     while (count--) res = seven.match(/7/);
  4. };

is an unfair comparison to the others as it is creating a regex object on the fly on every iteration.
Something like:
  1. benchStringMatch = function(count) {
  2.     var seven = "12734", res, hasSeven = /7/;
  3.     while (count--) res = seven.match(hasSeven);
  4. };

Is much faster (although still much worse than the other options)

Christian Harms's picture
unfair comparison ...
Christian Harms - Fri, 12/03/2010 - 09:42

Yes - but this was a code line in one of the posted solutions. Building a RegEx-Object is mostly better than using it on-the-fly.

Twitter Trackbacks for Javascript algorithm performance : A's picture
Pingback
Twitter Trackbacks for Javascript algorithm performance : A (not verified) - Fri, 12/03/2010 - 10:54

[...] Javascript algorithm performance : And the winner is ... | united-coders.com united-coders.com/christian-harms/javascript-algorithm-performance-and-the-winner-is – view page – cached Our little programming contest was fun and we can learn something about best practices in javascript algorithm performance. I have prepared some micro benchmarks for common code sniplets to find the best variant. After the section with the micro benchmarks you can find the best-performed solution by running the JSLitmus test and browse through the javascript code. And yes - our co-author Matthias... Read moreOur little programming contest was fun and we can learn something about best practices in javascript algorithm performance. I have prepared some micro benchmarks for common code sniplets to find the best variant. After the section with the micro benchmarks you can find the best-performed solution by running the JSLitmus test and browse through the javascript code. And yes - our co-author Matthias had the best solution with factor 20-35 faster than the clean code variant. No solution is close with the performance to Matthias' solution! View page Tweets about this link [...]