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

114

Considérez le code suivant ( pest de type unsigned char*et bitmap->widthest d'un type entier, qui est exactement inconnu et dépend de la version d'une bibliothèque externe que nous utilisons):

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

Vaut-il la peine de l’optimiser [..]

Pourrait-il y avoir un cas où cela pourrait donner des résultats plus efficaces en écrivant:

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

... ou est-ce trivial pour le compilateur d'optimiser?

Que considérez-vous comme un «meilleur» code?

Note de l'éditeur (Ike): pour ceux qui s'interrogent sur le texte barré, la question originale, telle que formulée, était dangereusement proche d'un territoire hors sujet et était sur le point d'être fermée malgré des retours positifs. Ceux-ci ont été radiés. Cependant, veuillez ne pas punir les personnes qui ont répondu à ces sections frappées de la question.

Yaron Cohen-Tal
la source
19
Si *pest du même type que widthalors, ce n'est pas trivial à optimiser, car cela ppourrait pointer widthet le modifier à l'intérieur de la boucle.
emlai
31
Demander si le compilateur optimise une opération particulière est généralement la mauvaise question. Ce qui vous intéresse (généralement) en fin de compte, c'est la version qui s'exécute le plus rapidement, que vous devez simplement mesurer.
SirGuy
4
@GuyGreer Je suis d'accord, même si je dirais que la question est bonne, ou du moins intéressante, je pense malheureusement que la réponse est "il faut la mesurer, par cas d'utilisation". La raison en est que la fonctionnalité est portable, mais les performances ne le sont pas. Cela dépend donc en fait de chaque partie du processus de construction, en commençant par le compilateur et en finissant sur le site cible (combinaison os / matériel). Et bien sûr, la meilleure estimation est que le compilateur est plus intelligent que l'humain.
luk32
19
Si j'étais un compilateur, je verrais que vos deux exemples ne sont pas les mêmes. Il est possible que cela ppointe vers la même mémoire que bitmap->width. Par conséquent, je ne peux pas légalement optimiser le premier exemple au second.
Mysticial
4
Où «p» est-il stocké? Je suggérerais que vous pourriez obtenir un gain de performances vraiment énorme en faisant quelque chose comme "char * restrict p2 = p;" puis en utilisant "p2" plutôt que "p" dans votre boucle. Ensuite, si vous souhaitez que les modifications apportées à "p2" soient appliquées de nouveau à p, utilisez "p + = (p2-p);". Notez qu'aucun pointeur écrit pendant la durée de vie de p2 par un pointeur non copié de la forme p2 ne peut être lu en utilisant un pointeur copié depuis p2, ni vice versa, et aucune copie de p2 ne peut être utilisée à quelque fin que ce soit après la durée de vie de p2, mais un compilateur peut les utiliser faits pour permettre des optimisations qui ne peuvent être effectuées par aucun autre moyen.
supercat du

Réponses:

81

À première vue, 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:

La source unoptimized.cpp

remarque: 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<unsigned>(bitmap.width) ; ++x)
    {
        argv[x][0] = '\0';
    }
    return 0;
}

La source optimized.cpp

