Qt et les chaînes de caractères : sémantique d'ordonnancement mémoire

Image non disponible

Ce week-end, un utilisateur a posté sur la mailing list qt4-preview-feedback un message disant que la documentation de QAtomicInt avait besoin d'un peu de travail. Je lui ai répondu que la sémantique d'ordonnancement mémoire serait mieux expliquée dans un livre que dans la documentation Qt.

En y repensant plus tard, je me suis dit que nous pourrions ajouter un peu de documentation à ce sujet. Voici un petit test.

Commentez 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 Memory ordering semantics de Thiago Macieira paru dans Qt Labs.

II. Introduction

L'année dernière, aux Qt Developer Days 2008, j'ai tenu une conférence sur les threads. À l'époque, Qt 4.5 n'était pas encore sorti, Qt 4.4 était donc tout ce que nous avions. Une des fonctionnalités de Qt 4.4 était QtConcurrent et les nouvelles classes atomiques. Je les ai mentionnées, mais j'ai évité d'aller trop loin. Le faire n'aurait intéressé qu'une douzaine de personnes dans la salle.

Peut-être serez-vous intéressés. Cependant, avant d'y aller, une petite leçon d'Histoire.

III. Histoire

Je pensais juste donner quelques faits ; cependant, si vous en voulez, il suffit de visiter Wikipédia. Il serait beaucoup plus intéressant d'avoir les informations importantes racontées en prose, d'une manière traditionnelle.

Plaçons-nous donc dans le bon état d'esprit. Vous racontez cette histoire à vos petits-enfants, voire vos arrière-petits-enfants. Toute inexactitude présente ici n'est que le résultat d'une tradition orale, ce ne sont plus que des légendes.

Hwæt! En des temps immémoriaux, avant que time_t ne soit compté, le Sage racontait cette fable. Dans l'ombre se tapissait l'Ingénieur, personne ne savait d'où il venait. On attribuait bien des créations fantastiques à l'Ingénieur, il inspirait le respect chez ses pairs.
Et l'Ingénieur créa le Processeur, car l'Ingénieur pouvait alors se reposer pendant que le Processeur travaillait. Et, pendant un certain temps, tous étaient contents, car il y avait le Travail pour tout le monde et du repos pour tout le monde.
Mais il vint un temps où le Processeur s'est retourné vers l'Ingénieur et lui dit : « hello, world! Maître, tu m'as donné le Travail et tu m'as donné un but. Et je suis heureux de faire le Travail, car je peux apprendre. Mais, Maître, écoute ma prière : le Travail que tu nous proposes grandit sans cesse et tes humbles serviteurs ne peuvent pas s'en sortir. Ne pourrais-tu pas m'offrir de la compagnie ? Je pourrai ainsi faire le Travail plus vite. »
Et l'Ingénieur ressentit de la pitié pour le Processeur. Ainsi apparut un autre Processeur. L'Ingénieur dit au monde : « appelons-le Processeur2 ! »
Ensuite vint celui qui avait la vision du futur et qui pouvait dire ce qui allait se passer. Il s'appelait l'Analyste et prédit ainsi : « ces deux Processeurs devraient effectuer le Travail en tandem et ils devraient aller plus vite que quiconque. Cette union sera connue sous le nom de Double-Processeur. Dans les années à venir, cette union cette union donnera naissance aux Doubles-Coeurs, aux Quadruples-Coeurs et à d'autres bêtes dont les noms nous sont encore inconnus. Cependant, seulement des conflits en proviendront ! »
Plusieurs éons ayant passé (en temps ordinateur), Processeur et Processeur2 travaillaient et apprenaient beaucoup plus. Ainsi parla le Processeur : « hello, world! Maître, ton art est grand et, pendant plusieurs éons, nous avons réalisé ton Travail, en suivant ton Assembleur opcode par opcode. Nous n'avons pas perdu un cycle de tes Tableaux d'Assembleur. Mais Processeur2 m'a appris beaucoup et jure que nous pourrions faire ton Travail plus vite que tu l'avais prévu, seul toi peut nous donner le pouvoir qu'il en soit ainsi. »
Ainsi l'Ingénieur laissa les Processeurs exécuter ses Instructions plus vite que ses cycles et leur donna le don du Cache. Puis le conflit vint au monde et les Processeurs se sont battus pour la Mémoire : ce que l'un écrivait, l'autre ne lisait pas. L'Ingénieur est venu au monde une deuxième fois et peina pour que les Processeurs arrêtent leur guerre. Beaucoup de ce qui a été détruit pendant cette ère de labeur pour l'Ingénieur a été reconstruit. Il a décalé les règles et les Processeurs ont exécuté son Assembleur. Il a imposé ensuite l'Ordonnancement Mémoire. Ainsi, les Processeurs ont mis de côté leur guerre. Le monde en fut changé à jamais.

