En C ++, devrais-je prendre la peine de mettre en cache les variables ou laisser le compilateur faire l’optimisation? (Aliasing)

Au premier abord, je pensais que le compilateur pouvait générer un assemblage équivalent pour les deux versions avec des indicateurs d’optimisation activés. Quand je l’ai vérifié, j’ai été surpris de voir le résultat:

Source unoptimized.cpp

note: ce code n’est pas destiné à être exécuté.

 struct bitmap_t { long long width; } bitmap; int main(int argc, char** argv) { for (unsigned x = 0 ; x < static_cast(bitmap.width) ; ++x) { argv[x][0] = '\0'; } return 0; } 

Source optimized.cpp

note: ce code n’est pas destiné à être exécuté.

 struct bitmap_t { long long width; } bitmap; int main(int argc, char** argv) { const unsigned width = static_cast(bitmap.width); for (unsigned x = 0 ; x < width ; ++x) { argv[x][0] = '\0'; } return 0; } 

Compilation

• $ g++ -s -O3 unoptimized.cpp
• $ g++ -s -O3 optimized.cpp

Assemblage (non optimisé.s)

  .file "unoptimized.cpp" .text .p2align 4,,15 .globl main .type main, @function main: .LFB0: .cfi_startproc .cfi_personality 0x3,__gxx_personality_v0 movl bitmap(%rip), %eax testl %eax, %eax je .L2 xorl %eax, %eax .p2align 4,,10 .p2align 3 .L3: mov %eax, %edx addl $1, %eax movq (%rsi,%rdx,8), %rdx movb $0, (%rdx) cmpl bitmap(%rip), %eax jb .L3 .L2: xorl %eax, %eax ret .cfi_endproc .LFE0: .size main, .-main .globl bitmap .bss .align 8 .type bitmap, @object .size bitmap, 8 bitmap: .zero 8 .ident "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-16)" .section .note.GNU-stack,"",@progbits 

Assemblage (optimisé.s)

  .file "optimized.cpp" .text .p2align 4,,15 .globl main .type main, @function main: .LFB0: .cfi_startproc .cfi_personality 0x3,__gxx_personality_v0 movl bitmap(%rip), %eax testl %eax, %eax je .L2 subl $1, %eax leaq 8(,%rax,8), %rcx xorl %eax, %eax .p2align 4,,10 .p2align 3 .L3: movq (%rsi,%rax), %rdx addq $8, %rax cmpq %rcx, %rax movb $0, (%rdx) jne .L3 .L2: xorl %eax, %eax ret .cfi_endproc .LFE0: .size main, .-main .globl bitmap .bss .align 8 .type bitmap, @object .size bitmap, 8 bitmap: .zero 8 .ident "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-16)" .section .note.GNU-stack,"",@progbits 

diff

 $ diff -uN unoptimized.s optimized.s --- unoptimized.s 2015-11-24 16:11:55.837922223 +0000 +++ optimized.s 2015-11-24 16:12:02.628922941 +0000 @@ -1,4 +1,4 @@ - .file "unoptimized.cpp" + .file "optimized.cpp" .text .p2align 4,,15 .globl main @@ -10,16 +10,17 @@ movl bitmap(%rip), %eax testl %eax, %eax je .L2 + subl $1, %eax + leaq 8(,%rax,8), %rcx xorl %eax, %eax .p2align 4,,10 .p2align 3 .L3: - mov %eax, %edx - addl $1, %eax - movq (%rsi,%rdx,8), %rdx + movq (%rsi,%rax), %rdx + addq $8, %rax + cmpq %rcx, %rax movb $0, (%rdx) - cmpl bitmap(%rip), %eax - jb .L3 + jne .L3 .L2: xorl %eax, %eax ret 

L'assemblage généré pour la version optimisée charge effectivement ( lea ) la constante de width contrairement à la version non optimisée qui calcule le décalage de width à chaque itération ( movq ).

Quand j'aurai le temps, je publie éventuellement un sharepoint repère à ce sujet. Bonne question.

Il y a en réalité des informations insuffisantes de votre extrait de code pour pouvoir dire, et la seule chose à laquelle je peux penser est l’aliasing. De notre sharepoint vue, il est assez clair que vous ne voulez pas que p et bitmap pointent vers le même emplacement en mémoire, mais le compilateur ne le sait pas et (car p est de type char* ) Ce code fonctionne même si p et bitmap chevauchent.

Cela signifie que dans ce cas, si la boucle change bitmap->width travers le pointeur p cela doit être vu lors de la relecture bitmap->width , ce qui signifie que le stocker dans une variable locale serait illégal.

