Optimization of code Optimization of code is done by applying code transformations to improve performance, like execution time, code size, minimum resource utilization etcetera. These transformations can be made either at a high level or at a low level. In computing, optimization is the process of modifying a system to improve its efficiency. Optimization is a program transformation technique, which tries to improve the code by making it consume less resources (i.e. CPU, Memory) and deliver high speed. In optimization, high-level general programming constructs are replaced by very efficient low-level programming codes. A code optimizing. Optimization is a program transformation technique, which tries to improve the code by making it consume less resources (i.e. CPU, Memory) and deliver high speed. In optimization, high-level general programming constructs are replaced by very efficient low-level programming codes. A code optimizing.

Introduction

This article is intended to introduce softwaredevelopers into the topic of optimization techniques. For this, different optimization techniques will be explored.

Asa first step, I have chosen an easy tounderstand algorithm to which I have applied various optimization techniques:

The problem we will solve is the 3n + 1 problem (details): for every number n between 1 and 1000000 apply the following function:

until the number becomes 1, counting the number of time we applied the function.

Thisalgorithm will be executed for all the numbers between 1 and 1000000. No inputnumber from the keyboard will be read and the program will print the result,followed by the execution time (in milliseconds) needed to compute the result.

Test machine will be a laptop with the following specs: AMD Athlon 2 P340 Dual Core 2.20 GHz, 4 GB of RAM, Windows 7 Ultimate x64.

Languages used for implementation: C# and C++ (Visual Studio 2010).

Prerequisite

N/A

Differentimplementations for the same problem

Theinitial version of implementation: for each number between 1 and 1000000, the abovementioned algorithm will be applied, generating a sequence of numbers until nbecomes 1. The steps needed to reach to 1 will be countedand the maximum number of steps will be determined.

C++ code:

C# code:

I compiled the code for both Debug and Release builds, both 32 bit and 64 bit version. I then ran every executable 100 times and computed the average time(ms) it takes to do the calculations.

Here are the results:

First thing to be observed in the table is thatthe 32 bits program versions are 5 to 7 times slower than the 64 bits versions.This is due to the fact that on x64 architectures one register can hold a long long variable and on x86 we need 2 registers. This means that on x86 operations with long long values are slow. Because of this we will not examine the 32 bits anymore in thisarticle.

Code Optimization Pdf

Second thing to be noticed is the differencebetween Release and Debug builds and, also, that for C# the differences arebigger than for C++.

C Code Optimization Techniques Pdf Pdf

Anotherobservation is the difference between the C# Release version and C++ Releaseversion. This, together with the previous observation, makes me believe that theC# compiler performs optimization better than the C++ compiler (maybe evenemploying some of the optimization techniques we are going to talk aboutlater).

Thefirst optimizations I will apply are related to performing the mathematicaloperations faster by replacing the conventional way of doing them with anunconventional way.

Ifwe look at the above code we see that we have only 3 complex mathematicaloperations: modulo 2 operation(%),multiplication by 3(*) and division by 2(/).

First operation I will optimize is the modulo 2.We know that all numbers are represented in memory as a sequence of bits. wealso know, the representation of an odd number will always have its last bit 1(5= 101, 13 = 1101, etc.) and the representation of an even number will alwayshave its last bit 0( 6 = 110, 22 = 10110). So if we can get the last bit of anumber and test it against 0 we know if a number is odd or even. To get thelast bit of a number I use the bitwise AND operator(&).

In C++, replace:

with:

In C#, replace:

with:

Here are the results:

C++Release version benefits most from this optimization. The difference inimprovement between the C++ Release and Debug versions leads me to believe thatthe compiler is able to remove more instructions in the Release build with thenew optimization algorithm.

C#seems not to benefit too much from this optimization.

Thenext operation I will try to optimize is the division by 2. If we look again atthe binary representation of the numbers, we can observe that when we divide by2 we discard the last bit of the number and we add a 0 bit before the remainingbits. So 5 (=101) / 2 = 2 (=010), 13 (=1101) / 2 = 6 (=0110), 6 (=110) / 2 = 3(= 011), etc. I will replace this operation with the bitwise right shiftoperation that produces the same result.

In C++, replace:

with:

In C#, replace:

with:

Here are the results:

C++Debug, C# Debug, C# Release version gain between 65 and 200 milliseconds fromthis optimization.

C++Release gains almost nothing from this replacement probably because thecompiler was already performing this optimization.

Lastmathematical operation that consumes time is the multiplication by 3. The onlything we can do to this operation is to replace it by additions.

In C++ replace:

with:

In C# replace:

with:

Here are the results:

Thebiggest performance gain can be observed in the C# Release version, followed bythe C++ Release version.

C# Debug version shows a decreased performance dueto the fact that the current software version executes more instructions thanthe previous one and the compiler can not optimize the instructions (it can notreplace them with anything else because we might need to set a break point on any of them).

Thereis one last mathematical optimization we can perform based on some special instructions that theprocessor implements. These instructions are the so-called conditional moveinstructions. To determine the compiler to generate a conditional moveinstruction, I will replace the IF statement (which checks if the number is oddor even) with the ternary operator( ?: ).

Tobe able to implement the optimization mentioned above we need to modify theproblem statement. If the number is even, it will be divided by 2 (as imposedfor the problem). If the number is odd then it can be expressed as 2 * n + 1. Applyingthis modifications to the initial form of the function we will obtain:

From the above equation we can see that we can perform2 steps of the algorithm into 1. We will rewrite the algorithm so that wecompute next value of the number to test, assuming the current value is even.Then we will save the value of the last bit of the current number to test. Ifthis value is true, we will increment the current cycle count and add the currentnumber + 1 to the next value of the number to test. (Note: this optimizationwill become really important in one of the next articles when I will talk aboutSSE).

Free download turbo c 4.5 setup for windows xp free. In C++ replace:

with:

In C# replace:

with:

Here are the results:

Both debug builds show a slowdown, because weare now executing more instructions compared to the previous versions of thecode and the compilers can not optimize them.

TheC# Release version shows a slowdown because there are no conditional moveinstructions in C#.

Thepower of this category of instructions is proved by the increased speed of theC++ Release version.

Itcan be noticed the I did solve the problem using recursion. For this problem, arecursive algorithm would be extremely slow: the maximum cycle length is 525,so assuming that most of the numbers have a cycle length of around 150 (just a guess,not actually verified), if we have 150 recursive calls for every number between1 and 1000000, we would have to perform 150000000 calls. This, clearly, is nota small number and, because calling a function takes a lot of time, recursion is,definitely, not a good solution for this problem.

Points of Interest

It'stime to draw the conclusions:

1. Modulo and division operation take a lot of time and they should be replaced bysomething else.
2. Try to analyze the problem and obtain an alternate representation of theproblem.
3. Try to eliminate the IF statements from your code in the case that their onlypurpose is to set some values based on a condition.

Thenext time topic will be about how to make our program faster, using threadingin C# and C++.

History

• 27 May 2012 - Initial release.
• 28 May 2012 - I would like to thank anlarke for pointing out things that could be improved in the article and for submitting his code (C++ Debug time: 546.76 ms, C++ Release time: 386.35 ms). Also I would like to thank Reonekot for his clarification on the WoW topic. He is right and the performance problems are caused by the fact that the registers are 32 bits (for x86) and 64 bits (for x64).