General C/C++ Optimizations

Discussions Regarding Coding (C/C++/Objective-C Mainly)

General C/C++ Optimizations

Postby L. Spiro » Tue Jul 26, 2011 8:21 am

These few tips are often overlooked but can be easily integrated into your daily coding routine in order to speed up your code.

For Loops
When iterating through an array, it is common to start at index 0 and go to the end.
Sometimes this order is necessary for algorithmic correctness, but when the order of the traversal does not matter it is always faster to start at the end of the list and go to 0.
There are two loops for doing this depending on whether you are using a signed iterator or an unsigned iterator.
Signed:
Code: Select all
for ( int i = iTotal; --i >= 0; ) {
    // Do whatever.
}


Unsigned:
Code: Select all
for ( unsigned int i = uiTotal; i--; ) {
    // Do whatever.
}


Logic
There are 4 primary reasons for this order:
  • The compiler has many ways to test values against 0. It is always faster than testing against any other number, even if the number is loaded into a register.
  • In situations such as this:
    Code: Select all
    for ( int i = 0; i < pObj->Total(); ++i )

    the compiler may or may not cache the result of pObj->Total(). If not, it will incur the overhead of a function call for every iteration of the loop.
    Even if you are sure your compiler will do the caching, it certainly won’t in debug mode, and in debug mode function calls incur an even more severe cost. Debug builds may be slower by default, but there is no reason not to help them get a bit more speed; it is for your own good. A backwards loop guarantees the function is called only once, and also frees up a register.
  • It implicitly solves problems with deleting items from lists while traversing them. If you start from 0 and go up, any deletion you make will need an adjustment to i in order not to stkip the next item.
  • It is just faster to type. Compare the lengths in characters:
    Code: Select all
    for ( unsigned int i = uiTotal; i--; ) {

    Code: Select all
    for ( unsigned int i = 0; i < uiTotal; ++i ) {


Division
Avoid division where possible. It can be up to 25 times slower than multiplication.
In this example, we are dividing by a constant number:
Code: Select all
for ( unsigned int i = 512; i--; ) {
    float fRatio = i / 512.0f;
}

It is better to multiply by the reciprocal. And to be sure the compiler can optimize this correctly, it is best to move the reciprocal to the left side, since multiplication is order-independent.
The fixed version becomes:
Code: Select all
for ( unsigned int i = 512; i--; ) {
    float fRatio = (1.0f / 512.0f) * i;   // Anyone who wants to understand this can figure it out pretty easily, so this does not abstract code too much.
}


In some cases this is impossible because you don’t know the divisor. The most common example is in vector normalization. Naturally, a division must be made here, but one common mistake is to unnecessarily divide repeatedly:
Code: Select all
float fLen = x * x + y * y + z * z;
if ( fLen ) {
    fLen = ::sqrtf( fLen );
    x /= fLen;
    y /= fLen;
    z /= fLen;
}

This common mistake is very easy to avoid by caching the reciprocal and using it for repeated multiplication instead of repeated division:
Code: Select all
float fLen = x * x + y * y + z * z;
if ( fLen ) {
    fLen = 1.0f / ::sqrtf( fLen );
    x *= fLen;
    y *= fLen;
    z *= fLen;
}


There are other cases where division is unavoidable and only performed once, so caching the reciprocal is pointless. However there is a chance that the division may not be necessary to perform if the function can exit early. The division operation should be performed as late as possible.
Computing the closest point on a triangle to a given point in space is one example of this.
If the closest point on the triangle is on the face of the triangle or on an edge, one division is necessary. However if we can prove quickly that the closest point on the triangle to a given point in space is one of the vertices of the triangle, we can return that point without performing any divisions at all and we have saved time.


This will be updated as I have time.


L. Spiro
It is amazing how often people try to be unique, and yet they are always trying to make others be like them.
- L. Spiro 2011
L. Spiro
Site Admin
 
Posts: 54
Joined: Thu Jul 21, 2011 2:59 pm
Location: Tokyo, Japan

Re: General C/C++ Optimizations

Postby kemicza » Sat Jul 30, 2011 3:56 pm

Very useful, thanks.
kemicza
I Have a Question
 
Posts: 1
Joined: Sat Jul 30, 2011 3:54 pm

Re: General C/C++ Optimizations

Postby L. Spiro » Sat Jul 30, 2011 9:42 pm

No problem. Hoping to get more content up soon.


L. Spiro
It is amazing how often people try to be unique, and yet they are always trying to make others be like them.
- L. Spiro 2011
L. Spiro
Site Admin
 
Posts: 54
Joined: Thu Jul 21, 2011 2:59 pm
Location: Tokyo, Japan


Return to Coding

Who is online

Users browsing this forum: No registered users and 0 guests

cron