remarque: 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<unsigned>(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

Assemblée (unoptimized.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'assembly généré pour la version optimisée charge en fait ( lea) la widthconstante contrairement à la version non optimisée qui calcule le widthdécalage à chaque itération ( movq).

Quand j'aurai le temps, je publie finalement un point de repère à ce sujet. Bonne question.

YSC
la source
3
Il serait intéressant de voir si le code a été généré différemment si vous effectuez un cast au const unsignedlieu de simplement unsigneddans le cas non optimisé.
Mark Ransom
2
@MarkRansom Je suppose que cela ne devrait pas faire de différence: la "promesse" d'être const n'est que pendant la comparaison unique, pas pour toute la boucle
Hagen von Eitzen
13
N'utilisez JAMAIS la fonction mainpour tester une optimisation. Gcc le marque délibérément comme froid et désactive ainsi certaines optimisations. Je ne sais pas si c'est le cas ici, mais c'est une habitude importante à prendre.
Marc Glisse
3
@MarcGlisse Vous avez raison à 100%. Je l'ai écrit à la hâte, je vais l'améliorer.
YSC du
3
Voici un lien vers les deux fonctions dans une unité de compilation sur godbolt , en supposant qu'il bitmaps'agit d'un fichier global. La version non-CSEd utilise un opérande mémoire to cmp, ce qui n'est pas un problème pour perf dans ce cas. S'il s'agissait d'un local, le compilateur pourrait supposer que d'autres pointeurs ne pouvaient pas "le savoir" et pointer dessus. Ce n'est pas une mauvaise idée de stocker des expressions impliquant des globaux dans des variables temporaires, tant que cela améliore (ou ne nuit pas) la lisibilité, ou si les performances sont critiques. À moins qu'il ne se passe beaucoup de choses, ces habitants peuvent généralement vivre dans des registres et ne jamais être renversés.
Peter Cordes
38

Les informations de votre extrait de code sont en fait insuffisantes pour pouvoir le dire, et la seule chose à laquelle je peux penser est l'aliasing. De notre point de vue, il est assez clair que vous ne voulez pas pet bitmappointer vers le même emplacement en mémoire, mais le compilateur ne le sait pas et (parce qu'il pest de type char*) le compilateur doit faire fonctionner ce code même si pet se bitmapchevauchent.

Cela signifie dans ce cas que si la boucle change bitmap->widthvia le pointeur, pcela doit être vu lors de la relecture bitmap->widthultérieure, ce qui signifie à son tour 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'ai vu des preuves circonstancielles de cela, mais je n'ai jamais directement cherché des informations sur ce que fait le compilateur dans ce cas), et vérifier rapidement si les pointeurs alias et exécutez le code le plus rapide s'il détermine que c'est correct.

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

À mon avis, des questions comme celles-ci sont acceptables si votre objectif est d'en apprendre davantage sur les théories et les techniques d'optimisation du compilateur, mais c'est une perte de temps (une micro-optimisation inutile) si votre objectif final est de rendre le programme plus rapide.

SirGuy
la source
1
@GuyGreer: C'est un bloqueur d'optimisation majeur; Je trouve malheureux que les règles linguistiques se concentrent sur les règles relatives aux types efficaces, plutôt que sur l'identification de situations dans lesquelles les écritures et les lectures d'éléments différents sont ou ne sont pas sans séquence. Les règles écrites dans de tels termes pourraient mieux répondre aux besoins du compilateur et du programmeur que les présentes.
supercat du
3
@GuyGreer - un restrictqualificatif ne serait-il pas la réponse au problème d'aliasing dans ce cas?
LThode
4
D'après mon expérience, restrictc'est en grande partie aléatoire. MSVC est le seul compilateur que j'ai vu qui semble le faire correctement. ICC perd les informations d'alias lors des appels de fonction même s'ils sont en ligne. Et GCC n'obtient généralement aucun avantage à moins que vous ne déclariez chaque paramètre d'entrée comme restrict(y compris thispour les fonctions membres).
Mysticial
1
@Mystical: Une chose à retenir est que chartous les types d'alias sont associés , donc si vous avez un char *, vous devez l'utiliser restrictsur tout. Ou si vous avez forcé les règles strictes d'alias de GCC avec -fno-strict-aliasingalors tout est considéré comme un alias possible.
Zan Lynx
1
@Ray La proposition la plus récente pour une restrictsémantique semblable en C ++ est N4150 .
TC du
24

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

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

Donc, je suppose que l'aliasing est le truc, je n'y avais pas pensé.

[Éditer]

J'ai essayé à nouveau la première version avec tous les pointeurs définis avec __restrict__, et les résultats sont les mêmes. Bizarre .. Soit l'aliasing n'est pas le problème, soit, pour une raison quelconque, le compilateur ne l'optimise pas bien même avec __restrict__.

[Modifier 2]

Ok, je pense que j'ai été à peu près capable 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<unsigned>(bitmap->width);  ++x)
{
    d[i++] = 0xAA;
    d[i++] = 0xBB;
    d[i++] = 0xCC;
}

