Dans quel cas l'incrément des éléments
std :: vector sera-t-il plus rapide - s'ils sont de type
uint8_t ou
uint32_t ?
Afin de ne pas raisonner abstraitement, nous considérons deux implémentations spécifiques:
void vector8_inc(std::vector<uint8_t>& v) { for (size_t i = 0; i < v.size(); i++) { v[i]++; } } void vector32_inc(std::vector<uint32_t>& v) { for (size_t i = 0; i < v.size(); i++) { v[i]++; } }
Essayons de deviner
Il est facile de répondre à cette question en utilisant le benchmark, et un peu plus tard nous le ferons, mais d'abord nous essaierons de deviner (cela s'appelle "un raisonnement basé sur des principes de base" - cela semble plus scientifique).
Tout d’abord, il vaut la peine de se poser une question:
quelle est la taille de ces vecteurs ?
Eh bien, choisissons un certain nombre. Soit 20 000 éléments dans chacun.
De plus, il est connu que nous testerons le processeur Intel Skylake - nous verrons les caractéristiques des commandes d'addition pour
les opérandes
8 bits et
32 bits avec adressage direct. Il s'avère que leurs principaux indicateurs sont les mêmes: 1 opération par cycle et un retard de 4 cycles par accès mémoire (1). Dans ce cas, le retard n'a pas d'importance, car chaque opération d'addition est effectuée indépendamment, de sorte que la vitesse calculée est de 1 élément par cycle, à condition que tout le reste du travail sur la boucle soit effectué en parallèle.
Vous pouvez également remarquer que 20 000 éléments correspondent à un ensemble de données de 20 Ko pour la version avec
uint8_t et jusqu'à 80 Ko pour la version avec
uint32_t . Dans le premier cas, ils s'intègrent idéalement dans le cache de niveau L1 des ordinateurs modernes basés sur x86, et dans le second - pas. Il s'avère que la version 8 bits aura une longueur d'avance grâce à une mise en cache efficace?
Enfin, nous constatons que notre tâche est très similaire au cas classique de
la vectorisation automatique : dans une boucle avec un nombre connu d'itérations, une opération arithmétique est effectuée sur des éléments situés séquentiellement en mémoire. Dans ce cas, la version 8 bits devrait avoir un énorme avantage sur la version 32 bits, car une opération vectorielle traitera quatre fois plus d'éléments et, en général, les processeurs Intel effectuent des opérations vectorielles sur des éléments à un octet à la même vitesse que sur 32. éléments de bits.
D'accord, arrêtez de pester. Il est temps de passer au test.
Benchmark
J'ai obtenu les timings suivants pour des vecteurs de 20 000 éléments sur des
compilateurs gcc 8 et
clang 8 avec différents niveaux d'optimisation:
Il s'avère que, à l'exception du niveau
-O1 , la version avec
uint32_t est plus rapide que la version avec
uint8_t , et dans certains cas, elle est significative: 5,4 fois sur gcc au niveau
-O3 et exactement 8 fois sur clang aux deux niveaux,
-O2 et
- O3 . Oui, l'incrément des entiers 32 bits dans
std :: vector est jusqu'à huit fois plus rapide que l'incrément des entiers 8 bits sur le compilateur populaire avec des paramètres d'optimisation standard.
Comme d'habitude, tournons-nous vers la liste des assembleurs dans l'espoir qu'elle éclairera ce qui se passe.
Voici une liste pour gcc 8 au niveau
-O2 , où la version 8 bits est "seulement" 1,5 fois plus lente que la version 32 bits (2):
8 bits: .L3: inc BYTE PTR [rdx+rax] mov rdx, QWORD PTR [rdi] inc rax mov rcx, QWORD PTR [rdi+8] sub rcx, rdx cmp rax, rcx jb .L3
32 bits: .L9: inc DWORD PTR [rax] add rax, 4 cmp rax, rdx jne .L9
La version 32 bits ressemble exactement à ce que nous attendions d'une boucle non développée (3): un incrément (4) avec une adresse, puis trois commandes de contrôle de boucle:
ajouter rax ,
4 - un incrément de la variable inductive (5) et quelques commandes
cmp et
jne pour vérifier les conditions de sortie de la boucle et de saut conditionnel dessus Tout a l'air génial - le déploiement compenserait le coût de l'incrémentation du compteur et de la vérification de la condition, et notre code atteindrait presque la vitesse maximale possible de 1 élément par cycle d'horloge (6), mais pour une application open source, cela suffira. Et qu'en est-il de la version 8 bits? En plus de la commande
inc avec l'adresse, deux commandes supplémentaires pour lire dans la mémoire sont exécutées, ainsi que la
sous- commande, qui est prise de nulle part.
Voici une liste avec des commentaires:
8 bits: .L3: inc BYTE PTR [rdx+rax] ; v[i] mov rdx, QWORD PTR [rdi] ; v.begin inc rax ; i++ mov rcx, QWORD PTR [rdi+8] ; v.end sub rcx, rdx ; end - start (.. vector.size()) cmp rax, rcx ; i < size() jb .L3 ; . i < size()
Ici
vector :: begin et
vector :: end sont les pointeurs internes de
std :: vector , qu'il utilise pour indiquer le début et la fin de la séquence d'éléments contenus dans la zone sélectionnée pour lui (7), ce sont essentiellement les mêmes valeurs qui sont utilisés pour implémenter
vector :: begin () et
vector :: end () (bien qu'ils soient d'un type différent). Il s'avère que toutes les commandes supplémentaires ne sont qu'une conséquence du calcul de
vector.size () . Cela ne semble pas inhabituel? Mais après tout, dans la version 32 bits, bien sûr,
size () est également calculé, cependant, ces commandes n'étaient pas dans cette liste. Le calcul de
size () ne s'est produit qu'une seule fois - en dehors de la boucle.
Alors, quel est le problème? La réponse courte est l'
alias de pointeur . Je donnerai une réponse détaillée ci-dessous.
Réponse détaillée
Le vecteur
v est transmis à la fonction par référence, qui est en fait un pointeur masqué. Le compilateur doit aller aux membres
v :: begin et
v :: end du vecteur pour calculer sa taille
size () , et dans notre exemple,
size () est calculé
à chaque itération. Mais le compilateur n'est pas obligé d'obéir aveuglément au code source: il peut très bien porter le résultat de l'appel de la fonction
size () en dehors de la boucle, mais seulement s'il sait avec certitude que la sémantique du programme
ne changera pas . De ce point de vue, le seul endroit problématique dans la boucle est l'incrément
v [i] ++ . L'enregistrement a lieu à une adresse inconnue. Une telle opération peut-elle changer la valeur de size ()?
Si l'enregistrement se produit dans
std :: vector <uint32_t> (c'est-à-dire par le pointeur
uint32_t * ), alors non, il ne peut pas modifier la valeur
size () . L'écriture dans des objets de type
uint32_t ne peut modifier que des objets de type
uint32_t , et les pointeurs impliqués dans le calcul de
size () ont un type différent (8).
Cependant, dans le cas de
uint8_t , au moins sur les compilateurs populaires (9), la réponse sera la suivante: oui, théoriquement, la valeur de
size () peut changer , car
uint8_t est un alias pour le caractère
non signé , et les tableaux du type
char non signé (et
char ) peuvent
Alias avec tout autre type . Cela signifie que, selon le compilateur, l'écriture sur des
pointeurs uint8_t peut modifier le contenu de la mémoire d'origine inconnue à n'importe quelle adresse (10). Par conséquent, il suppose que chaque opération d'incrémentation
v [i] ++ peut modifier la valeur
size () et est donc obligé de la recalculer à chaque itération de la boucle.
Nous savons tous que l'écriture dans la mémoire pointée par
std :: vector ne changera jamais sa propre
taille () , car cela signifierait que le vecteur lui-même a été en quelque sorte alloué dans son propre tas, et c'est pratiquement impossible et s'apparente au problème du poulet et des œufs (11). Mais malheureusement, cela n'est pas connu du compilateur!
Qu'en est-il du reste des résultats?
Eh bien, nous avons découvert pourquoi la version avec
uint8_ est légèrement plus lente que la version de
uint32_t sur gcc au niveau
-O2 . Mais pourquoi expliquer l'énorme différence - jusqu'à 8 fois - sur clang ou le même gcc sur
-O3 ?
Tout est simple ici: dans le cas de
uint32_t, clang peut effectuer une auto-vectorisation de boucle:
.LBB1_6: ; =>This Inner Loop Header: Depth=1 vmovdqu ymm1, ymmword ptr [rax + 4*rdi] vmovdqu ymm2, ymmword ptr [rax + 4*rdi + 32] vmovdqu ymm3, ymmword ptr [rax + 4*rdi + 64] vmovdqu ymm4, ymmword ptr [rax + 4*rdi + 96] vpsubd ymm1, ymm1, ymm0 vpsubd ymm2, ymm2, ymm0 vpsubd ymm3, ymm3, ymm0 vpsubd ymm4, ymm4, ymm0 vmovdqu ymmword ptr [rax + 4*rdi], ymm1 vmovdqu ymmword ptr [rax + 4*rdi + 32], ymm2 vmovdqu ymmword ptr [rax + 4*rdi + 64], ymm3 vmovdqu ymmword ptr [rax + 4*rdi + 96], ymm4 vmovdqu ymm1, ymmword ptr [rax + 4*rdi + 128] vmovdqu ymm2, ymmword ptr [rax + 4*rdi + 160] vmovdqu ymm3, ymmword ptr [rax + 4*rdi + 192] vmovdqu ymm4, ymmword ptr [rax + 4*rdi + 224] vpsubd ymm1, ymm1, ymm0 vpsubd ymm2, ymm2, ymm0 vpsubd ymm3, ymm3, ymm0 vpsubd ymm4, ymm4, ymm0 vmovdqu ymmword ptr [rax + 4*rdi + 128], ymm1 vmovdqu ymmword ptr [rax + 4*rdi + 160], ymm2 vmovdqu ymmword ptr [rax + 4*rdi + 192], ymm3 vmovdqu ymmword ptr [rax + 4*rdi + 224], ymm4 add rdi, 64 add rsi, 2 jne .LBB1_6
Le cycle a été déployé 8 fois, et c'est en général la performance maximale que vous pouvez obtenir: un vecteur (8 éléments) par cycle d'horloge pour le cache L1 (cela ne fonctionnera plus en raison de la limitation d'une opération d'écriture par cycle d'horloge (12)).
La vectorisation n'est pas effectuée pour
uint8_t , car elle est gênée par la nécessité de calculer
size () pour vérifier l'état de la boucle à chaque itération. La raison du décalage est toujours la même, mais le décalage lui-même est beaucoup plus important.
Les timings les plus bas sont expliqués par la vectorisation automatique: gcc ne l'applique qu'au niveau
-O3 , et clang s'applique aux niveaux
-O2 et
-O3 par défaut. Le compilateur gcc de niveau -cc génère un code légèrement plus lent que clang car il ne développe pas la boucle autovectorisée.
Corriger la situation
Nous avons découvert quel est le problème - comment pouvons-nous le résoudre?
Tout d'abord, essayons une façon qui ne fonctionnera pas, à savoir, nous allons écrire un cycle plus idiomatique basé sur un itérateur:
for (auto i = v.begin(); i != v.end(); ++i) { (*i)++; }
Le code que
gcc génère au niveau
-O2 sera légèrement meilleur que l'option avec
size () :
.L17: add BYTE PTR [rax], 1 add rax, 1 cmp QWORD PTR [rdi+8], rax jne .L17
Deux opérations de lecture supplémentaires sont devenues une, car nous comparons maintenant avec le pointeur de
fin du vecteur, plutôt que de recalculer
size () , en soustrayant le pointeur de début du vecteur du pointeur de fin. Par le nombre d'instructions, ce code rattrape
uint32_t , car l'opération de lecture supplémentaire a fusionné avec l'opération de comparaison. Cependant, le problème n'a pas disparu et la vectorisation automatique n'est toujours pas disponible, donc
uint8_t est toujours nettement derrière
uint32_t - plus de 5 fois sur gcc et clang aux niveaux où la vectorisation automatique est fournie.
Essayons autre chose. Nous ne réussirons pas à nouveau, ou plutôt, nous trouverons
une autre méthode inopérante.
Dans cette version, nous calculons
size () une seule fois avant la boucle et mettons le résultat dans une variable locale:
for (size_t i = 0, s = v.size(); i < s; i++) { v[i]++; }
Cela semble fonctionner? Le problème était
size () , et maintenant nous avons ordonné au compilateur de valider le résultat de
size () dans la variable locale
s au début de la boucle, et les variables locales, comme vous le savez, ne se croisent pas avec d'autres données. Nous avons fait ce que le compilateur ne pouvait pas faire. Et le code qu'il va générer sera en fait meilleur (par rapport à l'original):
.L9: mov rdx, QWORD PTR [rdi] add BYTE PTR [rdx+rax], 1 add rax, 1 cmp rax, rcx jne .L9
Il n'y a qu'une seule opération de lecture supplémentaire et aucune
sous- commande. Mais que fait cette commande supplémentaire (
rdx, QWORD PTR [rdi] ) si elle n'est pas impliquée dans le calcul de la taille? Il lit le pointeur
data () de
v !
L'expression
v [i] est implémentée en tant que
* (v.data () + i) , et le membre renvoyé par
data () (et, en fait, un pointeur de
début régulier) pose le même problème que
size () . Certes, je n'ai pas remarqué cette opération dans la version originale, car là, elle était "gratuite", car elle devait encore être effectuée pour calculer la taille.
Ours avec un peu plus, nous avons presque trouvé une solution. Il vous suffit de supprimer de notre boucle
toutes les dépendances sur le contenu de
std :: vector . La façon la plus simple de le faire est de modifier un peu notre idiome avec un itérateur:
for (auto i = v.begin(), e = v.end(); i != e; ++i) { (*i)++; }
Maintenant, tout a radicalement changé (ici, nous comparons uniquement les versions avec
uint8_t - dans l'une, nous enregistrons l'itérateur
final dans une variable locale
avant la boucle, dans l'autre - non):
Ce petit changement nous a donné une augmentation de 20 fois la vitesse à des niveaux avec auto-vectorisation. De plus, le code avec
uint8_t n'a pas seulement rattrapé le code avec
uint32_t - il l'a dépassé presque exactement 4 fois par gcc
-O3 et clang
-O2 et
-O3 , comme nous nous y attendions au tout début, en s'appuyant sur la vectorisation: au final, exactement quatre fois plus les éléments peuvent être traités par une opération vectorielle et nous avons besoin de quatre fois moins de bande passante - quel que soit le niveau de cache (13).
Si vous avez lu à cet endroit, alors vous devez vous être exclamé tout ce temps:
Mais qu'en est -il de la boucle for avec traversée de bande introduite en C ++ 11?Je m'empresse de vous faire plaisir: ça marche! En fait, c'est du sucre syntaxique, derrière lequel notre version avec un itérateur se cache presque sous la même forme, où nous avons fixé le pointeur de
fin dans une variable locale avant le début de la boucle. Sa vitesse est donc la même.
Si nous décidions soudainement de revenir aux temps anciens des grottes et d'écrire une fonction de type C, un tel code fonctionnerait tout aussi bien:
void array_inc(uint8_t* a, size_t size) { for (size_t i = 0; i < size; i++) { a[i]++; } }
Ici, le pointeur vers le tableau
a et la
taille de la variable sont passés à la fonction par valeur, ils ne peuvent donc pas être modifiés suite à l'écriture dans le pointeur
a (14) - tout comme les variables locales. Les performances de ce code sont les mêmes que celles des options précédentes.
Enfin, sur les compilateurs où cette option est disponible, vous pouvez déclarer un vecteur avec
__restrict (15):
void vector8_inc_restrict(std::vector<uint8_t>& __restrict v) { for (size_t i = 0; i < v.size(); i++) { v[i]++; } }
Le
mot clé __restrict ne
fait pas partie de la norme C ++, mais fait partie de la norme
C depuis C99 (en tant que
restriction ). S'il est implémenté en tant qu'extension C ++ dans le compilateur, il est très probable qu'il obéira à la sémantique de C. Bien sûr, il n'y a pas de liens en C, vous pouvez donc remplacer mentalement le lien vers le vecteur par un pointeur vers le vecteur.
Notez que restrict n'a pas de
propriété transitive: l'action du spécificateur
__restrict , avec laquelle un lien vers
std :: vector est déclaré, s'applique uniquement aux membres du vecteur lui-même, et non à la région de tas référencée par
v.data () . Dans notre cas, il n'en faut pas plus, car (comme dans le cas des variables locales) il suffit de convaincre le compilateur que les termes eux-mêmes, pointant vers le début et la fin du vecteur, ne se croisent avec rien. La clause sur
restrict , cependant, est toujours pertinente, car l'écriture via
v.data () peut toujours entraîner la modification d'autres objets dans votre fonction en raison d'un alias.
Déception
Nous arrivons ici à la dernière - et très décevante - conclusion. Le fait est que toutes les solutions présentées ci-dessus ne s'appliquent qu'à ce cas spécifique, lorsque le vecteur peut théoriquement interférer avec lui-même. La solution était de sortir de la boucle ou d'isoler le résultat de l'appel de la
taille () ou de la
fin () du vecteur, et de
ne pas dire au compilateur que l'écriture dans les données du vecteur n'affecte pas les autres données. Ce code sera difficile à mettre à l'échelle à mesure que la fonction se développera.
Le problème d'aliasing n'a pas disparu, et les commandes d'écriture peuvent toujours obtenir "n'importe où" - il n'y a tout simplement pas d'autres données dans cette fonction qui peuvent être affectées ... pour l'instant. Dès qu'un nouveau code y apparaîtra, tout sera répété. Voici
un exemple au pied levé . Si vous écrivez dans des tableaux d'éléments de type
uint8_t en petites boucles, vous devez vous battre avec le compilateur jusqu'à la fin (16).
Commentaires
Je serai heureux de toute rétroaction. Je n'ai pas encore de système de commentaires (17), donc, comme d'habitude, nous allons discuter dans
ce fil sur HackerNews .
- En accédant à la mémoire ici, il est entendu que la chaîne de dépendances passe par la mémoire: les commandes d'écriture à la même adresse doivent lire la dernière valeur qui y est écrite, donc ces opérations sont dépendantes (en pratique, la redirection pour le chargement (STLF) sera utilisée si l'enregistrement est suffisant souvent). Les dépendances de la commande add lors de l'accès à la mémoire peuvent se produire par d'autres moyens, par exemple en calculant l'adresse, mais dans notre cas, cela n'est pas pertinent.
- Seul un petit cycle est illustré ici; Le code d'installation est simple et fonctionne rapidement. Pour voir la liste complète, téléchargez le code sur godbolt .
- Peut-être devrait-on l'appeler simplement «minimisé»? Quoi qu'il en soit, le compilateur gcc ne fait généralement pas de boucle, même aux niveaux -O2 et -O3 , sauf dans des cas spéciaux où le nombre d'itérations est petit et connu au stade de la compilation . Pour cette raison, gcc affiche des résultats de test inférieurs à ceux de clang, mais il économise beaucoup sur la taille du code. Vous pouvez forcer gcc à dérouler des boucles en appliquant une optimisation de profil ou en activant l' indicateur -funroll-loops .
- En fait, la commande inc DWORD PTR [rax] dans gcc est une optimisation manquée: il est presque toujours préférable d'utiliser la commande add [rax], 1 , car elle ne comprend que 2 micro-opérations combinées contre 3 pour inc . Dans ce cas, la différence n'est que d'environ 6%, mais si le cycle était légèrement élargi pour que seule l'opération d'enregistrement soit répétée, la différence serait plus importante (une nouvelle expansion ne jouerait plus de rôle, puisque nous atteindrions la limite de 1 opération d'enregistrement par cycle, qui ne dépend pas du nombre total de micro-opérations).
- J'appelle cette variable inductive , et pas seulement i , comme dans le code source, car le compilateur a converti les opérations unitaires de l'incrément i en incréments de 4 octets du pointeur stocké dans le registre rax , et corrigé en conséquence la condition de boucle. Dans sa forme originale, notre boucle adresse les éléments du vecteur, et après cette conversion, elle incrémente le pointeur / itérateur, ce qui est un moyen de réduire le coût des opérations .
- En fait, si vous activez -funroll-loops , sur gcc, la vitesse sera de 1,08 mesure par élément avec un déploiement 8x . Mais même avec ce drapeau, il ne prolongera pas la boucle pour la version avec des éléments 8 bits, donc le décalage de vitesse sera encore plus perceptible!
- Ces membres ont un modificateur privé , et leurs noms dépendent de l'implémentation, mais dans stdlibc ++, ils ne sont pas vraiment appelés début et fin , comme dans gcc. Ils sont appelés _Vector_base :: _ Vector_impl :: _ M_start et _Vector_base :: _ Vector_impl :: _ M_finish respectivement , c'est-à-dire entrez la structure _Vector_impl , qui est membre de _M_impl (et la seule) de la classe _Vector_base , et qui, à son tour, est la classe de base pour std :: vector . Eh bien! Heureusement, le compilateur gère facilement cette pile d'abstractions.
- La norme ne prescrit pas quels devraient être les types internes de membres std :: vector , mais dans la bibliothèque libstdc ++, ils sont simplement définis comme Alloc :: pointer (où Alloc est l'allocateur du vecteur), et pour l' objet std :: allocation par défaut, ils seront simplement pointeurs de type T * , c'est-à-dire pointeurs réguliers vers un objet - dans ce cas uint32_t * .
- Je fais cette réservation pour une raison. On soupçonne que uint8_t peut être considéré comme un type autre que char , char signé et char non signé . Étant donné que l'aliasing fonctionne avec les types de caractères , cela ne s'applique pas en principe à uint8_t et devrait se comporter comme tout autre type sans caractère. Cependant, aucun des compilateurs que je connais ne le pense: dans tous, typedef uint8_t est un alias de caractère non signé , de sorte que les compilateurs ne voient pas la différence entre eux, même s'ils souhaitent l'utiliser.
- Par "origine inconnue", je veux dire ici seulement que le compilateur ne sait pas où le contenu de la mémoire pointe ni comment il est apparu. Cela inclut des pointeurs arbitraires transmis à la fonction, ainsi que des variables globales et statiques. , , , , , ( - ). , malloc new , , , , : , , . , malloc new .
- , std::vector - ? , std::vector<uint8_t> a a.data() placement new b . std::swap(a, b) , – , b ? , b . : - (, ), , .
- 8 , .. 32 . , std::vector .
- - 4 : , , – . : 8- L1, 32- – L2 , .
- , – : . , , «».
- v[i] , .
- . , «» , uint8_t . , , , uint8_t , . , clang, gcc , , uint8_t . - gcc , . , , - __restrict .
- - , , ( Disqus), ( ), .
. : Travis Downs. Incrementing vectors .