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

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 2

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 3

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 4

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 5

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 6

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.