Et mesuré (a dû 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<unsigned>(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.

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

Yaron Cohen-Tal
la source
4
Cela semble devoir être un commentaire, même si cela répond techniquement à la question. Notez également, malheureusement, vous n'avez pas démontré que l'aliasing était la chose. Cela semble probable, certainement plausible, mais c'est différent de conclure que c'était tout.
SirGuy
@GuyGreer: Voir mon [edit 2] - maintenant je pense que c'est à peu près prouvé.
Yaron Cohen-Tal
2
Je me demande simplement pourquoi vous avez commencé à utiliser la variable "i" lorsque vous avez "x" dans votre boucle?
Jesper Madsen
1
Est-ce juste moi qui trouve la phrase 54% plus rapide difficile à comprendre? Voulez-vous dire que c'est 1,54 fois la vitesse de la vitesse non optimisée, ou autre chose?
Roddy
3
@ YaronCohen-Tal donc deux fois plus vite? Impressionnant, mais pas ce que j'aurais compris "54% plus rapide"!
Roddy
24

D'autres réponses ont souligné que le fait de sortir l'opération du pointeur de la boucle peut changer le comportement défini en raison des règles d'aliasing qui permettent à char d'aliaser n'importe quoi et n'est donc pas une optimisation autorisée pour un compilateur même si dans la plupart des cas c'est évidemment correct pour un humain programmeur.

Ils ont également souligné que le hissage de l'opération hors de la boucle est généralement, mais pas toujours, une amélioration du point de vue des performances et est souvent un inconvénient du point de vue de la lisibilité.

Je tiens à souligner qu'il existe souvent une «troisième voie». Plutôt que de compter jusqu'au nombre d'itérations souhaité, vous pouvez effectuer un compte à rebours jusqu'à zéro. Cela signifie que le nombre d'itérations n'est nécessaire qu'une seule fois au début de la boucle, il n'a pas besoin d'être stocké après cela. Mieux encore au niveau de l'assembleur, cela élimine souvent le besoin d'une comparaison explicite car l'opération de décrémentation définira généralement des indicateurs indiquant si le compteur était égal à zéro avant (indicateur de retenue) et après (indicateur zéro) la décrémentation.

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

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

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

Vous pouvez également vous débarrasser des casts 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 est de l'assigner directement à une variable.

plugwash
la source
2
J'ai vu ce deuxième cas formaté comme x --> 0, résultant en l'opérateur "downto". Assez drôle. PS Je ne considère pas que faire une variable pour la condition finale soit un négatif pour la lisibilité, cela peut en fait être le contraire.
Mark Ransom
Cela dépend vraiment, parfois une déclaration devient si horrible que la diviser en plusieurs déclarations améliore la lisibilité, mais je ne pense pas que ce soit le cas ici.
plugwash
1
+1 Bonne observation, même si je dirais que hisser static_cast<unsigned>(bitmap->width)et utiliser à la widthplace dans la boucle est en fait une amélioration de la lisibilité, car il y a maintenant moins de choses à analyser par le lecteur par ligne. Les opinions des autres peuvent cependant différer.
SirGuy
1
Il existe de nombreuses autres situations où le comptage à la baisse est supérieur (par exemple, lors de la suppression d'éléments d'une liste). Je ne sais pas pourquoi cela n'est pas fait plus souvent.
Ian Gold du
3
Si vous voulez écrire des boucles qui ressemblent davantage à l'asm optimal, utilisez do { } while(), car dans ASM vous créez des boucles avec une branche conditionnelle à la fin. Les boucles for(){}et habituelles while(){}nécessitent des instructions supplémentaires pour tester la condition de la boucle une fois avant la boucle, si le compilateur ne peut pas prouver qu'elle s'exécute toujours au moins une fois. Bien sûr, utilisez for()ou while()quand il est utile de vérifier si la boucle doit même s'exécuter une fois, ou quand elle est plus lisible.
Peter Cordes
11

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

"L'aliasing strict est une hypothèse, faite par le compilateur C (ou C ++), que le déréférencement des pointeurs vers des objets de types différents ne fera jamais référence au même emplacement mémoire (c'est-à-dire les alias les uns des autres)."

[…]

L'exception à la règle est a char*, qui est autorisé à pointer vers n'importe quel type.

L'exception s'applique également aux pointeurs unsignedet signed char.

C'est le cas dans votre code: vous modifiez *pvia pquel est un unsigned char*, donc le compilateur doit supposer qu'il pourrait pointer vers bitmap->width. Par conséquent, la mise en cache de bitmap->widthest une optimisation invalide. Ce comportement empêchant l'optimisation est illustré dans la réponse de YSC .

Si et seulement si ppointé vers un non charet un non decltype(bitmap->width)type, la mise en cache serait-elle une optimisation possible.

emlai
la source
10

La question posée à l'origine:

Vaut-il la peine de l'optimiser?

Et ma réponse à cela (recueillir un bon mélange de votes à la hausse et à la baisse ..)

Laissez le compilateur s'en soucier.

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é ??

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

Malgré les votes négatifs (et voyant maintenant le problème d'aliasing), je suis toujours satisfait de cela comme une réponse valide. Si vous ne savez pas s'il 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 savoir s'il vaut la peine d'optimiser un fragment de code?

Tout d'abord, votre application ou bibliothèque doit-elle s'exécuter 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 plutôt que celle de demain?

Vous seul pouvez vraiment le dire, en fonction de ce à quoi sert 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. Les profileurs vous diront où votre code passe son temps. Si votre fragment ne s'affiche pas comme un goulot d'étranglement, il vaut mieux le laisser seul. Les profileurs et autres outils de mesure vous diront également si vos modifications ont fait une différence. Il est possible de passer des heures à optimiser le code, seulement pour constater que vous n'avez fait aucune différence perceptible.

Qu'entendez-vous 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 mauvais» n'est pas une excuse pour un code bâclé ou inefficace.

Le code optimisé sacrifie normalement certains des attributs ci-dessus pour les performances. Cela pourrait impliquer l'introduction de variables locales supplémentaires, avoir des objets avec une portée plus large que prévue ou même inverser l'ordre normal des boucles. Tous ces éléments peuvent être moins clairs ou concis, alors documentez le code (brièvement!) Pour expliquer pourquoi vous faites cela.

Mais souvent, avec du code «lent», ces micro-optimisations sont le dernier recours. Le premier endroit à regarder est les algorithmes et les structures de données. Existe-t-il un moyen d'éviter de faire le travail? Les recherches linéaires peuvent-elles être remplacées par des recherches binaires? Une liste chaînée serait-elle plus rapide ici qu'un vecteur? Ou une table de hachage? Puis-je mettre en cache les résultats? Prendre de bonnes décisions «efficaces» ici peut souvent affecter les performances d'un ordre de grandeur ou plus!

Roddy
la source
12
Lorsque vous effectuez une itération sur la largeur d'une image bitmap, la logique de bouclage peut représenter une partie importante du temps passé dans la boucle. Plutôt que de s'inquiéter d'une optimisation prématurée, il vaut mieux dans ce cas développer des bonnes pratiques efficaces dès le départ.
Mark Ransom
4
@MarkRansom était en partie d'accord: mais les «meilleures pratiques» seraient soit a: utiliser une bibliothèque existante ou un appel API pour remplir les images, soit b: demander au GPU de le faire pour vous. Cela ne devrait jamais être le genre de micro-optimisation non mesurée que l'OP suggère. Et comment savez-vous que ce code est exécuté plus d'une fois, ou avec des bitmaps plus grands que 16 pixels de large ...?
Roddy
@Veedrac. Appréciez la justification du -1. L'orientation de la question a subtilement et substantiellement changé depuis que j'ai répondu. Si vous pensez que la réponse (développée) n'est toujours pas utile, il est temps pour moi de la supprimer ... "Vaut-il la peine ..." est toujours principalement basé sur l'opinion, de toute façon.
Roddy
@Roddy J'apprécie les modifications, elles aident (et mon commentaire semblait probablement trop dur de toute façon). Cependant, je suis toujours sur la clôture, car c'est vraiment une réponse à une question qui ne convient pas à Stack Overflow. Il semble qu'une bonne réponse serait spécifique à l'extrait, comme le sont les réponses hautement votées ici.
Veedrac
6

J'utilise le modèle suivant dans une situation comme celle-ci. Il est presque aussi court que le premier cas du vôtre, et est meilleur que le second cas, car il maintient la variable temporaire locale à la boucle.

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

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

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

Edit2:: J'ai mesuré ma suggestion par rapport au code d'origine sur vs2013, j'ai obtenu une amélioration de% 1. Pouvons-nous faire mieux? Une simple optimisation manuelle permet d'améliorer 3 fois la boucle d'origine sur une machine x64 sans recourir à des instructions exotiques. Le code ci-dessous suppose un système little endian et une image bitmap correctement alignée. 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. Très bientôt dans le futur, le compilateur sera en mesure de produire du code toujours le plus rapide. J'ai peur que ce soit le futur lorsque le compilateur sera aussi une IA de programmeur, donc nous serions sans travail. Mais pour l'instant, écrivez simplement du code qui montre que vous savez qu'une opération supplémentaire dans la boucle n'est pas nécessaire.

#include <memory>
#include <time.h>

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_line> 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<unsigned>(bitmap->width); ++x)
    //for (unsigned x = 0, n = static_cast<unsigned>(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<unsigned>(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<unsigned>(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<unsigned>(bitmap->width); x < n; ++x)
    {
      if ((*p++ != 0xAA) || (*p++ != 0xBB) || (*p++ != 0xCC))
      {
        printf("EEEEEEEEEEEEERRRRORRRR!!!\n");
        abort();
      }
    }
  }

  return 0;
}
0kcats
la source
Vous pouvez économiser 25% supplémentaires sur 64 bits si vous utilisez trois int64_t au lieu de int64_t et int32_t.
Antonín Lejsek
5

