Qt et les chaînes de caractères : améliorer les performances des chaînes avec SIMD... ou pas

Le site Qt Labs permet aux développeurs de Qt de présenter les projets, plus ou moins avancés, sur lesquels ils travaillent.

Nokia, Qt, Qt Quarterly et leurs logos sont des marques déposées de Nokia Corporation en Finlande et/ou dans les autres pays. Les autres marques déposées sont détenues par leurs propriétaires respectifs.

Cet article est la traduction de l'article Improving the string performance with more SIMD (or not) de Thiago Macieira paru dans Qt Labs.

En début d'année, Benjamin codait une version améliorée à l'aide de SSE2 et de Neon de la conversion vers et depuis Latin1 (ISO-8859-1) de QString. Cela est déjà dans la branche Qt 4.7 (commit 60fd302e) et permet d'obtenir des amélirations de 400 % dans la conversion fromLatin1, un peu moins dans l'autre sens, à cause des vérifications nécessaires pour s'assurer que les caractères UTF-16 tiennent bien dans Latin1. L'année dernière, j'ai aussi amélioré la fonction QString::operator==, avec un peu de code de Lars.

C'est pourquoi j'ai décidé de continuer à améliorer.

Pour être clair et pour éviter tout acte de violence à la fin de l'article, je n'ai pu obtenir aucune amélioration, mon code ne sera donc pas ajouté à qstring.cpp. J'ai cependant beaucoup appris. Vous pouvez d'ailleurs voir tout le travail dans la série de commits s'achevant en 9a468f59472e8978aa18b75e9786718a8823bbec.

Ainsi, la première chose que j'ai essayée était de prendre la fonction qMemEquals dans trois formes différentes : comparaison bit à bit (comme memcmp), comparaison par entier court non signé (ushort) et un code adaptatif qui essaie de comparer par lots de 32 bits après l'alignement des données. La dernière correspond à ce que fait qMemEquals dans Qt 4.6 et 4.7.

La chose suivante fut que l'on a besoin d'un set de données réaliste, au lieu de générer des données aléatoires au début du test. Ainsi, j'ai modifié qMemEquals et récupéré toutes les chaînes que le Qt Demo Browser essayait de comparer, avec les propriétés d'alignement de chaque chaîne. Puis, j'ai écrit un script Perl pour générer les données pour le test.

Ensuite, j'ai passé un certain nombre d'après-midi à apprendre les intrinsèques Intel et à essayer les différentes possibilités d'optimisation. On peut voir toutes les tentatives dans les commits à l'outil de test.

Finalement, je me suis demandé si j'optimisais la bonne fonction, j'ai donc essayé de voir combien de fois qMemEquals est appelée. Il appert que la fonction dans qstring.cpp la plus souvent appelée et la plus gourmande en temps CPU était ucstrncmp. On peut considérer le test d'égalité de qMemEquals comme un cas particulier d'une comparaison ordonnante (ucstrncmp). Avec cette nouvelle information, je suis retourné aux appels de ucstrncmp et ai refait le travail d'optimisation.

Il n'y a pas de graphique à montrer, parce que, au final, elles n'améliorent rien du tout. Par contre, voici tout ce que j'ai appris entre temps.

Les instructions SSE2 opèrent sur des blocs de 16 octets et effectuent des chargements en mémoire bien plus rapidement quand les données sont alignées sur 16 octets. Cependant, le décalage des composantes du tableau dans QString::Date est de 18 octets, c'est-à-dire que 90 à 99 % des données sont désalignées de deux ou dix octets (sur des plateformes 32 bits ; sur x86-64, ce ne serait que deux octets). On ne peut pas modifier ça dans Qt 4, mais c'est quelque chose à considérer pour Qt 5, un commentaire reste donc dans QString pour montrer que l'on devrait aligner les données. Ceci ne sera d'une quelconque aide que si la fonction système malloc retourne aussi de la mémoire alignée sur 16 octets, ce qui n'est pas le cas sous Linux 32 bits.

Ceci est particulièrement vrai sur des processeurs Atom, où les meilleurs résultats pour ucstrncmp ont été obtenus pour les versions alignées (ssse3_aligning2, sse2_aligning, ssse3_aligning).

Ou : les chaînes sont trop courtes.