Cela étant dit, je pense que certains compilateurs génèreront parfois deux versions du même code (j’en ai vu des preuves indirectes, mais jamais directement des informations sur ce que le compilateur fait dans ce cas), et vérifier rapidement si les pointeurs alias et exécutez le code plus rapide s’il détermine que c’est correct.

Cela étant dit, je maintiens mon commentaire sur la simple mesure de la performance des deux versions. Mon argent consiste à ne pas voir de différence de performance cohérente entre les deux versions du code.

À mon avis, de telles questions sont acceptables si vous voulez en savoir plus sur les théories et les techniques d’optimisation du compilateur, mais c’est une perte de temps (une micro-optimisation inutile) si votre objective est de rendre le programme plus rapide.

D’autres réponses ont souligné que le fait de hisser l’opération de pointeur hors de la boucle peut modifier le comportement défini en raison de règles d’alias permettant à alias de n’utiliser aucun alias et ne constitue donc pas une optimisation acceptable. programmeur.

Ils ont également souligné que le fait de sortir l’opération de la boucle est généralement, mais pas toujours, une amélioration du sharepoint vue de la performance et qu’elle est souvent négative du sharepoint vue de la lisibilité.

J’aimerais souligner qu’il y a souvent une “troisième voie”. Au lieu de compter jusqu’au nombre d’itérations souhaité, vous pouvez compter jusqu’à zéro. Cela signifie que le nombre d’itérations n’est nécessaire qu’une fois au début de la boucle, il n’est pas nécessaire de le stocker ensuite. Mieux encore au niveau de l’assembleur, cela élimine souvent la nécessité d’une comparaison explicite, car l’opération de décrémentation définira généralement des indicateurs indiquant si le compteur était à zéro à la fois avant (indicateur de portage) et après (indicateur zéro) la décrémentation.

 for (unsigned x = static_cast(bitmap->width);x > 0; x--) { *p++ = 0xAA; *p++ = 0xBB; *p++ = 0xCC; } 

Notez que cette version de la boucle donne des valeurs x dans la plage 1..width plutôt que la plage 0 .. (width-1). Cela n’a pas d’importance dans votre cas, car vous n’utilisez pas x pour rien, mais c’est quelque chose dont vous devez être conscient. Si vous voulez une boucle de compte à rebours avec des valeurs de x dans la plage 0 .. (width-1), vous pouvez le faire.

 for (unsigned x = static_cast(bitmap->width); x-- > 0;) { *p++ = 0xAA; *p++ = 0xBB; *p++ = 0xCC; } 

Vous pouvez également vous débarrasser des castings dans les exemples ci-dessus si vous le souhaitez sans vous soucier de son impact sur les règles de comparaison, car tout ce que vous faites avec bitmap-> width, c’est l’atsortingbuer directement à une variable.

Ok, les gars, donc j’ai mesuré, avec GCC -O3 (en utilisant GCC 4.9 sous Linux x64).

Il s’avère que la deuxième version est 54% plus rapide!

Donc, je suppose que l’aliasing est la chose, je n’y avais pas pensé.

[Modifier]

J’ai réessayé la première version avec tous les pointeurs définis avec __ressortingct__ et les résultats sont les mêmes. Weird .. Soit l’aliasing n’est pas le problème, ou, pour une raison quelconque, le compilateur ne l’optimise pas même avec __ressortingct__ .

[Edit 2]

Ok, je pense que j’ai été en mesure de prouver que l’aliasing est le problème. J’ai répété mon test d’origine, cette fois en utilisant un tableau plutôt qu’un pointeur:

 const std::size_t n = 0x80000000ull; bitmap->width = n; static unsigned char d[n*3]; std::size_t i=0; for (unsigned x = 0; x < static_cast(bitmap->width); ++x) { d[i++] = 0xAA; d[i++] = 0xBB; d[i++] = 0xCC; } 

Et mesuré (devait utiliser “-mcmodel = large” pour le lier). Puis j’ai essayé:

 const std::size_t n = 0x80000000ull; bitmap->width = n; static unsigned char d[n*3]; std::size_t i=0; unsigned width(static_cast(bitmap->width)); for (unsigned x = 0; x < width; ++x) { d[i++] = 0xAA; d[i++] = 0xBB; d[i++] = 0xCC; } 

Les résultats de la mesure étaient les mêmes - On dirait que le compilateur a pu l’optimiser par lui-même.