Il y a deux choses à considérer.

A) À quelle fréquence l'optimisation sera-t-elle exécutée?

Si la réponse n'est pas très fréquente, comme uniquement lorsqu'un 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 opter pour l'optimisation. Si c'est même un peu complexe, assurez-vous de mettre un commentaire pour expliquer ce qui se passe pour aider le prochain qui arrive.

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

Si vous ne voyez pas un énorme gain de performances, rendre votre code cryptique simplement pour enregistrer quelques cycles d'horloge n'est pas une bonne idée. Beaucoup de gens vous diront que tout bon programmeur devrait être capable de regarder le code et de comprendre ce qui se passe. C'est vrai. Le problème, c'est que dans le monde des affaires, le temps supplémentaire pour déterminer cela coûte de l'argent. Donc, si vous pouvez le rendre plus joli à lire, faites-le. Vos amis vous en remercieront.

Cela dit, j'utiliserais personnellement l'exemple B.

soulsabr
la source
4

Le compilateur est capable d'optimiser beaucoup de choses. Pour votre exemple, vous devriez opter pour la lisibilité, la maintenabilité et ce qui suit votre norme de code. Pour plus d'informations sur ce qui peut être optimisé (avec GCC), consultez ce billet de blog .

Guillaume Racicot
la source
4

