Optimization Tips and Tricks

March 29, 2017 | Views: 2790

Begin Learning Cyber Security for FREE Now!

FREE REGISTRATIONAlready a Member Login Here

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

I found some information surfing the net, so I studied the GCC documentation and several articles about the programming language and decided to share the tricks with you.
I will try to be as clear as possible to avoid misunderstandings. To understand this article, all that is required is a basic knowledge related to arrays and pointers. Well, after this boring introduction we get to 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 applies 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.

void sum(int* first, int* second, int* sum, int elements)
{
 for (int i = 0; i < elements; i++)
     sum[i] = first[i] + second[i];
}

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

void sum(int* first, int* second, int* sum, int elements)
{
 for (int i = 0; i < elements; i++)
     *(sum + i) = *(first + i) + *(second + i);
}

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

void sum(int* first, int* second, int* sum, int elements)
{
 for (int i = 0; i < elements; i++)
     *(sum++) = *(first++) + *(second++);
}

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:

void sum(int* first, int* second, int* sum, int elements)
{
 --first;
 --second;
 --sum;
 for (int i = 0; i < elements; i++)
     *(++sum) = *(++first) + *(++second);
}

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 an 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:

void sum(int* first, int* second, int* sum, int elements)
{
 for (int i = 0; i < elements i++)
 {
     *sum = *first + *second;
     ++first;
     ++second;
     ++sum;
 }
}

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.

Share with Friends
FacebookTwitterLinkedInEmail
Use Cybytes and
Tip the Author!
Join
Share with Friends
FacebookTwitterLinkedInEmail
Ready to share your knowledge and expertise?
1 Comment
  1. Nice explanations, I love it when people push the algorithms further within the capacities of the programming language they use. Good Work! 😀 +10

Comment on This

You must be logged in to post a comment.

Our Revolution

We believe Cyber Security training should be free, for everyone, FOREVER. Everyone, everywhere, deserves the OPPORTUNITY to learn, begin and grow a career in this fascinating field. Therefore, Cybrary is a free community where people, companies and training come together to give everyone the ability to collaborate in an open source way that is revolutionizing the cyber security educational experience.

Support Cybrary

Donate Here to Get This Month's Donor Badge

 
Skip to toolbar

We recommend always using caution when following any link

Are you sure you want to continue?

Continue
Cancel