IV. Ordonnancement mémoire

Maintenant que l'ordonnancement mémoire a été introduit, voyons pourquoi. Les anciens systèmes, en fait jusqu'aux 386 et 486, exécutaient toujours tout dans l'ordre et avaient des sémantiques de temps bien définies. Une instruction qui chargeait des données en mémoire depuis la mémoire dans un registre avait besoin de trois cycles : lire l'instruction, récupérer les données, exécuter l'instruction. Les processeurs s'améliorant, leurs horloges sont devenues beaucoup plus rapides que la mémoire, le cache a été introduit.

Cela signifie qu'un processeur pourrait avoir une lecture en mémoire depuis le cache, au lieu de la mémoire. Il pourrait même se satisfaire d'écrire uniquement dans le cache pour une écriture en mémoire. Comme notre conte l'explique, cela fonctionne très bien pour un processeur. Quand il y en a plus d'un, ils doivent s'organiser, car, en général, l'écriture du cache en mémoire principale est retardé. Pour s'assurer que l'un peut lire ce que l'autre écrit, ce dernier doit écrire en mémoire plus tôt.

Il y a quatre types d'ordonnancement mémoire :
  • pas d'ordonnancement ;
  • écrire en mémoire toutes les lectures de cache, en s'assurant que toutes les nouvelles lectures s'effectuent depuis la mémoire principale ;
  • écrire en mémoire toutes les écritures de cache, en s'assurant que toutes les écritures ont été effectuées en mémoire principale ;
  • ordonnancement complet, combinant les deux types précédents.

On y reviendra très bientôt.

Pour contourner le problème, les processeurs modernes exécutent aussi des opérations hors service. On leur permet de réordonner les instructions fournies, pourvu que, à un certain niveau, tout se passe comme si ces opérations étaient effectuées dans l'ordre. L'architecture x86, à l'origine, terminait complètement une instruction avant de passer à la suivante, c'est donc le comportement requis aujourd'hui : toutes les opérations doivent se dérouler comme si elles étaient finies avant que la suivante commence. Tout accès mémoire doit aussi avoir l'air d'être exécuté dans l'ordre dans lequel il a été assemblé.

L'Itanium (IA-64) enlève certaines de ces restrictions. Tout d'abord, toutes les instructions peuvent avoir lieu en parallèle ou bien se finir ou démarrer dans tout ordre que le processeur pourrait trouver adapté. Pour se resynchroniser, l'assembleur introduit un bit de stop, indiquant que les instructions avant ce stop doivent être finies avant qu'une autre instruction après le stop soit démarrée. Ceci, à l'intérieur d'un thread uniquement. À l'extérieur de ce thread, soit ce qui est vu depuis un autre processeur, l'architecture n'impose aucune garantie : les accès en mémoire peuvent avoir lieu dans n'importe quel ordre.

V. L'atomique et les autres données

Il est important de noter que la sémantique d'ordonnancement mémoire ne concerne pas que les données. QAtomicInt et QAtomicPointer exécutent des chargements, des stockages, des échanges, des récupérations et des additions, des tests et des définitions toujours de manière atomique. Pour un atome de mémoire (soit l'entier derrière QAtomicInt ou le pointeur que contient QAtomicPointer), l'opération est soit exécutée entièrement soit pas du tout. En d'autres mots, personne ne peut jamais voir les données dans un statut intermédiaire. C'est la définition d'atomique.

Maintenant, la sémantique mémoire s'occupe de la manière dont les autres données sont affectées par l'opération atomique. Imaginez le code suivant dans un thread :

 
Sélectionnez
extern int x, y, z; 
x = 1; 
y = 2; 
z = 3;

Et celui-ci dans un autre :

 
Sélectionnez
extern int x, y, z; 
if (z == 3) 
	printf("%d %d", x, y);

