General Programming Lesson 1 -- Difficulty: Easy-Moderate |
June 22nd, 2007 - Math optimizations |
Speeding up small math functions can have a big result if they're something you're doing many times each frame. For instance if you're checking distance on 30 objects 60 times per second, and each distance check involves 1 square root, 3 power functions, 3 subtractions, and 2 additions. Your looking at taking up tens of thousands of cycles per second just on checking distances. Checking distances may be one thing on a list of 50 different things that occur each game loop. Finding a way to optimize your math can make a difference of a couple of frames per second, to 10-15 depending on how math intensive your program may be.
Square root and power (exponential) functions:
The square root function should be avoided whenever it can, but to get a proper distance we usually need the pathagorean theorum so this can't be helped. Also, squaring a number requires the Math.Pow() function which also should be avoided when possible. It is actually slightly faster to multiply the variables out yourself then to use the Pow function. For example, this would be the original unoptimized function:
| public double distanceFromSource(Vector3 source, Vector3 target) { return Math.Sqrt((source.X - target.X) * (source.X - target.X) + (source.Y - target.Y) * (source.Y - target.Y) + (source.Z - target.Z) * (source.Z - target.Z)); } |
And consider the possibility of using 2D Vectors (Vector2) if your 3D game takes place on a single plane or level, like a top-down game, or if your game is 2D. The difference would be that you wouldn't need to check the Z axis, making the function about 30% faster.
While knowing the details of finding distances between two positions is an important lesson, I should note that XNA comes with its own built in function to do this, and it may be even more efficient.
| Vector3 FirstToSecond = Source.Position - Target.Position; float DistanceFirstToSecond = FirstToSecond.Length(); |
As I said earlier, the square root function is relatively expensive, and should be avoided when possible, so when using lengths, there are sometimes ways to avoid using them. For instance, sometimes you want to check if a length is equal to zero, possibly to verify a vector was never defined, or to check for errors, rather than your the .Length() function, you could try this:
| Vector3 FirstToSecond = Source.Position - Target.Position; |
Also, using LengthSquared() works well in situations where you want to simply compare two distances to see which is furthest.
|
float DistanceA = VectorOne.LengthSquared(); |
Division:
Whenever using division by constant values (like 3, or PI), consider using multiplication in it's place. Multiplication takes fewer CPU cycles.
An simple example would be:
Before
| ActivePlayer.Speed /= 4; // Slow player down to 1/4th of their original speed |
Optimized
| ActivePlayer.Speed *= 0.25f; // 1/4 is the same as .25 |
I believe many compilers make optimizations like this for you, so most of the time you will want to use whichever looks better. However I would recommend using *= whenever it looks appropriate as good practice. Additionally, when dividing by an integer value, such as 4, be cautious. In this example, if ActivePlayer.Speed was an integer itself, your division by 4 will result in another integer. So if .speed were 10, we'd get 10 / 4 = 2. If you want a floating point result you need a floating point division, so 10.0f / 4 = 2.5 would work, but usually to be safe, just divide by a float, that way you're not dependant on what your variable's data type is: 10 / 4.0f = 2.5;
Bitwise Operators:
There are some instances where you can speed up your exponential math by less often seen methods, such as the Shift Operator ( << ). This is different than the stream << operator. The shift operator shifts the bits in your number either left <<, or right >>. If you don't know what a bit is yet, get yourself an assembly book or take a class. Assembly may seem like an old dinosaur but there is nothing faster than doing something just like you intend it to be done, which sometimes is only accomplished through assembly.
A left shift by one is the same as multiplying a number by 2:
| 2 * 2; // 4 2 << 1; // 4 |
If you shifted left by two is the same a multiplying by 4.
| 2 * 2 * 2, or 2 * 4 // 8 2 << 2; // 8 |
Shifting right by one is the same as dividing by 2.
| 8 / 2 // 4 8 >> 1; // 4 |
Bitwise operators may not be used often by beginners, but it's never too early to start, here's a good link to get you started. And again, many compilers will do stuff like this for you, but a little extra knowledge never hurt anything.
