Optimisation de la division par 2

candide a écrit :

Bonjour,

Différentes lectures m'avaient fait admettre que le reste d'un entier
modulo 2 ie (x % 2) produisait un code équivalent à sa version bit à bit
ie (x & 1).

En fait c'est faux si x est signé.

(x % 2) en version signée est traduite comme
x - ((x + (((unsigned)x)>>31)) & ~1)
(en assumant du 32bit).

L'idée est ici de soustraire à x tout sauf son bit de poids faible tout
en soustrayant 2 si x est impair négatif. Ainsi on a bien les valeurs 0,
1 et -1 dispo. C'est vraiment un codage compact du calcul.

int est_pair1(int n)
{
return !(n % 2);
}

Ici quand je regarde les code ASM de GCC et de VS, on a pas du tout la
même chose.

GCC:
xorl %eax, %eax
testb $1, 4(%esp)
sete %al
ret
(C'est grosso modo un "and" ce truc). GCC ne se préoccupe pas trop du
signe de n % 2 et fait quelque chose de sioux.

VC (98):
and eax, -2147483647
jns SHORT $L105
dec eax
or eax, -2
inc eax
$L105:
neg eax
sbb eax, eax
inc eax
ret 0

Le "and" du début effectue le test n<0 tout en préservant le bit de
poids faible (+/- sioux). S'en suivent des calculs revenant à calculer 0
si le bit de poids faible est 0, et -1 sinon.

En fait la partie jusqu'à L105 est un calcul effectif de (n % 2) tenant
compte du signe. La partie finale après L105 calcule une inversion 0->1,
!0 ->0.

Donc VC effectue assez peu d'optim, il calcule (n % 2) puis le "not" du
résultat du modulo. En fait ce calcul du modulo fait par VC est une
version sans décalage, mais avec saut. Cela peut être intéressant
suivant le type de CPU.

Cela dit, quoi qu'il en soit GCC s'en sort haut la main car il a compris
qu'on se fiche de calculer exactement (n%2) et se contente d'un test sur
le bit de poids faible de n directement. C'est d'ailleurs le code que
fait VC98 sur les unsigned:
mov eax, DWORD PTR _n$[esp-4]
not eax
and eax, 1

La morale est qu'il vaut mieux clairement utiliser des unsigned pour les
manip bit-à-bits car "d'une façon générale", les compilos semblent être
mieux capables de mener les optims jusqu'au bout et produire un code asm
performant.

sam.

Pierre Maurette a écrit :

Vous ne chronométrez pas les instructions que vous voulez tester, ou
disons que vous les chronométrez noyées dans le bruit. Votre programme
passe tout son temps dans les appels de fonctions, dans une moindre
mesure dans les printf(), et quelsues autres trucs.

Certes, il y a du bruit mais je ne crois pas que ce soit gênant pour
discriminer puisque tous les tests font le même bruit. Disons que ça va
juste changer les proportions de lenteur.

- dans vos fonctions est_pairx(), mettre juste
return 0;
Si ça se trouve ce sera plus long ;-)

Pas compris.

- virer le printf() dans test().

Il est bien pratique pour vérifier la conformité entre les tests mais on
peut réduire les affichages.

- remplacer le f(i * j) dans test() par l'une ou l'autre de vos
instructions.

Oui mais il faut bien que je fasse quelque chose d'utile (sinon les
optimisations peuvent ignorer les calculs) et d'assez long pour que ce
soit significatif.

- Alternativement, écrire une:
static int est_pair(int n) // ou static inline etc.
{
return !(n % 2);
}
et l'appeler directement dans test().

Jamais bien compris cet histoire de inlining mais de toute façon, la
question ne va plus se poser puisque je vais réécrire les tests sans
appel de fonctions.

Puisque vous êtes sur l'optimisation, voyez le f(i*j) en fond de boucle.
Ça peut être coûteux et bien plus long (le bruit le bruit) que votre

Vous proposez quoi à la place car je n'ai pas beaucoup d'imagination ?

instruction à tester, si le compilateur ne constate pas à votre place
que cette multiplication de deux valeurs non constantes n'est en fait
qu'un incrément.