On déclare les variables x, y et z en tant que variables normales, aucune opération atomique n'est exécutée ici. Sur x86 et x86-64, ces instructions se comporteront comme l'intuition le dicte : la seule sortie possible est 1 2.

Par contre, sur IA-64, aucune garantie de ce type n'est possible. Comme exposé précédemment, le processeur peut exécuter les mémoires dans un ordre qui lui semble opportun. Par exemple, x et z pourraient être dans la même ligne de cache, avec y dans une autre, ainsi x et z seront écrits en même temps, mais aucune garantie pour y.

Pire encore, l'autre processeur peut exécuter les chargements dans l'ordre qu'il préfère. Il pourrait charger x, y et z dans cet ordre, mais il pourrait aussi récupérer x et y avant que leurs valeurs ne soient modifiées, ainsi qu'un z déjà modifié. En conclusion, le code ci-dessus pourrait afficher n'importe quoi !

Étrange ? Absolument.

Voici l'endroit précis où la sémantique d'ordonnancement mémoire apparaît :

  • dans une sémantique de libération, le processeur garantit que toutes les opérations d'écriture passées sont finies et deviennent visibles au moment où la libération a lieu ;
  • dans une sémantique d'acquisition, le processeur garantit qu'aucune opération de lecture future n'a démarré, il verra toutes les opérations d'écritures libérées par les autres processeurs.

Ainsi, si le thread 1 de l'exemple précédent voulait s'assurer que les valeurs écrites dans x et y soient visibles, il aurait requis une libération de mémoire sur z. Si le thread 2 avait voulu s'assurer que les valeurs de x et y avaient été mises à jour, il aurait requis une acquisition de chargement sur z.

Les noms acquisition et libération proviennent des opérations sur les mutex. Quand un mutex est acquis, il doit s'assurer que le processeur verra la mémoire écrite par les autres processeurs. Il exécute donc une opération d'acquisition. Quand le mutex est libéré, il doit s'assurer que les valeurs changées par le thread deviennent visibles aux autres threads, il exécute donc une opération de libération.

Les deux autres opérations que QAtomicInt supporte sont juste une combinaison d'acquisition et de libération ou d'aucune. L'opération relaxed signifie qu'il n'y a ni acquisition, ni libération dans les opérations effectuées, juste l'opération atomique. A contrario, ordered signifie que l'opération est complètement ordonnée : les sémantiques d'acquisition et de libération sont appliquées.

VI. Utilisation pratique

VI-A. Relaxed

Comme dit précédemment, la sémantique relaxed signifie qu'aucun ordonnancement mémoire n'est appliqué. Seule l'opération atomique elle-même est exécutée. Le cas le plus commun est des chargements et stockages quelconques. La plupart des architectures modernes les exécutent atomiquement pour des puissances de deux plus petites ou égales à la taille du registre. Que des lectures et écritures plus grandes soient atomiques ou non dépend de la plateforme (par exemple, un nombre en virgule flottante double précision sur une architecture 32 bits).

Mais on peut trouver d'autres cas pour d'autres opérations atomiques. Par exemple, QAtomicInt offre ref() et unref(), qui ne sont que des emballages de fetchAndAddRelaxed(1) et fetchAndAddRelaxed(-1). Cela signifie que le comptage de références est atomique, sans plus.

VI-B. Acquire et Release

Pour voir si les sémantiques d'acquisition et de libération sont requises, on donne souvent les mutex comme exemple. Cependant, les mutex sont des bêtes assez complexes. Examinons un cas plus simple :

 
Sélectionnez
class SpinLock 
{ 
	QAtomicInt atomic; 
	
public: 
	void lock() 
	{ 
		while (!atomic.testAndSetAcquire(0, 1)) 
			; 
	} 
	void unlock() 
	{ 
		atomic.testAndSetRelease(1, 0); 
	} 
}

Cette classe possède deux méthodes, comme QMutex : lock et unlock. La plus intéressante est lock : elle possède une boucle qui tente toujours de changer la valeur de atomic de 0 à 1. S'il y parvient, c'est une opération d'acquisition, ce qui signifie que le thread courant devrait voir maintenant toute écriture libérée avant cette acquisition.

