The Why's of Loop Unrolling

I came across some interesting information today that some here might 
find interesting.

Often in discussing Javascript loop optimization, loop unrolling and 
Duff's Device come up:
http://home.earthlink.net/~kendrasg/info/js_opt/jsOptMain.html
(bottom of page)

And often shortly thereafter, the "But why...?" question arises, and I'm 
yet to find a good answer, just guesses. This leads some (like myself) 
to be skeptical of how dependable the performance benefit really is - 
when is it really appropriate, and when can it do harm? Does adding 1 to 
a variable (or often, subtracting 1) and checking it really harm a loop 
THAT much?

Stepping out of Javascript land for a bit (I know, it's weird out there) 
I came upon this optimization paper from AMD, while optimizing an image 
analysis algorithm written in C#:
http://developer.amd.com/articles.jsp?id=1&num=12

It's an 18 page article but basically it states that:
1) AMD 64 (so surely Pentium 4 as well) CPUs are aggressive out-of-order 
CPUs - they'll ask for far more instructions than they've processed to 
find anything they can do ahead of time. The implication of this is that 
a Javascript interpreter is going to be treated just as aggressively - 
meaning the CPU is digging into your Javascript for out-of-order 
execution opportunities, as disjoint as the scenario may seem.

2) A typical floating-point operation (for example) requires 4 CPU 
ticks, but a new one can be fed to the pipeline each tick. That means 
executing f++; 5 times would normally take 5*4=20 ticks, but with 
Out-Of-Order it can be done in 8 ticks. Note that from what I've read, 
Pentium 4 series CPUs have even longer pipelines, some ops taking over 
20 ticks.

3) The CPU will not violate "dependency chains" - basically, it can't 
unroll most loops because it risks calculating data based on variables 
that aren't ready yet.

So you can see how this very low-level technology is the most likely 
source of the benefit of something as high-level as Javascript loop 
unrolling.

So how many unrollings should you do, and where does the benefit fall 
off? This appears to depend on the CPU. For example, if a CPU has 4 
integer pipelines each taking one tick to process, the optimal loop 
unrolling for an integer op is 4. If a CPU has 4 float pipelines each 
taking 4 ticks, the optimal loop unrolling is a little more complicated. 
You could try 16 - because it can place the first 4 in the 4 pipes, the 
next 4 at the next tick while it waits for the first 4, etc. This would 
cause 16*4 ticks worth of calculations to be processed in just 7 ticks! 
But - unrolling further does offer some benefit because you continue to 
keep the float pipelines fully fed longer (they have to starve during 
the loop increment and check). You would want to use increments equal to 
the number of float pipelines - 4 in this case - so even 32 may have a 
good impact.

So, there's the explanation - it's not that a loop condition hurts 
performance, it's that it doesn't offer any optimization and impedes 
others by creating a dependency chain. Loop unrolling is a way of 
explicitly creating multiple dependency chains the CPU can safely 
process in parallel.

Outside the Javascript world, a process called "Auto Vectorization" 
attempts to do this sort of parallelization automatically during compile 
time, and should a browser implement such a vectorizing compiler, the 
benefits of loop unrolling may evaporate. However, Auto Vectorization is 
for now a buggy process, so loop unrolling may be your best bet for some 
time to come.

Happy loop unrolling,
-Chris Moschini


Unsubscribe
[email protected]

List info
http://www.quirksmode.org/dom/list.html 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/wdf-dom/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/wdf-dom/join
    (Yahoo! ID required)

<*> To change settings via email:
    mailto:[email protected] 
    mailto:[email protected]

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/