Title: Increase your Program's Execution Speed?

I asked The Harpist to add a commentary because the subject is one where experience and awareness of changing conditions is important, Francis

Note that these tips are in no particular order. If anybody has anything that they could add to this, why not write in? Also, please note that these tips are for increasing program execution speed, which may be at the expense of program maintainability, reusability, portability, and possibly (almost certainly) size as well.

1. Think about the types which you are using for variables. Characters are sometimes twice as fast as integers, and if integers stay in their range, they could be used instead. If you're concerned about your program looking nice with descriptive types, you could use #define or typedef, eg. #define shortNumber unsigned char.

Also, avoid floating point numbers like the plague - they can be eighty times slower than characters, unless you have a floating point co-processor. You could multiply the value by a large number and process it in terms of that, and the extra code needed to do so shouldn't take nearly so much time as the floating point arithmetic. For example, instead of multiplying something by 0.8, multiply it by 4 and divide it by 5, or, instead of multiplying something by x where x needs accuracy of 0.01, multiply by 100x and divide by 100. Think carefully about whether you would store the floats in ints, chars, or longs.

int x;
int temp;
/* code initialising x */
temp = (x>>1 + x) >> 1;
// temp is now 3/4 of x
temp= temp + temp >> 4 + temp >>8;
// temp is now  0.7998046875 of x

On the subject of types, type conversions often take rather a lot of time as well, so try to avoid them when they are not necessary. For example, I have often seen code which has a function which takes, say, ints as parameters, and most of what it does to them is pass them to another function which takes chars as parameters. This means that, if the program passes chars to the function, it has to convert them to ints and back to chars and all for apparently no reason (there could be exceptions, of course).

2. Try doing various things with the compiler. Some compilers have an "optimise for speed" option, and turning this on sometimes helps. Be careful about compiler optimisations, though - they may introduce non-standard exceptions in areas such as type conversion. I have seen a "fast floating point" option, which, while it does speed up the floating point, inhibits all conversions, explicit or implicit, between floating point and non-floating point numbers.

Also, look for options like "Automatic register variables" to automatically store variables in CPU registers when they can, or, better, turn these options off, and use the register keyword to pick the best variables which could be register variables - the ones most often used.

You could try running your program through an executable file compressor such as PkLite or LzExe - this may improve the loading time, and some compressors also have the option to optimise the header. Make sure that you turn the debugging information off when you do this.

It is a good idea to turn the debugging information off anyway unless you really need it. Most debugging jobs I have come across could be done with a print statement in the right place, and anyway, I don't know about anybody else but my debugger tends to be rather unreliable. On the subject of debugging, beware testing routines which take time themselves - I have in the past spent weeks trying to optimise a really slow piece of code, and it turned out that what was really slowing it down was the clumsy algorithm I put in to time its execution speed!

3. Think about the structure of your program. Don't forget that the program that you design to make readable need not be the fastest implementation. Try to avoid using virtual functions in classes, since these can slow down execution as the program has to decide which function to call. Avoid unnecessary recalculations by storing the values in variables, for example, for (int i=0; i<=10; i++) printf("%d\n", myfunc(2*b)); could be made quicker by for (int i=0, int j=myfunc(2*b); i<=10; i++) printf("%d\n", j); Be careful, though, whThe last of these is very important. An error handling routine that has never been checked is next to useless. Debuggers allow you to change the value of critical variables and thereby force execution down little used paths.en doing this - some calculations are quicker left as they are, and sometimes the value may be different each time, in which case, leave it!

void fn (const int * cpi, int * pi){
  *pi+= *cpi;  // line A
  printf("%d", *cpi);  // line B
}

In some cases when a function performs a calculation based on its parameter and nothing else, and the parameter can be of a limited number of values, it may be better to store the values given by the function at the start of the program for any of the parameters used. For example, if you needed to calculate the sines of integer angles between 0 and 360 degrees use a statement like "#pragma startup" (Borland C++ 3.0) or something similar to execute a function when the program starts which initializes an array with the values necessary, obtained by calling the functions if you like - or you could even embed the code into the executable, and then just use the array. An example follows, which is also an example of avoiding the use of floating point:

