Comment évaluer correctement un programme C++ [modèle]

Question

<arrière-plan>

Je suis à un point où j'ai vraiment besoin d'optimiser le code C++.J'écris une bibliothèque pour les simulations moléculaires et je dois ajouter une nouvelle fonctionnalité.J'ai déjà essayé d'ajouter cette fonctionnalité par le passé, mais j'ai ensuite utilisé des fonctions virtuelles appelées dans des boucles imbriquées.J'avais un mauvais pressentiment à ce sujet et la première mise en œuvre a prouvé que c'était une mauvaise idée.Cependant, c'était correct pour tester le concept.

< /arrière-plan>

Maintenant, j'ai besoin que cette fonctionnalité soit aussi rapide que possible (enfin, sans code assembleur ni calcul GPU, cela doit toujours être C++ et plus lisible que moins).Maintenant, j'en sais un peu plus sur les modèles et les politiques de classe (d'après l'excellent livre d'Alexandrescu) et je pense qu'une génération de code au moment de la compilation peut être la solution.

Cependant, je dois tester la conception avant de faire le énorme travail de mise en œuvre dans la bibliothèque.La question porte sur la meilleure manière de tester l’efficacité de cette nouvelle fonctionnalité.

Évidemment, je dois activer les optimisations car sans ce g++ (et probablement d'autres compilateurs aussi), certaines opérations inutiles seraient conservées dans le code objet.Je dois également faire un usage intensif de la nouvelle fonctionnalité du benchmark car un delta de 1e-3 seconde peut faire la différence entre un bon et un mauvais design (cette fonctionnalité sera appelée des millions de fois dans le programme réel).

Le problème est que g++ est parfois "trop ​​intelligent" en optimisation et peut supprimer une boucle entière s'il considère que le résultat d'un calcul n'est jamais utilisé.J'ai déjà vu cela une fois en regardant le code d'assemblage de sortie.

Si j'ajoute un peu d'impression à la sortie standard, le compilateur sera alors obligé de faire le calcul dans la boucle mais je comparerai probablement principalement l'implémentation d'iostream.

Alors, comment puis-je faire un correct benchmark d'une petite fonctionnalité extraite d'une bibliothèque ?Question connexe :est-ce une approche correcte de faire ce genre de in vitro tests sur une petite unité ou ai-je besoin de tout le contexte ?

Merci pour les conseils !

---

Il semble y avoir plusieurs stratégies, depuis les options spécifiques au compilateur permettant un réglage précis jusqu'à des solutions plus générales qui devraient fonctionner avec chaque compilateur comme volatile ou extern.

Je pense que je vais essayer tout cela.Merci beaucoup pour toutes vos réponses !

Answer 1

Si tu veux forcer n'importe lequel compilateur pour ne pas supprimer un résultat, demandez-lui d'écrire le résultat dans un objet volatile.Cette opération ne peut pas être optimisée, par définition.

template<typename T> void sink(T const& t) {
   volatile T sinkhole = t;
}

Pas de surcharge iostream, juste une copie qui doit rester dans le code généré.Désormais, si vous collectez les résultats d’un grand nombre d’opérations, il est préférable de ne pas les supprimer une par une.Ces copies peuvent encore ajouter des frais généraux.Au lieu de cela, collectez d'une manière ou d'une autre tous les résultats dans un seul objet non volatile (tous les résultats individuels sont donc nécessaires), puis attribuez cet objet de résultat à un objet volatile.Par exemple.si vos opérations individuelles produisent toutes des chaînes, vous pouvez forcer l'évaluation en additionnant toutes les valeurs de caractères ensemble modulo 1<<32.Cela n’ajoute pratiquement aucune surcharge ;les chaînes seront probablement en cache.Le résultat de l'addition sera ensuite attribué à volatile, de sorte que chaque caractère de chaque piqûre doit en fait être calculé, aucun raccourci n'est autorisé.

Answer 2

Sauf si vous avez un vraiment compilateur agressif (peut arriver), je suggère de calculer une somme de contrôle (il suffit d'ajouter tous les résultats ensemble) et de générer la somme de contrôle.

En dehors de cela, vous souhaiterez peut-être examiner le code assembleur généré avant d'exécuter des tests de performance afin de pouvoir vérifier visuellement que les boucles sont réellement exécutées.

Answer 3

Les compilateurs sont uniquement autorisés à éliminer les branches de code qui ne peuvent pas se produire.Tant qu’il ne peut exclure qu’un branchement soit exécuté, il ne l’éliminera pas.Tant qu'il existe une certaine dépendance aux données quelque part, le code sera là et sera exécuté.Les compilateurs ne sont pas très intelligents pour estimer quels aspects d'un programme ne seront pas exécutés et n'essaient pas de le faire, car c'est un problème NP et difficilement calculable.Ils ont quelques contrôles simples comme pour if (0), mais c'est tout.

Mon humble opinion est que vous avez peut-être été confronté à un autre problème plus tôt, comme la façon dont C/C++ évalue les expressions booléennes.

Quoi qu'il en soit, puisqu'il s'agit d'un test de vitesse, vous pouvez vérifier que les choses sont appelées par vous-même - exécutez-le une fois sans, puis une autre fois avec un test des valeurs de retour.Ou une variable statique incrémentée.A la fin du test, imprimez le numéro généré.Les résultats seront égaux.

Pour répondre à votre question sur les tests in vitro :Oui, fais ça.Si votre application est si urgente, faites-le.D'un autre côté, votre description fait allusion à un problème différent :si vos deltas sont dans un laps de temps de 1e-3 secondes, alors cela ressemble à un problème de complexité informatique, puisque la méthode en question doit être appelée très, très souvent (pour quelques exécutions, 1e-3 secondes est négligeable).

Le domaine problématique que vous modélisez semble TRÈS complexe et les ensembles de données sont probablement énormes.De telles choses constituent toujours un effort intéressant.Assurez-vous d’abord que vous disposez absolument des structures de données et des algorithmes appropriés, puis micro-optimisez tout ce que vous souhaitez par la suite. Donc, je dirais de regarder d’abord l’ensemble du contexte. ;-)

Par curiosité, quel est le problème que vous calculez ?

Answer 4

Vous avez beaucoup de contrôle sur les optimisations de votre compilation.-O1, -O2, etc. ne sont que des alias pour un tas de commutateurs.

À partir des pages de manuel

       -O2 turns on all optimization flags specified by -O.  It also turns
       on the following optimization flags: -fthread-jumps -falign-func‐
       tions  -falign-jumps -falign-loops  -falign-labels -fcaller-saves
       -fcrossjumping -fcse-follow-jumps  -fcse-skip-blocks
       -fdelete-null-pointer-checks -fexpensive-optimizations -fgcse
       -fgcse-lm -foptimize-sibling-calls -fpeephole2 -fregmove -fre‐
       order-blocks  -freorder-functions -frerun-cse-after-loop
       -fsched-interblock  -fsched-spec -fschedule-insns  -fsched‐
       ule-insns2 -fstrict-aliasing -fstrict-overflow -ftree-pre
       -ftree-vrp

Vous pouvez modifier et utiliser cette commande pour vous aider à affiner les options à étudier.

       ...
       Alternatively you can discover which binary optimizations are
       enabled by -O3 by using:

               gcc -c -Q -O3 --help=optimizers > /tmp/O3-opts
               gcc -c -Q -O2 --help=optimizers > /tmp/O2-opts
               diff /tmp/O2-opts /tmp/O3-opts Φ grep enabled

Une fois que vous avez trouvé l'optimisation coupable, vous ne devriez plus avoir besoin du cout.

Answer 5

Si cela vous est possible, vous pouvez essayer de diviser votre code en :

• la bibliothèque que vous souhaitez tester compilée avec toutes les optimisations activées
• un programme de test, reliant dynamiquement la bibliothèque, avec les optimisations désactivées

Sinon, vous pourriez spécifier un niveau d'optimisation différent (il semble que vous utilisiez gcc...) pour la fonction de test avec l'attribut optimiser (voir http://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html#Function-Attributes).

Answer 6

Vous pouvez créer une fonction factice dans un fichier cpp séparé qui ne fait rien, mais prend comme argument quel que soit le type de résultat de votre calcul.Ensuite, vous pouvez appeler cette fonction avec les résultats de votre calcul, forçant gcc à générer le code intermédiaire, et la seule pénalité est le coût d'appel d'une fonction (qui ne devrait pas fausser vos résultats à moins que vous l'appeliez un parcelle!).

Answer 7

#include <iostream>

// Mark coords as extern.
// Compiler is now NOT allowed to optimise away coords
// This it can not remove the loop where you initialise it.
// This is because the code could be used by another compilation unit
extern double coords[500][3];
double coords[500][3];

int main()
{

//perform a simple initialization of all coordinates:
for (int i=0; i<500; ++i)
 {
   coords[i][0] = 3.23;
   coords[i][1] = 1.345;
   coords[i][2] = 123.998;
 }


std::cout << "hello world !"<< std::endl;
return 0;
}

Answer 8

modifier:la chose la plus simple que vous puissiez faire est simplement d'utiliser les données de manière parasite après l'exécution de la fonction et en dehors de vos références.Comme,

StartBenchmarking(); // ie, read a performance counter
for (int i=0; i<500; ++i)
 {
   coords[i][0] = 3.23;
   coords[i][1] = 1.345;
   coords[i][2] = 123.998;
 }
StopBenchmarking(); // what comes after this won't go into the timer

// this is just to force the compiler to use coords
double foo;
for (int j = 0 ; j < 500 ; ++j )
{
  foo += coords[j][0] + coords[j][1] + coords[j][2]; 
}
cout << foo;

---

Ce qui fonctionne parfois pour moi dans ces cas-là, c'est de cacher le in vitro tester à l'intérieur d'une fonction et transmettre les ensembles de données de référence volatil pointeurs.Cela indique au compilateur qu'il ne doit pas réduire les écritures ultérieures sur ces pointeurs (car ils pourraient être par exemple E/S mappées en mémoire).Donc,

void test1( volatile double *coords )
{
  //perform a simple initialization of all coordinates:
  for (int i=0; i<1500; i+=3)
  {
    coords[i+0] = 3.23;
    coords[i+1] = 1.345;
    coords[i+2] = 123.998;
  }
}

Pour une raison que je n'ai pas encore comprise, cela ne fonctionne pas toujours dans MSVC, mais c'est souvent le cas - regardez la sortie de l'assembly pour en être sûr.Rappelez-vous également que volatil déjouera certaines optimisations du compilateur (il interdit au compilateur de conserver le contenu du pointeur dans le registre et force les écritures à se produire dans l'ordre du programme), ce n'est donc digne de confiance que si vous l'utilisez pour l'écriture finale des données.

En général, les tests in vitro comme celui-ci sont très utiles à condition de garder à l’esprit que cela ne résume pas toute l’histoire.Je teste généralement mes nouvelles routines mathématiques de manière isolée, comme celle-ci, afin de pouvoir itérer rapidement uniquement sur les caractéristiques du cache et du pipeline de mon algorithme sur des données cohérentes.

La différence entre un profilage de tubes à essai comme celui-ci et son exécution dans "le monde réel" signifie que vous obtiendrez des ensembles de données d'entrée très variés (parfois dans le meilleur des cas, parfois dans le pire des cas, parfois pathologique), le cache sera dans un état inconnu à l'entrée. la fonction, et vous pouvez avoir d'autres threads qui frappent sur le bus ;vous devriez donc exécuter quelques tests sur cette fonction in vivo ainsi que lorsque vous avez terminé.

Answer 9

Je ne sais pas si GCC a une fonctionnalité similaire, mais avec VC++ vous pouvez utiliser :

#pragma optimize

pour activer/désactiver sélectivement les optimisations.Si GCC a des fonctionnalités similaires, vous pouvez créer avec une optimisation complète et simplement le désactiver si nécessaire pour vous assurer que votre code est appelé.

Answer 10

Juste un petit exemple d'optimisation indésirable :

#include <vector>
#include <iostream>

using namespace std;

int main()
{
double coords[500][3];

//perform a simple initialization of all coordinates:
for (int i=0; i<500; ++i)
 {
   coords[i][0] = 3.23;
   coords[i][1] = 1.345;
   coords[i][2] = 123.998;
 }


cout << "hello world !"<< endl;
return 0;
}

Si vous commentez le code de "double coords[500][3]" jusqu'à la fin de la boucle for, cela générera exactement le même code assembleur (je viens d'essayer avec g++ 4.3.2).Je sais que cet exemple est beaucoup trop simple et je n'ai pas pu montrer ce comportement avec un std::vector d'une simple structure "Coordonnées".

Cependant je pense que cet exemple montre quand même que certaines optimisations peuvent introduire des erreurs dans le benchmark et je voulais éviter certaines surprises de ce genre lors de l'introduction de nouveau code dans une bibliothèque.Il est facile d'imaginer que le nouveau contexte pourrait empêcher certaines optimisations et conduire à une bibliothèque très inefficace.

La même chose devrait également s'appliquer aux fonctions virtuelles (mais je ne le prouve pas ici).Utilisé dans un contexte où un lien statique ferait l'affaire, je suis assez convaincu que les compilateurs décents devraient éliminer l'appel d'indirection supplémentaire pour la fonction virtuelle.Je peux essayer cet appel en boucle et conclure qu'appeler une fonction virtuelle n'est pas si grave.Ensuite, je l'appellerai des centaines de milliers de fois dans un contexte où le compilateur ne peut pas deviner quel sera le type exact du pointeur et aura une augmentation de 20% du temps d'exécution...

Answer 11

au démarrage, lisez à partir d'un fichier.dans votre code, dites if(input == "x") cout<< result_of_benchmark;

Le compilateur ne pourra pas éliminer le calcul, et si vous vous assurez que l'entrée n'est pas "x", vous ne comparerez pas l'iostream.