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

C++ Discussion :

optimiser le temps de calcul


Sujet :

C++

  1. #1
    Futur Membre du Club
    Femme Profil pro
    Inscrit en
    Février 2012
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Algérie

    Informations professionnelles :
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Février 2012
    Messages : 2
    Points : 5
    Points
    5
    Par défaut optimiser le temps de calcul
    Salut,,

    S V P,, Avez vous des astuces qui me permettent d'optimiser le temps de calcul de mon programme écrit en c++,,

    Merci par avance!!

  2. #2
    Membre chevronné Avatar de Ehonn
    Homme Profil pro
    Étudiant
    Inscrit en
    Février 2012
    Messages
    788
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 34
    Localisation : France

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

    Informations forums :
    Inscription : Février 2012
    Messages : 788
    Points : 2 160
    Points
    2 160
    Par défaut
    Bonjour

    Il nous faudrait plus de détail (code par exemple) pour te répondre. Voici quelques généralités
    - faire des benchmarks
    - flags de compilation (-O3 -DNDEBUG -march=native -ffast-math)
    - réduire la complexité de l'algorithme
    - éviter les calculs et les copies inutils
    - parcourir la mémoire "dans le bon sens"
    - parallélisation

  3. #3
    Rédacteur

    Avatar de Davidbrcz
    Homme Profil pro
    Ing Supaéro - Doctorant ONERA
    Inscrit en
    Juin 2006
    Messages
    2 307
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Suisse

    Informations professionnelles :
    Activité : Ing Supaéro - Doctorant ONERA

    Informations forums :
    Inscription : Juin 2006
    Messages : 2 307
    Points : 4 732
    Points
    4 732
    Par défaut
    Optimiser, ce n'est pas une question d'astuce : il faut être précis et méthodique.

    Il faut d'abords commencer par profiler ton programme, voir ou le programme passe du temps et quels sont les bottlenecks.
    Avec ces infos, on peut essayer d'adapter l'algorithme (source première de gain de performance [1]). Après, on peut éventuellement regarder le tête du code (copie a outrance, cache friendly or not)

    Et si jamais ca suffit pas, on peut alors aller chercher dans le multi threading

    Bref, sans plus de détail ni de contexte, difficile d’être plus précis.

    ------------------------------------------
    1 : Ca peut etre un changement de complexite (n^2 en n*log n) par exemple, que des changements qui vont impacter les accès mémoires (cache miss, ...)
    "Never use brute force in fighting an exponential." (Andrei Alexandrescu)

    Mes articles dont Conseils divers sur le C++
    Une très bonne doc sur le C++ (en) Why linux is better (fr)

  4. #4
    Membre régulier
    Homme Profil pro
    Développeur du dimanche
    Inscrit en
    Février 2013
    Messages
    154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur du dimanche

    Informations forums :
    Inscription : Février 2013
    Messages : 154
    Points : 105
    Points
    105
    Par défaut
    Salut,

    Ce qui prend généralement le plus de temps, dans un programme, c'est les boucles. Heureusement, il y a cet article :
    http://frouin.me/optimisation-en-cpp/

    Après.. Toutes les structures que tu utilises dans ton programme (vector, list, map) n'ont pas la même réactivité si je puis dire : penche toi sur la notion de complexité, et poses toi toujours la question de savoir si tu ne peux pas utiliser une autre structure.

    Le plus simple, évidement, c'est de chronométrer un algorithme (perso j'utilise sf::Clock avec la bibliothèque SFML, mais il doit y avoir l'équivalent dans la bibli standard), et de voir quelles modifications peuvent être efficaces en terme de rapidité.

    Cordialement,
    "There should be no boundaries to human endeavor" - Hawking
    Retrouvez moi sur GitHub : https://github.com/JeanLouisMassei

  5. #5
    Expert éminent sénior

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 189
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 189
    Points : 17 141
    Points
    17 141
    Par défaut
    J'avais eu un professeur qui résumait l'optimisation ainsi:

    1. Choisir un compromis espace-temps
    2. Établir un contexte favorable,
    3. Réduire le volume total d'informations, après tout, "La plus rapide façon de calculer, c'est encore de ne pas calculer du tout",
    4. Réduire la complexité de tous les grands calculs,
    5. Si le programme reste trop lent, envisager des optimisations "magiques"


    Ce qui signifie concrètement:
    Mémoire ou temps
    Un programme devra choisir entre utiliser moins de mémoire et moins de temps. Dans ton cas, c'est moins de temps.

    Établir un contexte favorable
    Ehonn en a parlé, il s'agit de choisir les flags de compilations orienté vers cette optimisation.

    Réduire le volume total d'informations
    Là, il s'agit de tenter de supprimer des calculs.
    Je n'ai pas d'idée d'exemple à te donner, mais l'idée est que rien n'ira plus vite que de se passer d'un long calcul.

    Réduire la complexité de tous les grands calculs
    Ça demande de savoir quels sont les longs calculs, donc de profiler.
    Cela dit, tu peux avoir une idée initiale: les calculs qui sont le but du programme.
    Un programme de calcul matriciel va très certainement devoir optimiser la somme et le produit matriciel.

    Une fois que tu le sais, renseigne toi sur la complexité espérable.
    Par exemple un tri en N*log N, une recherche dans un espace trié en log N.

    Vérifie aussi si tu passes plus de temps à lire et ordonner tes données ou à les consulter.
    Ça te permettra de choisir entre une collection triée (comme un arbre, et donc une map) ou une collection plus rapide à parcourir, mais à trier une fois (vector)

    Dans ce cadre de réduction de complexité, il faut choisir une unité de temps.
    J'en vois trois: l'affectation, l'accès à une collection et l'accès disque

    En général, c'est en nombre d'accès aux collections qu'il faut faire attention.

    Quant à la magie, réserve la aux cas ultimes, et c'est vraiment au coup par coup, une fois que tu sais que le programme est algorithmiquement optimal.
    Mes principes de bases du codeur qui veut pouvoir dormir:
    • Une variable de moins est une source d'erreur en moins.
    • Un pointeur de moins est une montagne d'erreurs en moins.
    • Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
    • jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
    • La plus sotte des questions est celle qu'on ne pose pas.
    Pour faire des graphes, essayez yEd.
    le ter nel est le titre porté par un de mes personnages de jeu de rôle

  6. #6
    Rédacteur

    Avatar de Davidbrcz
    Homme Profil pro
    Ing Supaéro - Doctorant ONERA
    Inscrit en
    Juin 2006
    Messages
    2 307
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Suisse

    Informations professionnelles :
    Activité : Ing Supaéro - Doctorant ONERA

    Informations forums :
    Inscription : Juin 2006
    Messages : 2 307
    Points : 4 732
    Points
    4 732
    Par défaut
    Citation Envoyé par MrPchoun Voir le message
    Salut,

    Ce qui prend généralement le plus de temps, dans un programme, c'est les boucles. Heureusement, il y a cet article :
    http://frouin.me/optimisation-en-cpp/

    Après.. Toutes les structures que tu utilises dans ton programme (vector, list, map) n'ont pas la même réactivité si je puis dire : penche toi sur la notion de complexité, et poses toi toujours la question de savoir si tu ne peux pas utiliser une autre structure.

    Le plus simple, évidement, c'est de chronométrer un algorithme (perso j'utilise sf::Clock avec la bibliothèque SFML, mais il doit y avoir l'équivalent dans la bibli standard), et de voir quelles modifications peuvent être efficaces en terme de rapidité.

    Cordialement,
    Le lien que tu donne est clairement le genre de chose a (globalement) NE PAS FAIRE, c'est a dire des micros optimisations dans tous les sens, qui vont dégrader fortement la lisibilité du code (et donc complexifier sa maintenance et/ou debug) alors que le compilateur fera mieux que toi dans 99% des cas Tant que la règle du As-if n'est pas brise, il peut faire ce qu'il veut avec ton programme (réarrangement des instructions, réutilisation de variable,...) et au final ce que tu aura écrit ne sera pas ce qui sera exécute.
    "Never use brute force in fighting an exponential." (Andrei Alexandrescu)

    Mes articles dont Conseils divers sur le C++
    Une très bonne doc sur le C++ (en) Why linux is better (fr)

  7. #7
    Membre chevronné Avatar de Ehonn
    Homme Profil pro
    Étudiant
    Inscrit en
    Février 2012
    Messages
    788
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 34
    Localisation : France

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

    Informations forums :
    Inscription : Février 2012
    Messages : 788
    Points : 2 160
    Points
    2 160
    Par défaut
    Citation Envoyé par leternel Voir le message
    Réduire le volume total d'informations
    Là, il s'agit de tenter de supprimer des calculs.
    Je n'ai pas d'idée d'exemple à te donner, mais l'idée est que rien n'ira plus vite que de se passer d'un long calcul.
    Pour les calculs itératifs (convergence), on peut commencer en simple précision et finir en double précision.
    Dans certains cas, on peut se contenter d'une solution approchée (algorithme génétique contre recherche exhaustive).

  8. #8
    Membre régulier
    Homme Profil pro
    Développeur du dimanche
    Inscrit en
    Février 2013
    Messages
    154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur du dimanche

    Informations forums :
    Inscription : Février 2013
    Messages : 154
    Points : 105
    Points
    105
    Par défaut
    Citation Envoyé par Davidbrcz Voir le message
    Le lien que tu donne est clairement le genre de chose a (globalement) NE PAS FAIRE, c'est a dire des micros optimisations dans tous les sens, qui vont dégrader fortement la lisibilité du code (et donc complexifier sa maintenance et/ou debug) alors que le compilateur fera mieux que toi dans 99% des cas Tant que la règle du As-if n'est pas brise, il peut faire ce qu'il veut avec ton programme (réarrangement des instructions, réutilisation de variable,...) et au final ce que tu aura écrit ne sera pas ce qui sera exécute.
    Bonjour,

    Effectivement, certaines optimisations proposées par l'article rendent le code carrément illisible, après si on les utilise juste pour une petite fonction, à mon sens, ce n'est pas bien grave. Il y a tout de même quelque éléments intéressants : éviter les tests dans les boucles, préférer les entiers aux réels, les multiplications (*0.5) aux divisions (/2), et dans une série de tests, placer le test le plus probable en tête..



    Cordialement,
    "There should be no boundaries to human endeavor" - Hawking
    Retrouvez moi sur GitHub : https://github.com/JeanLouisMassei

  9. #9
    Rédacteur

    Avatar de Davidbrcz
    Homme Profil pro
    Ing Supaéro - Doctorant ONERA
    Inscrit en
    Juin 2006
    Messages
    2 307
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Suisse

    Informations professionnelles :
    Activité : Ing Supaéro - Doctorant ONERA

    Informations forums :
    Inscription : Juin 2006
    Messages : 2 307
    Points : 4 732
    Points
    4 732
    Par défaut
    Citation Envoyé par MrPchoun Voir le message
    Bonjour,

    Effectivement, certaines optimisations proposées par l'article rendent le code carrément illisible, après si on les utilise juste pour une petite fonction, à mon sens, ce n'est pas bien grave. Il y a tout de même quelque éléments intéressants : éviter les tests dans les boucles, préférer les entiers aux réels, les multiplications (*0.5) aux divisions (/2), et dans une série de tests, placer le test le plus probable en tête..



    Cordialement,
    Non. Dans le tas, ya du bon sens (oui, l'arithmétique entiere est plus rapide que celle flottants, c'est logique). Pour multiplication vs division, j'attends de voir l'ASM généré, car c'est typiquement le truc que le compilateur va faire comme un grand.

    Pour placer le coup du test le plus probable, c'est vrai mais il faut connaitre comment marche un processeur pour comprendre le pourquoi.
    Pour éviter de pourrir le pipeline d'instruction, le CPU va faire lors d'un test un pari sur quelle branche va être la bonne et charger les instructions correspondantes. Si jamais il se plante, il doit vider le pipeline et ca prend du temps. Si en plus c'est dans une boucle et quil se plante a chaque fois, tu plombes les perfs...

    C'est pareil pour le cache ; le temps d’accès RAM est constant, donc autant en lire le plus possible (en choisissant via le principe de localité) et mettre le tout en cache. Donc si a l'instruction suivante, tu n'utilises pas ce qui mis en cache, tu prends un cache miss, le CPU doit alors vider le cache et retourner chercher ce qu'il faut en RAM. ca aussi ca plombe les perfs...

    En général les gains se feront sur l'algorithme : En premier lieu en réduisant la complexité de l'algorithme, et ensuite travailler le code pour qu'il soit cache friendly. Mais ca ne se fait pas sans avoir lu un cours d’architecture, ce qui devrait être obligatoire dans tout cursus qui fait du big data/HPC.
    "Never use brute force in fighting an exponential." (Andrei Alexandrescu)

    Mes articles dont Conseils divers sur le C++
    Une très bonne doc sur le C++ (en) Why linux is better (fr)

  10. #10
    Membre chevronné
    Avatar de Joel F
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Septembre 2002
    Messages
    918
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Service public

    Informations forums :
    Inscription : Septembre 2002
    Messages : 918
    Points : 1 921
    Points
    1 921
    Par défaut
    Citation Envoyé par MrPchoun Voir le message
    Salut,

    Ce qui prend généralement le plus de temps, dans un programme, c'est les boucles. Heureusement, il y a cet article :
    http://frouin.me/optimisation-en-cpp/
    j'aime bien ce billet, il contient plein de chose vrai ... en 1990 quand les compilos etaient juste merdiques .
    90% du temps ce genre de micro-optimisation est inutile, le compilo en fait des meilleurs, cf http://www.fefe.de/source-code-optimization.pdf

  11. #11
    Membre éprouvé
    Profil pro
    Inscrit en
    Mars 2010
    Messages
    309
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2010
    Messages : 309
    Points : 928
    Points
    928
    Par défaut
    Citation Envoyé par MrPchoun;7829721} Il y a tout de même quelque éléments intéressants : [...
    préférer [...] les multiplications (*0.5) aux divisions (/2)
    Euh, "lol"? Cet article est mauvais, et ta lecture de l'article est encore pire :-\

  12. #12
    Expert confirmé
    Homme Profil pro
    Étudiant
    Inscrit en
    Juin 2012
    Messages
    1 711
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2012
    Messages : 1 711
    Points : 4 442
    Points
    4 442
    Par défaut
    Citation Envoyé par TropMDR Voir le message
    Euh, "lol"? Cet article est mauvais, et ta lecture de l'article est encore pire :-\
    Hum ?

    Une multiplication (de float/double) est souvent plus rapide qu'une division (de float/double toujours), et ça reste une optimisation interdite pour un compilo : le résultat de x * 0.5f ou de x / 2.f n'est pas forcément le même à cause des erreurs d'arrondis.

  13. #13
    Membre chevronné Avatar de Ehonn
    Homme Profil pro
    Étudiant
    Inscrit en
    Février 2012
    Messages
    788
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 34
    Localisation : France

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

    Informations forums :
    Inscription : Février 2012
    Messages : 788
    Points : 2 160
    Points
    2 160
    Par défaut
    Même avec -ffast-math ou -Ofast ?

  14. #14
    Membre chevronné
    Avatar de Joel F
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Septembre 2002
    Messages
    918
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Service public

    Informations forums :
    Inscription : Septembre 2002
    Messages : 918
    Points : 1 921
    Points
    1 921
    Par défaut
    Citation Envoyé par Iradrille Voir le message
    Hum ?

    Une multiplication (de float/double) est souvent plus rapide qu'une division (de float/double toujours), et ça reste une optimisation interdite pour un compilo : le résultat de x * 0.5f ou de x / 2.f n'est pas forcément le même à cause des erreurs d'arrondis.
    non, diviser un reel IEEE par une puissance de deux reviens a decaler son exposant.
    C'ets plus vrai pour des cochonneries genre /3 ou/10.

    Anyway : optimisez d'abord les algos avant de vous touchez la nouille sur remplacer diviser par 17 par 3 shift/sub svp

  15. #15
    Futur Membre du Club
    Femme Profil pro
    Inscrit en
    Février 2012
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Algérie

    Informations professionnelles :
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Février 2012
    Messages : 2
    Points : 5
    Points
    5
    Par défaut
    Je suis très satisfaite de vos réponses précise et concrète et vous remercie donc sincèrement. Merci Beaucoup!!

  16. #16
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Mai 2014
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mai 2014
    Messages : 1
    Points : 0
    Points
    0
    Par défaut Petit droit de réponse :o)
    Juste pour préciser deux trois choses :

    1) Oui cet article date de il y a fort fort longtemps, gcc 2, et concernait des notes que j'avais prise lors d'écriture de code sur des Symbian, Wince ou Brew avec très peu de mémoire et ARM !
    2) Oui, il faudrait que je le reprenne, la lisibilité du code en prend un coup, et moi même n'est pas réussi très longtemps à m'y tenir, surtout en switchant de language.
    3) Bien sure de nos jours les pré-processeur / compilo s'en sorte mieux, après cela peut permettre de comprendre.
    4) J'ai quelques articles sur le timming et les optimis ASM (comme y'en a qui en parlent) : http://frouin.me/category/cpp/
    5) Je n'ai pas la science infuse donc ... c'est surtout un support de discussion et de réflexion

    Voila

  17. #17
    Membre éprouvé
    Profil pro
    Inscrit en
    Mars 2010
    Messages
    309
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2010
    Messages : 309
    Points : 928
    Points
    928
    Par défaut
    Allons y, parlons de http://frouin.me/optimisation-en-cpp/.

    Dans les cas ou l’indice de boucle n’est pas utilisé dans la boucle, une boucle pré-décrémentale et bien plus efficace qu’une boucle post-incrémentale :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    for(int i=0; i<Count; i++) DoSomething();
    Peut-être optimise par:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    for(int i=Count+1; --i;) DoSomething();
    Cette boucle génère 2 instructions de moins et réorganise la boucle de façon linéaire.
    Voyons voir. J'ai le code suivant:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void SlowIter(int iter, void (*f)()) {
      for (int i = 0; i < iter; i++) {
        f();
      }
    }
     
    void FastIter(int iter, void (*f)()) {
      for (int i = iter + 1; --i;) {
        f();
      }
    }
    Avec la version "rapide" et "lente" de la boucle. Le code genere par Clang en -O2:
    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
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    __Z8SlowIteriPFvvE:                     ## @_Z8SlowIteriPFvvE
    	.cfi_startproc
    ## BB#0:
    	pushq	%rbp
    Ltmp3:
    	.cfi_def_cfa_offset 16
    Ltmp4:
    	.cfi_offset %rbp, -16
    	movq	%rsp, %rbp
    Ltmp5:
    	.cfi_def_cfa_register %rbp
    	pushq	%r14
    	pushq	%rbx
    Ltmp6:
    	.cfi_offset %rbx, -32
    Ltmp7:
    	.cfi_offset %r14, -24
    	movq	%rsi, %r14
    	movl	%edi, %ebx
    	testl	%ebx, %ebx
    	jle	LBB0_2
    	.align	4, 0x90
    LBB0_1:                                 ## %.lr.ph
                                            ## =>This Inner Loop Header: Depth=1
    	callq	*%r14
    	decl	%ebx
    	jne	LBB0_1
    LBB0_2:                                 ## %._crit_edge
    	popq	%rbx
    	popq	%r14
    	popq	%rbp
    	ret
    	.cfi_endproc
     
    	.globl	__Z8FastIteriPFvvE
    	.align	4, 0x90
    __Z8FastIteriPFvvE:                     ## @_Z8FastIteriPFvvE
    	.cfi_startproc
    ## BB#0:
    	pushq	%rbp
    Ltmp11:
    	.cfi_def_cfa_offset 16
    Ltmp12:
    	.cfi_offset %rbp, -16
    	movq	%rsp, %rbp
    Ltmp13:
    	.cfi_def_cfa_register %rbp
    	pushq	%r14
    	pushq	%rbx
    Ltmp14:
    	.cfi_offset %rbx, -32
    Ltmp15:
    	.cfi_offset %r14, -24
    	movq	%rsi, %r14
    	movl	%edi, %ebx
    	testl	%ebx, %ebx
    	je	LBB1_2
    	.align	4, 0x90
    LBB1_1:                                 ## %.lr.ph
                                            ## =>This Inner Loop Header: Depth=1
    	callq	*%r14
    	decl	%ebx
    	jne	LBB1_1
    LBB1_2:                                 ## %._crit_edge
    	popq	%rbx
    	popq	%r14
    	popq	%rbp
    	ret
    	.cfi_endproc
    Difference? Ligne 21 [inlinecode]jle LBB0_2[/inlinecode] vs. ligne 57 [inlinecode]je LBB1_2[/inlinecode]. Soit aucune.

    Suivant
    Même dans certain cas ou l’indice est utilisé, il est plus efficace d’utiliser un autre index :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    for(int i=0; i<Count; i++) Tableau[i]=GetNextValue() ;
    Peut être optimise par

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    for(int i=Count+1,j=0; --i; j++) Tableau[j]=GetNextValue();
    Ou encore mieux

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    for(int i=Count+1,*ptr=Tableau; --i; ptr++) *ptr=GetNextValue();
    Testons. Code:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void SlowLoop(int size, int array[], void (*f)(int)) {
      for (int i = 0; i < size; i++) {
        f(array[i]);
      }
    }
     
    void FastLoop(int size, int array[], void (*f)(int)) {
      for (int i = size + 1, *ptr = array; i--; ptr++) {
        f(*ptr);
      }
    }
    Assembleur produit:
    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
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    	.section	__TEXT,__text,regular,pure_instructions
    	.globl	__Z8SlowLoopiPiPFviE
    	.align	4, 0x90
    __Z8SlowLoopiPiPFviE:                   ## @_Z8SlowLoopiPiPFviE
    	.cfi_startproc
    ## BB#0:
    	pushq	%rbp
    Ltmp3:
    	.cfi_def_cfa_offset 16
    Ltmp4:
    	.cfi_offset %rbp, -16
    	movq	%rsp, %rbp
    Ltmp5:
    	.cfi_def_cfa_register %rbp
    	pushq	%r15
    	pushq	%r14
    	pushq	%rbx
    	pushq	%rax
    Ltmp6:
    	.cfi_offset %rbx, -40
    Ltmp7:
    	.cfi_offset %r14, -32
    Ltmp8:
    	.cfi_offset %r15, -24
    	movq	%rdx, %r14
    	movq	%rsi, %rbx
    	movl	%edi, %r15d
    	testl	%r15d, %r15d
    	jle	LBB0_2
    	.align	4, 0x90
    LBB0_1:                                 ## %.lr.ph
                                            ## =>This Inner Loop Header: Depth=1
    	movl	(%rbx), %edi
    	callq	*%r14
    	addq	$4, %rbx
    	decl	%r15d
    	jne	LBB0_1
    LBB0_2:                                 ## %._crit_edge
    	addq	$8, %rsp
    	popq	%rbx
    	popq	%r14
    	popq	%r15
    	popq	%rbp
    	ret
    	.cfi_endproc
     
    	.globl	__Z8FastLoopiPiPFviE
    	.align	4, 0x90
    __Z8FastLoopiPiPFviE:                   ## @_Z8FastLoopiPiPFviE
    	.cfi_startproc
    ## BB#0:
    	pushq	%rbp
    Ltmp12:
    	.cfi_def_cfa_offset 16
    Ltmp13:
    	.cfi_offset %rbp, -16
    	movq	%rsp, %rbp
    Ltmp14:
    	.cfi_def_cfa_register %rbp
    	pushq	%r15
    	pushq	%r14
    	pushq	%rbx
    	pushq	%rax
    Ltmp15:
    	.cfi_offset %rbx, -40
    Ltmp16:
    	.cfi_offset %r14, -32
    Ltmp17:
    	.cfi_offset %r15, -24
    	movq	%rdx, %r14
    	movq	%rsi, %rbx
    	movl	%edi, %r15d
    	cmpl	$-1, %r15d
    	je	LBB1_3
    ## BB#1:                                ## %.lr.ph.preheader
    	notl	%r15d
    	.align	4, 0x90
    LBB1_2:                                 ## %.lr.ph
                                            ## =>This Inner Loop Header: Depth=1
    	movl	(%rbx), %edi
    	callq	*%r14
    	addq	$4, %rbx
    	incl	%r15d
    	jne	LBB1_2
    LBB1_3:                                 ## %._crit_edge
    	addq	$8, %rsp
    	popq	%rbx
    	popq	%r14
    	popq	%r15
    	popq	%rbp
    	ret
    	.cfi_endproc
     
     
    .subsections_via_symbols
    Pour aider a lire, la boucle "lente":
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    LBB0_1:                                 ## %.lr.ph
                                            ## =>This Inner Loop Header: Depth=1
    	movl	(%rbx), %edi
    	callq	*%r14
    	addq	$4, %rbx
    	decl	%r15d
    	jne	LBB0_1
    et la boucle "rapide":
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    LBB1_2:                                 ## %.lr.ph
                                            ## =>This Inner Loop Header: Depth=1
    	movl	(%rbx), %edi
    	callq	*%r14
    	addq	$4, %rbx
    	incl	%r15d
    	jne	LBB1_2
    Difference? Aucune. Perte de lisibilite? Considerable.

    La suivante est bien marrante:
    Par contre :

    ne sera pas optimisé par le compilateur et restera une multiplication.

    Alors que :

    est bien meilleur même si cela génère deux instructions au lieu d’une.
    Testons:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    int SlowMult(int i) {
      return i * 17;
    }
     
    int FastMult(int i) {
      return (i << 4) + i;
    }
    Code produit:
    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
    __Z8SlowMulti:                          ## @_Z8SlowMulti
    	.cfi_startproc
    ## BB#0:
    	pushq	%rbp
    Ltmp2:
    	.cfi_def_cfa_offset 16
    Ltmp3:
    	.cfi_offset %rbp, -16
    	movq	%rsp, %rbp
    Ltmp4:
    	.cfi_def_cfa_register %rbp
    	imull	$17, %edi, %eax
    	popq	%rbp
    	ret
    	.cfi_endproc
     
    	.globl	__Z8FastMulti
    	.align	4, 0x90
    __Z8FastMulti:                          ## @_Z8FastMulti
    	.cfi_startproc
    ## BB#0:
    	pushq	%rbp
    Ltmp7:
    	.cfi_def_cfa_offset 16
    Ltmp8:
    	.cfi_offset %rbp, -16
    	movq	%rsp, %rbp
    Ltmp9:
    	.cfi_def_cfa_register %rbp
    	imull	$17, %edi, %eax
    	popq	%rbp
    	ret
    	.cfi_endproc
    Et oui, vous avez bien lu, le code est rigoureusement le meme, mais en plus, c'est une multiplication par 17 et non pas un shift/add! Les auteurs de compilos sont obligés d'écrire des "desoptimiseurs" pour retirer ce genre de code stupide... En fait les approches ont le meme temps d'execution, mais la version a coup de shift et + a plus d'instructions. Et qui dit plus d'instructions dit mauvaise utilisation du cache. Bref, la encore, une optim qui ne sert a rien.

    La suggestion sur la "multiplication par l'inverse d'un flottant" oublie de preciser que le resultat n'est pas le meme. Et pour MrPchoun qui dit qu'il faut "preferer les multiplications (*0.5) aux divisions (/2)", j'ai fait le test, il n'y a aucune difference pour ces deux valeurs.

    Continuons:
    L’utilisation de variable temporaire dans des boucles permet de forcer le chargement en registre des valeurs. Ceci est particulièrement vrai pour les pointeurs et les références de tableau:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    If (NeedCopy)
    {
      for(int i=1001;--i;) DataCopy[i]=myClass.Data[i] ;
    }
    Deviendra :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    If (NeedCopy)
    {
      int *tmp=myClass.Data;
      for(int i=1001;--i;) DataCopy[i]=tmp[i];
    }
    Testons.
    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
    struct Foo {
      int size;
      int data[];
    };
     
    int SlowSum(const Foo& foo) {
      int result = 0;
      for (int i= 0; i < foo.size; i++) {
        result += foo.data[i];
      }
      return result;
    }
     
    int FastSum(const Foo& foo) {
      int result = 0;
      const int* data = foo.data;
      for (int i= 0; i < foo.size; i++) {
        result += data[i];
      }
      return result;
    }
    Le code produit est un peu trop long pour etre copie, mais voila la boucle interne "rapide":
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    LBB1_3:                                 ## %vector.body
                                            ## =>This Inner Loop Header: Depth=1
    	movdqa	%xmm1, %xmm2
    	movdqa	%xmm0, %xmm3
    	movdqu	4(%rdi,%rsi,4), %xmm0
    	movdqu	20(%rdi,%rsi,4), %xmm1
    	paddd	%xmm3, %xmm0
    	paddd	%xmm2, %xmm1
    	addq	$8, %rsi
    	cmpq	%rsi, %rax
    	jne	LBB1_3
    Et la "lente"
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    LBB0_3:                                 ## %vector.body
                                            ## =>This Inner Loop Header: Depth=1
    	movdqa	%xmm1, %xmm2
    	movdqa	%xmm0, %xmm3
    	movdqu	4(%rdi,%rsi,4), %xmm0
    	movdqu	20(%rdi,%rsi,4), %xmm1
    	paddd	%xmm3, %xmm0
    	paddd	%xmm2, %xmm1
    	addq	$8, %rsi
    	cmpq	%rsi, %rax
    	jne	LBB0_3
    C'est evidement rigoureusement le meme code, puisque le compilo a sorti de la boucle l'access au champ de la structure.

    En conclusion, cette page "d'optimisation" est pleine de suggestions qu'un compilateur fait tres bien tout seul, voir pire, que le compilo doit retirer! Et tout ca au prix d'un code source bien moins lisible.

    Donc je confirme: ces conseils sont A NE SURTOUT PAS SUIVRE

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [IDL] Optimisation en temps de calcul
    Par Cedric1988 dans le forum Autres EDI
    Réponses: 1
    Dernier message: 23/01/2014, 16h57
  2. Conteneur pour optimisation de temps de calcul
    Par Kaluza dans le forum SL & STL
    Réponses: 5
    Dernier message: 04/04/2010, 00h33
  3. Factorisation des nombres : optimisation du temps de calcul
    Par yoshik dans le forum Général Python
    Réponses: 27
    Dernier message: 21/11/2009, 19h46
  4. optimisation du temps de calcul
    Par deubelte dans le forum Macros et VBA Excel
    Réponses: 3
    Dernier message: 27/08/2007, 14h31
  5. optimisation du temps de calcul
    Par mhamedbj dans le forum Langage
    Réponses: 4
    Dernier message: 14/03/2007, 16h08

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