Comprends pas.



Bon, j'ai refait des tests en respectant ce que j'ai compris vos
propositions

Les résultats confirment :
-- qu'il y avait du bruit
-- que la tendance du premier test est conservée :
*) égalité pour gcc,
*) écart encore plus flagrant pour Visual.

Voici les temps pour les mêmes valeurs que dans la première batterie de
tests (avec optimisation pour les deux compilateurs) :
-----------------------------------
gcc sous Ubuntu
75000000
Temps CPU : 0.21 seconde.

75000000
Temps CPU : 0.21 seconde.

75000000
Temps CPU : 0.22 seconde.
-----------------------------------
Visual
75000000
Temps CPU : 0.13 seconde.

75000000
Temps CPU : 0.72 seconde.

75000000
Temps CPU : 0.14 seconde.
-----------------------------------



Voici le code, j'ai un écrit une bonne vieille macro illisible mais
c'est quand même plus simple pour faire évoluer des codes homogènes
entre les trois tests :


#include <stdio.h>
#include <time.h>

#define f0(n) (!((n) & 0x1))
#define f1(n) (!((n) % 2))
#define f2(n) (!((n) % 2U))

#define N 10000
#define NB_TESTS 10

#define TEST(f) {int nt = NB_TESTS;
clock_t now = clock();
unsigned s = 0;
for (nt = 0; nt < NB_TESTS; nt++)
{
int i, j = 0;
s = 0;

for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
s += (unsigned)f(i * j);
}
printf("%un", s);
printf("Temps CPU : %.2f seconde.nn",
(double) (clock() - now) / CLOCKS_PER_SEC / NB_TESTS);
}

int main(void)
{
TEST(f0)
TEST(f1)
TEST(f2)

return 0;
}

Samuel Devulder a écrit :

(x % 2) en version signée est traduite comme
x - ((x + (((unsigned)x)>>31)) & ~1)
(en assumant du 32bit).

Ah ! OK donc, ce n'est quand même pas une brute division.

Donc VC effectue assez peu d'optim, il calcule (n % 2) puis le "not" du
résultat du modulo. En fait ce calcul du modulo fait par VC est une
version sans décalage, mais avec saut. Cela peut être intéressant
suivant le type de CPU.

Pas tout compris car connais pas l'assembleur.

La morale est qu'il vaut mieux clairement utiliser des unsigned pour les
manip bit-à-bits car "d'une façon générale", les compilos semblent être
mieux capables de mener les optims jusqu'au bout et produire un code asm
performant.

Ah ! c'est ce notre -ed- nous a toujours dit et je crois qu'il a raison ;)

sam.

sam <--> asm

un nom prédestiné quoi !!

-ed- a écrit :

unsigned int i, j;
int s = 0;
clock_t start = clock ();
double ms;

for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
s += f (i * j);

J(avais pas fait gaffe mais il y a un risque d'overflow donc il vaudrait
mieux caster en unsigned ce que j'ai rectifié dans mes derniers tests,
cf. réponse à Pierre Maurette

-ed- a écrit :

On 29 oct, 23:14, candide <cand...@free.invalid> wrote:

#define N (unsigned int)10000

Une façon compliqué et erronée

Pourquoi erronée ?

#define N ((unsigned int)10000)

d'écrire

#define N 10000U

Exact.

Je suis un programmeur du dimanche ;)

-ed- a écrit :

On 29 oct, 23:14, candide <cand...@free.invalid> wrote:

printf("estpair%d : %.2lf secondesnn", j, duree/NB_TESTS);

N'existe pas.

Ah bon %lf pour printf() n'existe pas ?

C'est

printf("estpair%d : %.2f secondesnn", j, duree/NB_TESTS);

Exact. Et si j'en crois la Norme, ce que j'ai écrit serait même un UB.


A ma décharge, j'ai recopié ce type de code en 2005 (l'année où j'ai
commencé le C) sur un forum usenet (je sais plus lequel) car j'avais
besoin de timer du code. J'ai réutilisé ce code sans changement et j'ai
sans doute eu tort.


