4umi.com/web/javascript/optimize

Loop optimization

Basic Javascript

There are good ways to do things, and better ways. Some say optimizing should be part of the scripting process at every stage, some see optimization opportunities in every action, while others are of the opinion it is a step in its own right in the scripting process, and for another group it is a fundamental way of thinking. A basic rule for most is however: Don't.

Write logical, then all will be well. Write not so that your code conforms to this or that, but so that it does what it is for. But in human language, synonyms exist because two words that mean the same thing, do not really mean the same thing after all. It is no different in codeland.

Looping

The test on this page shows differences in performance between various ways of looping. Looping is a very common programming construct, and circumstances may dictate a variety of different approaches. Counting downwards generally seems faster than upwards iteration, and comparing to zero takes less cycles than comparing to other numbers, as does comparing to ranges. Bottom-line: simplify loop conditions, remove invariant code, unroll, flip and reverse. Of special interest is Duff's Device, seen in action in the last two functions. By unrolling in a looping fashion, it is a powerstation. For loops in seven eights, listen to the mad man.

There are great differences in performance of the various browsers as well as platforms. Tests differences are more dramatic in Netscape and Mozilla than in Internet Explorer. The latter generally does everything faster than any other browser.

Balancing

In an optimized script, no character is without justification. Not only the code, also its grammar is optimized. Comments and whitespace are removed, every variable and function name is as short as it can be, but to keep the code maintainable, the names should retain some meaning for the human reader. Make variable s generally hold a string, n a number, and o an object. Another factor for the quality of a functionality is the time wasted on vanity. Balance.

The loops

function _for() {
  for( var i=0; i<R; i++ ) {
    /*dummy();*/
  }
}
function _forback() {
  for( var i=R; i>0; i-- ) {
    /*dummy();*/
  }
}
function _forback2() {
  for( var i=R; i--; ) {
    /*dummy();*/
  }
}
function _while() {
  var i = R;
  while( i-- ) {
    /*dummy();*/
  }
}
function _do() {
  var i = 0;
  do {
    i++; /*dummy();*/
  }
  while( i<R );
}
function _doback() {
  var i = R;
  do {
    i--; /*dummy();*/
  }
  while( i>0 );
}
function _doback2() {
  var i = R - 1;
  do {
    /*dummy();*/
  }
  while( i-- );
}
function _doback3() {
  var i = R;
  if( i>0 ) {
    do {
      /*dummy();*/
    }
    while( --i );
  }
}

function _duff4() {
  var i = R % 4;
  if( i>0 ) {
    do {
      /*dummy();*/
    }
    while(--i);
  }
  i = parseInt( R / 4 );
  if( i>0 ) {
    do {
      /*dummy();*/
      /*dummy();*/
      /*dummy();*/
      /*dummy();*/
    }
    while(--i);
  }
}
function _duff8() {
  var i = R % 8;
  if( i>0 ) {
    do {
      /*dummy();*/
    }
    while( --i );
  }
  i = parseInt( R / 8 );
  if( i>0 ) {
    do {
      /*dummy();*/
      /*dummy();*/
      /*dummy();*/
      /*dummy();*/
      /*dummy();*/
      /*dummy();*/
      /*dummy();*/
      /*dummy();*/
    }
    while( --i );
  }
}

The testform

Control
 
 
Output

Duff’s Device

The magic of Duff’s Device was discovered by Tom Duff when he was at Lucasfilm. Working in C, he saw an optimization opportunity when he decided to unroll all the instructions he could out of an inner loop that copied data serially onto an output port. He then realized that the unrolled version could be implemented by interlacing the structures of a switch and a loop. The offspring of this marriage are all speed.

register n = (count + 7) / 8;   /* count > 0 assumed */

  switch (count % 8)
  {
  case 0:        do {  *to = *from++;
  case 7:              *to = *from++;
  case 6:              *to = *from++;
  case 5:              *to = *from++;
  case 4:              *to = *from++;
  case 3:              *to = *from++;
  case 2:              *to = *from++;
  case 1:              *to = *from++;
                    } while (--n > 0);
  }

Reference