L'utilisation de ce pointeur provoque une étrange désoptimisation en boucle chaude

122

Je suis récemment tombé sur une étrange désoptimisation (ou plutôt une opportunité d'optimisation manquée).

Considérez cette fonction pour un décompactage efficace des tableaux d'entiers de 3 bits en entiers de 8 bits. Il décompresse 16 ints à chaque itération de boucle:

void unpack3bit(uint8_t* target, char* source, int size) {
   while(size > 0){
      uint64_t t = *reinterpret_cast<uint64_t*>(source);
      target[0] = t & 0x7;
      target[1] = (t >> 3) & 0x7;
      target[2] = (t >> 6) & 0x7;
      target[3] = (t >> 9) & 0x7;
      target[4] = (t >> 12) & 0x7;
      target[5] = (t >> 15) & 0x7;
      target[6] = (t >> 18) & 0x7;
      target[7] = (t >> 21) & 0x7;
      target[8] = (t >> 24) & 0x7;
      target[9] = (t >> 27) & 0x7;
      target[10] = (t >> 30) & 0x7;
      target[11] = (t >> 33) & 0x7;
      target[12] = (t >> 36) & 0x7;
      target[13] = (t >> 39) & 0x7;
      target[14] = (t >> 42) & 0x7;
      target[15] = (t >> 45) & 0x7;
      source+=6;
      size-=6;
      target+=16;
   }
}

Voici l'assemblage généré pour les parties du code:

 ...
 367:   48 89 c1                mov    rcx,rax
 36a:   48 c1 e9 09             shr    rcx,0x9
 36e:   83 e1 07                and    ecx,0x7
 371:   48 89 4f 18             mov    QWORD PTR [rdi+0x18],rcx
 375:   48 89 c1                mov    rcx,rax
 378:   48 c1 e9 0c             shr    rcx,0xc
 37c:   83 e1 07                and    ecx,0x7
 37f:   48 89 4f 20             mov    QWORD PTR [rdi+0x20],rcx
 383:   48 89 c1                mov    rcx,rax
 386:   48 c1 e9 0f             shr    rcx,0xf
 38a:   83 e1 07                and    ecx,0x7
 38d:   48 89 4f 28             mov    QWORD PTR [rdi+0x28],rcx
 391:   48 89 c1                mov    rcx,rax
 394:   48 c1 e9 12             shr    rcx,0x12
 398:   83 e1 07                and    ecx,0x7
 39b:   48 89 4f 30             mov    QWORD PTR [rdi+0x30],rcx
 ...

Cela semble assez efficace. Simplement un shift rightsuivi d'un and, puis d'un storedans le targettampon. Mais maintenant, regardez ce qui se passe lorsque je change la fonction en méthode dans une structure:

struct T{
   uint8_t* target;
   char* source;
   void unpack3bit( int size);
};

void T::unpack3bit(int size) {
        while(size > 0){
           uint64_t t = *reinterpret_cast<uint64_t*>(source);
           target[0] = t & 0x7;
           target[1] = (t >> 3) & 0x7;
           target[2] = (t >> 6) & 0x7;
           target[3] = (t >> 9) & 0x7;
           target[4] = (t >> 12) & 0x7;
           target[5] = (t >> 15) & 0x7;
           target[6] = (t >> 18) & 0x7;
           target[7] = (t >> 21) & 0x7;
           target[8] = (t >> 24) & 0x7;
           target[9] = (t >> 27) & 0x7;
           target[10] = (t >> 30) & 0x7;
           target[11] = (t >> 33) & 0x7;
           target[12] = (t >> 36) & 0x7;
           target[13] = (t >> 39) & 0x7;
           target[14] = (t >> 42) & 0x7;
           target[15] = (t >> 45) & 0x7;
           source+=6;
           size-=6;
           target+=16;
        }
}

Je pensais que l'assemblage généré devrait être tout à fait le même, mais ce n'est pas le cas. En voici une partie:

...
 2b3:   48 c1 e9 15             shr    rcx,0x15
 2b7:   83 e1 07                and    ecx,0x7
 2ba:   88 4a 07                mov    BYTE PTR [rdx+0x7],cl
 2bd:   48 89 c1                mov    rcx,rax
 2c0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 2c3:   48 c1 e9 18             shr    rcx,0x18
 2c7:   83 e1 07                and    ecx,0x7
 2ca:   88 4a 08                mov    BYTE PTR [rdx+0x8],cl
 2cd:   48 89 c1                mov    rcx,rax
 2d0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 2d3:   48 c1 e9 1b             shr    rcx,0x1b
 2d7:   83 e1 07                and    ecx,0x7
 2da:   88 4a 09                mov    BYTE PTR [rdx+0x9],cl
 2dd:   48 89 c1                mov    rcx,rax
 2e0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 2e3:   48 c1 e9 1e             shr    rcx,0x1e
 2e7:   83 e1 07                and    ecx,0x7
 2ea:   88 4a 0a                mov    BYTE PTR [rdx+0xa],cl
 2ed:   48 89 c1                mov    rcx,rax
 2f0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 ...

Comme vous le voyez, nous avons introduit un redondant supplémentaire loadde la mémoire avant chaque shift ( mov rdx,QWORD PTR [rdi]). Il semble que le targetpointeur (qui est maintenant un membre au lieu d'une variable locale) doit toujours être rechargé avant d'être stocké dans celui-ci. Cela ralentit considérablement le code (environ 15% dans mes mesures).

Tout d'abord, j'ai pensé que le modèle de mémoire C ++ imposait peut-être qu'un pointeur de membre ne soit pas stocké dans un registre mais qu'il doive être rechargé, mais cela semblait être un choix délicat, car cela rendrait impossible de nombreuses optimisations viables. J'ai donc été très surpris que le compilateur ne soit pas stocké targetdans un registre ici.

J'ai essayé de mettre en cache le pointeur de membre moi-même dans une variable locale:

void T::unpack3bit(int size) {
    while(size > 0){
       uint64_t t = *reinterpret_cast<uint64_t*>(source);
       uint8_t* target = this->target; // << ptr cached in local variable
       target[0] = t & 0x7;
       target[1] = (t >> 3) & 0x7;
       target[2] = (t >> 6) & 0x7;
       target[3] = (t >> 9) & 0x7;
       target[4] = (t >> 12) & 0x7;
       target[5] = (t >> 15) & 0x7;
       target[6] = (t >> 18) & 0x7;
       target[7] = (t >> 21) & 0x7;
       target[8] = (t >> 24) & 0x7;
       target[9] = (t >> 27) & 0x7;
       target[10] = (t >> 30) & 0x7;
       target[11] = (t >> 33) & 0x7;
       target[12] = (t >> 36) & 0x7;
       target[13] = (t >> 39) & 0x7;
       target[14] = (t >> 42) & 0x7;
       target[15] = (t >> 45) & 0x7;
       source+=6;
       size-=6;
       this->target+=16;
    }
}

Ce code produit également le «bon» assembleur sans magasins supplémentaires. Donc, je suppose que le compilateur n'est pas autorisé à hisser la charge d'un pointeur de membre d'une structure, donc un tel "pointeur actif" devrait toujours être stocké dans une variable locale.

  • Alors, pourquoi le compilateur est-il incapable d'optimiser ces charges?
  • Est-ce le modèle de mémoire C ++ qui interdit cela? Ou est-ce simplement un défaut de mon compilateur?
  • Ma supposition est-elle correcte ou quelle est la raison exacte pour laquelle l'optimisation ne peut pas être effectuée?

Le compilateur utilisé était g++ 4.8.2-19ubuntu1avec -O3optimisation. J'ai également essayé clang++ 3.4-1ubuntu3avec des résultats similaires: Clang est même capable de vectoriser la méthode avec le targetpointeur local . Cependant, l'utilisation du this->targetpointeur donne le même résultat: une charge supplémentaire du pointeur avant chaque magasin.

J'ai vérifié l'assembleur de certaines méthodes similaires et le résultat est le même: il semble qu'un membre de thisdoit toujours être rechargé avant un magasin, même si une telle charge pourrait simplement être hissée en dehors de la boucle. Je vais devoir réécrire beaucoup de code pour me débarrasser de ces magasins supplémentaires, principalement en mettant en cache le pointeur moi-même dans une variable locale qui est déclarée au-dessus du code actif. Mais j'ai toujours pensé que jouer avec des détails tels que la mise en cache d'un pointeur dans une variable locale serait sûrement admissible à une optimisation prématurée de nos jours où les compilateurs sont devenus si intelligents. Mais il semble que je me trompe ici . La mise en cache d'un pointeur membre dans une boucle active semble être une technique d'optimisation manuelle nécessaire.

gexicide
la source
5
Je ne sais pas pourquoi cela a obtenu un vote négatif - c'est une question intéressante. FWIW J'ai vu des problèmes d'optimisation similaires avec des variables membres sans pointeur où la solution a été similaire, c'est-à-dire mettre en cache la variable membre dans une variable locale pour la durée de vie de la méthode. Je suppose que c'est quelque chose à voir avec les règles d'aliasing?
Paul R
1
Il semble que le compilateur n'optimise pas car il ne peut pas garantir que le membre n'est pas accessible via du code «externe». Donc, si le membre peut être modifié à l'extérieur, il doit être rechargé à chaque fois que vous y accédez. Semble être considéré comme une sorte de volatile ...
Jean-Baptiste Yunès
Non ne pas utiliser this->est juste du sucre syntaxique. Le problème est lié à la nature des variables (local vs membre) et aux choses que le compilateur en déduit.
Jean-Baptiste Yunès
Quelque chose à voir avec les alias de pointeur?
Yves Daoust
3
D'un point de vue plus sémantique, «l'optimisation prématurée» s'applique uniquement à l'optimisation prématurée, c'est-à-dire avant que le profilage ne l'ait trouvé problématique. Dans ce cas, vous avez diligemment profilé et décompilé et trouvé la source d'un problème et formulé et profilé une solution. Il n'est absolument pas «prématuré» d'appliquer cette solution.
raptortech97

Réponses:

107

Le crénelage du pointeur semble être le problème, ironiquement entre thiset this->target. Le compilateur prend en compte la possibilité plutôt obscène que vous avez initialisé:

this->target = &this

Dans ce cas, écrire à this->target[0]modifierait le contenu de this(et donc, this->target).

Le problème d'alias de mémoire n'est pas limité à ce qui précède. En principe, toute utilisation d' this->target[XX]une valeur (in) appropriée de donnée XXpourrait indiquer this.

Je connais mieux le C, où cela peut être résolu en déclarant des variables de pointeur avec le __restrict__mot - clé.

Peter Boncz
la source
18
Je peux le confirmer! Changer targetde uint8_tà uint16_t(pour que les règles strictes d'aliasing entrent en vigueur) l'a changé. Avec uint16_t, la charge est toujours optimisée.
gexicide
1
Pertinentes: stackoverflow.com/questions/16138237/…
user541686
3
Changer le contenu de thisn'est pas ce que vous voulez dire (ce n'est pas une variable); vous voulez dire changer le contenu de *this.
Marc van Leeuwen
L'esprit @gexicide explique comment l'alias strict entre en jeu et résout le problème?
HCSF
33

Des règles char*d'alias strictes permettent d'aliaser n'importe quel autre pointeur. Ainsi this->targetpeut alias avec this, et dans votre méthode de code, la première partie du code,

target[0] = t & 0x7;
target[1] = (t >> 3) & 0x7;
target[2] = (t >> 6) & 0x7;

est en fait

this->target[0] = t & 0x7;
this->target[1] = (t >> 3) & 0x7;
this->target[2] = (t >> 6) & 0x7;

qui thispeuvent être modifiés lorsque vous modifiez le this->targetcontenu.

Une fois this->targetmis en cache dans une variable locale, l'alias n'est plus possible avec la variable locale.

Jarod42
la source
1
Alors, pouvons-nous dire en règle générale: chaque fois que vous avez un char*ou void*dans votre struct, assurez-vous de le mettre en cache dans une variable locale avant d'y écrire?
gexicide
5
En fait, c'est lorsque vous utilisez un char*, pas nécessaire en tant que membre.
Jarod42
24

Le problème ici est l'alias strict qui dit que nous sommes autorisés à créer un alias via un char * et qui empêche l'optimisation du compilateur dans votre cas. Nous ne sommes pas autorisés à créer un alias via un pointeur d'un type différent qui serait un comportement indéfini, normalement sur SO, nous voyons ce problème qui est que les utilisateurs tentent d' alias via des types de pointeurs incompatibles .

Il semblerait raisonnable d'implémenter uint8_t en tant que caractère non signé et si nous regardons cstdint sur Coliru, il inclut stdint.h qui typedefs uint8_t comme suit:

typedef unsigned char       uint8_t;

si vous avez utilisé un autre type non-char, le compilateur devrait pouvoir optimiser.

Ceci est couvert dans le projet de section standard C ++ 3.10 Lvalues ​​and rvalues qui dit:

Si un programme tente d'accéder à la valeur stockée d'un objet via une valeur de glissement autre que l'un des types suivants, le comportement n'est pas défini

et comprend la puce suivante:

  • un type char ou char non signé.

Remarque, j'ai publié un commentaire sur les solutions possibles dans une question qui demande: Quand uint8_t est-il un caractère non signé? et la recommandation était:

Cependant, la solution de contournement triviale consiste à utiliser le mot-clé restrict ou à copier le pointeur vers une variable locale dont l'adresse n'est jamais prise afin que le compilateur n'ait pas à se soucier de savoir si les objets uint8_t peuvent l'aliaser.

Puisque C ++ ne supporte pas le mot-clé restrict, vous devez vous fier à l'extension du compilateur, par exemple gcc utilise __restrict__ donc ce n'est pas totalement portable, mais l'autre suggestion devrait l'être.

Shafik Yaghmour
la source
Ceci est un exemple d'endroit où le Standard est pire pour les optimiseurs qu'une règle permettrait à un compilateur de supposer qu'entre deux accès à un objet de type T, ou un tel accès et le début ou la fin d'une boucle / fonction où cela se produit, tous les accès au stockage utiliseront le même objet à moins qu'une opération intervenante n'utilise cet objet (ou un pointeur / référence vers celui-ci) pour dériver un pointeur ou une référence à un autre objet . Une telle règle éliminerait le besoin de "l'exception de type caractère" qui peut tuer les performances du code qui fonctionne avec des séquences d'octets.
supercat