[guide] Optimizations in your C++ Program

[refuge]

Hi everyone.
This is my very first real article on anything programming related, so bare with me.

I'm not actually going to go too far into this, just going to bring up some small things that you can do to make your programs more efficient (sometimes slightly, other times greatly).

Now, for those compiling with gcc, it's a pretty smart compiler, and it will most likely assume what you're trying to do, and correct it accordingly. Though the same cannot be said about every compiler, or every version of every compiler; such as the while vs for (I'll get to that in a moment); I think microsoft and borland's compile it literally (optimization, aside).
So it's better to be safe than sorry, especially if you don't know if your code will compiler on various platforms.

while() vs for()
NOTE:My compiler ended up auto-optimizing this, so I couldn't create some assembly code to match my argument (though you can google it up, and you'll find some code generated on other compilers which support this argument), but I can generate some assembly that would look similar, if you want.

There can be abit of controversy when it comes to for vs while for an infinite loop.
In a literal compilation, while() and for() will not do the same thing.
Consider the following two:

Code:

while(1)
  std::cout<<"oh noes!"<<std::endl;
for(;;)
  std::cout<<"oh noes!"<<std::endl;

What the program may compile to in the first example (via pseudo-assembly) is:

cpp Code:

label:
Check if '1'
print "oh noes!" endline
jump to 'label'

Here's the second code:

cpp Code:

<empty statement -- do nothing>
label:
<empty statement -- do nothing>
print "oh noes!" endline
<empty statement -- do nothing>
jump to 'label'

Where you see "<empty statement -- do nothing>", that's actually where the two semi-colons for the for loop are.
So in short..
A while() loop, since it's conditional, will validate to make sure that the condition '1' is true, if so, it will continue the loop, whereas a for() statement would have no statement to condition, so it simply loops.
One fun thing I like to do in my code, is this:

cpp Code:

#define EVER ;;
for(EVER) //muhaha!

Postfix vs Prefix operators
One thing I see alot in code, is the use of 'var++' over '++var'.
Protip: Unless you need the value of 'var' before incrementing it, use pre-incremental.
You may think, "what harm can ++i do?". Honestly, not that much, if it's just an integer.
See, when you use ++i, it increments i, and returns it's value. When you're using i++, it stores the value of i, increments it, and returns it's old value.
In assembly, this is just switching of three commands, but what about with objects?
A great example I found here, is the following:

cpp Code:

class MyClass
{
public:
    MyClass& operator++()    //Prefix increment operator  (++x)
    {
        //Perform increment operation
        return *this;
    }
 
    MyClass  operator++(int) //Postfix increment operator (x++)
    {
        MyClass temp = *this;
        //Perform increment operation
        return temp;
    }
};

As you see, a new object is initialized, holding the old object, and returns that object.
This means that you're taking a performance shot to the stack every time you use postfix.

Dynamic allocation vs static (for lack of a better term) allocation.
First off, let me define dynamic and static:

cpp Code:

{
  //static:
  object obj;
  int foo;
  foo = 0;
  obj.setValue(foo);
}
{
  //dynamic:
  object *obj = new object;
  int *foo = new int;
  *foo = 0;
  obj->setValue(*foo);
  delete foo;
  delete obj;
}
//Please excuse my dereferencing if it's wrong.

Now, the primary difference between the dynamic and static, is that when you dynamically allocate data, it is saved in the heap; whereas if you statically allocate it, it is saved on the stack.
So for large objects, it's a good idea to dynamically allocate it, to preserve the stack.
Another benefit of dynamically allocated objects, is that they don't have to follow the law of scope, and in a sense, they never go out of scope until they are manually deleted.

Two-Dimensional Array Access
Access wouldn't be the word -- I should say traverse a two-dimensional array.
But the question is, which is better to use?
ary[x][y] or ary[y][x]?

It may not seem like there's any difference, but one is actually much slower than the other.
Here's an example of what the array foo[3][3] would look like in memory (don't question my epic pant skillz ;D):

Putting more into perspective, consider the two:

cpp Code:

for(x=0; x<3; ++x)
  for(y=0; y<3; ++y)
    foo[x][y] = 0;
for(x=0; x<3; ++x)
  for(y=0; y<3; ++y)
    foo[y][x] = 0;

