Différence de performances entre entiers signés et non signés

**Goten** · 11/04/2009, 23h21

Salut à tous,

je me trouve face à un cas optimisé par le compilateur que je m'explique pas, enfin je m'explique pas la différence plus que notable de performances engendrés voici le code (tout ce qu'il y'a de plus banal) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
#include <iostream>
 
int main()
{
     int maxLenght = 0, result = 0, node, chainLenght;
 
    for(unsigned int i = 1; i<1000000; ++i)
    {
 
        node = i;
 
        chainLenght = 0;
 
        while(node!=1)
        {
            if(node%2 == 0)
            {
                node = node/2;
            }
            else //node is odd
            {
                node = 3*node + 1;
            }
 
            ++chainLenght;
        }
 
        if(chainLenght > maxLenght)
        {
            maxLenght = chainLenght;
            result = i;
        }
    }
 
    std::cout << result;
    return 0;
}

Je compile ce code puis j'exécute je m'attendais à quelque chose d'assez lent ... j'ai été servi : 15 minutes plus tard j'avais toujours aucun résultat, j'ai donc stoppé et cherché si il y'avait pas de boucle infinie ou autre. Puis me rendant à l'évidence me suis dit autant gagné un peu sur les types et les passé en unsigned int étant sur de n'avoir aucunes valeurs négatives :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
     unsigned int maxLenght = 0, result = 0, node, chainLenght;

Je recompile, exécute et là, en moins d'une seconde j'ai un résultat (valide soit dit en passant).

15 min vs 1 seconde... je trouve cette différence énorme, donc j'aimerais savoir si c'est parce que en signé il y'a des mécanismes de vérification qui se font dans mon dos? Ou alors le compilo a vraiment vraiment bien optimisé avec les unsigned.

Pour info j'ai compilé sous mingw en release et avec l'option -O3.

Merci d'avance pour vos réponses.

**ram-0000** · 11/04/2009, 23h31

Tient, cela ressemble à une suite de syracuse !!

Une petite idée comme cela, mais il faudrait voir le code assembleur généré. Ici :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
            if(node%2 == 0)
            {
                node = node/2;
            }

Quand node est unsigned,