En règle générale, laissez le compilateur faire l'optimisation pour vous, jusqu'à ce que vous décidiez que vous devez prendre le relais. La logique de cela n'a rien à voir avec les performances, 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 devez viser à écrire un code plus facile à lire pour un humain, puis ne vous soucier de l'optimisation que lorsque vous êtes convaincu que les performances sont plus importantes que la maintenabilité de votre code.

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

De plus, je peux penser à des situations pathologiques où cela pourrait en fait ralentir le code. Par exemple, considérons le cas où le compilateur n'a pas pu prouver que bitmap->widthc'était constant tout au long du processus. En ajoutant la widthvariable, vous forcez le compilateur à maintenir une variable locale dans cette portée. Si, pour une raison spécifique à la plate-forme, cette variable supplémentaire empêchait une certaine optimisation de l'espace de pile, il se peut qu'elle doive réorganiser la façon dont elle émet des codes octets et produire quelque chose de moins efficace.

A titre d'exemple, sous Windows x64, on est obligé d'appeler un appel API spécial, __chkstkdans le préambule de la fonction si la fonction utilisera plus d'une page de variables locales. Cette fonction donne aux fenêtres une chance de gérer les pages de garde qu'elles utilisent pour étendre la pile en cas de besoin. Si votre variable supplémentaire pousse l'utilisation de la pile de moins de 1 page à au-dessus de 1 page, votre fonction est maintenant obligée d'appeler __chkstkchaque fois qu'elle est entrée. Si vous optimisez cette boucle sur un chemin lent, vous risquez en fait de ralentir le chemin rapide plus que ce que vous avez enregistré sur le chemin lent!

