Week 10 Day 1 - Fast Inverse Square Root and Duff's Device
8We started off by reviewing Makefiles, as I am trying to encourage you all to make your own Makefiles and to feel comfortable tweaking them to squeeze more performance out of your code, or to reduce build times.
Next we reviewed pipelining again, and how RAW dependencies cause stalls in the pipeline, and talked about how to reorder instructions to minimize stalls again. We then reviewed IEEE 754 format.
We then studied two of the most horrible and also awesome algorithms known to computer scientists: the Fast Inverse Square Root algorithm and Duff's Device.
Inverse square roots are used when normalizing vectors. To normalize a vector means to make it of length one. For example, the vector {3,4} has a length of 5, so to normalize it you divide each element of the vector by the length, giving {3/5,4/5} as the result. Dividing by the length of a vector is... an inverse square root.
The Fast Inverse Square Root algorithm is a lossy approximation of doing a real square root, but it is good enough (4% error, or less than 1% error with one iteration of Newton's method) for computer graphics. While you might see 4% error with the human eye, less than 1% error is usually not perceptible
unless you're really looking for it. In video games, speed is more important than accuracy. So this ungodly hack of an algorithm is used to make it go quickly. Depending on your architecture, it can be very significantly faster. If you want more accuracy, you can slow it down to get more precision as well.
Duff's Device involves abusing the syntax of the C (and C++) language to do loop unroll 8 instructions at a time (which speeds up code significantly) without requiring the input to be a multiple of 8 (which is something I often do, it's nearly free to pad arrays these days). So if you're going to do 35 instructions in a tight loop, it will do four iterations of 8 instructions each, and then one iteration of 3 instructions. (4x8 + 3 = 35 instructions) Look at the syntax and cry. Or laugh? It's up to you.