Mais je tiens quand même à préciser qu'alors que ce besoin est très
courant, les docs ne donnent pas d'information sur cette question. Ma
version de la faq fclc ne dit rien (à propos, je signale à Éric Lévénez
qu'il serait bien qu'on puisse télécharger la faq au format texte, c'est
quand même plus pratique pour y faire des recherches de passer par Google).

La faq clc cite certes clock() mais n'en parle pas pour timer du code
et ne donne aucun exemple.

Et ton site, il dit quelque chose à ce sujet ?

Par contre, je viens de voir que tu donnes un exemple dans la FAQ de
developpez.

candide a écrit :

Samuel Devulder a écrit :

(x % 2) en version signée est traduite comme
x - ((x + (((unsigned)x)>>31)) & ~1)
(en assumant du 32bit).

Ah ! OK donc, ce n'est quand même pas une brute division.

Oui parce qu'on est dans une puissance de 2.

Donc VC effectue assez peu d'optim, il calcule (n % 2) puis le "not" du
résultat du modulo. En fait ce calcul du modulo fait par VC est une
version sans décalage, mais avec saut. Cela peut être intéressant
suivant le type de CPU.

Pas tout compris car connais pas l'assembleur.

En équivalent C il calcule le modulo signé ainsi pour une puissance de 2
(codée dans MASK):

#define MASK 0x00000001 /* de la forme (1<<k)-1 */

n &= 0x80000000 | MASK;
if(n<0) n = ((n-1) | ~MASK) + 1;

Ce pattern doit marcher avec n'importe quel MASK du type (1<<k) - 1.

De son coté le calcul du modulo "une puissance de 2" signé par GCC est
dans le genre ci:

if(n<0) n += MASK;
n = n - (n & ~MASK);

Les deux implémentation diffèrent dans le sens de celle de VC nécessite
moins de registres que celle de GCC. En effet n-1 se calcule directement
alors que "n - (un truc dépendant de n)" nécessite de sauvegarder n
dans un registre temporaire ou sur la pile.

sam <--> asm

un nom prédestiné quoi !!

Il y a de l'idée en effet.

sam.

candide, le 31/10/2009 a écrit :

Pierre Maurette a écrit :

Vous ne chronométrez pas les instructions que vous voulez tester, ou
disons que vous les chronométrez noyées dans le bruit. Votre programme
passe tout son temps dans les appels de fonctions, dans une moindre
mesure dans les printf(), et quelsues autres trucs.

Certes, il y a du bruit mais je ne crois pas que ce soit gênant pour
discriminer puisque tous les tests font le même bruit.

Une caractérisque première du bruit est d'être aléatoire. Donc l'idée
de "même bruit" n'a pas de sens.

Disons que ça va
juste changer les proportions de lenteur.

???

- dans vos fonctions est_pairx(), mettre juste
return 0;
Si ça se trouve ce sera plus long ;-)

Pas compris.

Tu m'étonnes, John. Si:

int est_pair0(int n)
{
return !(n & 0x1);
}

vous remplacez par:

int est_pair0(int n)
{
return 0;
}

chez moi c'est un peu plus long. Ce qui pourrait vous convaincre que
vous ne mesurez que du bruit.

- virer le printf() dans test().

Il est bien pratique pour vérifier la conformité entre les tests mais on
peut réduire les affichages.

Bien entendu. Le problème c'est que vous le placez avant la prise de
date. Il est très facile de contourner ce problème. CF Ed

- remplacer le f(i * j) dans test() par l'une ou l'autre de vos
instructions.

Oui mais il faut bien que je fasse quelque chose d'utile (sinon les
optimisations peuvent ignorer les calculs) et d'assez long pour que ce
soit significatif.

Bien entendu, il faut vérifier. Si ça ne marche pas, ne pas hésiter à
utiliser /volatil/.

- Alternativement, écrire une:
static int est_pair(int n) // ou static inline etc.
{
return !(n % 2);
}
et l'appeler directement dans test().

Jamais bien compris cet histoire de inlining

C'est quand même fondamental. Vous mesurez en réalité des appels
lourds, avec tout le bordel dans la pile et la pile de fonctions.

mais de toute façon, la
question ne va plus se poser puisque je vais réécrire les tests sans
appel de fonctions.

J'ai des doutes.

Puisque vous êtes sur l'optimisation, voyez le f(i*j) en fond de boucle.
Ça peut être coûteux et bien plus long (le bruit le bruit) que votre

Vous proposez quoi à la place car je n'ai pas beaucoup d'imagination ?

Ça c'est du B-A-BA de la programmation. Bien entendu à chaque turn du
fond de boucle, vous n'avez pas besoin de faire f(i*j) mais f(k) avec k
+= i)

instruction à tester, si le compilateur ne constate pas à votre place
que cette multiplication de deux valeurs non constantes n'est en fait
qu'un incrément.

Comprends pas.

Vous m'étonnez. CF plus haut. Rassurez-moi: vous êtes dans l'Education
Nationale ?

--
Pierre Maurette

Samuel Devulder, le 31/10/2009 a écrit :

[...]

En fait c'est faux si x est signé.

Vous parlez d'assembleur. En fait la différence, c'est...
C'est un peu compliqué à expliquer.

Peut-être pas si compliqué que ça...

Ce que je veux dire, c'est qu'en C, les variables sont signées, et ça
fout un grosse merde. En assembleur, ce sont les opérateurs qui sont -
ou non - signés, et c'est bien plus simple.

--
Pierre Maurette

Pierre Maurette a écrit :

Samuel Devulder, le 31/10/2009 a écrit :

[...]

En fait c'est faux si x est signé.

Vous parlez d'assembleur. En fait la différence, c'est...
C'est un peu compliqué à expliquer.

Bah de toute façon pour comprendre pourquoi tel ou tel code C a priori
équivalents ne marchent pas à la même vitesse, une bonne façon de
comprendre est de jeter un oeil au code ASM.

Pas besoin de tout savoir lire, on identifie assez vite les accès
mémoire, les sauts et les registres et le goulet d'étranglement saute au
yeux, mais pas toujours. Par exemple la recherche du min/max de la
semaine dernière, car là c'était en deçà de l'ASM que la différence
d'algo se produit (prédiction de sauts dans le CPU).

Peut-être pas si compliqué que ça...

Ce que je veux dire, c'est qu'en C, les variables sont signées, et ça
fout un grosse merde. En assembleur, ce sont les opérateurs qui sont -
ou non - signés, et c'est bien plus simple.

Oui, tu veux dire qu'en ASM on doit savoir ce que l'on fait. Ca devrait
être partout la même chose non? En fait le soucis est que l'on ne pense
pas naturellement en complément à 2. Je suis persuadé que beaucoup, si
ce n'est tous pensent intuitivement "positif" ou éventuellement avec un
bit de signe séparé du reste comme dans les float IEEE (donc 2 valeurs
de zéro). Cela n'aide pas à écrire des expressions valides
indépendamment du signe.

Du coup (x%16) devenant (x&15) marche bien pour les positifs et se casse
la figure pour les négatifs. Avec une représentation snnnnnnn (ie bit de
signe séparé) ça serait plus simple, on écrirait (x & 0b10001111) (abus
de notation avec le 0bnnnnn, mais il manque une façon simple de
représenter les nombres binaires en C de toute façon, donc j'emprunte au
vhdl pour l'occasion). Mais bon on est contraint au complément à 2, il
faut faire avec elle et ses pièges.

D'ailleurs la représentation en complément à 2 est assez dangereuse dans
le sens ou elle est "asymétrique". La valeur minimale est son propre
inverse (sommée à elle même elle le résultat vaut zéro), donc on ne peut
assumer que l'opposé d'un nombre négatif est toujours positif. C'est
assez troublant, et fait que par exemple que le code suivant est non
fiable malgré les gardes-fous:

#define SIZE 10
int tab[SIZE];

int get_tab(int n) {
if(n<0) n = -n;
if(n>=SIZE) n = SIZE-1;
return tab[n];
}

en effet get_tab(INT_MIN) déborde le tableau par le bas car le garde-fou
à n<0 ne change pas le signe de n quand n=INT_MIN.

sam.