Optimising Your C
by bkenwright@xbdev.net
Everyone when learning C or even C++, should know the basics of optimising
your code... as no matter how fast your CPU gets, you always want to squeeze
more and more out of it.... Make your CPU really perform for you. So
we'll go through some common optimisation techniques that would be useful to
just know...or maybe add to some of your code...
Lightning Fast Multiplication and Divide
Now when someone first said to me, how can you improve this line of code:
int i=2;
i = i*4;
Looking at it you think, its i*4....its a single line...it can't possibly be
improved any more...can it? Well this is where your secret knowledge of
binary arithmetic comes in handy, as a binary shift left (<<), or shift right (>>) uses
less CPU time than an arithmetic multiplication.
Shifting left (<<) is multiplying by the power of 2, and shifting right (>>)
is dividing by the power of 2....
Looking at the powers of 2..
2
4
8
16
32
64
128
258
....
So for our little example above, we have:
i = i*4;
and we change it to:
i = i<<2;
Shifting it once, is the same as multiplying it by 2, shifting it two bits,
is the same as multiplying it by 4 etc.
Lets use a real world example... now in the days of dos, or in console game
programming such as GBA or XBOX possibly, you can access memory directly, and
that case memory is seen as a single array of
pixels. And to set a pixel at (x, y) you need to do this:
screen[y*480 + x] = colour;
But 480 isn't a power of 2?....Well this is where the magic comes in.... we
can break 480 into 2 numbers,
51232 = 480
y*(51232) is the same as y*(480)
multiply out gives:
y*512  y*32
And using our otimisation secret we get:
(y<<9)  (y<<5)
So putting it all together gives:
screen[(y<<9)  (y<<5) + x] = colour;
As remember binary shifts are extremely simple operations, and hence
extremely fast...faster then the multiplication operation.
Loops....
Not inside the loop...
One of the first things you need to remember with loops, is try and not put
things inside the loop that you don't have to.... a good and a bad example will
help demonstrate this:
Bad example:
// bad loop example
for(i=0;
i<10; i++)
{
int j = 2; // putting
declarations in the loop when you don't have to
aa[i] =
j;
}
Better example:
// better loop example
int j
= 2;
for(i=0;
i<10; i++)
{
aa[i] =
j;
}
Of course we could put aa[i]=2 etc in the loop...but I was just
demonstrating, that you should try and not put declarations or anything in the
loop if you can avoid it.
Loop unrolling..
Now taking this next loop as an example of how unrolling our code, can
improve its speed
//simple loop
int
indx=0;
for(i=0;
i<=40; i++)
{
aa[indx++].value
= true;
}
Using the wonderful trick of
unrolling, we can improve the speed of our code.
//unrolling the loop to improve speed
int
indx=0;
for(i=0;
i<=40; i+=2)
{
aa[indx++].value
= true;
aa[indx++].value
= true;
}
Why is this faster?... as each time around the loop we do a test to see if
its finished, but with our improved code, where only doing it half as many times. As the code would consist of a conditional jump and a jump
condition.
Loop flipping..
At first this might seem a bit tricky to understand, but its to do with how
the cpu does loops...
// using loop withoutflipping
int
idx=0;
for(i=0;
i<80; i+=2)
{
aa[indx++].value
= true;
aa[indx++].value
= true;
}
// using loop withflipping
int
idx=0;
i=0;
do
{
aa[indx++].value
= true;
aa[indx++].value
= true;
i+=2;
}while(i<80);
Flipping as we've done above, gets rid of the initial conditional jump at the
very start of our loop (first time), and gets ride of one of those jump
instructions from inside the loop. We only have one conditional jump instruction
at the end.
With flipping and unrolling we've improved our execution speed!
NOTE: On a 486 upwards... an ADD costs one cycle, while an IMUL costs between 13
and 42 cycles!. Thats worth noting :)
Further Loop Unrolling
[Under Construction]
Rounding Numbers the Fast Way
A nice example of where you may want to round a number, is when maybe you
want to have your graphics snap to grid?..hmmm??
This speed boost, will only work with numbers that are a power of 2 as with
most optimisation tricks... We do this by AND'ing our number with a bit mask.
An example is always the best way I think... If you wanted to round a number
to the nearest value of 4, you AND the number with 0xFC. In binary this
looks like 1111 1100.
Modulus %..speed up
Well this optimisation trick, only works on modulus numbers that are a power
of 2, and is relatively easy to implement.
How it works, is you take the modulus number and subtract 1 from it, you then
AND it with your number...
e.g.
28 % 8 = 4
Is the same as:
28 & (81) = 4
Again it might seem a bit worrying how this work, but if you look at it at
the binary level...it soon starts to fall into place. For example, 81
gives 7, and the binary of 7 is111.
So
28 > 11100 binary
7 > 00111 binary (e.g. 81)
& 00100 > 4
Using #define to optimise your code
This is a sweet optimisation trick, as each time you call a function its
costing you a small amount of processor time...even if its small. But if
your calling this function from a loop, or the function is very small then why
not use the #define statement. This will put your code inline and uses the
preprocessor.
example:
#define fixetoint(x) ((x) << 8 )
Register Variables ...eax...ebx...
There is a keyword in C called "register" which informs the compiler to try
and have this variable use one of the internal CPU registers and not a a memory
location. And as you should know, nothings faster than the CPU
registers...so you would do you code like this:
register int i;
But remember if you over use the register keyword it can also slow your code
down! But used wisely can give a 1015% speed improvement :)
Sweet Tricks
Usually with experience, and of course time, you learn all sorts of sneaky
tricks that you can put into your code. This is where we go over some of
these here.
Lets say you want to swap two variables.... int a and int b. How would
you go about this? Well the traditional way would be:
int a = 2;
int b = 3;
int temp;
temp = a;
a = b;
b = temp;
But this requires the use of another register/memory location called temp...
How would we do it without temp? Here is the answer:
#define SWAP(a, b) \
a ^= b;
\
b ^= a;
\
a ^= b;
Where of course, ^ is exclusive OR, and a^=b would be the same as a=a^b;
And for those that are a bit sceptical, we'll do a demo with some simple
binary :
a = 11
b = 10
a ^= b => a=01
b ^= a => b=11
a ^= b => a=10
After the operation:
a=10
b=11
Almost like magic :)
A very similar method, to the above one for swapping... is as shown:
#define SWAP(a, b) \
x = xy; \ // (comment:
would be the difference)
y = y+x; \ // (comment: alter y
depending on the difference)
x = yx; //
(comment: alter x by the difference to know get y)
Of course, I prefair the XOR method myself.... but I thought I'd give it a
quick mention, as I remember seeing it once... and its always worth knowing :)
Quick Division By 4
Sometimes it important to know if a number is exactly divisible by
4...especially with 32 bit machines.... a quick way to do this, without
resorting to modulus is to use a bit of binary arithmetic:
UINT i;
if( i & 3 ) // if false, then the number will divide exactly into 4
Lets look at the last 2 bits to see what they mean:
00  0
01  1
10  2
11  3
5 = 0000 0101 // 5/4=1.25
8 = 0000 1000 // 8/4=2
50 = 0011 0010 // 50/4=12.5
60 = 0011 1100 // 60/4=14
Note: I mention it here...but the fact of the matter, if you look at the
simplification of the modulus operation (%) earlier...you'll notice that its the
same.
[More To Be Added]
"inline" keyword