Puis j'ai essayé les codes originaux (avec un pointeur p ), cette fois quand p est de type std::uint16_t* . Encore une fois, les résultats étaient les mêmes - en raison d’un crénelage ssortingct. Ensuite, j'ai essayé de construire avec "-fno-ssortingct-aliasing", et j'ai encore vu une différence dans le temps.

La seule chose qui peut empêcher l’optimisation est la règle ssortingcte d’aliasing . En bref :

“Le crénelage ssortingct est une supposition, faite par le compilateur C (ou C ++), selon laquelle les pointeurs de déréférencement sur des objects de types différents ne feront jamais référence au même emplacement mémoire (alias les uns des autres).”

[…]

L’exception à la règle est un caractère char* , autorisé à pointer vers n’importe quel type.

L’exception s’applique également aux pointeurs de caractères unsigned et signed .

C’est le cas dans votre code: vous modifiez *p à p qui est un caractère unsigned char* , le compilateur doit donc supposer qu’il pourrait pointer sur bitmap->width . La mise en cache de bitmap->width est donc une optimisation non valide. Ce comportement de prévention d’optimisation est montré dans la réponse de YSC .

Si et seulement si p indiquait un type non char et non- decltype(bitmap->width) , la mise en cache serait-elle une optimisation possible.

La question posée à l’origine:

Est-ce que cela vaut la peine de l’optimiser?

Et ma réponse à cela (en recueillant un bon mélange de votes de haut en bas ..)

Laissez le compilateur s’en préoccuper.

Le compilateur fera certainement un meilleur travail que vous. Et il n’y a aucune garantie que votre «optimisation» soit meilleure que le code «évident» – l’avez-vous mesurée?

Plus important encore, avez-vous la preuve que le code que vous optimisez a un impact sur les performances de votre programme?

Malgré les inconvénients (et maintenant le problème de l’aliasing), je suis toujours satisfait de cette réponse. Si vous ne savez pas si cela vaut la peine d’optimiser quelque chose, ce n’est probablement pas le cas.

Une question assez différente, bien sûr, serait la suivante:

Comment puis-je savoir si cela vaut la peine d’optimiser un fragment de code?

Premièrement, votre application ou votre bibliothèque doit-elle fonctionner plus rapidement qu’elle ne le fait actuellement? L’utilisateur attend-il trop longtemps? Votre logiciel prévoit-il la météo d’hier au lieu de demain?

Seulement vous pouvez vraiment le dire, en fonction de votre logiciel et de ce que vos utilisateurs attendent.

En supposant que votre logiciel nécessite une optimisation, la prochaine chose à faire est de commencer à mesurer. Profilers vous indiquera où passe votre code. Si votre fragment ne s’affiche pas comme un goulot d’étranglement, mieux vaut le laisser seul. Les profileurs et autres outils de mesure vous indiqueront également si vos changements ont fait la différence. Il est possible de passer des heures à essayer d’optimiser le code pour constater que vous n’avez fait aucune différence.

Que voulez-vous dire par «optimisation», de toute façon?

Si vous n’écrivez pas de code «optimisé», votre code doit être aussi clair, net et concis que possible. L’argument «L’optimisation prématurée est mal» n’est pas une excuse pour un code négligé ou inefficace.

Le code optimisé sacrifie normalement certains des atsortingbuts ci-dessus pour la performance. Cela peut impliquer l’introduction de variables locales supplémentaires, des objects ayant une scope plus large que celle attendue ou même l’inversion d’un ordre de boucle normal. Tout cela peut être moins clair ou concis, alors documentez le code (brièvement!) Sur la raison pour laquelle vous faites cela.

Mais souvent, avec un code «lent», ces micro-optimisations sont le dernier recours. Le premier endroit à examiner concerne les algorithmes et les structures de données. Est-il possible d’éviter de faire le travail du tout? Les recherches linéaires peuvent-elles être remplacées par des recherches binarys? Une liste liée serait-elle plus rapide qu’un vecteur? Ou une table de hachage? Puis-je mettre les résultats en cache? Faire de bonnes décisions «efficaces» peut souvent affecter les performances d’un ordre de grandeur ou plus!

J’utilise le modèle suivant dans cette situation. Il est presque aussi court que le premier, et est meilleur que le second, car il conserve la variable temporaire locale à la boucle.

 for (unsigned int x = 0, n = static_cast(bitmap->width); x < n; ++x) { *p++ = 0xAA; *p++ = 0xBB; *p++ = 0xCC; } 

