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

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.

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

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.

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.