Discussion :

[Goten]

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]

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]

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]

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]

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]

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

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