Improvements in a loop : ++i better than i++ ?

[pete]

Spoon wrote:

If I were a compiler, I'd ouput the same code for "++i;" and "i++;"
(considering integral type for i).

What does the integral type of i have to do with it?

 

[stdazi]

Hello everybody

This code is intended to compute the number of partitions of a number.
see this link :http://en.wikipedia.org/wiki/Integer_partition

void partition(int n)
{
// total decrit la somme des nombres du tableau indice 0..ptcur
int total;

// prcur nombre d'elements utilises dans le tableau tab
int ptcur;

// nombre de partitions
int nb ;

// compteur de boucle pour l'initialisation
int i;

// tableau decrivant une solution
int *tab = malloc(n * sizeof(int));

if (tab == NULL)
{
fprintf(stderr, "Pb alloc memoire\n");
return;
}

// initialisation : la premiere partition n'est composee que de 1
for(i = 0; i < n; i++)
tab = 1;

nb = 1;
total = n;
ptcur = n-1;

// la boucle infernale
while (tab[0] != n)
{
if (total > n)
{
// on revient un cran en arrière
// et on augmente la valeur pointee
// car il n'y a pas de solution avec cette valeur
// a ce rang
total -= tab[ptcur];
--ptcur;
++tab[ptcur];
++total;
}
else
if (total == n)
{
// on a trouve une solution
// edit(tab, ptcur);
++nb;
// on revient un cran en arrière
// et on augmente la valeur pointee
// car on a epuise toutes les solutions avec cette valeur
// a ce rang
total -= tab[ptcur];
--ptcur;
++tab[ptcur];
++total;
}
else
{
// on avance d'un cran
++ptcur;
// un nombre du tableau est toujours superieur
// ou egal a ses precedents
tab[ptcur] = tab[ptcur-1];
total += tab[ptcur];
}
}
printf("Nombre de solutions %d\n", nb);
free(tab);

}

The loop while is executed à very big number of times (for n = 100
much more than 190,569,292 times which is the number of partitions of
100).

Is it possible to improve this code (not the algorithm) ?
e-g : is ++total faster than total++ in the absolute ?
is it better to compute r = total - n and test r > 0 and r == 0 or
test total > n and total == n ?
I can't test really on my system (Vista) cause of the multiprocessing,
sometimes it gaves me 11s or 13s for the same code and number 100.

Thank you for the hints.

This is OT as you don't want another algorithm, but, here is mine and
I'll be glad if someone can nitpick it

 

[stdazi]

Hello everybody

This code is intended to compute the number of partitions of a number.
see this link :http://en.wikipedia.org/wiki/Integer_partition

void partition(int n)
{
// total decrit la somme des nombres du tableau indice 0..ptcur
int total;

// prcur nombre d'elements utilises dans le tableau tab
int ptcur;

// nombre de partitions
int nb ;

// compteur de boucle pour l'initialisation
int i;

// tableau decrivant une solution
int *tab = malloc(n * sizeof(int));

if (tab == NULL)
{
fprintf(stderr, "Pb alloc memoire\n");
return;
}

// initialisation : la premiere partition n'est composee que de 1
for(i = 0; i < n; i++)
tab = 1;

nb = 1;
total = n;
ptcur = n-1;

// la boucle infernale
while (tab[0] != n)
{
if (total > n)
{
// on revient un cran en arrière
// et on augmente la valeur pointee
// car il n'y a pas de solution avec cette valeur
// a ce rang
total -= tab[ptcur];
--ptcur;
++tab[ptcur];
++total;
}
else
if (total == n)
{
// on a trouve une solution
// edit(tab, ptcur);
++nb;
// on revient un cran en arrière
// et on augmente la valeur pointee
// car on a epuise toutes les solutions avec cette valeur
// a ce rang
total -= tab[ptcur];
--ptcur;
++tab[ptcur];
++total;
}
else
{
// on avance d'un cran
++ptcur;
// un nombre du tableau est toujours superieur
// ou egal a ses precedents
tab[ptcur] = tab[ptcur-1];
total += tab[ptcur];
}
}
printf("Nombre de solutions %d\n", nb);
free(tab);

}

The loop while is executed à very big number of times (for n = 100
much more than 190,569,292 times which is the number of partitions of
100).

Is it possible to improve this code (not the algorithm) ?
e-g : is ++total faster than total++ in the absolute ?
is it better to compute r = total - n and test r > 0 and r == 0 or
test total > n and total == n ?
I can't test really on my system (Vista) cause of the multiprocessing,
sometimes it gaves me 11s or 13s for the same code and number 100.

Thank you for the hints.

This is OT as you don't want another algorithm, but, here is mine and
I'll be glad if someone can nitpick it

err ignore this post - posted in the wrong thread, sorry.

 

[Roberto Waltman]

The myth about ++i vs i++ dates back to when computers had much
simpler instruction sets and needed an extra operation to
post-increment. Unless you have an unusual use of your loop variable,
you will see zero difference.

The "extra operation", if required, has more to do with the need to
preserve the previous value before a post-(inc|de)crement operation.
For example, using the following two code fragments:

A) int i;
void f(int);
...
f(++i);

B) int i;
void f(int);
...
f(i++);

Using the imaginary processor instruction set of the DeathStation xK
series mentioned in other threads, the function call in (A) could be
translated as

INCREMENT I
PUSH I
CALL F

while the function call in (B) could be translated as

STORE I -> TEMP
PUSH I
CALL F
STORE TEMP -> I
INCREMENT I

The the OP: the answer is still "may be, may be not"
Start by measuring the performance of simple test programs that use
mostly the functions/operations you are trying to optimize.

Roberto Waltman

[ Please reply to the group,
return address is invalid ]

 

[Justin Spahr-Summers]

The "extra operation", if required, has more to do with the need to
preserve the previous value before a post-(inc|de)crement operation.
For example, using the following two code fragments:

A) int i;
void f(int);
...
f(++i);

B) int i;
void f(int);
...
f(i++);

Yes, but in the case that A and B have the same effect regardless of
the increment operator, like so:

A) int i = 3;
++i;

B) int i = 3;
i++;

Any compiler that has basic optimization skills should produce the
same machine code for both, instead of saving the value of "i", etc.
in the B example.

 

[Mark McIntyre]

On Wed, 08 Aug 2007 05:51:36 -0700, in comp.lang.c ,


The myth about ++i vs i++ dates back to when computers had much
simpler instruction sets

[...]
I think the myth has survived in part because of C++. The prefix and
suffix '++' operators can have significantly different performance,

Thats true. I chose not to mention this as I felt it would confuse an
already confused OP!

--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Peter J. Holzer]

The "extra operation", if required, has more to do with the need to
preserve the previous value before a post-(inc|de)crement operation.

Right, but your example doesn't show that.

For example, using the following two code fragments:

A) int i;
void f(int);
...
f(++i);

B) int i;
void f(int);
...
f(i++);

Using the imaginary processor instruction set of the DeathStation xK
series mentioned in other threads, the function call in (A) could be
translated as

INCREMENT I
PUSH I
CALL F

while the function call in (B) could be translated as

STORE I -> TEMP
PUSH I
CALL F
STORE TEMP -> I
INCREMENT I

There is a sequence point between the evaluation of the arguments of a
function and the call to the function, so this should be:

STORE I -> TEMP
INCREMENT I
PUSH TEMP
CALL F

which can of course be easily optimized to

PUSH I
INCREMENT I
CALL F

hp