Cela sera plus rapide avec un compilateur, une version de débogage ou certains indicateurs de compilation moins intelligents.

Edit1 : Placer une opération constante en dehors d'une boucle est un bon modèle de programmation. Il montre la compréhension des bases du fonctionnement de la machine, en particulier en C / C ++. Je dirais que l'effort à faire pour se prouver devrait être sur les personnes qui ne suivent pas cette pratique. Si le compilateur punit pour un bon motif, c'est un bogue dans le compilateur.

Edit2:: J'ai mesuré ma suggestion contre le code original sur vs2013, obtenu une amélioration de% 1. Pouvons-nous faire mieux? Une simple optimisation manuelle donne trois fois plus d’amélioration que la boucle originale sur une machine x64 sans avoir recours à des instructions exotiques. Le code ci-dessous suppose un petit système endian et un bitmap correctement aligné. TEST 0 est original (9 sec), TEST 1 est plus rapide (3 sec). Je parie que quelqu'un pourrait rendre cela encore plus rapide, et le résultat du test dépendrait de la taille du bitmap. Certainement dans le futur, le compilateur sera capable de produire du code toujours plus rapide. Je crains que ce ne soit le futur quand le compilateur sera également un programmeur AI, nous serions donc sans travail. Mais pour l'instant, écrivez simplement le code qui montre que vous savez qu'une opération supplémentaire dans la boucle n'est pas nécessaire.

 #include  #include  struct Bitmap_line { int blah; unsigned int width; Bitmap_line(unsigned int w) { blah = 0; width = w; } }; #define TEST 0 //define 1 for faster test int main(int argc, char* argv[]) { unsigned int size = (4 * 1024 * 1024) / 3 * 3; //makes it divisible by 3 unsigned char* pointer = (unsigned char*)malloc(size); memset(pointer, 0, size); std::unique_ptr bitmap(new Bitmap_line(size / 3)); clock_t told = clock(); #if TEST == 0 for (int iter = 0; iter < 10000; iter++) { unsigned char* p = pointer; for (unsigned x = 0; x < static_cast(bitmap->width); ++x) //for (unsigned x = 0, n = static_cast(bitmap->width); x < n; ++x) { *p++ = 0xAA; *p++ = 0xBB; *p++ = 0xCC; } } #else for (int iter = 0; iter < 10000; iter++) { unsigned char* p = pointer; unsigned x = 0; for (const unsigned n = static_cast(bitmap->width) - 4; x < n; x += 4) { *(int64_t*)p = 0xBBAACCBBAACCBBAALL; p += 8; *(int32_t*)p = 0xCCBBAACC; p += 4; } for (const unsigned n = static_cast(bitmap->width); x < n; ++x) { *p++ = 0xAA; *p++ = 0xBB; *p++ = 0xCC; } } #endif double ms = 1000.0 * double(clock() - told) / CLOCKS_PER_SEC; printf("time %0.3f\n", ms); { //verify unsigned char* p = pointer; for (unsigned x = 0, n = static_cast(bitmap->width); x < n; ++x) { if ((*p++ != 0xAA) || (*p++ != 0xBB) || (*p++ != 0xCC)) { printf("EEEEEEEEEEEEERRRRORRRR!!!\n"); abort(); } } } return 0; } 

Il y a deux choses à considérer.

A) À quelle fréquence l’optimisation fonctionnera-t-elle?

Si la réponse n’est pas très fréquente, comme lorsque l’utilisateur clique sur un bouton, ne vous inquiétez pas si cela rend votre code illisible. Si la réponse est 1000 fois par seconde, vous voudrez probablement aller avec l’optimisation. Si c’est un peu complexe, assurez-vous de commenter ce qui se passe pour aider le prochain à venir.

B) Cela rendra-t-il le code plus difficile à entretenir / dépanner?

Si vous ne constatez pas de gain de performance énorme, il est déconseillé de rendre votre code cryptique simplement pour économiser quelques tics d’horloge. Beaucoup de gens vous diront que tout bon programmeur devrait pouvoir regarder le code et comprendre ce qui se passe. C’est vrai. Le problème est que dans le monde des affaires, le temps supplémentaire qui en découle coûte de l’argent. Donc, si vous pouvez le rendre plus joli à lire, alors faites-le. Vos amis vous en remercieront.

Cela dit, j’utiliserais personnellement l’exemple de B.

Le compilateur est capable d’optimiser beaucoup de choses. Pour votre exemple, vous devriez aller pour la lisibilité, la durabilité et ce qui suit votre norme de code. Pour plus d’informations sur ce qui peut être optimisé (avec GCC), voir cet article de blog .

