Aujourd'hui, nous mesurerons les performances des différentes implémentations de la fonction toupper, car c'est ce qu'elles font le mardi.
En fait, je ne me soucie pas de la fonction
toupper , je viens d'écrire un autre post récemment et j'avais besoin d'une sorte de trame commune, et
toupper semble être un candidat assez intéressant et inoffensif pour les benchmarks. J'ai essayé de choisir quelque chose d'aussi simple que possible qui ne me laisserait pas de côté, mais il se trouve que dans ce test, j'ai rencontré un problème étrange.
Ce message sera petit - un article plus complet sur le sujet original, peut-être plus intéressant, devrait être publié prochainement. Si vous souhaitez reproduire les résultats avec moi, vous
pouvez prendre le code source
sur github .
Ainsi, nous considérerons trois implémentations de la fonction
toupper , qui traduit les caractères majuscules d'un tableau composé d'éléments de type
char , à savoir, il prend un tableau en argument et modifie directement ses éléments afin que toutes les lettres minuscules soient capitalisées.
Dans la première implémentation, nous appelons simplement
la fonction toupper [1]
de la bibliothèque standard C et exécutons une boucle de style C:
void toupper_rawloop(char* buf, size_t size) { for (size_t i = 0; i < size; i++) { buf[i] = toupper(buf[i]); } }
Dans la deuxième implémentation, nous utilisons une approche
plus moderne en remplaçant le cycle brut par
std :: transform :
void toupper_transform(char* buf, size_t size) { std::transform(buf, buf + size, buf, ::toupper); }
Enfin, dans la troisième implémentation, nous utilisons un algorithme spécial qui fonctionne avec des caractères ASCII. Il vérifie si le caractère se situe dans la plage
a - z , et en cas de succès, substitue la même lettre en majuscule, en soustrayant le nombre 32 du code de caractère [2]:
void toupper_branch(char* buf, size_t size) { for (size_t i = 0; i < size; i++) { char c = buf[i]; if (c >= 'a' && c <= 'z') { buf[i] = c - 32; } } }
Ça a l'air facile, non?
Maintenant, nous allons mesurer la vitesse de ces implémentations sur mon ordinateur portable avec le processeur Skylake i7-6700HQ sur le compilateur gcc 5.5 avec les paramètres par défaut. Les résultats sont donnés sous forme de diagramme de dispersion [3]:
Nous traiterons immédiatement trois questions qui ne sont pas pertinentes pour notre tâche.
Tout d'abord, regardez le graphique de l'algorithme de branchement (montré en vert). Il varie considérablement en fonction de la taille des données d'entrée - les deux autres graphiques restent presque plats. Ce n'est en fait qu'un artefact de test. Les caractères ASCII d'entrée sont sélectionnés au hasard [4], par conséquent, le facteur décisif dans le cas de la troisième implémentation est le fonctionnement de l'algorithme de prédiction de branche. Avec une petite quantité de données, il mémorise complètement la séquence des éléments au fur et à mesure que l'itération est effectuée, donc le nombre de ratés est petit et la vitesse est élevée,
comme indiqué dans cette note . À mesure que la taille de la séquence de données augmente, l'algorithme de prédiction se souvient de moins en moins jusqu'à ce qu'il commence enfin à manquer avec chaque lettre majuscule (0,27 manque par caractère), puis le graphique est nivelé.
Deuxièmement, faites attention au groupe de taches vertes en haut à gauche, correspondant à des vitesses beaucoup plus faibles de la variante avec ramification
toupper_branch :
Ce n'est pas un artefact isolé: ces taches sont apparues lors de plusieurs lancements. En même temps, ils ne peuvent pas être reproduits si vous testez l'algorithme uniquement sur ces tailles de données - ils n'apparaissent que lorsque le test est exécuté sur toutes les tailles. Mais dans ce cas, ils n'apparaissent pas toujours. Je ne l'ai pas particulièrement exploré, mais je peux supposer que cela est dû à certains conflits de noms ou d'alias dans l'algorithme de prédiction de branche ou lors du mappage de pages physiques de 4 Ko de mémoire en virtuel (bien que la randomisation de l'espace d'adressage virtuel ait été désactivée).
Troisièmement, l'implémentation de
toupper_rawloop (représentée en bleu) sur le graphique ressemble à deux lignes distinctes: l'une légèrement au-dessus de la marque de 2 mesures par caractère, et l'autre au niveau de 1,5 mesure par caractère. Ces deux lignes sont apparues dans tous les testeurs. L'option plus rapide, avec une vitesse de 1,57 caractères par cycle, ralentit en fait sur les ports de téléchargement: la lecture des données sur les ports 2 et 3 se produit à une vitesse de 1,54 micro-opérations par cycle, elles seront donc occupées à 98%. Je n'ai pas pu établir la raison du «régime» plus lent.
Pendant que je traitais de cette question, le «régime» rapide a soudainement disparu et seul le lent est resté. Peut-être que le processeur a réalisé ce que j'essayais de faire et a secrètement téléchargé la mise à jour du microcode pour supprimer la contradiction, mais j'ai (toujours) la preuve - une image vectorielle avec des graphiques.
Qu'est-ce qui nous intéresse alors dans cet exemple?
Mais ce qui nous intéresse, c'est que la version avec un cycle brut est 3-4 fois plus rapide que la version avec
std :: transform : 1,5-2 cycles par caractère contre 7 avec quelques cycles par caractère.
Quelle est la question ici? Les algorithmes standard m'ont-ils échoué? Est-ce que
std :: transform a un défaut?
Pas vraiment. Plus précisément, pas du tout.
Il s'avère que de tels résultats apparaissent lorsque les fonctions sont compilées dans
différents fichiers . Si vous les mettez dans le même fichier, leurs performances deviennent également faibles.
Et non, l'alignement n'a rien à voir avec cela.
Mais ce n'est pas tout: la version rapide avec un cycle brut, lorsqu'elle est compilée dans un fichier séparé, ralentit si vous y attachez simplement le fichier d'en-tête
<algorithm> . Oui, c'est vrai: connectez simplement ce fichier, qui n'est jamais utilisé et ne génère aucun code dans le fichier objet final, et la vitesse du cycle «brut» chutera 3-4 fois. Au contraire, la version avec
std :: transform est accélérée à la limite si vous copiez et collez l'implémentation de
std :: transform à partir du fichier
<algorithm> , mais n'incluez pas ce fichier.
Les bizarreries ne s'arrêtent pas là (il n'y en aura plus, je vous le promets): l'inclusion du fichier
<algorithme> ne conduit pas toujours à l'effet décrit. Une baisse de vitesse se produit si
<algorithme> est connecté avant
<ctype.h> , mais si vous les
échangez , alors non:
Code lent: #include <algorithm> #include <ctype.h>
Code rapide: #include <ctype.h> #include <algorithm>
En fait, cette anomalie est apparue en moi (dans un autre projet) lorsque clang-format a automatiquement trié les fichiers d'en-tête inclus et placé l'
algorithme au tout début de la liste, où il appartient (d'où l'en-tête clickbait de l'article).
Naturellement, nous avons dû nous plonger tôt ou tard dans la liste des assembleurs. Nous ne retarderons pas ce moment désagréable.
Les versions
rapides et lentes des fonctions [5] sont illustrées ci-dessous, de petites boucles sont fournies avec des annotations:
<algorithme> se connecte en premier: toupper_rawloop(char*, unsigned long): push rbp push rbx lea rbp, [rdi+rsi] sub rsp, 8 test rsi, rsi je .L1 mov rbx, rdi .L5: movsx edi, BYTE PTR [rbx] ; char- *buf add rbx, 1 ; buf++ call toupper ; toupper(c) mov BYTE PTR [rbx-1], al ; buf[-1] cmp rbp, rbx ; buf == buf_end jne .L5 ; .L1: add rsp, 8 pop rbx pop rbp ret
<algorithme> est connecté en second: toupper_rawloop(char*, unsigned long): test rsi, rsi je .L7 push rbp push rbx mov rbp, rsi mov rbx, rdi sub rsp, 8 call __ctype_toupper_loc lea rsi, [rbx+rbp] mov rdi, rbx .L4: ; char- buf movsx rcx, BYTE PTR [rdi] ; toupper ; ( __ctype_toupper_loc) mov rdx, QWORD PTR [rax] ; buf++ add rdi, 1 ; toupper , ; mov edx, DWORD PTR [rdx+rcx*4] mov BYTE PTR [rdi-1], dl ; cmp rsi, rdi ; buf == end_buf jne .L4 ; add rsp, 8 pop rbx pop rbp .L7: rep ret
La principale différence est que dans la version lente, la fonction toupper est simplement appelée en boucle, tandis que dans la version rapide, les appels de fonction sont complètement absents, et il n'y a qu'une recherche dans la table de correspondance [6], c'est-à-dire le corps de la fonction
std :: toupper est substitué à l'endroit de l'appel.
Si vous regardez le
code source de la bibliothèque glibc, on y trouve l'implémentation de la fonction
toupper :
__extern_inline int
Comme nous pouvons le voir,
toupper est défini comme une fonction
externe en ligne qui vérifie d'abord que la taille du caractère char tient dans un octet [7], puis recherche le caractère dans la table de correspondance retournée par la fonction
__ctype_toupper_loc () . Cette fonction renvoie un pointeur de flux local (de type
const int ** ), qui, à son tour, pointe vers une table de correspondance, à partir de laquelle, en réponse à une demande de notre symbole, sa version majuscule est retournée [8].
Maintenant, il est clair ce qui se passe dans la fiche. Dans la version rapide de l'algorithme, le compilateur remplace le corps de la fonction
toupper , mais ne peut pas remplacer l'appel à la fonction
__ctype_toupper_loc () [9]. Cet appel, cependant, est déclaré comme
__attribute __ ((const)) , ce qui signifie que la valeur de retour dépend uniquement des arguments (qui ne sont pas ici). Le compilateur sait que cette fonction renvoie la même valeur à chaque fois, et prend donc son appel en dehors de la boucle, et dans la boucle elle-même il n'y a que quelques opérations de lecture associées à l'accès à la table de correspondance, à l'écriture d'une nouvelle valeur dans le tampon et au contrôle de la boucle.
Dans la version lente, l'appel à
toupper () reste dans le corps de la boucle. La boucle elle-même est plus courte d'une commande, mais, bien sûr, vous devez maintenant exécuter tout le code à l'intérieur de la fonction
toupper . Sur mon système, cela ressemble à ceci:
lea edx,[rdi+0x80] ; edx = rdi + 0x80 movsxd rax,edi ; c cmp edx,0x17f ; , c -128 255 ja 2a ; , mov rdx,QWORD PTR [rip+0x395f30] ; ; mov rdx,QWORD PTR fs:[rdx] ; ; mov rdx,QWORD PTR [rdx] ; ; mov rdx,QWORD PTR [rdx+0x48] ; toupper mov eax,DWORD PTR [rdx+rax*4+0x200] ; c 2a: ret
Comme il s'agit d'un appel non intégré, le programme fait plus de travail. Il y a au moins cinq opérations consécutives d'accès à la mémoire (la soi-disant poursuite des pointeurs, la poursuite du pointeur). Dans la version rapide, il n'en reste que deux, puisque tous les autres sont retirés de la boucle. Le délai entre l'appel d'une fonction et sa sortie devrait être d'environ 25 cycles, et nous avons environ 7 cycles qui sortent - cela signifie que le processeur a pu paralléliser l'appel, ce qui est assez bien, compte tenu des circonstances.
Pourquoi en est-il ainsi?
Dans une longue chaîne de fichiers d'inclusion, les fichiers d'en-tête C ++, tels que
<algorithm> , incluent à leur tour le fichier
<bits / os_defines.h> , qui contient la ligne suivante:
Lorsque le fichier
<ctype.h> est enfin connecté, à cause de cette directive, le code dans lequel
toupper est défini comme
externe en ligne ne peut pas être inclus:
#if !defined __NO_CTYPE # ifdef __isctype_f __isctype_f (alnum)
Veuillez noter que lors de la connexion de
<ctype.h>, la version C ++ de
toupper n'est jamais définie en tant que macro - au maximum en tant que
ligne externe - car les définitions des macros sont protégées par la
vérification! Defined __cplusplus et ne prendront donc jamais effet.
En général, je ne sais pas avec certitude si
__NO_CTYPE dans ce cas devrait exclure les corps des fonctions
tolower et
toupper déclarées comme
externes en ligne , mais c'est exactement ce qui se passe - et donc une baisse significative de la vitesse de notre cycle. En conclusion, je peux dire que si vous incluez
<cctype> au lieu de
<ctype.h> (c'est-à-dire que C ++ est la version du fichier d'en-tête C qui place les fonctions dans l'
espace de noms std ::) , alors dans ce cas, le code fonctionnera lentement car
<cctype> inclut finalement
<bits / os_defines.h> .
Est-ce que c'est si important? Non, non.
La fonction
toupper ne convient pas pour un travail sérieux avec des caractères de différentes langues, donc si vous avez besoin de traiter uniquement des caractères ASCII, vous pouvez écrire votre propre implémentation plus rapide. Si vous avez besoin de travailler sérieusement avec du texte, vous utiliserez très probablement UTF-8 et devrez utiliser une sorte d'ICU pour prendre en charge les paramètres régionaux, ou attendre que la prise en charge Unicode apparaisse en C ++ (cela peut prendre un certain temps) . Ainsi, la déclaration «le format de clang peut entraîner une baisse de performance de 4x» ne convient que comme en-tête de clickbait.
Cet effet est-il observé dans toutes les versions de libc? Oui, dans presque tous, mais même ici ce n’est pas si simple.
Les résultats ci-dessus sont valables pour gcc 5.5 et glibc 2.23, car j'ai utilisé ces versions, mais quelque chose de nouveau se produit dans les nouvelles versions (à partir de la glibc 2.27 environ). Là, l'activation de
<algorithm> avant
<ctype.h> donne toujours le même effet, mais maintenant
<stdlib.h> [10] crée également des problèmes: si vous l'activez avant
<ctype.h> , les performances chutent également, ce qui n'est pas observé dans les versions antérieures. De toute évidence, dans les versions plus récentes, le fichier
<stdlib.h> contient également la définition
__NO_CTYPE . Au moins, maintenant, il ne sera pas possible de blâmer le format clang pour le tri - ici, cela peut simplement aider à résoudre le problème (s'il n'y a pas d'autres fichiers problématiques dans la liste des fichiers connectés).
J'ai publié
un rapport de bogue dans libc , il est donc probable que ce bogue sera corrigé, mais il ne fait aucun doute que les erreurs liées à l'ordre dans lequel les fichiers d'en-tête sont connectés nous importuneront davantage.
Commentaires
Je n'ai pas de système de commentaires sur mon site, mais j'y travaille (c'est-à-dire en pleurant périodiquement qu'il est difficile de faire des commentaires sur un site statique).
En attendant, vous pouvez discuter de cet article sur le site Web de
Hacker News ou
lobste.rs .
Remerciements
Merci à l'utilisateur ufo de Hacker News, qui a
souligné qu'il n'est pas nécessaire d'utiliser la fonction lambda pour adapter
std :: toupper pour une utilisation dans
std :: transform , et aussi à Jonathan Muller qui a
expliqué que la fonction lambda est toujours nécessaire.
- Oui, la fonction toupper (3) du fichier d'en-tête <ctype.h> ne convient pas pour travailler avec la plupart des caractères non ASCII, car ne peut pas gérer des caractères supérieurs à un octet, mais il convient à notre tâche, car nous ne lui passerons que des chaînes de caractères ASCII.
- Dans le tableau ASCII, les caractères minuscules et majuscules sont très bien situés - à une distance de 32 positions l'un de l'autre, ce qui signifie que vous pouvez transférer des caractères d'un cas à l'autre simplement en soustrayant ou en ajoutant 32. En général, si nous savions avec certitude que toutes les entrées les données sont des lettres ASCII, nous pourrions réinitialiser le 5ème bit sans aucune vérification (par exemple, c & 0b11011111 ) afin de transformer n'importe quelle lettre majuscule en minuscule, alors que cela ne se refléterait pas dans les lettres minuscules. Mais nous ne le savons probablement pas, nous devons donc vérifier si le caractère est une lettre, afin de ne pas casser accidentellement des caractères non-lettre comme char .
- Cela devrait être appelé un nuage de points avec l'ajout de «bruit» à l'emplacement des points. En fait, il s'agit d'un diagramme de dispersion ordinaire dans lequel le paramètre qui nous intéresse (la taille des données d'entrée) est tracé sur l'axe des x, et la vitesse de travail est sur l'axe des y (mesures par symbole - plus la valeur est basse, plus la vitesse est élevée ). La principale caractéristique de ce diagramme est que pour chaque valeur de paramètre sur l'axe x, l'échantillonnage est effectué plusieurs fois: dans ce cas, le test est répété 10 fois pour chaque taille de réseau.
- À savoir, les caractères sont sélectionnés de manière aléatoire et uniforme dans la plage [32, 127], de sorte que la condition dans la fonction sera vraie dans environ 27% des cas.
- Les deux listes font référence à une implémentation de cycle brut et diffèrent uniquement dans l'ordre dans lequel les fichiers <algorithm> et <ctype.h> sont inclus . Le code source généré est le même pour toutes les implémentations - à la fois dans les versions rapides et lentes. Par exemple, une implémentation avec std :: transform produira le même code d'assembleur lent si vous incluez le fichier <algorithm> et le même code rapide si vous copiez uniquement la définition de fonction et n'incluez pas le fichier.
- Cependant, cette boucle rapide est plus lente qu'elle ne le pourrait car le pointeur vers la table de correspondance est lu trop de fois ( mov rdx, QWORD PTR [rax] ) à l'intérieur de la boucle. Ce pointeur peut être différent selon les paramètres régionaux, mais il n'est pas mis à jour pendant l'exécution du cycle et peut donc être déplacé en dehors du cycle. Il doit être que le compilateur pense qu'il n'y a pas assez de raisons à cela, puisque nous écrivons dans un tableau d'éléments de type char , et ils peuvent en principe être utilisés comme alias pour [rax] ie pointeur vers la table. Quoi qu'il en soit, même __restrict__ n'aidera pas ici. Mais dans une autre version de la boucle, où des valeurs plus strictes sont simplement ajoutées et rien n'est écrit dans le tableau, cette optimisation est appliquée - le pointeur est lu en dehors de la boucle.
- Cette vérification n'est pas reflétée dans le code assembleur substituable, car le compilateur sait déjà que les valeurs char sont toujours dans la plage [-128, 255] . La vérification n'est nécessaire que parce que l'API de la fonction toupper © accepte une valeur de type int plutôt que char , afin que l'utilisateur puisse lui transmettre tout nombre familier de type int , tandis que les tables de correspondance sont conçues uniquement pour les valeurs de type char , de sorte que la vérification permet d'éviter de lire en dehors du tampon .
- Soit dit en passant, cela explique pourquoi les procédures std :: toupper sont indépendantes de la taille des données d'entrée: elles n'utilisent pas de branches (sauf pour les vérifications de plage, qui sont remarquablement prédites), mais utilisent une table de correspondance indépendante des branches. ↵
- La substitution de cet appel ne fonctionnera pas même avec un désir très fort: le corps de la fonction n'est pas disponible dans le fichier d'en-tête.
- Je ne trouve aucunement défaut avec stdlib.h (ou <algorithme> , d'ailleurs) - il est fort possible que de nombreux autres fichiers d'en-tête C et tous les fichiers d'en-tête C ++ provoquent également ce comportement, je ne les ai tout simplement pas testés. J'ai connecté stdlib.h juste pour déterminer size_t .
Remarque Cet article a d'abord été publié sur le site Web
Performance Matters . Les articles traduits sont publiés ici avec la permission de l'auteur.