Here is what the first five steps of the first for/for loop is doing in memory:
(the red dot represents where in memory the program is pointing to, and the arrow represents where that pointer is pointing to).

As you can see, it's using the pointer foo[0] to reach each location of memory that is next to it.
Next, we look at the second part:


As you can see, the second way, the data pointer is throwing itself all over memory, instead of moving though it one block at a time.
To prove it's length, here is a program I threw together (well, I modified it from the original C program my professor used last year) that creates an array that's 0xF00*0xF00 in size, and traverses it:
http://pastebin.com/f45636265
Here are the results for when I ran it:
x->y: 0.0500
y->x: 0.1000
As expected, the latter was about half as slow.

switch() vs else if
I generated some assembly output for this one (I generated assembly output for the rest as well, but those aren't worth looking at).
One thing I try to do, is use switch() as much as possible, as opposed to else if.
Consider the following two programs:

cpp Code:

int main()
{
  int myVar = 0;
  int foo;
  if(myVar == 1)
    ++myVar;
  else if(myVar == 2)
    --myVar;
  else if(myVar ==  3)
    myVar++;
  else if(myVar ==  4)
    myVar--;
  else if(myVar ==  5)
    --myVar;
  else if(myVar ==  6)
    myVar=0x3;
  else if(myVar ==  7)
    myVar=0xff;
  else if(myVar ==  <img src="http://lastcode.net/images/smilies/CrystalXP/glasses.gif" style="vertical-align: middle;" border="0" alt="Glasses" title="Glasses" />
    myVar=0xff;
  else if(myVar ==  9)
    myVar=0x2a;
  else if(myVar ==  10)
    myVar=0x801;
  else if(myVar ==  11)
    myVar=0x6;
  else if(myVar ==  12)
    myVar=0xfa;
  else if(myVar ==  13)
    myVar=0x0354;
  else if(myVar ==  14)
    myVar=myVar+8;
  else if(myVar ==  15)
    myVar=415;
  else
    myVar=0xF;
  foo = myVar;
return 0;
}

cpp Code:

int main()
{
  int myVar = 0;
  int foo;
  switch(myVar)
  {
  case 1:
      ++myVar;
      break;
    case 2:
    --myVar;
    break;
  case 3:
    myVar++;
    break;
  case 4:
    myVar--;
    break;
  case 5:
    --myVar;
    break;
  case 6:
    myVar=0x3;
    break;
  case 7:
    myVar=0xff;
    break;
  case 8:
    myVar=0xff;
    break;
  case 9:
    myVar=0x2a;
    break;
  case 10:
    myVar=0x801;
    break;
  case 11:
    myVar=0x6;
    break;
  case 12:
    myVar=0xfa;
    break;
  case 13:
    myVar=0x0354;
    break;
  case 14:
    myVar=myVar+8;
    break;
  case 15:
    myVar=415;
    break;
  }
  foo = myVar;
  return 0;
}

The brackets are left out, as it would make the else if too long.
Now, when this is compiled, the first program would end up compiling into a mess of cmp and jmp commands, one-by-one, working its way down.
If myVar happened to be 15, it would end up doing 15 conditionals. The worst-case scenario here, would be that myVar isn't a number listed, and the result would be a test of every possible condition, until it reaches the else.

As for the switch(), that actually manages to be pretty efficient (well... VERY efficient).
This is because the second will compile into jump tables -- or hash maps. This means that there is only one test done, and it knows which to jump to.
You can find the assembly output for the first program here: http://pastebin.com/f511c7140 and the second here: http://pastebin.com/f654d9226

We now have a situation though. And that's the question of "what should we do with strings?".
I ran into this exact problem when I was writing my virtual machine, well, more specifically, my assembler.
In my first version, I was using a mess of else if and strcmp; here's a snippet of my parser, so you can see what I mean:

cpp Code:

char* first = new char[256];
  //Get first 4 characters
  while(line[j]!='\0' && line[j]!=' ' && line[j] != '\n' && line[j]!=';' && line[j]!='\r')
    first[j] = line[j++]; //Get instruction
  first[j++]='\0';
/*Flow*/
  if(!(strcmp("jmp", first)))
  {
    if(jumps(line, second, j, result, table, size))
    {
      result.dword = 1;
      return result;
    }
    else
      result.byte[3] = 0x20;//Set the highest byte
  }
  else if(!(strcmp("jz", first)))
  {
    if(jumps(line, second, j, result, table, size))
    {
      result.dword = 1;
      return result;
    }
    else
      result.byte[3] = 0x24;//Set the highest byte
  }
  else if(!(strcmp("jg", first)))
  //etc

This honestly was killing me!
The reason for this issue, is because a string (whether it's the std string, or a char*) is pretty much an array of characters, and you can't treat an array as one value.

My ultimate solution, was to hash the string, throw the solution keys into an enumeration, and run a switch() on the key -- it greatly improved the efficiency, and the num helped make things more sensible.

There are other solutions though; one, is to use nested switch() statements -- they have been used professionally before, but at the cost of making your wonderful code look horrible, also, the efficiency drops the more nested switches you use; here's an example that does something for the following strings: "jmp", "je", "cat"

cpp Code:

switch(str[0])
{
  case 'j':
    switch(str[1])
    {
      case 'm':
      //do stuff for jmp
      break;
      case 'e':
      //do stuff for je
      break;
    }
    break;
  case 'c':
    switch(str[1])
    {
      case 'a':
      //do stuff for "cat"
      break;
    }
    break;
}

The second, is to use the STL Container classes, and use the strings as the key, and just have the entries point to functions like in a hash table.

Other than that, I can't really think of any other ways of doing this.

Inline vs Non-Inline
Just a quickie on here.
If you call a certain function many times (esepcially a small function, such as void "addXY(int& x, int& y, int& z) {z = x+y;}", you may want to consider making it inline.
Use inline sparingly though, because it doesn't always result in faster code, and usually results in longer code

Preprocessors
Another controversy is whether to use #define (and macros) or use typedef (or functions).
Since the preprocessors are made during compile-time rather than run-time, they will be faster, but I personally use typedef over #define due to the fact I feel it's safer to work to work with type-safe objects then constants (you can fund much discussion on this subject).

Compiler Flags
For those using GCC, there are afew flags you should be aware of when compiling your code.
First, the -O (not -o) flag, you can choose the level of compiler-size optimization for your code:
-O0
This option turns all optimizations off.
-O1
This option will try to reduce the code's size and efficiency while trying not to slow down the compiling process.
-O2
Level two optimization will enable as just about all the compiler optimizations that shouldn't hurt your program. This one may show down the actual time it will take to compile, but it's worth it.
I'd always recommend -O2
-O3
This turns all the optimizations on; there's a chance it will break your code though, I don't touch it.
-mtune and -march
mtune will tune your program to your CPU type, and march will generate assembly for your specific CPU (it will assume that mtune=march).
If you don't mind your program only working on your computer, you can use:
-march=native
Which will detect your CPU type, and act accordingly.
If you want your binary to execute on any machine (well, any x86), you can use -march=generic (or -mtune=generic); it will use all of those slow legacy instructions for the 8086
You can see the rest of the -m optimizations here:
http://gcc.gnu.org/onlinedocs/gcc/i386-a...tions.html



Well, I hope this helped someone -- I enjoyed writing it atleat

[Uskdara]

This is all over my head, but it looks awesome and I can't thank you enough for contributing. I really like this site even though I'm new here and hope to learn a lot and people like you will make that possible! Thanks.

[refuge]

(02-21-2010 02:34 PM)Uskdara Wrote:  This is all over my head, but it looks awesome and I can't thank you enough for contributing. I really like this site even though I'm new here and hope to learn a lot and people like you will make that possible! Thanks.

Thanks!
C++ isn't too hard once you get the hang of it; it's actually one of the easier languages.

[Uskdara]

Yeah, I'm not completely illiterate, but I'm also far from experienced. I was just getting into object stuff, just got pass classes and functions in my college course when I had to drop out for financial reasons. (My Dad's net worth is too much for me to qualify for financial aid even though his business is in the negative, kind of irritating but oh well I'll keep saving up and earn my own way back)

[mickcy]

Thanks for contributing!

Argh! The knowledge, my head *explodes*.
Jk, now I know why there is the option of ++i or i++; xD
Other than using it like:

Code:

int a = i++;
int b = ++i;
std::cout << a << ", " << b << std::endl;

And I should start using switch() more. =/

[Anman]

Thanks for contributing such a well thought out and detailed tutorial! I'm sure this will help out a bunch of beginners.