Lors d'une tentative de résolution du problème de chargements non alignés en ajoutant des prologues d'alignement au code, on découvre que le travail supplémentaire requis dans le prologue dépasse presque complètement les avantages d'avoir aligné les chargements. En plus, dans la majorité des cas, la combinaison prologue et comparaison alignée était plus lente que la comparaison sans alignement. En jetant un coup d'œil aux statistiques des tailles de chaînes, il appert que la plupart des comparaisons sont très petites (de l'ordre de 15 QChar pour qMemEquals et de 38 pour ucstrncmp). Cela signifie que la boucle de comparaison de 16 octets est lancée seulement une ou trois fois. À l'inverse des données des images, qui peuvent facilement atteindre les dizaines de kilooctets, le prologue et l'épilogue ont un coût significatif ; leur complexité est ainsi mesurable.

Ceci inclut aussi du code pour le dispatching en temps réel, selon le CPU. La détection en temps réel requiert des fichiers .cpp séparés par niveau de fonctionnalités de l'architecture (soit un fichier pour SSE2, un autre pour SSE3 et un dernier pour SSE4.2) ; sinon, le compilateur pourrait commencer à utiliser des instructions d'un niveau supérieur dans du code qui est censé fonctionner à un niveau inférieur (pour GCC 4.4, #pragma et __attribute__ ne sont pas des solutions, cela ne fonctionne pas).

Il est fort probable que j'ai perdu plus de temps à optimiser les prologue et épilogue, à jouer avec les différentes approches de l'alignement des données qu'à optimiser effectivement le code de comparaison : l'avancement short par short jusqu'à l'alignement, les chargements non alignés au début des chaînes, puis à la première position alignée (ce qui faisait revérifier 6 ou 14 QChar), l'alignement avant le premier chargement (ce qui signifie le chargement de quelques octets supplémentaires avant le début de la chaîne).

Et n'ont pas assez de registres.

La majorité de mon travail a eu lieu sur une station Core i7 à 2,66 Ghz, c'est là que j'ai lancé mes benchmarks. Quand je suis passé à un netbook, avec un Atom N450, soit 1,66 Ghz, la situation était fort différente. Non seulement les benchmarks étaient bien plus lents pour les mêmes données, mais ils étaient encore plus affectés par l'alignement et la complexité. Comme dit précédemment, les meilleurs résultats venaient du code d'alignement et, par dessus tout, du code SSE3, qui était 10 % plus rapide que le prétendant suivant (sse2_aligning).

J'ai aussi essayé de lire le code assembleur pour voir pourquoi c'était si lent ; dans certains cas, il était clair que c'était à cause d'une pression sur les registres : le nombre de registres généraux disponibles pour du code PIC x86 (32 bits) n'est que de six (eax, ecx, edx, esi, edi, ebp, sans compter le pointeur de cadre ; GCC refuse d'utiliser le registre PIC même s'il n'est pas du tout nécessaire), la moitié est sauvegardée par l'appelant, l'autre par l'appelé. La moitié est prise par les données (les deux pointeurs et la longueur), ne laissant que trois registres pour le prologue. Ainsi, le code devait stocker et recharger certains résultats intermédiaires en mémoire, avec de gros problèmes de performances.

On peut alors envier l'IA64, avec 128 registres généraux, ou UltraSPARC, avec 32 de ces registres. Une fonction feuille a, sans utiliser les mécanismes de rotation des registres, neuf registres scratch disponibles, sauvés par l'appelant, sur UltraSPARC (%g1, %g4, %g5, %o0-%o5), neuf sur x86-64 (rax, rcx, rdx, rsi, rdi, r8-r11) et 27 sur Itanium (r2, r3, r8-r11, r14-r31, ainsi que trois registres d'entrée in0-in2 [r32-r34]). ARM ne dispose que de quatre de ces registres, mais il y a huit registres sauvés par l'appelé de plus.

Intel et AMD : quand allez-vous rendre ces huit registres supplémentaires disponibles sur 32 bits ?

En cours d'apprentissage de l'utilisation de la nouvelle instruction de comparaison de chaînes sur SSE4.2, je n'ai pas pu trouver le moindre exemple qui utilisait la longueur explicite. Tout ce que j'ai trouvé utilisait la longueur implicite (la longueur n'est pas connue a priori et un caractère NUL marque la fin). Tout d'abord, ceci fait une différence : deux chaînes ne peuvent pas être égales si elles ont des longueurs différentes, c'est-à-dire que qMemEquals est appelée bien moins souvent que la fonction publique QString::operator==. Même pour ucstrncmp, on ne doit comparer que la longueur de la chaîne la plus petite (et, si elles sont égales sur cette distance, la plus petite est la première).

Mais il y a apparemment une autre grosse différence : avec des longueurs implicites, on doit vérifier si le caractère NUL a été chargé dans le morceau de 16 octets chargé en mémoire et préparer un cas spécifique pour ce scénario. C'est là où je pense que les deux nouvelles instructions PCMPISTRI et PCMPISTRM de SSE4.2 doivent briller, parce qu'elles font d'elles-mêmes la vérification du NUL. Je n'ai pas remarqué beaucoup d'améliorations dans les versions explicites de ces instructions (PCMPESTRI et PCMPESTRM) en comparaison avec le code SSE antérieur.

Et un ajout au point précédent : les instructions à longueur explicite prennent deux registres de plus en entrée, ce qui ne fait qu'ajouter à la pression.

Merci à Louis du Verdier et à aieeeuuuuu pour leur relecture !