Computer Science Canada

Code Optimizations

Author:  TheXploder [ Mon Jan 17, 2005 9:48 pm ]
Post subject:  Code Optimizations

Optimizing your code is a crucial part of programming. I will try to cover Turing Optimizations but would also welcome any additional Optimizations for other programming languages, or additional optimizations for Turing.
If you know any way that will achieve the best results in terms of performance with any of the programming language, please share. Sharing of your knowledge will ensure others not make the same mistakes at the very beginning.

So to start off for Turing...

You can use a for inside a for, but don't have a loop in a loop.
Declare as few global variables as possible, and by that I don't want you using values only such as this:

code:

Draw.FillOval(0,0,10,10,1)
Draw.FillOval(10,10,10,10,1)
Draw.FillOval(20,20,10,10,1)
Draw.FillOval(30,30,10,10,1)
//....


Try to see patterns and get them into a for loop:
code:

for i : 0 .. 3
    Draw.FillOval (i * 10, i * 10, 10, 10, 1)
end for

Now you have more freedom you can achieve a greater number of ovals with 3 lines.

But you can achieve even greater freedom with a procedure and using local variables.
code:

procedure circle (x, y, size, clr : int)
    Draw.FillOval (x * size, y * size, size, size, clr)
end circle

for i : 0 .. 3
    circle (i, i, 10 - i, i)
end for

Now as you can see the spacing (position of the circle) will always depend on the size which depends on i as well as the colour depends on i.

And determining this kind of relation will optimize your code.

Author:  md [ Tue Jan 18, 2005 3:04 pm ]
Post subject: 

Quote:
You can use a for inside a for, but don't have a loop in a loop.
Declare as few global variables as possible, and by that I don't want you using values only such as this:

Nesting loops is in general slow, but sometimes there isn't any way around it. A good rule for loops, is use them only when nessary: a loop to draw three circles is slower than three draw calls.

Using as few global variables as possible is good programming practice, but it has zero application to optimization. If anything, by passing parameters that could have been global just slows down your program.

Quote:
Try to see patterns and get them into a for loop:

Not true; loops are faster in a few cases, but in most it is faster to unroll loops.

For example this:
code:

// psudo code...
for( int i = 0; i < 9; i+=3)
{
    drawcircle(position[i], radius[i]);
    drawcircle(position[i+1], radius[i+1]);
    drawcircle(position[i+2], radius[i+2]);
}

is faster than this:
code:

// psudo code...
for( int i = 0; i < 9; i++)
    drawcircle(position[i], radius[i]);

The reason is that there are fewer comparisons between i and 9, and fewer addition calls made during the entire loop. In this case the improvement is small, but when applied to loops that execute millions of times, speed improvements from loop unrolling can be huge.

Quote:
But you can achieve even greater freedom with a procedure and using local variables.
Code:

procedure circle (x, y, size, clr : int)
Draw.FillOval (x * size, y * size, size, size, clr)
end circle

for i : 0 .. 3
circle (i, i, 10 - i, i)
end for

Now as you can see the spacing (position of the circle) will always depend on the size which depends on i as well as the colour depends on i.

Again, this improves code readability, but infact slows down execution. Now instead of having one check, one addition, and one call for each circle (discounting the operations needed to calculate it's size, which are the same) we have one check, one add, and two calls. Procedure calls are among the slowest things you can do, and adding a procedure to wrap another procedure if one of the worst thigns you can do.

To really optimize your code you should remember the following:
1. If you must use loops, make them as few lines as possible, this will allow the processor to keep the loop in it's cache; meaning it doesn't have to keep fetching it from slow memory.

2. Unroll loops where ever possible. If you don't know how many times the loop will execute then doing this is difficult, but it can be done.

3. NEVER, EVER write procedures to wrap other procedures, all you end up doing is adding to the overhead of procedure calls.

4. Optimization is a trade off between code size, and execution time. In some cases it may be faster to copy the body of a small procedure where ever it is called; this is esspecially important in cases where the small procedure is called a large number of times.

There are many other optimizations that can be made, but those four rules are really all you need to write reasonably fast code.

Author:  Martin [ Tue Jan 18, 2005 5:48 pm ]
Post subject: 

Use only inline functions. :p


: