Forum Programmation.autre Optimisation de tests dans des boucles

Posté par  .
Étiquettes :
2
21
juin
2011

Je travaille actuellement sur un code qui contient de nombreux tests à l’intérieur de boucles.

Théoriquement, la plupart de ces tests peuvent être sortis des boucles puisque la valeur testée ne change pas en fonction des indices de boucle. Cependant, comme il y a plusieurs boucles imbriquées et plusieurs tests, extraire les tests des boucles revient à ajouter beaucoup de lignes code et diminue la lisibilité du code. Mon problème est que j’ai vraiment besoin de performances avec ce code.

Je ne suis pas développeur de formation et je ne parviens pas à trouver de réponse satisfaisante par des recherches sur Internet. Ma question est donc la suivante :

Dans un cas comme celui-ci :

for i1 = 1,maxi1
  for i2 = 1,maxi2
    for [...]
      for in = 1,maxin
        instructions_generales();
        select case(variable_exterieure_a_la_boucle)
        case (0)
          instructions_zero(i1, i2, ..., in);
        case (1)
          instructions_un(i1, i2, ..., in);
        [...]
        case (m)
          instructions_m(i1, i2, ..., in);
      end
    [...] end
  end
end

le compilateur est-il capable d’extraire les tests des boucles tout seul pour optimiser le code, ou vaut-il mieux optimiser à la main. Je préférerais nettement laisser ce travail au compilateur, mais les performances sont ici plus importantes que la lisibilité du code.

Pour info, j’utilise GCC (avec gfortran au cas ou ce serait dépendant du langage).

Merci beaucoup de votre aide, et bonne journée !

  • # Mémoriser l'appel

    Posté par  (site web personnel) . Évalué à 2.

    Je ne connais pas trop le fortran et ne sais pas si c'est faisable, mais voilà comment je verrais les choses :

     case (0)
    ma_fonction = instructions_zero;
case (1)
    ma_fonction = instructions_un;
[...]
case (m)
    ma_fonction = instructions_m;

for i1 = 1,maxi1
  for i2 = 1,maxi2
    for [...]
      for in = 1,maxin
        instructions_generales();
        ma_fonction(il, i2, ..., in);
      end
    [...] end
  end
end

    • [^] # Re: Mémoriser l'appel

      Posté par  (site web personnel) . Évalué à 1.

      Sans optimisation du compilateur cette version est moins performante que la première. En effet à chaque itération de la boucle, tu fais un appel de fonction ce qui est plus coûteux qu'un test.
      Ensuite pour optimisation tu peux définir ta fonction comme "inline", afin qu'elle soit remplacée par son code à chaque occurrence au lieu d'un appel de fonction.
      Après optimisation, si chaque appel à la fonction est remplacé par son code, je pense que cette version est plus rapide. Mais il n'y a qu'un moyen d'en être sûr, c'est de vérifier ;-)

      • [^] # Re: Mémoriser l'appel

        Posté par  (site web personnel) . Évalué à 1.

        Je crois que tu n'as pas compris mon code, l'appel à la fonction est déjà présent dans le 1er code !

        Seulement, au lieu de faire le test à chaque fois pour appeler la fonction à exécuter, j'effectue ce test une seule fois, et sauvegarde un alias vers la fonction à exécuter.

        Ensuite, dans la boucle, je récupère cet alias (pointeur, objet fonction…), et le traite comme une fonction, en lui donnant les paramètres issus des boucles.

        Ça permet de gagner un niveau d'indentation dans la boucle, n niveaux d'indentations dans le select case (donc lisibilité), mais surtout de rendre le code un peu plus modulaire ( mais après on s'éloigne des contraintes de vitesse c'est vrai ).

        • [^] # Re: Mémoriser l'appel

          Posté par  . Évalué à 2.

          Je crois pourtant qu'il a raison. Ta version oblige a faire un appel de fonction là où il y a potentiellement un "inlining" dans le premier.

          Ta version a une bien meilleure lisibilité, mais je ne crois pas qu'elle soit plus performante.

          Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

          • [^] # Re: Mémoriser l'appel

            Posté par  . Évalué à 1.

            Si un appel de fonction est gênant, pourquoi ne pas remplacer par des gotos ?
            D'ailleurs, un switch n'est il pas transformé par le compilateur en une "table de goto", faisant qu'il ne fait pas réellement de tests sur la valeur mais uniquement une indirection ?

    • [^] # Re: Mémoriser l'appel

      Posté par  . Évalué à 6.

      si Fortran accepte, je ferais ça aussi.

      Sinon, on peut aussi écrire une boucle dédiée à chaque cas.

      En tout état de cause, pour savoir quelle est la version la plus performante, plutôt que de jouer aux devinettes sur ce que fait ou ne fait pas le compilo ;), le mieux est encore de mesurer les différences de performances entre chaque version. Globalement, pour les questions de perfs, il ne faut rien préjuger et toujours mesurer. Ensuite, (ou plutôt pour commencer) il faut encore vérifier que le bout de code sur lequel on travaille est effectivement susceptible d'avoir un impact sur les performances (c'est peut-être pas la peine d'optimiser quelques calculs si les I/O représentent 90% du traitement), et pour ça, profiling et compagnie.

  • # Perf sur des boucles

    Posté par  . Évalué à 2.

    Mis à part dupliquer ton code m fois (pour chaque cas), je ne vois pas comment tu pourrais gagner plus. Par contre si tu as la chance d’exécuter ton code sur du SMP, tu pourrais utiliser OpenMP pour paralléliser tes boucles.

    Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

  • # sortir le case

    Posté par  . Évalué à 1.

    Question optim le truc le plus simple c'est comme variable_exterieure_a_la_boucle ne change pas pendant les boucles c'est de mette le switch case autour des boucles c'est pas ce qu'il y a de plus beau, le code et dupliqué etc ... mais c'est efficace.

    ca donnerai un truc du genre :

     select case(variable_exterieure_a_la_boucle)
        case (0)
         for i1 = 1,maxi1
            for i2 = 1,maxi2
               for [...]
                  for in = 1,maxin
                     instructions_generales();
                     instructions_zero(i1, i2, ..., in);
                  end
              [...] end
            end
        end 
        case (1)
         for i1 = 1,maxi1
            for i2 = 1,maxi2
               for [...]
                  for in = 1,maxin
                     instructions_generales();
                     instructions_un(i1, i2, ..., in);
                  end
              [...] end
            end
        end 
        case (m)
        for i1 = 1,maxi1
            for i2 = 1,maxi2
               for [...]
                  for in = 1,maxin
                     instructions_generales();
                     instructions_un(i1, i2, ..., in);
                  end
              [...] end
            end
        end

    Je connais pas le fortran mais il y a peut être des macro pour éviter d'écrire a chaque fois toutes les boucles et ne pas introduire de bug (surtout si tu doit toutes les modifier).

    avec un peu de chance dans certain cas du case toute les boucle ne sont pas utile et tu pourra aussi gagner un peux.

    Au final tu peux peu être repenser globalement ton algo pour trouver un autre façon de faire.

    • [^] # Re: sortir le case

      Posté par  . Évalué à 1.

      Bon, eh bien cette réponse et celles du dessus confirment ce que je craignais, je vais devoir sortir le test de mes boucles manuellement… Merci pour toutes vos remarques. En vrac :

      • ce ne sont pas forcément des appels à fonction dans les boucles;
      • MPI viendra probablement se greffer la dessus plus tard;
      • je préfère éviter les macros en Fortran car elles ne sont pas habituelles, dépendent du pré-processeur utilisé et que j'aimerais à terme ne pas être le seul capable de travailler sur ce code (éventuellement le libérer un jour mais je doute qu’il suscite beaucoup d’intérêt);
      • et question profiling, c’est tout vu, il s’agit d’un code de calcul scientifique avec presque aucune IO et presque toutes les boucles présentent ce genre de défaut.

      Un grand merci à tous !

  • # prédiction de branchement

    Posté par  (site web personnel) . Évalué à 3.

    Ce qui coûte, ce sont les branchements dont l'issue varie d'un test à l'autre. Si dans ton test d'intérieur de boucle le résultat du test (la valeur du select case) est toujours le même, le cache de prédiction de branchement de ton processeur va faire son travail et réduire la durée de tes branchements à presque rien. Du coup ton code devrait déjà tourner presque à fond de ses capacités.

    Tu peux aussi te débarasser du coût d'appel des fonctions en les rendant "statiques" (je ne connais pas l'équivalent en fortran), en gros tu indiques que tes fonction instructions_zero n'est pas prévue pour être appelée en dehors du même fichier .f, et le compilo va remplacer le code d'appel de chaque fonction par le contenu de la fonction elle-même.

    Sinon, comme dit au dessus, si tu sors le test des boucles, tu devrais gagner un peu aussi.

Suivre le flux des commentaires

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