Loop Optimization--Part 3 of Chapter 10 from Speed Up Your Site (3/6)--WebReference.com

[previous] [next]

Speed Up Your Site, Chapter 10: Optimizing JavaScript for Execution Speed

Unroll or Eliminate Loops

Unrolling a loop reduces the cost of loop overhead by decreasing the number of times you check the loop condition. Essentially, loop unrolling increases the number of computations per iteration. To unroll a loop, you perform two or more of the same statements for each iteration, and increment the counter accordingly. So instead of this:

var iter = number_of_iterations;
for (var i=0;i<iter;i++) {
  foo();
}

Do this:

var iter = multiple_of_number_of_unroll_statements;
for (var i=0;i<iter;) {
  foo();i++;
  foo();i++;
  foo();i++;
  foo();i++;
  foo();i++;
  foo();i++;
}

I've unrolled this loop six times, so the number of iterations must be a multiple of six. The effectiveness of loop unrolling depends on the number of operations per iteration. Again, the simpler, the better. For simple statements, loop unrolling in JavaScript can speed inner loops by as much as 50 to 65 percent. But what if the number of iterations is not known beforehand? That's where techniques like Duff's Device come in handy.

Duff's Device

Invented by programmer Tom Duff while he was at Lucasfilm Ltd. in 1983,^[16] Duff's Device generalizes the loop unrolling process. Using this technique, you can unroll loops to your heart's content without knowing the number of iterations beforehand. The original algorithm combined a do-while and a switch statement. The technique combines loop unrolling, loop reversal, and loop flipping. So instead of this (see Listing 10.15):

Listing 10.15 Normal for Loop

testVal=0;
iterations=500125;
for (var i=0;i<iterations;i++) {
  // modify testVal here
}

Do this (see Listing 10.16):

Listing 10.16 Duff's Device

function duffLoop(iterations) {
  var testVal=0;
  // Begin actual Duff's Device
  // Original JS Implementation by Jeff Greenberg 2/2001
  var n = iterations / 8;
  var caseTest = iterations % 8;  
  do {
    switch (caseTest)
    {
    case 0: [modify testVal here];
    case 7: [ditto];
    case 6: [ditto];
    case 5: [ditto];
    case 4: [ditto];
    case 3: [ditto];
    case 2: [ditto];
    case 1: [ditto];
    }
    caseTest=0;
  }
  while (--n > 0);
}

Like a normal unrolled loop, the number of loop iterations (n = iterations/8) is a multiple of the degree of unrolling (8, in this example). Unlike a normal unrolled loop, the modulus (caseTest = iterations % 8) handles the remainder of any leftover iterations through the switch/case logic. This technique is 8 to 44 percent faster in IE5+, and it is 94 percent faster in NS 4.7.

---

16. Tom Duff, "Tom Duff on Duff's Device" [electronic mailing list], (Linköping, Sweden: Lysator Academic Computer Society, 10 November 1983 [archived reproduction]), available from the Internet at https://www.lysator.liu.se/c/duffs-device.html. Duff describes the loop unrolling technique he developed while at Lucasfilm Ltd. Back

[previous] [next]

Created: January 27, 2003
Revised: January 27, 2003

URL: https://webreference.com/programming/optimize/speedup/chap10/3/3.html