Forum Programmation.c++ Techniques d'optimisation C++

Posté par . Licence CC by-sa
Tags : aucun
2
8
nov.
2014

Bonjour à tous

Je cherche des ressources sur le net à propos des techniques d'optimisation en c++, et bizarrement je ne trouve pas grand chose. Mon problème est simple : je développe des outils de traitement d'images à la fois de grandes tailles et nombreuses. Ce sont des algorithmes scientifiques peu efficaces quand ils sont implémentés "naïvement", mais qui peuvent être grandement optimisés… si je savais comment faire !
Il y a bien quelques tutos sur le principe de localité, le cache-miss, les instructions SSE, etc… mais si vous avez un lien vers quelque chose de complet, je suis preneur !

Merci

  • # the root of all evil

    Posté par (page perso) . Évalué à 6.

    En général, il vaut mieux écrire ton code de manière « naïve » puis mesurer ce qui prend du temps et optimiser ce qui est nécessaire. Bien sûr il faut commencer par avoir un algorithme relativement efficace mais c'est indépendant du langage.

    pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.

  • # Optimisations

    Posté par (page perso) . Évalué à 3.

    L'optimisation ce n'est pas juste tenir compte des principes de localité, cache-miss, etc…

    Afin d'en arriver à ce stade, il faut d'abord optimiser l'algorithme lui-même. Et là, c'est indépendant du langage.

    Ensuite, tu peux te poser la question de la parallélisation de ton algo. Plusieurs aspects à prendre en compte : lancer plusieurs thread en même temps, travailler sur plusieurs jeux de données en même temps (SSE et localité). Et durant cette phase, tu peux te poser la question de savoir s'il pourrait être judicieux d'utiliser la carte graphique par exemple (CUDA, OpenCL)

    Enfin, tu termines par essayer les "truc" pour optimiser l'implémentation.

    Le stade ultime : identifier les goulots d'étranglement et écrire le code correspondant en assembleur (mais attention, ce n'est pas toujours pertinent de le faire ! Les compilateurs actuels prennent en compte de nombreuses optimisations (par exemple : réagencement des instructions)

    Mais ensuite, les techniques ne sont pas forcément lié au langage. Ce sont plus souvent des concepts génériques.

    • [^] # Re: Optimisations

      Posté par . Évalué à 2.

      Pardon, j'ai donné le bâton pour me faire battre en parlant d'implémentation "naïve" :)
      En fait l'algo est déjà optimisé, par exemple suppression des if dans les boucles, traitement des images par tuile, allocation minimale, etc…
      Pour traiter les lots d'image je parallélise par processus pour occuper tous les cœurs, plutôt que par thread.

  • # Agner Fog

    Posté par . Évalué à 4. Dernière modification le 08/11/14 à 16:13.

    À l'adresse http://agner.org/optimize il propose un guide d'optimisation en C++.

    Cela dit je rejoins les avis postés plus haut : dans l'ordre, pour optimiser un code de calcul, il faut
    1. prendre le bon algorithme (avec la bibliothèque standard C++, prendre le bon conteneur)
    2. mesurer ce qui prend vraiment du temps (sous Linux, perf est ton ami !)
    3. optimiser, dans l'ordre selon moi :

    - bien régler les cut-offs entre différents algorithmes (ex: un algo en O(n2) peut être bien plus rapide qu'un algo en O(n log n) pour les petits n ! Du coup si l'algo est récursif, les dernières étapes doivent se faire avec l'algo en O(n2) )
    - savoir pourquoi ce qui prend du temps prend du temps (branch-misses ? recalculs incessants qu'on pourrait précalculer une bonne fois ? cache-misses ? etc. etc.)
    - améliorer le code en fonction de l'étape précédente, notamment les structures de données : jouer avec les flags du compilateur genre O2, lto, march si on connaît le processeur cible, etc.
    - faciliter la vectorisation (le compilateur le fait facilement si on lui tend un peu la main ! gcc a une option pour savoir pourquoi une boucle n'a pas été vectorisée le cas échéant)
    - paralléliser (seulement une fois que le code est bien optimisé pour un cœur, car c'est sur un cœur que les gains sont les plus importants : avec plusieurs cœurs la concurrence pour les cache est beaucoup plus rude, sans compter les besoins en communication entre les cœurs ! ). C'est une étape parfois difficile si le code n'est pas un peu pensé pour au début, qui peut donc nécessiter pas mal de refactoring.

    Si c'est du libre, n'hésite pas à donner un lien je pourrais jeter un œil éventuellement.

    • [^] # Re: Agner Fog

      Posté par . Évalué à 1.

      Merci pour le lien et pour les quelques idées, je vais regarder tout ça.
      Je connaissais vaguement perf, mais je ne l'ai jamais utilisé… quelle différence avec cachegrind/callgrind ? Par exemple ça pourrait être utile de profiler unitairement les instructions d'une fonction.

      • [^] # Re: Agner Fog

        Posté par . Évalué à 2.

        quelle différence avec cachegrind/callgrind ?
        La vitesse, la précision, le nombre d'événements mesurables…

    • [^] # Re: Agner Fog

      Posté par . Évalué à 2.

      • paralléliser (seulement une fois que le code est bien optimisé pour un cœur, car c'est sur un cœur que les gains sont les plus importants : avec plusieurs cœurs la concurrence pour les cache est beaucoup plus rude, sans compter les besoins en communication entre les cœurs ! ). C'est une étape parfois difficile si le code n'est pas un peu pensé pour au début, qui peut donc nécessiter pas mal de refactoring.

      Oui, c'est parfois difficile parce que c'est très tard pour le faire, un bon algo séquentiel parallélisé ne donne pas nécessairement un bon algo parallèle… Je modifierais ta hiérarchie ainsi :

      Cela dit je rejoins les avis postés plus haut : dans l'ordre, pour optimiser un code de calcul, il faut
      0. déterminer les performances que l'on veut atteindre et les ressources qui pourront être utilisées
      1. prendre le bon algorithme (avec la bibliothèque standard C++, prendre le bon conteneur)
      2. mesurer ce qui prend vraiment du temps (sous Linux, perf est ton ami !)
      3. optimiser, dans l'ordre selon moi :
      […]

      Please do not feed the trolls

  • # Info depuis la source

    Posté par (page perso) . Évalué à 2.

    qui peuvent être grandement optimisés

    C'est simple : il te suffit de demander à la personne qui t'a dit que ça peut être grandement optimisé.
    Soit la personne sort ça d'un chapeau, dans ce cas laisse tomber, il y a des choses plus efficaces à faire dans la vie. Soit la personne sait de quoi elle parle, dans ce cas tu vas avoir ton information.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.