const float deg2rad=180/M_PI;
long sine[360], cosine[360];
void initTrig() {
  for (float lp=0; lp<360; lp++) {
  // lp is float because of trig functions
    sine[lp]=sin(lp/deg2rad)*65536L;
    cosine[lp]=cos(lp/deg2rad)*65536L;
  }
}

#pragma startup initTrig
#define angleRange(angle) \
  while ((angle)<0) (angle)=(angle)+360;\
  (angle)=(angle) % 360

// rotation about the origin-not a float in sight
void rotate(long &x, long &y, int angle) {
  angleRange(angle);
  long x2= y*-sine[angle]/65536L+x*cosine[angle]/65536L;
  y=x*sine[angle]/65536L+y*cosine[angle]/65536L;
  x=x2;
}

inline void angleRange(int & angle){
  angle %= 180;
  if (angle<0) angle += 180;
}

inline void angleRange(int & angle){
  angle %= 180;
}

#define angleRange(x)  x%180

void rotate(long & x, long & y, int angle) {
  angleRange(angle);
  long x2= (x*sine[angle + 90] -y*(sine[angle]) >> 16;
  y=(x*sine[angle]+y*sine[angle+90]) >> 16;
  x=x2;
}

It is sometimes worth using macros instead of small functions, as there is an overhead in calling a function. A function which added its two arguments, for example, would be better as a macro. How much execution time you could save here is dependent on how big you don't mind your program getting - if you implement larger functions as macros, you may save more time, especially functions which are called often. Or, you could include the source in your main module - optimising at each call. There are disadvantages in this approach: if you were to change the function, you may run into problems, and there are also problems with static variables. If you run the program through an executable file compressor, there shouldn't be too many problems with the size, unless you run out of memory - executable file compressors rarely cope with overlays.

What I've just been saying is perhaps going a bit too far, though it may be used in a part of the program where speed is really essential, at the sacrifice of maintainability. However, if possible, try to avoid functions like the following, which may be better as several different functions, depending on how it is called:

void myfunc(int whatToDo) {
  switch (whatToDo) {
    case 1: /* this */ break;
    case 2: /* that */ break;
    case 3: /* the other */ break;
    default: printf("Bug!\n");
  }
}

Conditionals also take time - in some small loops, if the value is likely to be the same, it is worth writing out the loop twice, and putting an "if else" statement around the whole lot, rather than writing the loop which consists entirely of an "if else" statement. For example, the following:

for (int i=0; i<=10; i++)
  if (j==2) {
    /* this */
  } else {
    /* that */
  }

may be quicker when re-arranged as follows, depending on how big you don't mind your program getting (which is why I said SMALL loops):

if (j==2)
  for (int i=0; i<=10; i++) {
    /* this */
  }
else
  for (int i=0; i<=10; i++) {
    /* that */
  }

Don't forget that there can be problems with maintenance, and also to leave it alone if the conditional is likely to change within the loop. Remember, the purpose of optimisation is not to change the function of your program: if in doubt, leave it alone, or at least keep a backup of your original code. In case something does go wrong, it may be worth trying one change at a time only, so you may be able to find and solve the problem quicker.

4. Choose carefully which standard library functions you are going to use. Standard library functions are sometimes designed to work in a variety of ways, sometimes checking for things which your program doesn't really need. For example, if you are writing a game which involves printing to the screen, do you really need to use a function which checks to see if output is being redirected to a file? It seems to me that, in this situation, the likelihood of the user wanting to redirect a player walking across the screen is not really worth the extra time the check takes - why not use a different function instead? If you are quite concerned, you could always add a command - line option to your program to use the old calls, but try to avoid too many conditionals. And why use a function with capabilities of formatting the text when you don't need it to be formatted, or writing in different fonts, etc. when it is not necessary?

Some standard library functions on some compilers rely on external variables - pay attention to these. For example, there may be a variable specifying whether to use BIOS calls or direct screen writes. In some cases, it may be better to write your own functions, at least for parts which need to be quick. If you program in Assembler then that's all the better.

5. Think about the data structures of the program. Try to avoid using the heap whenever it can be avoided. Use of new and delete takes time. Also, it may be worth considering declaring some data static in functions where it is often used, if speed is really necessary. Try to create as many of the program's objects as possible at the start of the program, and destroy them at the end - but don't forget the impli-cations this may have for memory requirements. When deciding a data structure, there are several things to consider, including the speed of accessing the data within the structure (a linked list may take a while), and the speed of altering the structure if necessary (it may take some time to insert data into an array). How the structure is to be used is quite important here.

6. Concentrate on the bottlenecks. Try not to waste time optimising code which decodes the command-line arguments, for example, if it's only called once. (If this example is not only called once, why not?) The code which needs to be optimised is usually the code that would make the most difference if it were optimised. It may be worth concentrating on the parts of the program where speed is necessary to the greatest degree. For example, if programming a game, speed is ideal in routines to play the game, but not so necessary in the editor. There are probably better things to concentrate on when writing a music transcription program than making sure that files are saved to disk in as short a time as possible. The time it takes a database to load doesn't usually matter as much as the time it takes to change records.

7. It may be worth trying to put speed in its proper place. There are other things to consider when writing a program. As an example of this, I have heard of a music program which can draw a score in 0.1 seconds, which may be ideal for some applications, but the way in which the program is written may pose problems if the authors wanted to port it to another platform, or add a major feature to the drawing algorithm having neglected it for long enough to be not sure about how it works. Also, what if the authors were to suddenly die, and nobody else could work out what the program was about? Size is another thing, though not in this example, and also, again not necessarily in this example, the time it takes one to write a program as well, or possibly the time it would take to use some of the routines in other programs. More specialised routines can hinder reuse, but can also increase execution speed.

Well, that's it. If anybody has any more suggestions, it may be worth writing in - there is no need to assume that everybody in ACCU knows everything you do and more. If you think that there's something wrong, please write in as well, for the benefit of readers. And please don't forget the scope of the article, as I keep saying - it is to do with increasing the execution speed of programs, and there may be problems involved in some of the methods. If this isn't clear, people may start writing programs which are quite fast, and then starting again whenever there's a bug, and other people may take offence at seeing some of these methods in print. By the way, for those who would, this isn't the worst that you can get - to end this article, here is a snippet of BBC BASIC code I once saw in a magazine (and I understand that the company which used to publish the magazine is a member of ACCU, but please don't take offence, those were the old days):

1040FORI%=A%TOA%+287STEP21:$I%=STRING$(20,CHR$7)+CHR$0:NEXT
1050A%?166=0:COLOUR1
1330FORJ%=1TOI%-1
1340IFX%(I%)<>X%(J%)GOTO1360
1350IFK%=0K%=J%ELSEK%=-1
1360NEXT
1370IFK%=0PROCNL:GOTO1420
1380IFK%=-1GOTO1320
1390U%(I%)=U%(K%)-3:L%(I%)=31-L%(K%)
1400IFU%(I%)<12ANDL%(I%)<12GOTO1320

Sorry I can't put the complete listing in, but it's full of code like that! The programmer must have had considerable skill debugging it. Oh, and I've just got to include this one:

2200 IF?P%=9 AND HT%(Q%)=0 THEN HT%(Q%)=1:VDU23,246+Q%,0,0,060,60,60,60,255,255:?P%=7:A%?(1+17*Q%)=10+Q%:COLOUR3:PRINTTAB(MX%(Q%),MY%(Q%)‑1)CHR$(246+Q%):SOUND1,1,200,20:ENDPROC

Now we can agree. I always hated the way so many people wanted to hype up BBC BASIC when there were already much better compiled BASICs the other side of the Atlantic.