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 right
suivi d'un and
, puis d'un store
dans le target
tampon. 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 load
de la mémoire avant chaque shift ( mov rdx,QWORD PTR [rdi]
). Il semble que le target
pointeur (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é target
dans 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-19ubuntu1
avec -O3
optimisation. J'ai également essayé clang++ 3.4-1ubuntu3
avec des résultats similaires: Clang est même capable de vectoriser la méthode avec le target
pointeur local . Cependant, l'utilisation du this->target
pointeur 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 this
doit 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.
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.Réponses:
Le crénelage du pointeur semble être le problème, ironiquement entre
this
etthis->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 dethis
(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éeXX
pourrait indiquerthis
.Je connais mieux le C, où cela peut être résolu en déclarant des variables de pointeur avec le
__restrict__
mot - clé.la source
target
deuint8_t
àuint16_t
(pour que les règles strictes d'aliasing entrent en vigueur) l'a changé. Avecuint16_t
, la charge est toujours optimisée.this
n'est pas ce que vous voulez dire (ce n'est pas une variable); vous voulez dire changer le contenu de*this
.Des règles
char*
d'alias strictes permettent d'aliaser n'importe quel autre pointeur. Ainsithis->target
peut alias avecthis
, et dans votre méthode de code, la première partie du code,est en fait
qui
this
peuvent être modifiés lorsque vous modifiez lethis->target
contenu.Une fois
this->target
mis en cache dans une variable locale, l'alias n'est plus possible avec la variable locale.la source
char*
ouvoid*
dans votre struct, assurez-vous de le mettre en cache dans une variable locale avant d'y écrire?char*
, pas nécessaire en tant que membre.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:
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:et comprend la puce suivante:
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:
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.
la source