C – Optimization and tricks

My project's page

C – Optimization and tricks

10 March 2017 Programming 0

Hello everyone. Lately, working on a C project it happened to be dealing with a few tips regarding the optimization.

I found few information surfing the net so I studied the GCC documentation and several articles about the programming language, and decided to share them, even if small, tricks with you.
I will try to be as clear as possible to avoid misunderstandings. To understand this article are required basic knowledge related to arrays and pointers.
Well, after this boring introduction we pass the point. In the program optimization phase, one of the first things to consider is the use of arrays and indexes. To access an element of an array using indexes the compiler must perform a series of calculations, especially multiplications. My advice if you want to optimize a program that makes extensive use of arrays is to see these structures for what they really are: a pointer to the first element to which apply the pointer arithmetic.

At first glance this approach might seem confusing, but it is quite simple, it just needs to reason about a bit. Using pointer arithmetic, the increase of a pointer is reduced to a trivial amount that requires much less computational resources.
Snippets like those in the example below would be best to avoid them if your goal is to do a much faster and optimized program.

An alternative fully equivalent to this code (although improved) could be this:

We can see that this code could be written a little differently and more clearly using the operator of post-increment getting a snippet like this:

Reflecting for a moment we can see that the post-increment operations are slightly slower than pre-increment once: this is because the compiler is obliged to keep a copy of the old value, return it not yet increased, run the code and make the increase. If you made few iterations all this has a insignificant weight, but I can assure you that in a high number of iterations the difference in terms of performance and computational complexity is significant.
This is why I thought of a solution that uses only pointer arithmetic and pre-increment.
This should be the end result:

In the snippet above I’ve decreased the pointers and then increase them in the for loop without losing information. Having reached this point, I was happy with my program because I was able to optimize it and to compact the code. But that’s not all: there is a serious mistake in my program, can you notice it yourself?

Ok, I’ll tell you if you had not noticed. Talking to a friend and rereading a moment the ANSI C manual, in section 6 (about arrays and pointers) I noticed that what I had done was wrong at all well: despite this program works on almost all of the CPU is a undefined behavior. Decrementing the pointer to the first element of an array makes me get out of the array’s dedicated memory. On some compilers or CPU that causes the program to lock up and throws an exception that would be: Out of Memory or Segmentation Fault. In this order, I immediately rushed to correct this reproach. In this case the correction was rather trivial and obvious, I show:

Perfect, now I have the soul in peace and the program works correctly without any “unsafe” code. Arrived at this point we can try to analyze briefly this piece of code and relate it to the background. As we can see, compared to the first snippets I do not use neither indices nor a post-increment operators, I simply use pointer arithmetic and pre-increment operators.

I hope I was clear enough, for any doubt or error reporting as well write in the comments. Soon I will publish other guides, including one concerning pointer arithmetic.

Leave a Reply

Your email address will not be published. Required fields are marked *