Original Post
Hello everybody, {edit 09/10/2004: minor corrections, added the "array access" part} Be aware that this is a rather long post. I noticed that there were a lot of posts about code optimisations in the last days . Most of them are clearly dedicated to a particular problem (either having a faster sin/cos/sqrt/whatever or dealing with the classical “what is the faster” issue). Only a few of them are really dealing with real optimisations – I mean : algorithm optimisations.
introduction
Given my personal experience, I would say that optimising your code is not really useful. It usually take a long time to get a 2% speedup, and since time is money, it should not be done unless you really need this 2% speedup. Optimising your algorithm can really improve things. This is not that difficult, since most optimisations are in fact some kind of code organisation change. Sometime, you’ll want to completely change your algorithm in order to get one which is better/faster/more robust/etc. As a professional programmer, I know you don’t do this often – it costs money :/ Anyway, even algorithm optimisations should not be done unless you know it is needed. You must first write working and maintainable code. Then, once everything is tested and works, you may want to optimise the slow parts of your program. I want this thread to be useful for people that are currently in the optimisation process. This “guide” is not intended to be a “how to write optimised code guide”. These are advices and micro-tricks that will solve micro-problems you may have. I will not deal here with any sort of large scale optimisation techniques. Be aware that most optimisations have pros and cons. And read Antareus post below :)on the use of float and double
double are either 64 bits or 80 bits, depending on your compiler settings. IEEE floats are 32 bits. They fit in a general purpose register. The FPU is happy with them. You can use them in SSE code. So : don’t use double – unless necessary, of course, and as a side note if a code needs double then it shouldn’t need code optimisations – use floats. Anything below this line will consider that you are using floats. Your compiler may allow you to use float versions of most of the math library functions. These float versions are usually faster than their double equivalents. They are post-fixed with an “f” : sinf(), cosf(), sqrtf() and so on. For the sake of clarity, I’ll still use the non-float function name – you’ll have to shake your head and say “doh ! I remember he wants to use only floats ! So he do not mean sqrt() here, but sqrtf()”. Simple :)converting from float to ints
When you cast a float to an int, the compiler implicitly calls the ftol() function. ftol() performs a lot of check in order to avoid NaN and other bad float problems. The point is that ftol() is slow. You can rewrite your own ftol() using the FPU – this is only 3 asm instructions – or using a pure integer technique. Of course, you’ll loose all the goodies of ftol() and you may have some weird problems with your newly computed integer value (but hey, that’s the trade between precision and accuracy :P). For those interested, see this site.sin() and cos()
Most sin/cos optimisations come from the good old demo age, when using the FPU was considered as blatantly stupid. Remember that today’s processors are a lot faster than a 8087. Let’s name it: the sin/cos lookup table. I saw some implementations of this one in recent threads, and I have to assume that it is not dead. Surprising ^_^. A correct sin/cos LUT (let’s call it SINLUT for short) do not use a degree index. If you LUT has k x 180 entries (with k = integer > 0) then you won’t be able to achieve very good performances with your LUT, because you’ll need a costly modulus operator. A better solution is to use a LUT with 2^n entries, because of one of the characteristics of 2^n numbers: whatever k (integer, >0) is, k AND ((2^n)-1) < 2^n. The AND operator is very fast and can be paired with a lot of other instructions on our intel processors. Now, what should we use as “n” ? n should be chosen so than 2^n > 360. The precision you’ll get with 256 values for 360° is not that interesting. Remember that is you sin/cos precision is too low then you may have some precision issue in your code, and those may be hard to track and to debug. n = 9 should be ok in most cases. n=10 would create a 4096 byte-long LUT (sizeof(float)*1024) which is also the size of a Windows memory page. There is no speed gain between 512 and 1024 entries (if you manage to have all your 1024 values in a single memory page ; if you fail to achieve that, you may get some page fault penalties (see below) when looping through the array) but you’ll gain additional precisions.sqrt()
The C library square root usually uses the FPU. You may be able to use the SSE reciprocal square root when available (RSQRT, which gives you 1/sqrt(x) – and remember that x / sqrt(x) = sqrt(x)). You may also want to use a lookup table too – I’m not sure it is that interesting. After all, the input of the sqrt() function can be really big : what if your array do not handle it ?fabs()
fabsf() gives you the absolute value of a float. The absolute value of a float can be obtained by zeroing the sign bit of the float – which appear to be the most significant bit of the float. Therefore, an inlined function which only does
int f = (*(int *)(&myFloat)) & 0x7FFFFFFF;
return *(float *)(&f);
array access
Memory access is fast. Well, not exactly. Memory access seems to be fast, unless you run into cache miss or even worse : page faults. On Windows NT4/2k/XP, page faults are not these crappy Win9x crashes. A page fault is a kernel exception which tells the kernel that the needed memory page is not currently available to the process - the corresponding PTE valid bit is clear (... what did he said ? oh, sorry : check here and here for further informations about PTEs). The system then need to load this new page and setup some internal informations. This is slow as hell. [as a side note : starting from WinNT4, the default memory pages size is 4KB]. Cache miss are simpler - this is more a processor problem : the data you want to read/write is not in the processor data cache, therefore the processor data cache needs a refill before you can use it. This is still a very costly information. Now you perhaps wonder what I really want to say. Consider this array (silly, I know, but an array is still an array):
float array[1024][1024];
// code1
for (int x=0; x<1024; x++) {
for (int y=0; y<1024; y++) {
array[x][y] = some_computed_value(x, y);
}
}
// code2
for (int y=0; y<1024; y++) {
for (int x=0; x<1024; x++) {
array[x][y] = some_computed_value(x, y);
}
}
