TechTalk

I am busy with a coding assignment as part of my Honours degree in computer science. It is nice and challenging, the correctness, in other words, soundness and completeness, of our implementations, although counting the majority of the marks, is not the only thing we will be assessed on, how efficient our implementations are, in terms of speed of execution and size of output, also counts towards our marks. So I started to research a little on implementing more efficient code. Some real neat things you can do to, automagically make code more efficient…

Use the correct data structure for the job at hand. Using the STL is one very easy step, the STL or Standard Template Library, are a set of optimized template data structures, which can replace normal data structures like arrays and linked lists, this not only safes time in terms of implementation but they are also optimized for speed.

Use loops only when needed, don’t put code in a loop that does not belong there. Obvious?

Some magic? Instead of using multiplication rather use some other faster operation. This is not as easy to achieve but when implemented correctly it can make your code super fast. One thing I always do is:


#DEFINE POW2(x) 1 << x


This small piece of code will be used to calculate powers of 2 very fast and efficiently. Instead of calling math.pow(2,3) you can use POW2(3), which will also return 8 but just way more efficiently. By bit shifting a value you can calculate powers of 2. Bit shifting can also be applied to indexing of pointer arrays to have super fast array access. (but this falls outside of scope, i am not going to explain pointer arithmetic here!)

Check out other highly optimized code and learn. What is the most optimized pieces of code out there? Glad you asked, it is non other than games, yes games.
take this function floating all over the web:


float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // Yummy!
i = 0x5f3759df - ( i >> 1 ); // Magic number
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}

This is from Quake 3 and it is a, very, very efficient way to calculate inverse square roots of floats… I sometimes just put this in my code because i can, it is sooo elegant and fast!
Read more on this…
The compiler self, is for some reason overlooked sometimes? using /ox compiler directives is a very good way to optimize code effortlessly. Read your compiler docs for more on this…

Have fun….

Bookmark me: