Un meilleur job mieux payé ?

Deviens chef de projet, développeur, ingénieur, informaticien

Mets à jour ton profil pro

ça m'intéresse

Qt et les chaînes de caractères : la théorie des chaînes

Image non disponible

Tout le monde sait que tout framework, toolkit et langage plus récent que le C dispose de sa propre classe de chaîne de caractères. Certains disent même qu'il s'agit d'une fonctionnalité du langage C que de ne pas disposer d'un tel type, le gardant ainsi simple et effilé. D'autres en parlent comme d'un inconvénient, leur permettant de bomber la poitrine et de faire tomber les débutants dans le piège de la comparaison de chaînes avec == au lieu de strcmp().

5 commentaires Donner une note à l'article (5)

Article lu   fois.

Les deux auteurs

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

I. L'article original

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 String Theory de Thiago Macieira paru dans Qt Labs.

II. Introduction

Le C++ ne manque pas à la règle, ses premières versions n'ayant pas non plus été bénéficiaires d'une classe pour les chaînes de caractères. Ce n'est qu'avec l'apparition de la STL (Standard Template Library) qu'est apparue std::string. Mais c'était déjà trop tard pour Qt : Qt 1 était déjà sorti depuis longtemps et incluait déjà sa propre classe de chaînes (QString). Et, pendant très longtemps, Qt n'a pas pu se baser sur l'implémentation fournie par le compilateur de l'utilisateur.

Maintenant, ce problème a disparu mais QString est toujours là, pour plusieurs raisons :

  • QString est implicitement partagée ;
  • QString est Unicode.

La première de ces innovations était déjà présente dans Qt 1, mais la seconde est celle qui va nous intéresser. Dans Qt 2.0, QString a été refondue, passant d'un tableau d'octets à une chaîne Unicode. L'ancienne version de Qt 1 est devenue la classe QCString dans Qt 2 et 3 et survit encore aujourd'hui sous le nom de Q3CString, mais implémentée en utilisant le nouvel QByteArray.

III. La question de l'encodage

Dès que l'on commence à parler de chaînes Unicode encodées sur huit bits, une question vient immédiatement à l'esprit : quel encodage ? Même aujourd'hui, avec l'UTF-8 qui se répand, on ne peut pas se baser sur ce fait. Les éditeurs de texte sous Windows montrent d'ailleurs le plus mauvais exemple. Puisque Qt doit convertir la chaîne (sur huit bits) en UTF-16 (le format utilisé par QString actuellement), on doit connaître l'encodage qui a été utilisé. C'est pourquoi on trouve la fonction QTextCodec::setCodecForCStrings() dans l'API Qt.

Cela fonctionne très bien pour les développeurs d'applications... Quid des développeurs de bibliothèques ? Si on veut que la bibliothèque utilisée par les développeurs d'applications qui utilisent d'autres encodages dans leurs applications fonctionne toujours, il reste un problème à résoudre. Une solution est de se restreindre aux codes ASCII, soit de 0 à 127. En espérant que cela fonctionne. Dans la plupart des cas, cela fonctionnera bien. Mais il y a quelques encodages plus spéciaux qui ne sont pas complètement compatibles avec l'ASCII.

Par exemple, saviez-vous que l'encodage Shift-JIS pour le japonais ne dispose pas de back slash \ ? La plupart des utilisateurs japonais de Windows pensent que C:¥Windows¥System32 est ce que tout le monde voit.

Il y a cependant là un inconvénient : si le développeur d'applications définit le codec pour la gestion des encodages à quelque chose de complexe, toutes vos fonctions simplement ASCII seront parsées avec ce codec.

On pourrait alors utiliser la fonction QString::fromLatin1, apparue avec Qt 2. Cette fonction convertit une chaîne encodée en Latin1 (ISO-8859-1) en UTF-16. C'est, en fait, une opération très simple, parce que ISO-8859-1 correspond parfaitement aux 256 premiers caractères Unicode. Ainsi, c'est une opération très rapide, il n'y aura pas de problème de performances à cause d'un codec lent.

L'utilisation de QString::fromLatin1 est très largement répandue dans les applications et bibliothèques Qt 2 et 3, autant que dans Qt lui-même. En fait, on trouvera probablement ce genre de code dans beaucoup de fichiers source :

 
Sélectionnez
#define QFL1(x) QString::fromLatin1(x)

IV. Une question de performances

Cela n'élimine cependant pas les conséquences en termes de performances. Cela crée une QString dans tous les cas et cela pourrait être une perte de temps processeur pour des opérations simples, particulièrement sur des variables temporaires. Par exemple, une comparaison comme celle-ci

 
Sélectionnez
if (text == QString::fromLatin1("Qt")) 
	doSomething();

va lancer la construction d'une QString temporaire et de ses structures internes, allouera de la mémoire sur le tas pour accueillir chaleureusement une version UTF-16 de la chaîne "Qt", exécutera la comparaison et supprimera le tout. Cela ressemble furieusement à une grande perte de temps.

En effet, les ingénieurs derrière Qt pensent très exactement la même chose. Dans Qt 4.0, une classe QLatin1String a été introduite. On peut la résumer comme suit :

 
Sélectionnez
class QLatin1String 
{ 
public: 
	inline explicit QLatin1String(const char *s) : chars(s) {} 
	inline QLatin1String &operator=(const QLatin1String &other) 
	{ chars = other.chars; return *this; } 
	
	// add here inlined operator==, operator!=, operator< , operator>, etc. 
	// against QString and against const char* 
private: 
	const char *chars; 
};

On peut regarder son implémentation actuelle complète dans le code source de Qt : petit, presque trivial. Cela nous permet de réécrire la comparaison ci-dessus en :

 
Sélectionnez
if (text == QLatin1String("Qt")) 
	doSomething();

Ainsi, pourvu que l'on ait une fonction operator== qui compare une QString à une QLatin1String sans devoir d'abord convertir le tout, le tour est joué. On ne peut pas en retirer plus.

V. Petit tour dans l'assembleur

Il y a deux problèmes avec l'implémentation dans Qt 4.4 : tout d'abord, il manque beaucoup de surcharges dans QString qui pourraient prendre en argument une QLatin1String. Par exemple, QString::replace. Cette fonction a des surcharges pour des QChar, QString et QRegExp. Ce qui signifie qu'une QString temporaire est construite si on veut appeler cette fonction avec un argument QLatin1String. Ce problème sera résolu pour Qt 4.5, avec une autre série d'optimisations (la fonction QString::replace va elle-même être améliorée).

L'autre problème est la signature de ces fonctions. Prenons l'exemple le plus simple de qstring.h, son constructeur :

 
Sélectionnez
inline QString(const QLatin1String &latin1);

Comme on peut le voir, la fonction prend une référence constante à un objet QLatin1String. On a vu dans la définition précédente que QLatin1String n'est rien d'autre qu'un emballage autour d'un pointeur sur char *. Cela signifie malheureusement que l'on demande au compilateur de passer une référence à un pointeur, soit une double indirection pour les données. Vous n'écririez jamais une fonction dont l'argument est de type const char * const &, n'est-ce pas ?

En d'autres mots, pour terminer cet appel, le compilateur doit calculer l'adresse des données, la sauvegarder quelque part et passer l'adresse de ce quelque part en argument de l'appelant. Une analyse du code assembleur généré révèle l'erreur.

Code C++   Assembleur x86 Assembleur x86-64 Assembleur IA-64
 
Sélectionnez
extern "C" function(const char*); 
function("foo");

Non PIC

 
Sélectionnez
movl $.LC0, (%esp) 
call _function
 
Sélectionnez
movl $.LC0, %edi 
call _function

N'existe pas

 
Sélectionnez
extern "C" function(const char*); 
function("foo");

PIC

 
Sélectionnez
leal .LC0@GOTOFF(%ebx), %eax 
movl %eax, (%esp) 
call _function
 
Sélectionnez
leaq .LC0(%rip), %rdi 
call _function
 
Sélectionnez
addl out0 = @gprel(.LC0), r1;; 
br.call rp = _function
 
Sélectionnez
extern "C" function(const QLatin1String &); 
function(QLatin1String("foo"));

Non PIC

 
Sélectionnez
leal -4(%ebp), %eax 
movl $.LC0, -4(%ebp) 
movl %eax, (%esp) 
call _function
 
Sélectionnez
movq %rsp, %rdi 
movq $.LC0, (%rsp) 
call _function

N'existe pas

 
Sélectionnez
extern "C" function(const QLatin1String &); 
function(QLatin1String("foo"));

PIC

 
Sélectionnez
leal .LC0@GOTOFF(%ebx), %eax 
movl %eax, -8(%ebp) 
leal -8(%ebp), %eax 
movl %eax, (%esp) 
call _function
 
Sélectionnez
leaq .LC0(%rip), %rax 
movq %rsp, %rdi 
movq %rax, (%rsp) 
call _function
 
Sélectionnez
addl r14 = @gprel(.LC0), r1 
adds out0 = 16, r12;; 
st8 [out0] = r14 
br.call rp = _function

Ce code assembleur généré pour un appel avec un caractère constant n'implique presque aucune opération sur la mémoire : en x86, les arguments des fonctions sont passés sur la pile. Cependant, sur x86-64 et IA64, où les arguments sont passés dans les registres, il n'y a aucune opération mémoire. Quand le code est assemblé, tout ce qui restera est une addition. Néanmoins, l'appel avec une référence constante cause toujours des opérations mémoire, dans toutes les architectures.

Ainsi, que se passe-t-il si on passe l'objet QLatin1String par valeur ?

Code C++   Assembleur x86 Assembleur x86-64 Assembleur IA-64
 
Sélectionnez
extern "C" function(QLatin1String); 
function(QLatin1String("foo"));

Non PIC

 
Sélectionnez
movl $.LC0, (%esp) 
call _function
 
Sélectionnez
movl $.LC0, %edi 
call _function

N'existe pas

 
Sélectionnez
extern "C" function(QLatin1String); 
function(QLatin1String("foo"));

PIC

 
Sélectionnez
leal .LC0@GOTOFF(%ebx), %eax 
movl %eax, (%esp) 
call _function
 
Sélectionnez
leaq .LC0(%rip), %rdi 
call _function
 
Sélectionnez
addl out0 = @gprel(.LC0), r1;; 
br.call rp = _function

Comme on peut le voir, c'est la même chose qu'avec la version const char * ! Que devrait-on faire à présent ? On devrait remplacer tous les arguments qui prennent un const QLatin1String & par un simple QLatin1String. Maintenant, il faut encore le faire sans casser la compatibilité source ou binaire.

Le code ci-dessus a été généré avec gcc -O2 -S, mais les instructions qui n'étaient pas utiles au discours ont été supprimées.

Quelques explications d'assembleur
PIC signifie Position Independent Code, le code en question peut être chargé à n'importe quelle adresse en mémoire. C'est le mode par défaut et même le seul sur IA64. Le symbole .LC0 est l'endroit où le compilateur met la chaîne "foo" terminée par le caractère \0. Sur IA64, le registre r1 est appelé pointeur global (parfois gp dans le code source) et pointe sur le centre des données du module, alors que r12 est le pointeur sur le tas (parfois sp). Sur x86, le compilateur utilise n'importe quel registre pour stocker l'adresse du GOT et, dans ce cas, il choisit le registre %ebx. Sur x86-64, cela n'est pas nécessaire, étant donné qu'un adressage relatif au pointeur d'instruction est utilisé. Les symboles débutant par @ sont les drapeaux de l'éditeur de liens : ils lui disent de générer des informations de relocation at ce point dans le code (GOTOFF est l'offset du GOT - Global Offset Table -, @gprel signifie relatif au gp, soit la même chose mais sous un autre nom, ainsi l'opération ci-dessus était out0 = (.LCO - gp) + gp).

VI. Remerciements

Merci à Louis du Verdier, à Claude Leloup et à LittleWhite pour leur relecture !

Qt et les chaînes de caractères
La théorie des chaînes
Améliorer les performances lors du rendu avec plus de SIMD
Améliorer les performances des chaînes avec SIMD... ou pas
Chaînes et SIMD, la revanche (de Latin1)
QString et Unicode, optimisation de QString::fromUtf8
UTF-8, Latin1 et charsets
Sémantique d'ordonnancement mémoire
  

Copyright © 2008 Thiago Macieira. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.