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

Question

Considérons le code suivant ( p est de type unsigned char* y bitmap->width est d'un certain type d'entier, dont le type exact est 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;
}

_{<s>Est-ce que cela vaut la peine de l'optimiser [ ]</s>}

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 de l'optimiser ?

_{<s>Que considérez-vous comme un "meilleur" code ?</s>}

_{<em>Note du rédacteur (Ike) : pour ceux qui s'interrogent sur le texte barré, la question originale, telle qu'elle était formulée, se rapprochait dangereusement du hors-sujet et était sur le point d'être fermée malgré les réactions positives. Ces éléments ont été rayés. Mais s'il vous plaît, ne punissez pas les personnes qui ont répondu à ces sections biffées de la question.</em>}

Answer 1

À première vue, je pensais que le compilateur pouvait générer un assemblage équivalent pour les deux versions avec les drapeaux d'optimisation activés. Lorsque 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<unsigned>(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<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

---

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

Montage (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 se charge effectivement ( lea ) le width contrairement à la version non optimisée qui calcule la constante width à chaque itération ( movq ).

Quand j'aurai le temps, je posterai éventuellement quelques repères à ce sujet. Bonne question.

Answer 2

En fait, votre extrait de code ne contient pas suffisamment d'informations pour que nous puissions en juger, et la seule chose à laquelle je pense est l'aliasing. De notre point de vue, il est assez clair que vous ne voulez pas p y bitmap pour pointer vers le même emplacement en mémoire, mais le compilateur ne sait pas cela et (parce que p est de type char* ) le compilateur doit faire fonctionner ce code même si p y bitmap chevauchement.

Cela signifie dans ce cas que si la boucle change bitmap->width par le biais du pointeur p alors cela doit être vu en relisant bitmap->width plus tard, ce qui signifie que le stocker dans une variable locale serait illégal.

Ceci étant dit, je crois que certains compilateurs génèrent parfois deux versions du même code (j'ai vu des preuves circonstancielles de cela, mais je n'ai jamais cherché directement des informations sur ce que le compilateur fait dans ce cas), et vérifient rapidement si les pointeurs sont alias et exécutent le code le plus rapide s'il le juge bon.

Cela étant dit, je maintiens mon commentaire sur la simple mesure des performances des deux versions, je parie qu'il n'y a pas de différence de performance constante entre les deux versions du code.

À mon avis, les questions de ce type sont acceptables si votre objectif est d'apprendre les théories et techniques d'optimisation du compilateur, mais c'est une perte de temps (une micro-optimisation inutile) si votre objectif final est d'accélérer le programme.

Answer 3

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'alias qui permettent aux chars d'aliaser n'importe quoi et donc n'est pas une optimisation admissible pour un compilateur même si dans la plupart des cas, elle est évidemment correcte pour un programmeur humain.

Ils ont également fait remarquer que le fait de sortir l'opération de la boucle constitue généralement, mais pas toujours, une amélioration du point de vue des performances et est souvent négatif du point de vue de la lisibilité.

Je tiens à souligner qu'il existe souvent une "troisième voie". Au lieu de compter jusqu'au nombre d'itérations souhaité, vous pouvez décompter 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 met généralement en place des drapeaux qui indiquent si le compteur était nul avant (drapeau de report) et après (drapeau de 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 des valeurs de x dans l'intervalle 1..width plutôt que dans l'intervalle 0..(width-1). Cela n'a pas d'importance dans votre cas car vous n'utilisez pas réellement x pour quoi que ce soit, mais c'est quelque chose dont il faut être conscient. Si vous voulez une boucle de compte à rebours avec des valeurs de x dans l'intervalle 0..(width-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 leur impact sur les règles de comparaison puisque tout ce que vous faites avec bitmap->width est de l'assigner directement à une variable.

Answer 4

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 le crénelage est le problème, je n'y avais pas pensé.

[Edit]

J'ai réessayé 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, ou, pour une raison quelconque, le compilateur ne l'optimise pas bien même avec __restrict__ .

[Edit 2]

Ok, je pense que j'ai réussi à prouver que le crénelage est le problème. J'ai répété mon test original, en utilisant cette fois 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é (j'ai 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 - Il semble que le compilateur ait pu l'optimiser par lui-même.

Puis j'ai essayé les codes originaux (avec un pointeur p ), cette fois-ci lorsque p est de type std::uint16_t* . Encore une fois, les résultats étaient les mêmes - dus à un aliasing strict. J'ai ensuite essayé de construire avec "-fno-strict-aliasing", et j'ai de nouveau constaté une différence de temps.

Answer 5

La question posée à l'origine :

Cela vaut-il la peine de l'optimiser ?

Et ma réponse à cela (qui a recueilli un bon mélange de votes positifs et négatifs )

Laissez le compilateur s'en occuper.

Le compilateur fera presque certainement un meilleur travail que vous. Et Et il n'y a aucune garantie que votre "optimisation" soit meilleure que le code "évident". code " évident " - l'avez-vous mesuré ?

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

Malgré les votes négatifs (et maintenant que je vois le problème d'aliasing), je suis toujours satisfait de cette réponse comme étant valide. 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 ?

Tout d'abord, 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 le temps d'hier au lieu de celui de demain ?

Vous êtes le seul à pouvoir le dire, en fonction de la finalité de votre logiciel et des attentes de vos utilisateurs.

En supposant que votre logiciel ait besoin d'être optimisé, la prochaine chose à faire est de commencer à mesurer. Les profileurs vous diront où votre code passe son temps. Si votre fragment n'apparaît pas comme un goulot d'étranglement, il vaut mieux le laisser tranquille. Les profileurs et autres outils de mesure vous diront également si vos changements ont fait une différence. Il est possible de passer des heures à essayer d'optimiser le code, pour se rendre compte que vous n'avez fait aucune différence notable.

Qu'entendez-vous par "optimiser", d'ailleurs ?

Si vous n'écrivez pas un code "optimisé", votre code doit être aussi clair, propre et concis que possible. L'argument "L'optimisation prématurée est un mal" 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. Il peut s'agir d'introduire des variables locales supplémentaires, d'avoir des objets dont la portée est plus large que prévu ou même d'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 un code "lent", ces micro-optimisations sont le dernier recours. Le premier point à examiner est celui des algorithmes et des 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 qu'un vecteur ? Ou une table de hachage ? Puis-je mettre les résultats en cache ? Prendre de bonnes décisions "efficaces" ici peut souvent affecter les performances d'un ordre de grandeur ou plus !