l'opération modulo 2 peut être remplacée par un test sur le bit de poid faible (ce qui n'est peut être pas vrai en logique signée, à confirmer). Je ne sais pas en quoi est transformé le modulo en assembleur (une division puis test du reste, cela doit être assez long)
la division par 2 peut être remplacée par un décalage (ce qui n'est peut être pas vrai en logique signée)

**Goten** · 11/04/2009, 23h43

Yep ça en est bien une.

Bon euh là j'ai fait ça vite fait sous windows et code::blocks, donc je sais pas comment avoir accès à l'assembleur généré :/. (si quelqu'un a une idée), sinon je ferais ça demain sous linux avec gcc.

**koala01** · 12/04/2009, 09h47

Salut,

Ce serait bien possible que l'optimisation puisse se faire en logique signée et non signée car, sauf erreur, les processeurs "PC" travaillent en complement à 2 lorsqu'ils utilisent des nombres signés (et négatifs)

L'"astuce", c'est que tu ne devrais normalement pas avoir de nombres négatifs dans une suite de syracuse (sauf en cas de dépassement de valeur)

Pour obtenir le code assembleur, il faut passer par la compilation en mode console (menu démarrer->exécuter->taper cmd) et lancer la commande

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

gcc -S fichier_a_compiler.cpp

Le code assembleur sera fourni dans un fichier nommé fichier_a_compiler.s

**Goten** · 12/04/2009, 10h55

Hum, ouaip koala je connais bien l'option -S, seulement elle n'est pas dispo sous code::blocks. Et à ma connaissance sans cygwin on peut pas appellé mingw directement en console sous windows.
Bref je booterais sous nux histoire de voir le code asm produit.

**Médinoc** · 12/04/2009, 11h15

Envoyé par Goten

Et à ma connaissance sans cygwin on peut pas appellé mingw directement en console sous windows.

C'est faux, je l'ai déjà fait.

**Goten** · 12/04/2009, 11h19

Et donc, comment?

(le à ma connaissance, incluait que si quelqu'un savait comment faire j'étais ouvert à toute proposition, parce que ça peut être utile par moment.

**Arzar** · 12/04/2009, 11h32

Euu dites les gens vous croyez vraiment qu'une bête changement de signed à unsigned peut déclencher une optimisation faisant passer un programme de 15min à 1 seconde.

Y a juste un overflow sur node qui dépasse INT_MAX (les valeurs de la suite de Syracuse ça peut monter très haut avant de revenir à 1), donc node part dans les négatifs et on tombe sur une boucle infinie...

**Goten** · 12/04/2009, 11h35

J'ai pas osé émettre l'hypothèse, ne sachant pas jusqu'où montait la suite de syracuse mais en effet ça me semble plus probable... Quoique... tu penses que ça peut dépasser les 2^32 pour une valeur de départ inférieur à 1 millions?

**Arzar** · 12/04/2009, 11h42

Oui, ça ne m'étonnerait pas.
Je me souviens plus jeune mettre acharné sur ma calculatrice pour vérifier que même un grand nombre, comme 1 million, revenait toujours à 1 (à la main, je ne connaissais pas la programmation à l'époque

) et j'avais vite abandonné car les valeurs montaient parfois vraiment très haut. Il y a un exemple sur la page wikipédia anglaise qui part de 27 et dépasse les 9000 par exemple.

**Arzar** · 12/04/2009, 12h26

Bon je viens de tester rapidement au debuggeur et node passe effectivement dans les négatifs.

Avec en prime une découverte mathématique majeure ! La conjecture de Syracuse est fausse pour les entiers négatifs ! La suite ne se stabilise pas autour de -1, mais fait des sortes de cycle .

**ram-0000** · 12/04/2009, 12h35

Bon ben il faut passer au unsigned long long int. Avec 64 bits, tu devrait pouvoir aller plus loin.

**Goten** · 12/04/2009, 17h23

Bon après quelques tests pour affiché la valeur maximale de la suite, avec un unsigned int ou un unsigned long long j'ai pas la même valeur. Donc j'en déduit que si c'est passé avec un unsigned int (résultat juste) c'est un coup de chance.

Donc pour un n<1000000 la suite de syracuse monte jusqu'à 569111483520.

**koala01** · 12/04/2009, 20h00

Envoyé par Goten

Et donc, comment?

(le à ma connaissance, incluait que si quelqu'un savait comment faire j'étais ouvert à toute proposition, parce que ça peut être utile par moment.

Tout simplement:

Tu commence par rajouter le chemin Disque:\La\OuSeTrouve\Gcc\bin à ta variable PATH

Procédure:
menu démarrer->panneau de configuration->système->onglet "avancé"->cliquer sur le bouton "variables d'environnement":
dans la liste "variables système", trouver la variable Path, cliquer sur modifier, aller en fin de ligne, rajouter un point virgule ";"suivi du chemin à suivre pour arriver au dossier bin du dossier gcc

Par la suite, il te suffit de lancer une console
procédure:
menu démarrer->exécuter->taper "cmd" et cliquer sur "ok" ou
menu démarrer->tous les programmes->accessoires->Invite de commandes

Tu peux t'assurer que l'exécutable gcc est bien reconnu (et en profiter pour vérifier la version) en tapant "gcc -v"

"YAPUKA" aller dans le dossier dans lequel se trouvent les fichier à compiler et à t'amuser

**Goten** · 12/04/2009, 20h47

Héhé, bien fait de parler moi :p. Merci bien, tout est en ordre

.

Différence de performances entre entiers signés et non signés

C++

Discussions similaires

Partager

Partager