La méthode unlock fait l'inverse : elle change atomic de 1 à 0 dans une opération de libération. Ce n'est en fait pas requis : le compilateur génère généralement une méthode de libération de mémoire pour des variables volatiles comme QAtomicInt. Ce qui signifie qu'on aurait pu simplement écrire atomic = 0;.

VI-C. Ordered

Le cas d'utilisation de cette sémantique est, en fait, assez rare. Habituellement, c'est plus je ne peux pas savoir si une acquisition ou une libération sera suffisante, j'utilise donne un ordonnancement complet.

Mais il y a un cas d'utilisation de cette sémantique dans le code de Qt : la macro (non documentée) Q_GLOBAL_STATIC. Un ou plusieurs threads peuvent être en compétition pour exécuter une opération. Le premier qui la complète gagne. Il publiera ses conclusions aux autres threads (soit une libération), alors que les threads perdants devront acquérir les conclusions. Le code simplifié de cette macro est le suivant :

 
Sélectionnez
Type *gs() 
{ 
	static QBasicAtomicPointer<Type> pointer = Q_BASIC_ATOMIC_INITIALIZER(0); 
	if (!pointer) { 
		Type *x = new Type; 
		if (!pointer.testAndSetOrdered(0, x)) 
			delete x; 
	} 
	return pointer; 
}

Ce que le code fait : il vérifie si le pointeur est toujours NULL. Si oui, il crée un nouvel objet de type Type et essaie de le définir dans le pointeur atomique. Si cette opération peut s'effectuer avec succès, on doit effectuer une opération de libération pour publier le contenu du nouvel objet aux autres threads. Sinon, on doit effectuer une acquisition pour obtenir le contenu du nouvel objet du thread gagnant.

Mais... cela est-il correct ?

Pas entièrement. Ce que l'on doit faire, en réalité, c'est un testAndSetReleaseAcquire, qui n'est pas disponible dans Qt. Ainsi, on pourrait le diviser en un testAndSetRelease avec un Acquire dans le cas perdant. C'est exactement ce qui est fait dans QWeakPointer :

 
Sélectionnez
ExternalRefCountData *x = new ExternalRefCountData(Qt::Uninitialized); 
x->strongref = -1; 
x->weakref = 2; // the QWeakPointer that called us plus the QObject itself 
if (!d->sharedRefcount.testAndSetRelease(0, x)) { 
	delete x; 
	d->sharedRefcount->weakref.ref(); 
} 
return d->sharedRefcount;

Comme on peut le voir, si le test et l'affectation ont lieu avec succès, il exécute une libération, ainsi l'autre thread peut voir le résultat. Que se passe-t-il en cas d'échec ? Il doit effectuer une acquisition... mais où est-elle ?

En fait, elle y est, mais bien cachée sous l'opérateur ->. Rappelez-vous ce qui a été dit : les compilateurs génèrent des acquisitions pour les variables volatiles. Ainsi, pour appeler QAtomicInt::ref() avec this = &d->sharedRefCount->weakref, le compilateur doit charger la valeur de d->sharedRefCount et c'est une opération d'acquisition.

VII. Conclusion

Alors, compris ? Sinon, c'est assez normal, ce n'est pas un sujet facile. Relisez et faites des recherches sur le sujet de l'ordonnancement mémoire. Le but, ici, était d'essayer et de voir si cela avait un certain sens que d'expliquer cela dans la documentation Qt.

Cependant, à moins d'écrire quelque chose comme une pile sans verrou, il y a des chances que vous n'ayez pas grand-chose à faire de ces sémantiques. Vous pouvez simplement vous reposer sur le processeur ainsi que sur les classes de sémaphores de Qt (QMutex, QWaitCondition, QSemaphore, QReadWriteLock) et le mécanisme inter-thread de signaux et de slots. C'est même tout si vous ne faites pas de multithreading.

Si vous écrivez une pile sans verrou, vous être probablement familier du problème ABA, qui ne peut pas être résolu par QAtomicInt ou QAtomicPointer. Il requiert une opération connue sous le nom de double comparaison et échange et, pour expliquer pourquoi, on aurait encore besoin d'un autre article. Et expliquer pourquoi le jeu d'instructions AMD64 n'en avait pas à l'origine, comme IA-64. (386 non plus, mais ce n'est pas un problème pour nous puisque Qt ne supporte pas 386).

VIII. Remerciements

Merci à Louis du Verdier et à Claude Leloup 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 © 2009 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.