En règle générale, laissez le compilateur faire l’optimisation pour vous, jusqu’à ce que vous déterminiez que vous devez prendre le relais. La logique de cela n’a rien à voir avec la performance, mais plutôt avec la lisibilité humaine. Dans la grande majorité des cas, la lisibilité de votre programme est plus importante que ses performances. Vous devriez viser à écrire du code plus facile à lire pour un humain, puis vous soucier uniquement de l’optimisation lorsque vous êtes convaincu que les performances sont plus importantes que la maintenabilité de votre code.

Une fois que vous constatez que les performances sont importantes, vous devez exécuter un profileur sur le code pour déterminer les boucles inefficaces et les optimiser individuellement. Il peut en effet y avoir des cas où vous souhaitez effectuer cette optimisation (surtout si vous migrez vers C ++, où les conteneurs STL sont impliqués), mais le coût en termes de lisibilité est élevé.

De plus, je peux penser à des situations pathologiques où il pourrait ralentir le code. Par exemple, considérons le cas où le compilateur n’a pas pu prouver que bitmap->width était constant tout au long du processus. En ajoutant la variable width , vous forcez le compilateur à conserver une variable locale dans cette étendue. Si, pour une raison spécifique à une plate-forme, cette variable supplémentaire empêche une optimisation de l’espace de la stack, elle peut devoir réorganiser la façon dont elle émet des bytecodes et produire quelque chose de moins efficace.

Par exemple, sous Windows x64, il est obligatoire d’appeler un appel API spécial, __chkstk dans le préambule de la fonction si la fonction utilise plus d’une page de variables locales. Cette fonction donne à Windows une chance de gérer les pages de garde utilisées pour développer la stack si nécessaire. Si votre variable supplémentaire pousse l’utilisation de la stack de moins de 1 page à au moins 1 page, votre fonction est maintenant obligée d’appeler __chkstk chaque saisie. Si vous deviez optimiser cette boucle sur un chemin lent, vous pourriez en fait ralentir davantage le chemin rapide que vous en avez enregistré sur le chemin lent!

Bien sûr, c’est un peu pathologique, mais le but de cet exemple est que vous pouvez réellement ralentir le compilateur. Cela montre simplement que vous devez profiler votre travail pour déterminer où vont les optimisations. En attendant, ne sacrifiez pas la lisibilité de quelque manière que ce soit pour une optimisation qui peut ou non être importante.

La comparaison est fausse puisque les deux extraits de code

 for (unsigned x = 0; x < static_cast(bitmap->width); ++x) 

et

 unsigned width(static_cast(bitmap->width)); for (unsigned x = 0; x 

ne sont pas équivalents

Dans le premier cas, la width est dépendante et non pas constante, et on ne peut pas supposer qu'elle ne changera pas entre les itérations suivantes. Ainsi, il ne peut pas être optimisé, mais doit être vérifié à chaque boucle .

Dans votre cas optimisé, une variable locale se voit atsortingbuer la valeur bitmap->width à un moment donné pendant l'exécution du programme. Le compilateur peut vérifier que cela ne change pas réellement.

Avez-vous pensé au multi-threading, ou peut-être que la valeur pourrait dépendre de l'extérieur, de sorte que sa valeur est volatile. Comment pourrait-on s'attendre à ce que le compilateur comprenne toutes ces choses si vous ne le dites pas?

Le compilateur peut seulement faire aussi bien que votre code le permet.

À moins que vous ne sachiez exactement comment le compilateur optimise le code, il est préférable de faire vos propres optimisations en conservant la lisibilité du code et sa conception. En pratique, il est difficile de vérifier le code de l’assemblage pour chaque fonction que nous écrivons pour les nouvelles versions du compilateur.

Le compilateur ne peut pas optimiser bitmap->width car la valeur de la width peut être modifiée entre les itérations. Il y a quelques raisons les plus courantes:

1. Multi-threading. Le compilateur ne peut pas prédire si un autre thread est sur le sharepoint changer de valeur.
2. Modification à l’intérieur de la boucle, il n’est parfois pas simple de dire si la variable sera modifiée à l’intérieur de la boucle.
3. C’est l’appel de fonction, par exemple iterator::end() ou container::size() , il est donc difficile de prédire si le résultat sera toujours le même.

Pour résumer (mon opinion personnelle) pour les endroits qui nécessitent un haut niveau d’optimisation, vous devez le faire vous-même, ailleurs, le compilateur peut l’optimiser ou non.