Friday, January 23rd, 2009

Speed up your JavaScript with memoization and queueing

Category: JavaScript, Performance

<>p>Nicholas C. Zakas is back at it with part two of his Speed up your JavaScript series.

This time he again discusses the problem with loops, and in this case nested loops:

javascript
< view plain text >
  1. function bubbleSort(items){
  2.     for (var i=items.length-1; i >= 0; i--){
  3.         for (var j=i; j >= 0; j--){
  4.             if (items[j] < items[j-1]){
  5.                 var temp = items[j];
  6.                 items[j] = items[j-1];
  7.                 items[j-1] = temp;
  8.             }
  9.         }
  10.     }
  11. }

What can you do to minimize the steps? He first talks about splitting it up asynchronously, and then goes into Doug Crockfords memoizer function, applying it to the standard Fibonnaci:

javascript
< view plain text >
  1. function memoizer(memo, fundamental) {
  2.     var shell = function (n) {
  3.         var result = memo[n];
  4.         if (typeof result !== 'number') {
  5.             result = fundamental(shell, n);
  6.             memo[n] = result;
  7.         }
  8.         return result;
  9.     };
  10.     return shell;
  11. };
  12.  
  13. var fibonacci =
  14.     memoizer([0, 1], function (recur, n) {
  15.        return recur(n - 1) + recur(n - 2);
  16.     });

Finally, he attacks functions that just do too much, and kicks off the pieces so the browser can get back to its work:

javascript
< view plain text >
  1. function schedule(functions, context){
  2.     setTimeout(function(){
  3.         var process = functions.shift();
  4.         process.call(context);
  5.  
  6.         if (functions.length > 0){
  7.             setTimeout(arguments.callee, 100);
  8.         }
  9.     }, 100);
  10. }
  11.  
  12. schedule([doSomething, doSomethingElse, doOneMoreThing], window);

Of course, for serious workload, this is what Web Workers are ideal for. In fact I just saw a new post on using Workers in extensions that shows the API nicely.

Also, just in case you are going for a Google front end position and you want to marry JavaScript and algorithms, how about remembering binarySearch to go along with the earlier bubbleSort:

javascript
< view plain text >
  1. Array.prototype.binarySearch = function binarySearch(find, comparator) {
  2.   var low = 0;
  3.   var high = this.length - 1;
  4.   var i, comparison;
  5.   while (low < = high) {
  6.     i = parseInt((low + high) / 2);
  7.     comparison = comparator(this[i], find);
  8.     if (comparison < 0) { low = i + 1; continue; };
  9.     if (comparison > 0) { high = i - 1; continue; };
  10.     return i;
  11.   }
  12.   return null;
  13. };

Related Content:

  • Caching Scenarios
    Caching is a quick and easy way to save roundtrips between your application and where you store your data. However, it’s not as easy as just...

Posted by Dion Almaer at 6:03 am
6 Comments

+++--
3.3 rating from 18 votes

6 Comments »

Comments feed TrackBack URI

dejavu … and in my “Stressfull procedure? Distribute your task!” entry I implemented the delay and the in-line or propagated scope.
The result with the queue callbacks stack is a slower application that is more responsive instead of a “not that quick” one that is stuck till the end of the loop. As summary, a slower execution for a faster, non modal, interaction, sounds weird, doesn’t it? :D

Comment by WebReflection — January 23, 2009

Just out of interest, regarding the Zakas “schedule” example how would I pass parameters to each function.

Comment by doomedlung — January 23, 2009

I did a “more generic” version of a memoization function not so long ago, if someone’s interested.

http://blog.thejit.org/2008/09/05/memoization-in-javascript/

Comment by philogb — January 23, 2009

@ doomedlung: I tried creating a method for that. It accepts any number of arguments as long as those arguments has a string representation. If you can imporve it please let me know.

You can find it at http://www.jslab.dk/library/Function.memoize

Comment by Tavs — January 23, 2009

I like building the memoization right into the function, using the fact that a function is an object that can have properties.

Comment by Nosredna — January 23, 2009

Wow, takes me right back to Intro to Programming…nice.

Comment by mjuhl — January 26, 2009

Leave a comment

You must be logged in to post a comment.