J'ai deux algorithmes écrites en C ++. Autant que je sache, il est conventionnel de compiler avec
-O0 -NDebug (g ++) en comparant les performances de deux algorithmes (asymptomatiquement ils sont identiques).
Mais je pense que le niveau d'optimisation est injuste pour l'un d'entre eux, car il utilise STL dans tous les cas. Le programme qui utilise un tableau simple surpasse l'algorithme STL-Heavy 5 fois plus rapide tout en compilé avec des options -O0. Mais la différence de performance n'est pas très différente lorsque je les compile avec -O2 -Ndebug.
Y a-t-il un moyen de tirer le meilleur parti de STL (je reçois des performances lourdes sur l'opérateur de vecteur []) dans le niveau d'optimisation -O0?
Quel niveau d'optimisation (et éventuellement variables comme -NDebug) que vous utilisez en comparant deux algorithmes?
Ce sera également une bonne aide si quelqu'un peut donner une idée de la tendance à la recherche académique sur la comparaison des performances des algorithmes écrites en C ++?
OK, pour isoler le problème du niveau d'optimisation, j'utilise un algorithme, mais deux implémentations différentes maintenant.
J'ai changé l'une des fonctions avec des pointeurs bruts (int et booléen) à std :: vecteur et std :: vecteur ... avec -O0 -ndebug Les performances sont 5.46S (pointeur brut) et 11.1S (STD ::vecteur). Et avec -O2 -Ndebug, les performances sont des 2,02s (pointeur brut) et 2.21S (std :: vecteur). Même algorithme, une implémentation utilise 4/5 des matrices dynamiques de Int et de Boolean. Et l'autre utilise à l'aide de std :: vecteur et std :: vecteur à la place. Ils sont les mêmes dans tous les autres cas
Vous pouvez voir que dans -O0 std :: vecteur est surperformé avec deux fois plus rapides. En -o2, ils sont presque les mêmes.
Mais je suis vraiment confus, car dans les domaines académiques, lorsqu'ils publient les résultats des algorithmes en heure de fonctionnement, ils compilent les programmes avec -O0.
Y a-t-il des options de compilation que je manque?
5 Réponses :
Les optimisations du compilateur ne changeront généralement pas l'ordre de complexité d'un algorithme, juste la constante et le facteur d'échelle linéaire. Les compilateurs sont assez intelligents, mais ils ne sont pas que intelligent.
allez-vous compiler votre code pour la libération avec Just -O0? Probablement pas. Vous pouvez également comparer la performance des algorithmes lorsqu'il est compilé avec les indicateurs de compilation que vous avez réellement l'intention d'utiliser.
Je ne vois aucune raison de ne pas compiler et de les exécuter à la fois à O2. Sauf si vous le faites comme un exercice purement académique (et même si vous étiez très improbable, les optimisations produiraient des changements fondamentaux dans les propriétés de l'algorithme - cependant, je pense que je serais heureux si GCC a commencé à tourner O (n) Source dans l'assemblée O (LGN)), vous voudrez des informations qui consistent à savoir ce que vous obtiendriez lors de l'exécution du programme final. Vous ne relâchez probablement pas le programme avec des optimisations de O0, vous ne voulez donc pas comparer les algorithmes sous O0 Optimisations.
Cela dépend de ce que vous voulez optimiser pour.
Je suggère d'utiliser Je crois que vous devez utiliser Dans les deux cas, la vitesse de l'algorithme ne dépend pas compilateur, mais un compilateur peut changer radicalement la façon dont les codes se comporte si elle peut « prouver » qu'il peut.
Le code de la commune »détecte GCC tel que la main-codé En ce qui concerne votre dernière édition:
Vous pouvez voir que dans -O0 std :: vecteur est
surperformé avec deux fois plus rapide
pointeurs. Alors que dans -O2 ils sont presque
même.
En effet, -O2 -NDEBUG -ftree-vectoriser , et si votre code est conçu pour fonctionner spécifiquement sur x86 ou x86_64, ajoutez -msse2 . Cela vous donnera une idée générale sur la façon dont elle fonctionnera Gimple.
Taille
-Os -fno-RTTI -fno-exceptions -fomit-frame-pointer . Cela réduira la taille de l'exécutable à un degré (en supposant C ++).
min () et max () et les transforme en une instruction SSE (x86 / x86_64 et quand - MSSE est définie) ou en utilisant cmov lorsque i686 est disponible (SSE a une priorité plus élevée). GCC prendra également la liberté dans les boucles réordonnancement, et inline fonctions dérouler si elle veut, et même supprimer le code inutile.
std :: vector a encore du code qui jette des exceptions et peut utiliser RTTI. Essayez de comparer avec -O2 -NDEBUG -ftree-vectoriser -fno-RTTI -fno-exceptions -fomit-frame-pointer , et vous verrez que std :: vecteur sera légèrement mieux que votre code . GCC sait ce que « intégré » types sont et comment les exploiter en utilisation réelle du monde et se fera un plaisir le faire - tout comme il sait ce que memset () et memcpy () fonctionne et comment optimiser en conséquence lorsque la taille de la copie est connue.
L'objectif principal est de comparer, de ne pas optimiser. Mais je suppose que les bibliothèques modernes sont écrites d'une manière sans optimisation, elles semblent plus lentes des codes écrits à la main.
STL est très lourd lorsqu'il n'est pas optimisé. GCC générera du code comme il le voit et ne passera pas une seconde sur l'optimisation. STL est conçu pour être utilisé dans de nombreux cas, un code spécialisé sera donc susceptible de surperformer - mais si vous écrivez la même idée exacte la même derrière cela, STL gagnera à cause de ce qui a été indiqué dans la réponse.
std :: vecteur :: peut légitimement jeter une exception, également toutes les fonctions qui causent une réaffectation peuvent également lancer des exceptions. -Fno-RTTI et -FNO-EXCEPTIONS Cause GCC Départ du support C ++ conforme et brisera le code.
Il ne cassera pas de code. Si GCC considère que le code repose sur des exceptions, il ne compilera pas. Même pour -fno-rtti. Si votre code n'a pas essayer {} catch {} n'importe où, c'est "sûr" pour le compilateur de ne pas jeter une exception physique - mais pour faire l'équivalent de met et sortie (1) .
Comment pouvez-vous casser le code s'il ne peut pas être exécuté? GCC est très intelligent, ne le sous-estimez pas à cause de ce que vous avez lu à ce sujet il y a 7 ans.
Lorsque j'écris du code, s'il ne compile pas, il est cassé. Je ne me souviens pas exactement de ce que j'aurais peut-être lu sur GCC il y a 7 ans, mais je ne prétends pas que ce n'est pas intelligent. Ce qui est vrai, c'est que si vous désactivez RTTI et des exceptions, le GCC n'agit plus comme un compilateur C ++. En particulier, le comportement de std :: vecteur changera. Quel effet cela dépend de la nature exacte du code client.
Op voulait la vitesse. Pensez-vous que chaque code est propre et conforme à la spécification? Qu'en est-il des exploits d'IEEE floats? Parfois, les hacks sont bons - aussi longtemps que vous pouvez prouver qu'ils sont. J'ai confiance en GCC pour compiler le meilleur possible. J'ai travaillé avec GCC depuis plus de 8 ans maintenant, et bien que je puisse toujours écrire une meilleure assemblée que celle-ci, je sais comment le code devrait être structuré pour être mieux optimisé et comment la plupart des drapeaux se comportent.
J'ai à la fois des exceptions et un casting dynamique. Mais je me souviendrai de cela, quand j'aurai un peu de temps libre, je vais essayer de rendre mon code gratuit de cela. (Je l'ai déjà fait, mais il semble que la prise (STD :: Bad_alloc) a été utilisée presque tous les blocs.) Mais est-ce ce qui fait STD :: Vecteur d'agir plus lentement? Je pensais que c'était le moyen indirect d'accéder à des informations (la plupart probablement des fonctions de const, qui sont généralement optimisées avec une valeur simple en lecture).
Vous avez deux algorithmes implémentés en C ++. Si vous souhaitez comparer les performances relatives des deux implémentations, vous devez utiliser le niveau d'optimisation que vous allez utiliser dans votre produit final. Pour moi, c'est Si vous souhaitez analyser la complexité d'un algorithme, c'est plus un problème d'analyse où vous examinez le nombre total d'opérations qui doivent être effectuées pour différentes tailles et caractéristiques des intrants.
En tant que code d'écriture de développeur où la performance est un problème, il est judicieux de connaître la gamme d'optimisations qu'un compilateur peut, et est susceptible de s'appliquer à votre code. Ne pas optimiser injustement pénalise le code écrit clairement, mais conçu pour être facilement optimisé contre le code qui est déjà «micro-optimisé». -O3 .
-O3 n'est pas autorisé à casser le code juridique, qui constituerait un bug de compilateur. Avez-vous une référence?
Encore une fois, l'objectif principal est de ne pas optimiser, mais de comparer.
J'avais l'habitude de compiler sans optimisation pour toutes les comparaisons, mais l'utilisation de STL me forçait à utiliser l'optimisation.
Une comparaison équitable est celle qui utilise des conditions équitables. C ++ est conçu pour être optimisé. Le code non optimisé est bénéfique pour la vitesse de compilation et de facilité de débogage. La comparaison des performances du code non optimisé n'est pas utile car elle ne reflète pas les situations de performance du monde réelles.
@Liranuna - J'aimerais aussi voir une référence pour -O3 CASSE CODE. Le seul code que j'ai jamais vu brisé par -O3 était quelque chose qui était faux de commencer, mais a été suffisamment malchanceux pour "apparaître" correct à des niveaux d'optimisation inférieurs.
Une telle comparaison est inférieure à l'équité que de produire des informations utiles. Vous devez utiliser le niveau d'optimisation que vous envisagez d'utiliser lorsque / si le code est mis en mode de production. Si vous faites essentiellement des recherches, vous ne prévoyez pas personnellement de le mettre en production, vous êtes coincé avec le travail légèrement plus difficile de deviner ce que quelqu'un qui le mettrait en production serait probablement faire.
De manière réaliste, même si vous faites du développement, pas de recherche, vous êtes coincé avec un peu de cela quand même - il est presque impossible de prédire quel niveau d'optimisation que vous pourriez éventuellement utiliser avec ce code particulier.
Personnellement, j'utilise habituellement -O2 avec GCC. Ma règle générale consiste à utiliser le plus bas niveau d'optimisation qui allume l'affranchissement automatique. J'écris beaucoup de mon code avec l'attente que les petites fonctions seront inlinées par le compilateur - et écrivent le code spécifiquement pour aider à le faire (par exemple, en utilisant souvent des fonctions au lieu de fonctions). Si le compilateur n'est pas défini pour produire du code pour ceux qui enline, vous n'obtenez pas ce que je voulais vraiment. La performance du code quand elle est compilée de cette façon ne signifie rien dire: je le ferais certainement pas planifier jamais vraiment l'utiliser de cette façon.
J'ai bien peur que ceux-ci «dans des domaines académiques» ne soient faux sur ce point. Ne pas optimiserait injustement le code qui est écrit judicieusement avec des parties distinctes divisées dans des fonctions distinctes, ne réutiliserait pas de variables locales à des utilisations séparées et que le général n'est pas écrit comme une fonction grosse, micro-optimisée, lapine-warren.
Si vous souhaitez mettre cela dans un document de recherche, énumérez simplement les données pour tous les niveaux d'optimisation et expliquez les différences. De bons universitaires fournissent toutes les informations nécessaires pour rendre leurs résultats reproductibles et compréhensibles. Je suppose que généralement la performance différence entre deux algorithmes ne dépendrait pas beaucoup du niveau d'optimisation défini pour effectuer les mesures. Dans ces cas, il suffit de coller à -O0 est apparemment courant et semble avoir un sens. Mais pour vous, cela compte, vous pouvez expliquer cela, et vous allez bien.
Je suis d'accord avec Kaka Woef et Charles Bailey, mais j'ajouterais également qu'une comparaison entre les algorithmes est exactement celle-ci et non une comparaison des styles STL vs. non-STL ou d'autres styles de mise en œuvre. Vous devez vous assurer que vous comparez ce que vous aimez. Si la performance du monde réel est ce que vous aimez, compilez avec les options que vous utiliseriez pour une construction du monde réel. Assurez-vous simplement d'indiquer quelles options que vous utilisez et utilisez la même chose pour les deux - même si la comparaison est pour votre propre avantage, elle pourrait économiser de la confusion plus tard.