Ce post présente des astuces sur l'optimisation, beaucoup d'entre elles sont déjà implémentées dans les compilateurs, à condition de mettre les bonnes options de compilations (c'est le cas des inline par exemple).
Je pense surtout que ce qui est important c'est la démarche à suivre.
1) est-ce la peine d'optimiser son programme ?
- Est ce que le gain de temps d'exécution rentabilise le temps de développement?
- Est ce que mon programme marche? (en effet, nombreux programmeurs pensent à écrire du code optimisé AVANT d'écrire du code qui marche) C'est une erreur, non seulement on ne peut pas savoir en cas de plantage si c'est le programme ou l'optimisation qui est fausse, et on obtient souvent du code illisible. Ensuite on risque de passer du temps à "optimiser" des fonctions qui ne sont jamais appelées, ou pire a écrire un code sous optimal, puisqu'on n'a aucune référence de benchmark pour savoir si notre code exotique "optimisé" est meilleur qu'un code standard habituel, simple et lisible.
2) Comment tester la vitesse de mon programme :
- Bien réfléchir a un benchmark représentatif de l'utilisation, car suivant votre application vous optimiserez :
- le temps de chargement de l'application (firefox, pdf reader)
- le temps d'exécution de l'application (7zip, xvid)
- la réactivité (unreal, quake).
Dans certains cas, il vous faut faire un compromis, par exemple si vous réalisez un jeu de tir, c'est sans doutes primordial d'avoir 25 FPS, au delà ce qui compte, c'est le temps de réaction entre l'appui sur une touche et sa prise en compte par le jeu. Qu'il tourne à 25 ou à 150 FPS le joueur il ne le voit pas, par contre si quand il appuie sur tirer et qu'il faut 5 secondes avant de décocher la première cartouche votre joueur risque de trouver votre jeu bien pourri.
3) Quelle est la partie de mon programme critique?
- Il n'est pas néscessaire d'optimiser des instructions qui ne consomment pas de temps, mieux vaux utiliser un profiler pour concentrer ses efforts sur les lignes de code chronophages.
4) Optimiser l'algo ou son implémentation?
- calculer la complexité de l'algorithme utilisé, regarder dans la littérature si elle est optimale ( ex : est ce que le problème que je résoud en N² ne se résoud pas en N?). Dans le cas ou ce calcul est difficile, un bench peut être suffisant.
- si l'algorithme est optimal, il faut optimiser son code, sinon il faut éventuellement changer d'algo.
5) Optimiser:
- tester différentes options de compilation avec votre benchmark.
- ensuite réfléchir à ce que l'on optimise : le temps d'exécution, l'occupation de mémoire vive, l'occupation d'espace disque? Il est par exemple tout a fait inutile d'avoir un algo d'affichage jpg de la mort, si ce qui consomme le plus de temps c'est de lire de jpg sur le disque.
- pour optimiser le processeur, sur les machines actuelles il est utile de paralléliser son code en fonction du nombre de CPU, et de penser à utiliser les GPU si ils sont disponibles.
- pour optimiser la mémoire, il faut bien penser ses structures de données et éviter la redondance.
- pour limiter les accès disques il faut penser a précharger en mémoire vive les informations nescessaires. Une astuce consiste a précharger les informations qui SERONT nescessaires pendant qu'on traite des informations actuelles (faire une file).
ensuite il y a les astuces dont on a parlé dans ce post, elles ne sont pas stupides, mais ce sont de petites bidouilles, pas une méthode d'optimisation. Je rajouterais juste:
- passer les objets apr référence const à chaque fois que c'est possible,
- et son corrolaire, pour ne pas se planter : interdire la copie implicite des gros objets.
Choisir un algorithme de compression efficace comme le H264 pour les vidéos
avec un taux de compression environ 3 fois supérieur comparé au MPEG2 et 2 fois supérieur au MPEG4
qualité DVD avec un bit-rate de 2Mbps ou qualité VHS dès 1Mbps
avec une licence pour l'utiliser la moins cher du marché 0.35$ l'unité au lieu de 2.5$ pour le MPEG4
pour 160Go résolution D1 soit 704*576 ça nous donne 360 heures de vidéos
La plupart des ralentissements dans un programme sont causés par de mauvais algos et du NIH (pourquoi réécrire la STL?).
Après, essayer de sauver 3 ou 4 microsecondes par ci-par là alors que notre programme plante encore, je doute que ça soit très productif.
Surtout que les astuces contenant "toujours" ou "jamais", ou étant écrites à l'impératif sont généralement très néfastes, car celui qui les donne ne connaît pas nos besoins.
AMA, il ne faut plus utiliser "register" : les compilos savent bien quelles variables doivent etre gardée en registres en priorité. Imposer "register" risque juste de perturber le compilo. Je n'utilise plus du tout "register" (je ne programme pas pour systemes embarqués, mais pour des PC)
Pour moi, le piege le plus affreux en C++ est la copie non désirée : un appel d'une fonction ou on a "simplement" oublié un & -> recopie d'objet...
Une astuce : quand on souhaite qu'un objet ne soit jamais recopié, c'est de définir un contructeur par recopie et un operateur= en private Le compilo refusera de compiler tant qu'il y aura des recopies (non désirées dans le cas d'un objet qu'on ne souhaite jamais recopier, forcément !)
Ensuite, allez, je joue sur les mots : pour la division a remplacer par des rotations de bits, d'une part, je pense que les compilos actuels le font tout seul, d'autre part, dans ce cas la, on ne parle pas de rotation, mais de décalage de bits (la rotation ramenant les bits sorties de l'autre coté)
Ensuite, il faut savoir repérer une zone critique :
J'ai connu des gens qui optimisaient a mort des fonctons appelées une seule fois : ils gagnaient 1 millieme de seconde en optimisant... une seule fois... ça c'est inutile.
Les optimisations ne doivent etre faites qu'en zone critique : par exemple les fonctions appelées des millions de fois dans une boucle.
Ensuite, en ce qui concerne les conditions avec des &&, des || etc...
Bien choisir dans quel ordre on les met : le compilo les lit toujours de gauche a droite : si on met le truc le plus calculatoire tout a droite, on a des chances que le && ou le || aie déja validé ou invalidé la condition et ne rentre donc pas dans le truc le plus calculatoire.
Donc d'une maniere générale, ranger les conditions de la moins calculatoire a la plus calculatoire. Mais il existe cependant des exceptions, basées sur des statistiques a faire : si un truc bien calculatoire a 99% de chances de faire casser la if, alors qu'un truc moins calculatoire n'a que 0.0001% de le faire, alors on pourra inverser. (chaque cas sa réflexion)
Ne pas oublier, pour la gestion des if, les regles de simplifications de conditions (théoreme de De Morgan) si besoin (cela dit, possible que les compilos le fassent d'eux meme)
Pour les expressions booléennes (&& ||) , si mes souvenirs sont bons, le programme compilé réalise les appels de la gauche à la droite et stoppe dès que le résultat devient trivial.
ex:
1||f(); n'exécutera jamais f(),
0&&f(); n'exécutera jamais f(),
1&&f(); exécutera toujours f(),
0||f(); exécutera toujours f().
C'est ça. Sauf si l'opérateur a été surchargé pour tes types, auquel cas il devient une "banale" fonction, et donc l'ordre d'évaluation des arguments n'est plus spécifié. Et adieu l'optimisation.
Ouais enfin pour surcharger || ou &&, faut le vouloir quand même.
D'ailleurs au point 30 de C++ Coding.Standard 101 Rules Guidelines and Best Practices , les auteurs (Herb Sutter, Andrei Alexandrescu) disent bien qu'il ne faut pas le faire pour des raisons de préservation de la sémantique naturelle de ces opérareurs et aussi à cause de l'ordre de l'évaluation des arguments, qui devient indéfini.
"Eviter l'allocation dynamique - Seulement pour certains cas bien precis ou une optimisation tres pousse"
Désolé
Mis à part si on oublie ou qu'on place mal les "delete", je ne vois pas en quoi l'allocation dynamique c'est mal
A partir du moment où vous avez besoin d'un tableau à dimensions non définis (donc pour tout programme un tant soit peu poussé), il faut de l'allocation dynamique pour être pile poile dedans niveau mémoire.
Après, qu'il s'agisse de std::vector ou d'allocations dynamiques faites à la main, ça ne change rien du moment que c'est bien fait
La plupart des librairies utilisent l'allocation dynamique, mais il s'agit d'objets on ne le voit pas
L'exemple bateau, chaque string utilise une allocation dynamique. Donc pour toi, string est gourmand.
Pareil pour la SDL, pareil pour la SFML. Pareil pour quasiment tout en fait.
C'est sur qu'il faut pas qu'il y est allocation dynamique à chaque ligne de code Mais faut vraiment être un bourrin de première ou avoir un code qui sert pas à grand chose pour faire ça
pour l'allocation dynamique la règle générale est:
- Vous connaissez la place néscessaire lorsque vous écrivez le code vous utilisez l'allocation statique.
- Vous ne connaissez pas la place nescessaire quand vous codez, vous utilisez l'allocation dynamique.
C'est d'ailleurs une attitude assez innée : personne ne va s'embeter avec un truc* , new delete si il suffit de mettre truc.
Ah, bah tiens c'est toi que je retrouve ici ^^. Je complète le post de montgaulois en indiquant qu'en effet c'est une optimisation intéressante, j'en parle dans mon tutoriel sur les algorithmes de tri : http://bakura.developpez.com/tutoriel/cpp/tri/#LV (d'ailleurs, merci vraiment à toi pour m'avoir fait découvrir cette astuce, je pense que peu de gens la connaisse). D'après les tests qu'on avait fait, cette optimisation n'est pas faite toute seule, même en mode Release avec les optimisations poussées au maximum et, dans certains cas, ça apporte vraiment de gros gains !
D'après les tests qu'on avait fait, cette optimisation n'est pas faite toute seule, même en mode Release avec les optimisations poussées au maximum et, dans certains cas, ça apporte vraiment de gros gains !
C'est normale. Le compilateur, ne peut pas savoir qu'il suffit de swapper la mémoire entre deux class de ta création. Les class de la s(t)l utilise cette méthode.
Il est intéressant de savoir que cette méthode deviendra obsolète avec les rvalue reference dans le c++0x
Et l'apparition de la sémantique de déplacement va changer 2-3 toutes petites choses sur comment on peut écrire swap encore plus efficacement.
Sinon aujourd'hui, de manière générale, l'idiome pimpl (qui a un surcoût constant sur tous les accès) permet d'accélérer les déplacements et les swap.
Quant à l'alloc dynamique, c'est couteux. D'où que dans certains domaines très particuliers (typiquement l'embarqué), on les évite. Soit on connait certaines contraintes qui nous permettent de dire : "256789 octets suffisent, on les prend une fois pour toutes, et on ne code rien de réentrant.", soit on utilise des pools de mémoire pré-allouée (ou autres resize() sur des vecteurs, ...).
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
* Un wrapper C++ pour sqlite * Une alternative a boost units
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
* Un wrapper C++ pour sqlite * Une alternative a boost units
* Un wrapper C++ pour sqlite * Une alternative a boost units