i++ less efficient than ++i, how to show this?

Question

I am trying to show by example that the prefix increment is more efficient than the postfix increment.

In theory this makes sense: i++ needs to be able to return the unincremented original value and therefore store it, whereas ++i can return the incremented value without storing the previous value.

But is there a good example to show this in practice?

I tried the following code:

int array[100];

int main()
{
  for(int i = 0; i < sizeof(array)/sizeof(*array); i++)
    array[i] = 1;
}

I compiled it using gcc 4.4.0 like this:

gcc -Wa,-adhls -O0 myfile.cpp

I did this again, with the postfix increment changed to a prefix increment:

for(int i = 0; i < sizeof(array)/sizeof(*array); ++i)

The result is identical assembly code in both cases.

This was somewhat unexpected. It seemed like that by turning off optimizations (with -O0) I should see a difference to show the concept. What am I missing? Is there a better example to show this?

Answer 1

Try to use while or do something with returned value, e.g.:

#define SOME_BIG_CONSTANT 1000000000

int _tmain(int argc, _TCHAR* argv[])
{
    int i = 1;
    int d = 0;

    DWORD d1 = GetTickCount();
    while(i < SOME_BIG_CONSTANT + 1)
    {
        d += i++;
    }
    DWORD t1 = GetTickCount() - d1;

    printf("%d", d);
    printf("\ni++ > %d <\n", t1);

    i = 0;
    d = 0;

    d1 = GetTickCount();
    while(i < SOME_BIG_CONSTANT)
    {
        d += ++i;

    }
    t1 = GetTickCount() - d1;

    printf("%d", d);
    printf("\n++i > %d <\n", t1);

    return 0;
}

Compiled with VS 2005 using /O2 or /Ox, tried on my desktop and on laptop.

Stably get something around on laptop, on desktop numbers are a bit different (but rate is about the same):

i++ > 8xx < 
++i > 6xx <

xx means that numbers are different e.g. 813 vs 640 - still around 20% speed up.

And one more point - if you replace "d +=" with "d = " you will see nice optimization trick:

i++ > 935 <
++i > 0 <

However, it's quite specific. But after all, I don't see any reasons to change my mind and think there is no difference :)

Answer 2

Ok, all this prefix/postfix "optimization" is just... some big misunderstanding.

The major idea that i++ returns its original copy and thus requires copying the value.

This may be correct for some unefficient implementations of iterators. However in 99% of cases even with STL iterators there is no difference because compiler knows how to optimize it and the actual iterators are just pointers that look like class. And of course there is no difference for primitive types like integers on pointers.

So... forget about it.

EDIT: Clearification

As I had mentioned, most of STL iterator classes are just pointers wrapped with classes, that have all member functions inlined allowing out-optimization of such irrelevant copy.

And yes, if you have your own iterators without inlined member functions, then it may work slower. But, you should just understand what compiler does and what does not.

As a small prove, take this code:

int sum1(vector<int> const &v)
{
    int n;
    for(auto x=v.begin();x!=v.end();x++)
            n+=*x;
    return n;
}

int sum2(vector<int> const &v)
{
    int n;
    for(auto x=v.begin();x!=v.end();++x)
            n+=*x;
    return n;
}

int sum3(set<int> const &v)
{
    int n;
    for(auto x=v.begin();x!=v.end();x++)
            n+=*x;
    return n;
}

int sum4(set<int> const &v)
{
    int n;
    for(auto x=v.begin();x!=v.end();++x)
            n+=*x;
    return n;
}

Compile it to assembly and compare sum1 and sum2, sum3 and sum4...

I just can tell you... gcc give exactly the same code with -02.

Answer 3

You won't see any difference with integers. You need to use iterators or something where post and prefix really do something different. And you need to turn all optimisations on, not off!

Answer 4

I like to follow the rule of "say what you mean".

++i simply increments. i++ increments and has a special, non-intuitive result of evaluation. I only use i++ if I explicitly want that behavior, and use ++i in all other cases. If you follow this practice, when you do see i++ in code, it's obvious that post-increment behavior really was intended.

Answer 5

This code and its comments should demonstrate the differences between the two.

class a {
    int index;
    some_ridiculously_big_type big;

    //etc...

};

// prefix ++a
void operator++ (a& _a) {
    ++_a.index
}

// postfix a++
void operator++ (a& _a, int b) {
    _a.index++;
}

// now the program
int main (void) {
    a my_a;

    // prefix:
    // 1. updates my_a.index
    // 2. copies my_a.index to b
    int b = (++my_a).index; 

    // postfix
    // 1. creates a copy of my_a, including the *big* member.
    // 2. updates my_a.index
    // 3. copies index out of the **copy** of my_a that was created in step 1
    int c = (my_a++).index; 
}

You can see that the postfix has an extra step (step 1) which involves creating a copy of the object. This has both implications for both memory consumption and runtime. That is why prefix is more efficient that postfix for non-basic types.

Depending on some_ridiculously_big_type and also on whatever you do with the result of the incrememt, you'll be able to see the difference either with or without optimizations.

Answer 6

Several points:

• First, you're unlikely to see a major performance difference in any way
• Second, your benchmarking is useless if you have optimizations disabled. What we want to know is if this change gives us more or less efficient code, which means that we have to use it with the most efficient code the compiler is able to produce. We don't care whether it is faster in unoptimized builds, we need to know if it is faster in optimized ones.
• For built-in datatypes like integers, the compiler is generally able to optimize the difference away. The problem mainly occurs for more complex types with overloaded increment iterators, where the compiler can't trivially see that the two operations would be equivalent in the context.
• You should use the code that clearest expresses your intent. Do you want to "add one to the value", or "add one to the value, but keep working on the original value a bit longer"? Usually, the former is the case, and then a pre-increment better expresses your intent.

If you want to show the difference, the simplest option is simply to impement both operators, and point out that one requires an extra copy, the other does not.

Answer 7

In the general case, the post increment will result in a copy where a pre-increment will not. Of course this will be optimized away in a large number of cases and in the cases where it isn't the copy operation will be negligible (ie., for built in types).

Here's a small example that show the potential inefficiency of post-increment.

#include <stdio.h>

class foo 
{

public:
    int x;

    foo() : x(0) { 
        printf( "construct foo()\n"); 
    };

    foo( foo const& other) { 
        printf( "copy foo()\n"); 
        x = other.x; 
    };

    foo& operator=( foo const& rhs) { 
        printf( "assign foo()\n"); 
        x = rhs.x;
        return *this; 
    };

    foo& operator++() { 
        printf( "preincrement foo\n"); 
        ++x; 
        return *this; 
    };

    foo operator++( int) { 
        printf( "postincrement foo\n"); 
        foo temp( *this);
        ++x;
        return temp; 
    };

};


int main()
{
    foo bar;

    printf( "\n" "preinc example: \n");
    ++bar;

    printf( "\n" "postinc example: \n");
    bar++;
}

The results from an optimized build (which actually removes a second copy operation in the post-increment case due to RVO):

construct foo()

preinc example: 
preincrement foo

postinc example: 
postincrement foo
copy foo()

In general, if you don't need the semantics of the post-increment, why take the chance that an unnecessary copy will occur?

Of course, it's good to keep in mind that a custom operator++() - either the pre or post variant - is free to return whatever it wants (or even do whatever it wants), and I'd imagine that there are quite a few that don't follow the usual rules. Occasionally I've come across implementations that return "void", which makes the usual semantic difference go away.

Answer 8

In response to Mihail, this is a somewhat more portable version his code:

#include <cstdio>
#include <ctime>
using namespace std;

#define SOME_BIG_CONSTANT 100000000
#define OUTER 40
int main( int argc, char * argv[] ) {

    int d = 0;
    time_t now = time(0);
    if ( argc == 1 ) {
     for ( int n = 0; n < OUTER; n++ ) {
      int i = 0;
      while(i < SOME_BIG_CONSTANT) {
       d += i++;
      }
     }
    }
    else {
     for ( int n = 0; n < OUTER; n++ ) {
      int i = 0;
      while(i < SOME_BIG_CONSTANT) {
       d += ++i;
      }
     }
    }
    int t = time(0) - now; 
    printf( "%d\n", t );
    return d % 2;
}

The outer loops are there to allow me to fiddle the timings to get something suitable on my platform.

I don't use VC++ any more, so i compiled it (on Windows) with:

g++ -O3 t.cpp

I then ran it by alternating:

a.exe

and

a.exe 1

My timing results were approximately the same for both cases. Sometimes one version would be faster by up to 20% and sometimes the other. This I would guess is due to other processes running on my system.

Answer 9

I completely disagree, the color of the bike shed should be Green, clearly.

My argument why this is so breaks down into 7 parts, which I will explain thusly...

Answer 10

Either pre-increment or post-increment may be the most efficient (and if one of them is the most efficient, it's probably true that the other type is more effciient for decrements).

CPUs may well have a "fetch and increment" that is either a pre- or post-increment (some, I understand, have both) and if you use what's natively supported by your CPU, you'll probably get better performance than if you use something that needs to be implemented with more instructions.

Answer 11

Perhaps you could just show the theoretical difference by writing out both versions with x86 assembly instructions? As many people have pointed out before, compiler will always make its own decisions on how best to compile/assemble the program.

If the example is meant for students not familiar with the x86 instruction set, you might consider using the MIPS32 instruction set -- for some odd reason many people seem to find it to be easier to comprehend than x86 assembly.