IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Contribuez C++ Discussion :

De la rapidité du code [Trucs & Astuces]


Sujet :

Contribuez C++

  1. #41
    Membre éclairé
    Profil pro
    Inscrit en
    Juillet 2002
    Messages
    842
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2002
    Messages : 842
    Points : 696
    Points
    696
    Par défaut
    Va demander a ceux qui creent les moteurs 3D de quake 3 et dee unreal, si il n'utilise pas les optimisation du processeur. Si on parle d'optimisation, c'est parce que ca peut nous servir. (Moi je m'en sert pour l'ecriture d'un emulateur). Il n'y a pas tant de type dee processeur que ca, a partir du moment ou tu consifere que tu programmes pour un PC. Il y a (en assembleur) 4 types d'optimisations :

    - remplaceer des instructions assembleur par des equivalent qui sont plus rapide (En général pour le 486)

    - Optimisations pour le pentium 4 (Le trruc qui permet d'executer deux instructions en un cycle)

    - Utilisation de la cache.

    - Utilisation du mmx 3DNox, etc.

    Les optimisations du C++ concernent quant a elle, la quasi-totalité des procecsseurs puisque ce sont des optimisations d'algorythme.


    Blustuff.

  2. #42
    Membre éclairé
    Profil pro
    Inscrit en
    Juillet 2002
    Messages
    842
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2002
    Messages : 842
    Points : 696
    Points
    696
    Par défaut
    Ca m'intriguait alors j'ai mis mon compilateur a l'épreuve (BC++ Builder 4). Et ca marche. on peut bien effectuer des divisions ou des multiplications par des puissances de 2 sur dees nombres negatifs. Essayez voir si ca marche sur votrre compilateur :

    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
    #include "iostream.h"
     
    void main()
    {
      unsigned int a = 100;
      signed int b = -100;
     
      cout << (a >> 1) << '\n';
     
      asm shr a, 1
      cout << a  << '\n';
     
      cout << (b >> 1)  << '\n';
     
      asm sar b, 1
      cout << b  << '\n';
    }
    qui donne la sortie (theoriquement) :

    J'explique pour ceux que ca interesse. Lorsque le compilateur rencontre l'operateur << ou >> il "traduis" l'operation en une instructions assembleur choisie parmis "sar", "shr", "sal", "shl". Si c'est l'operateur >> l'instruction se finira par r (right) cad shr ou sar, si c'est << l'instruction sera shl ou sal. Si la variable a gauche de l'operateur << ou >> (cad l'operande sur laquelle on fait le décalage) est signed l'instrtuction correspondante sera sar ou sal, si l'operande est unsigned l'instruction assembleur sera shr ou shl.

    Voici la différence entrte un decalage signé et un décalage non signé :

    ---------------------------------------------------------------------------------
    --- Decalages vers la droite ---

    * Decalage signé :

    Ex :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    signed int a = 24;
    a >>= 2;
    Representation binaire de 24 : 00011000
    Après deux décalage à droite : xx000110

    Pour connaitree la valeur des x, lors d'un decalage signé on regarde le bit de poid le plus fort. Ici c'est 0. Donc les x seront remplacé par des 0

    Valeur finale de a : 00000110 (= 6 = 24 / 4)


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    signed int a = -24;
    a >>= 2;
    Representation binaire de 24 : 11101000
    Après deux décalage à droite : xx111010

    comme le bit de poid le plus fort est 1, les x sont remplacés par des 1

    Valeur finale de a : 11111010 (= -6 = -24 / 4)


    * Decalage non signé :

    Ex :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    unsigned int a = 24;
    a >>= 2;
    Representation binaire de 24 : 00011000
    Après deux décalage à droite : xx000110

    Dans le cas de nombres signés on remplace toujours les x par des 0.

    Valeur finale de a : 00000110 (= 6 = 24 / 4)


    --- Decalages vers la gauche ---

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    unsigned int a = 24
    signed b = 24;
    a <<= 2;
    b <<= 2;
    Representation binaire de 24 : 00011000
    Après deux décalage à gauche : 011000xx

    Pour le décalage a gauche, que l'operande soit signée ou non signée les x sopnt toujours remplacés par 0. (Ca n'aurait aucun sens si ct autrtement). C'est la raison pour laquelle sal et shl represente la même opération pour le processeur.

    Valeur finale de a : 01100000 (= 96 = 24 * 4)

    ---------------------------------------------------------------------------------


    Quoiqu'il arrive les décalages de bits sont toujours (theoriquement) des divisions ou des multiplications par des puissances de 2.


    Blustuff.

  3. #43
    Membre averti

    Inscrit en
    Juin 2002
    Messages
    97
    Détails du profil
    Informations forums :
    Inscription : Juin 2002
    Messages : 97
    Points : 307
    Points
    307
    Par défaut
    Citation Envoyé par Blustuff
    Toutes les variables constantes donnent exactement le même effet que les #define
    Malheureusement non.
    Une constante externe, par exemple, a une valeur inconnue du compilateur.
    La preuve: elle ne peut pas servir de valeur case ou paramètre de patron en C++.

    Je comprends pas pourquoi << fonctionne pas pour les negatifs.
    Mais il marche ! La subtilité, c'est que >> arrondit vers le bas:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     3>>1 =  1,5 =  1
    -3>>1 = -1.5 = -2
    Ça n'est bien sûr pas une spécification du standard.

    Et comme la division est définie comme entière, elle est censée arrondir vers 0, donc le compilateur ne remplace pas /2 par >>1 pour une valeur susceptible d'être négative.
    CQFD.




    Quand je pense 'optimisation'...

    1) Il ne s'agit pas de faire le boulot du compilateur.
    Simplement, au lieu d'être passif, on peut l'aider en se se débrouillant pour lui présenter les choses de façon favorable.
    Encore faut-il avoir un vrai compilateur !

    2) Le compilateur a une portée limitée.
    Il y a des choses qui ne sont pas de son ressort, comme l'organisation intelligente des E/S, appels systèmes et accès mémoire.
    C'est au développeur de connaître les coûts de ces opérations et de ne pas faire l'andouille.

    3) Il n'y a pas que la vitesse propre a optimiser.
    Il y a aussi la taille et la charge placée sur le système.

    4) Une optimisation bien pensée sera portable, sûre, et automatique.


    Si on pense à la réutilisation de code, ça ne fait pas de mal d'être vigilant dès le départ.
    Une optimisation n'est pas forcément possible après-coup si c'est l'organisation qui est en cause.

    On peut optimiser une fonction tout de qu'on veut, si à la base on aurait pu éviter son appel...
    "J'ai toujours rêvé d'un ordinateur qui soit aussi facile à utiliser qu'un téléphone. Mon rêve s'est réalisé : je ne sais plus comment utiliser mon téléphone."-Bjarne Stroustrup
    www.stroustrup.com

  4. #44
    Membre éclairé
    Profil pro
    Inscrit en
    Juillet 2002
    Messages
    842
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2002
    Messages : 842
    Points : 696
    Points
    696
    Par défaut
    oui, mais c'est de la connerie ca les variables const externes :). Non, c'est vrai qu'en fait j'y avait pas pensé. Mais pour cec qui est des consts non externes mon compilateurs me les integre directement. Pour -3 >> 1 ca peut etre vrai, si on considère bien la definition ded la division euclidienne :

    n = q*p + r avec q quotient, et r reste, 0 <= r < q

    donc le resulta de la division euclidienne de -3 par 2 est -2 !!! (Cela dit ca n'a pas grand interet)


    blustuff

  5. #45
    Futur Membre du Club
    Inscrit en
    Novembre 2002
    Messages
    6
    Détails du profil
    Informations forums :
    Inscription : Novembre 2002
    Messages : 6
    Points : 5
    Points
    5
    Par défaut
    Un petit conseil pour ceux qui utilise Borland C++:
    Compiler en mode "ANSI" et hop en 2 temps trois mouvements le programme est près a etre executé !!!
    Dans la vie on nait, on meurt et entre-temps, on s'occupe !!

  6. #46
    Membre averti

    Inscrit en
    Juin 2002
    Messages
    97
    Détails du profil
    Informations forums :
    Inscription : Juin 2002
    Messages : 97
    Points : 307
    Points
    307
    Par défaut
    Il y a des conventions de passage d'argument aux fonctions.
    C'est non-standard, mon compilateur dispose de:
    fastcall qui utilise les registres (pour les arguments qui y tiennent).
    stdcall qui utilise la pile.

    fastcall devrait donc améliorer les performances.
    Je pense même que cela évite à la fonction de devoir systématiquement sauvegarder et restaurer les registres, puisque l'appelant sait qu'ils vont être utilisés.

    Mais est-ce le cas ?
    Y a-t'il des cas défavorables ?


    Dans un autre registre...
    L'exemple des 'extern const' montre que la compilation en modules suivie de liaison entrave les optimisations globales, c-a-d à travers tout le code source utilisé par l'exécutable.
    Comment peut-on aider le compilateur à faire des optimisations globales ?
    Est-ce que mettre tout le code dans un unique fichier source peut aider ?
    (on peut simuler cela en faisant un source qui #include une fois seulement de chaque autre source)
    "J'ai toujours rêvé d'un ordinateur qui soit aussi facile à utiliser qu'un téléphone. Mon rêve s'est réalisé : je ne sais plus comment utiliser mon téléphone."-Bjarne Stroustrup
    www.stroustrup.com

  7. #47
    Membre expérimenté

    Profil pro
    Programmeur
    Inscrit en
    Août 2002
    Messages
    1 091
    Détails du profil
    Informations personnelles :
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Programmeur

    Informations forums :
    Inscription : Août 2002
    Messages : 1 091
    Points : 1 679
    Points
    1 679
    Par défaut
    le compilateur de VC++ 7 fait des optimisations globales (entre les .o d'un projet). Je ne sais pas ce que ca recouvre.
    Pour fastcall ca marche presque toujours faut juste faire attention aux callbacks, et evidemment a l'appel d'une fonction d'un .o ou d'un .lib depuis un projet qui n'utilise pas les memes conditions d'appels.

    Pour le gros fichier source on fait comme ca chez nous. Mais c'est moins pour des problemes d'optimisations (les fonctions a inliner sont dans les headers et on n'a pas de extern const, que des classes et des objets)
    que pour des problemes de temps de compilations.
    Les differentes libs mettent un quart d'heure a compiler en mode "allsource" (un gros fichier avec les include par librairie ou dll).
    Le comportement doit etre identique entre le projet compile allsource et celui compile normalement.

    LeGreg

    Mon site web | Mon blog | Mes photos | Groupe USA
    > BONJOUR, JE SUIS NOUVEAU SUR CE FORUM
    > presse la touche caps lock, stp
    > OH.. MERCI C EST BEAUCOUP PLUS FACILE COMME CA

  8. #48
    Membre confirmé

    Homme Profil pro
    Indépendant
    Inscrit en
    Juin 2002
    Messages
    540
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Indépendant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Juin 2002
    Messages : 540
    Points : 607
    Points
    607
    Par défaut
    Et pour celui qui en veux, éditer l'assembleur à partir du C++, puis ré-arranger le fichier assembleur.
    Fondateur Alien6 : Prescriptive Analytics & Machine Learning Software

  9. #49
    Membre expérimenté

    Profil pro
    Programmeur
    Inscrit en
    Août 2002
    Messages
    1 091
    Détails du profil
    Informations personnelles :
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Programmeur

    Informations forums :
    Inscription : Août 2002
    Messages : 1 091
    Points : 1 679
    Points
    1 679
    Par défaut
    Question posee en entretien d'embauche:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    int tab[MAX];
    for (int i=0; i<MAX; i++)
    {
       tab[i] = a * i * i + b * i + c + d;
    }
    1 - Lister les optimisations possibles pour rendre ce code plus rapide

    2 - parmi les optimisations citées quelle est l'optimisation la plus susceptible d'etre effectuee par le compilateur et qu'il ne sert donc à rien d'effectuer à la main.

    Evidemment l'interet est de voir si le candidat connait un tant soit peu les mécanismes d'optimisations des compilateurs et ne va donc pas passer son temps a optimiser du code inutilement.

    LeGreg

    Mon site web | Mon blog | Mes photos | Groupe USA
    > BONJOUR, JE SUIS NOUVEAU SUR CE FORUM
    > presse la touche caps lock, stp
    > OH.. MERCI C EST BEAUCOUP PLUS FACILE COMME CA

  10. #50
    Membre éclairé
    Profil pro
    Inscrit en
    Juillet 2002
    Messages
    842
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2002
    Messages : 842
    Points : 696
    Points
    696
    Par défaut
    moi pour répondre a cette question j'ai absolument besoin de savoir ce que sont a, b, c et d. De quel type ? des constantes ? ca va changer bcp de choses notement comment le compilateur va optimiser...

    P.S. J'ai été très decu par l'optimisation que fesait mon compilateur de mon code.

  11. #51
    Membre expérimenté

    Profil pro
    Programmeur
    Inscrit en
    Août 2002
    Messages
    1 091
    Détails du profil
    Informations personnelles :
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Programmeur

    Informations forums :
    Inscription : Août 2002
    Messages : 1 091
    Points : 1 679
    Points
    1 679
    Par défaut
    ah bon tu en as besoin?

    Pas besoin de se compliquer la tete
    c'est juste un exemple a la con et
    il n'y a pas de piege.

    LeGreg

    Mon site web | Mon blog | Mes photos | Groupe USA
    > BONJOUR, JE SUIS NOUVEAU SUR CE FORUM
    > presse la touche caps lock, stp
    > OH.. MERCI C EST BEAUCOUP PLUS FACILE COMME CA

  12. #52
    Membre éclairé
    Profil pro
    Inscrit en
    Juillet 2002
    Messages
    842
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2002
    Messages : 842
    Points : 696
    Points
    696
    Par défaut
    déja moi si MAX est inferieur à 10000 j'optimise pas, si c et d sont des constantes, le compilateur les remplace a l'execution par le resultat. Si a,b,c et d ne sont pas des int les optimisations vont etre différentes, suivant le type de chacune, pour eviter le maximum de conversions.

  13. #53
    Membre expérimenté

    Profil pro
    Programmeur
    Inscrit en
    Août 2002
    Messages
    1 091
    Détails du profil
    Informations personnelles :
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Programmeur

    Informations forums :
    Inscription : Août 2002
    Messages : 1 091
    Points : 1 679
    Points
    1 679
    Par défaut
    Citation Envoyé par Blustuff
    déja moi si MAX est inferieur à 10000 j'optimise pas, si c et d sont des constantes, le compilateur les remplace a l'execution par le resultat. Si a,b,c et d ne sont pas des int les optimisations vont etre différentes, suivant le type de chacune, pour eviter le maximum de conversions.
    peu importe MAX, ce code peut etre execute beaucoup
    de fois et on aimerait qu'il soit le plus rapide possible.

    tab[i] est un int dans ce bout de code et on part du principe que
    a b c et d sont des int aussi si ca t'arrange mais il y a des optimisations qui n'ont pas besoin de cette indication.

    Si c et d sont des constantes (pourquoi as-tu besoin que ce soit
    des constantes?) tu peux effectivement sortir le calcul du resultat de la boucle. Meme si tu prends le probleme de travers je t'accorde cette premiere optimisation.

    Dans un premier temps tu te contentes de faire comme si le compilateur n'optimisait pas (c'est ce qu'on m'a demandé de faire).

    LeGreg

    Mon site web | Mon blog | Mes photos | Groupe USA
    > BONJOUR, JE SUIS NOUVEAU SUR CE FORUM
    > presse la touche caps lock, stp
    > OH.. MERCI C EST BEAUCOUP PLUS FACILE COMME CA

  14. #54
    Membre éclairé
    Profil pro
    Inscrit en
    Juillet 2002
    Messages
    842
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2002
    Messages : 842
    Points : 696
    Points
    696
    Par défaut
    oki, je me trompe peut etre mais j'ai fait quelques test. J'arrive a ca :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
      tab[0] = c + d;
      int x = b - a - c - d;
      a *= 2;
     
      for (int i = 1 ; i < MAX ; i++)
      {
         x -= a;
         tab[i] = tab[i-1] - x;
      }
    La seule optimisation de mon compilateur est d'utiliser un pointeur sur &Tab[i] L'optimisation courante en caclulant par recursion pour supprimer les multiplication me fait gagner ~20% de vitese ce qui est un peu ridicule pour les calculs que ca demande. Un solution qui me semblait plus rapide était d'utiliser les pointeur comme on le fait de manière courante

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    for (int* p = tab, p < &tab[MAX] ; p++)
    Le code asm corespondant est plus rapide quand on compte les cycles manuelement. Mais certaienemnt pour des raisons de pairing et d'autres trucs difficilement prévisibles et dépendant du compilateur c'est plus lent.

    De toute facon 3 multiplication par ittération c'est même pas encore très lourd surtout que le compilateur s'arrange pour que les registres utilisés soient différents ce qui permet dee les faire en parrallèle.

    En résumé si jamais on a un code comme ca, autant le laisser tel quel.


    P.S.

    si c et d sont des constantes, j'entends par là les deux cas suivants :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    const int c = 3;
    const int d = 4;
     
    int e = c + d;
    et

    dans ces deux cas le compilateur effectue le calcul lui même. Donc si ce sont des constantes on laisse tel quel, si ce ne sont pas des constantes on sort le calcul de la boucle.

  15. #55
    Membre expérimenté

    Profil pro
    Programmeur
    Inscrit en
    Août 2002
    Messages
    1 091
    Détails du profil
    Informations personnelles :
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Programmeur

    Informations forums :
    Inscription : Août 2002
    Messages : 1 091
    Points : 1 679
    Points
    1 679
    Par défaut
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
      tab[0] = c + d;
      int x = b - a - c - d;
      a *= 2;
     
      for (int i = 1 ; i < MAX ; i++)
      {
         x -= a;
         tab[i] = tab[i-1] - x;
      }
    A mon avis c'est tres complique et ca ne marche pas.
    Surtout pourquoi autant de soustractions ?

    De toute facon 3 multiplication par ittération c'est même pas encore très lourd surtout que le compilateur s'arrange pour que les registres utilisés soient différents ce qui permet dee les faire en parrallèle.
    Le but ce n'est pas de discuter le cout individuel d'une operation
    mais de reduire le cout global sur un grand nombre d'appels.

    En résumé si jamais on a un code comme ca, autant le laisser tel quel.
    Je n'ai pas la reponse a cette question. A mon avis c'est une question ouverte telle qu'on peut te la poser a un entretien. L'examinateur s'attend a ce que tu proposes un certain nombre d'optimisation et que tu voies que le code qui suit ne peut pas etre compile litteralement pour s'executer de facon optimale meme si dans 98% des cas on s'en fout. En fait ce n'est pas le but de la question de savoir si ca a un sens.

    De toute facon, je ne pense pas que les programmeurs dans sa boite passent leur temps a se poser ce genre de questions, c'est juste un exo d'entretien..

    dans ces deux cas le compilateur effectue le calcul lui même. Donc si ce sont des constantes on laisse tel quel, si ce ne sont pas des constantes on sort le calcul de la boucle.
    Donc selon toi les chances pour qu'une telle optimisation ait lieu
    est de 50% ?

    En fait tu te rends bien compte que cette discussion est ridicule puisque
    cette operation va disparaitre quoi qu'il arrive a cause d'une autre optimisation: du coup le fait de savoir de quel type c et d sont n'a plus grande importance.

    LeGreg

    Mon site web | Mon blog | Mes photos | Groupe USA
    > BONJOUR, JE SUIS NOUVEAU SUR CE FORUM
    > presse la touche caps lock, stp
    > OH.. MERCI C EST BEAUCOUP PLUS FACILE COMME CA

  16. #56
    Membre éclairé
    Profil pro
    Inscrit en
    Juillet 2002
    Messages
    842
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2002
    Messages : 842
    Points : 696
    Points
    696
    Par défaut
    c'est parce que en ecrivant

    Ui = ai² + bi + c +d

    on arrive à

    Ui+1 = Ui + 2ai + a + b + c + d

    ou

    Ui-1 = Ui - 2ai + a - b + c + d

    pour des raisons dont je ne me rappelle plus j'ai coisi la deuxième ce qui nous donne :

    Ui = Ui-1 + 2ai - a + b - c - d

    d'où toutes les soustractions.
    x contient -a + b - c - d, mis sous la forme b - a - c - d par flemme de mathematicien, et incrementé de 2a a chaque fois (pour ne pas refaire la multiplication, je double a avant, il faudrait passer par une autre variable theoriquement). Donc la déja cj'ai fait une erreur, c'est += au lieu de -= et dans le calcul c'est + x et pas - x. Ca me fait penser qu'on pourrait encore essayer de supprimer un accès en mémoire en passanat par une variable intermediaire :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
      tab[0] = c + d; 
      int x = b - a - c - d; 
      int y = a * 2;
      int Temp = tab[0]; 
     
      for (int i = 1 ; i < MAX ; i++) 
      { 
         x += y;
         Temp += x;
         tab[i] = Temp; 
      }
    Mais la mon compilateur il en peux plus, puisque il déclare y dans la pile donc, un autre accès en mémoire, ce qui donne exactement la même chose, que la précedente. Pourtant moi je compte : 1)x 2)y, 3)i, 4)tab[i], 5)Temp, normalement 5 variables il y a largemnt de quoi les mettre en registre. Donc soit forcer les auto et les register, sois passer par l'asm. (moi j'y arrive pas avec mon compilo)

    Le coup d'une multiplication est important, puisque si l'on veut optimiser il ne va pas falloir forcement supprimer les multiplications, mais reduire le nombr d'operations.

    Le dernier code que j'ai optimisé j'ai plus que doublé ca rapidité. Même si j'en demande pas tant a chaque fois, pour 20 % c'était pas la peine de ce donner ce mal.

    Cela dit, j'avais enormement de mal a prevoir quel code serait plus rapide que quel autre. Sans faire des tests, j'en aurais jamais eu le coeur net.

  17. #57
    Membre expérimenté

    Profil pro
    Programmeur
    Inscrit en
    Août 2002
    Messages
    1 091
    Détails du profil
    Informations personnelles :
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Programmeur

    Informations forums :
    Inscription : Août 2002
    Messages : 1 091
    Points : 1 679
    Points
    1 679
    Par défaut
    J'ai un peu de temps a perdre
    (je suis entre deux boulots)

    Voila ce que donne la version initiale optimisee par le compilateur:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    004010A0   mov         edi,ecx
    004010A2   imul        edi,eax
    004010A5   add         edi,ebx
    004010A7   mov         dword ptr [eax*4+41CC18h],edi
    004010AE   add         ecx,3
    004010B1   inc         eax
    004010B2   cmp         ecx,3000h
    004010B8   jl          004010A0
    Et voici ce que donne une version optimisee a la main
    puis par le compilateur:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    004011D8   add         eax,4
    004011DB   add         edx,ebx
    004011DD   add         ecx,edx
    004011DF   mov         dword ptr [eax+4],ecx
    En pratique la deuxieme version
    mets trois fois moins de temps a s'executer.
    Le gain n'est donc pas vraiment negligeable pour du code
    critique.

    LeGreg

    Mon site web | Mon blog | Mes photos | Groupe USA
    > BONJOUR, JE SUIS NOUVEAU SUR CE FORUM
    > presse la touche caps lock, stp
    > OH.. MERCI C EST BEAUCOUP PLUS FACILE COMME CA

  18. #58
    Membre éclairé
    Profil pro
    Inscrit en
    Juillet 2002
    Messages
    842
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2002
    Messages : 842
    Points : 696
    Points
    696
    Par défaut
    houlà, tu pourrais tout donner ? moi ce eque je lis ca fait pas du tout cee qui est demandé a priori, ou alors j'ai pas saisi l'astuce. Quoiqu'il en soit, mon compilateur ne fait pas cecs optimisation là.

    Dans le deuxième code, il n'y a même pas de boucle !??

    Je vois mal par ailleur comment tu calcule le gain de x3. Ce qui ralentit considerablement la boucle ce sont les accès en mémoire. Et ca on y peut rien puuisque de toute facon on a le talbeau a remplir...

  19. #59
    Membre expérimenté

    Profil pro
    Programmeur
    Inscrit en
    Août 2002
    Messages
    1 091
    Détails du profil
    Informations personnelles :
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Programmeur

    Informations forums :
    Inscription : Août 2002
    Messages : 1 091
    Points : 1 679
    Points
    1 679
    Par défaut
    je n'ai pas mis tout le code genere juste la partie qui est repetee et qui
    est le seul truc qui importe si MAX est grand.

    On voit sur le premier segment en assembleur
    que le compilateur optimise pas mal de truc
    auxquels on n'aurait pas forcement pensé
    mais qu'il reste encore deux multiplications
    (il ne faut pas oublier celle qui est cachee dans l'ecriture tab[i])
    une comparaison et un jump par element du tableau.

    Dans la deuxieme version on a surement optimise
    le plus qu'on pouvait en se ramenant a quelque chose
    comme 4 additions par element du tableau (dont deux
    redondantes).

    Supprimer les multiplications est surement la partie la plus dure pour
    le compilateur et la main de l'homme aide pas mal dans ce cas la:
    en jouant avec deux variables temporaires et en supprimant l'ecriture
    tab[i] de la boucle:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    int temp1 = c + d ;
    int temp2 = a + b ;
    int * p = tab;
    const int a2 = 2 * a;
    for (j=0; j < MAX; j++) 
    { 
      *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
    }
    Reste la comparaison et le saut, on ne peut pas entierement les supprimer
    mais en partant du principe que MAX est grand devant 1
    on peut limiter leur cout par element du tableau.
    On deroule la boucle a la main et on se retrouve a un cout
    de 1/32 (comparaison + saut) par element de tableau a la place de 1.

    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
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    int temp1 = c + d ;
    int temp2 = a + b ;
    int * p = tab;
    const int MAXDIV = MAX >> 5; // divided by 32 
    const int MAXMOD = MAX & 31; // modulo 32
    const int a2 = 2 * a;
    for (j=0; j < MAXDIV; j++) 
    { 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
     
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
     
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
     
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
     
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
     
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
     
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
     
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2; 
     
    }
    for (j=0; j < MAXMOD; j++) 
    { 
        *p++ = temp1; temp1 = temp1 + temp2; temp2 = temp2 + a2;
    }
    J'ai choisi 32, apparemment le gain apporte
    devient vite negligeable (difference entre 1/32 et 1/64)
    par contre le surcout de developper trop la boucle lui peut
    devenir important (taille du code => influence sur le cache miss)

    LeGreg

    Mon site web | Mon blog | Mes photos | Groupe USA
    > BONJOUR, JE SUIS NOUVEAU SUR CE FORUM
    > presse la touche caps lock, stp
    > OH.. MERCI C EST BEAUCOUP PLUS FACILE COMME CA

  20. #60
    Membre éclairé
    Profil pro
    Inscrit en
    Juillet 2002
    Messages
    842
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2002
    Messages : 842
    Points : 696
    Points
    696
    Par défaut
    Une multiplication cachée dans Tab[i] ?????

    Qu'est ce que le compilateur a optimisé auquel on aurait pas pensé ? (Moi mon compilateur il optimise juste un seul truc, alors on va pas loin...)

    On gagne que dalle en déroulant la boucle. Les prediction on un taux de réussité très proche de 100 % quelque soit la methode ded prédiction, et le gain toutefois obtenu par le déroulement, est ridicule par rapport au coup de l'accès en mémoire. Si MAX est grand on va avoir 1 cache miss toutes les 8 iteration, ou développé, 4 miss pour 1 ittération, non ?

    Je crois que le seul gain interessant est la suppression des multiplication; parce que je me suiis trompé, il y en a 2 seulement en parrallèe la dernière devant attendre un resultat, c'est ce qui doit donner le gain de 20% chez moi.

Discussions similaires

  1. Réponses: 1
    Dernier message: 31/08/2014, 17h52
  2. Optimiser rapidité code
    Par bobosh dans le forum VBA Access
    Réponses: 2
    Dernier message: 28/08/2008, 16h12
  3. Optimisation code pour gagner en rapidité
    Par polodu84 dans le forum MATLAB
    Réponses: 2
    Dernier message: 05/03/2008, 15h32
  4. requete QBE / requete code : rapidité et index
    Par LostIN dans le forum Requêtes et SQL.
    Réponses: 11
    Dernier message: 05/07/2006, 08h54
  5. [rapidité du code] Mise a jour a partir d'un TQuery.
    Par goethe dans le forum Bases de données
    Réponses: 4
    Dernier message: 27/10/2004, 09h01

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo