Chapter 10: Optimizing JavaScript for Execution Speed

Duff's Device Optimization

Invented by programmer Tom Duff while he was at Lucasfilm Ltd. in 1983, Duff's Device generalizes the loop unrolling process. You can unroll loops to your heart's content using this technique, 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.

Ordinary for loop Duff's Device (8) Duff's Fast (8) Duff's Faster1 Duff's Faster2 Duff's Faster3 Duff's Faster4 Duff's Faster5 Duff's Faster6 Duff's Faster7 Duff's Faster8 Duff's Faster9 Duff's Faster10 Duff's Faster11 Duff's Faster12 Duff's Faster13 Duff's Faster14 Duff's Faster15
Total: ms ms ms ms ms ms ms ms ms ms ms ms ms ms ms ms ms ms
Per Cycle: ms ms ms ms ms ms ms ms ms ms ms ms ms ms ms ms ms ms

Note: The first printing of Speed Up Your Site assumed for the faster Duff's Device that n is greater than the degree you unroll the loop. A safer, more universal method is to check for a positive n in each loop, not just the first one in Duff's device.