Bien sûr, c'est un peu pathologique, mais le point 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, veuillez ne sacrifier en aucune manière la lisibilité pour une optimisation qui puisse ou non avoir une importance.

Cort Ammon
la source
4
Je souhaite que C et C ++ fournissent plus de moyens d'identifier explicitement les choses dont le programmeur ne se soucie pas. Non seulement ils donneraient plus de chances aux compilateurs d'optimiser les choses, mais cela éviterait aux autres programmeurs qui lisent le code d'avoir à deviner si, par exemple, il pourrait revérifier bitmap-> width à chaque fois pour s'assurer que les modifications affectent la boucle, ou s'il peut mettre en cache bitmap-> width pour s'assurer que les modifications apportées n'affectent pas la boucle. Avoir un moyen de dire "Cachez ceci ou pas - je m'en fiche" clarifierait la raison du choix du programmeur.
supercat
@supercat Je suis tout à fait d'accord, car on peut voir si l'on regarde les tas de langages ratés et ratés que j'ai cherché à écrire pour résoudre ce problème. J'ai trouvé qu'il est remarquablement difficile de définir «ce dont» quelqu'un ne se soucie pas sans tellement de syntaxe impie que cela n'en vaut pas la peine. Je continue ma recherche en vain.
Cort Ammon
Il n'est pas possible de le définir dans tous les cas, mais je pense qu'il y a beaucoup de cas où le système de types pourrait aider. C'est trop C a décidé de faire des types de caractères "l'accesseur universel" plutôt que d'avoir un qualificateur de type un peu plus lâche que "volatile" qui pourrait être appliqué à n'importe quel type, avec la sémantique que les accès de ces types seraient traités en séquence avec accès de type équivalent non qualifié et également avec accès de tous types de variables avec ce même qualificatif. Cela aiderait à préciser si l'on utilisait des types de caractères parce qu'il fallait le ...
supercat
... comportement d'aliasing, ou si on les utilisait parce qu'ils étaient de la bonne taille pour répondre à ses besoins. Il serait également utile d'avoir des barrières d'alias explciit qui pourraient dans de nombreux cas être placées en dehors des boucles, contrairement aux barrières implicites associées aux accès de type caractère.
supercat du
1
C'est un discours judicieux, mais, généralement, si vous sélectionnez déjà C pour votre tâche, les performances sont probablement très importantes et les différentes règles doivent s'appliquer. Sinon, il peut être préférable d'utiliser Ruby, Java, Python ou quelque chose de similaire.
Audrius Meskauskas
4

La comparaison est erronée car les deux extraits de code

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

et

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

ne sont pas équivalents

Dans le premier cas, il widthest dépendant et non constant, et on ne peut pas supposer qu'il ne peut pas changer 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 reçoit la valeur de 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 être dépendante de l'extérieur de sorte que sa valeur soit volatile. Comment s'attendrait-on à ce que le compilateur trouve toutes ces choses si vous ne le dites pas?

Le compilateur ne peut faire que ce que votre code le permet.

g24l
la source
2

À 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é et la conception du code. En pratique, il est difficile de vérifier le code d'assemblage pour chaque fonction que nous écrivons pour les nouvelles versions du compilateur.

Vinayak SM
la source
1

Le compilateur ne peut pas optimiser bitmap->widthcar la valeur de widthpeut ê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 point de changer de valeur.
  2. Modification à l'intérieur de la boucle, parfois il n'est pas simple de dire si la variable sera modifiée à l'intérieur de la boucle.
  3. Il est appel de fonction, par exemple , iterator::end()ou container::size()il est donc difficile de prédire si elle retourne toujours le même résultat.

Pour résumer (mon opinion personnelle) pour les endroits qui nécessitent un haut niveau d'optimisation, vous devez le faire vous-même, dans d'autres endroits, laissez-le, le compilateur peut l'optimiser ou non, s'il n'y a pas de grande différence, la lisibilité du code est la cible principale.

ST3
la source