I. Problème▲
I-A. Question JG▲
1. Pourquoi Optimized::String n'est-il pas sûr du point de vue de la thread safety ? Donnez des exemples.
I-B. Questions Guru▲
2. Démontrez comment créer une Optimized::String (à partir de GotW n°44) avec thread safety :
a) en présumant l'existence d'opérations atomiques pour l'obtention, la mise en place et la comparaison des valeurs entières ; et
b) en présumant qu'il n'y en a pas.
3. Quels sont les effets sur les performances ? Discutez.
II. Solution▲
II-A. Introduction▲
C++ standard est silencieux sur le sujet des fils d'exécution (threads). Contrairement à Java, C++ n'a aucun support incorporé pour les fils d'exécution et ne cherche pas à traiter les problèmes de sécurité des fils d'exécution par le langage. Alors pourquoi un GotW sur les fils d'exécution ? Simplement parce que nous sommes de plus en plus nombreux à écrire des programmes à fils multiples (MT), et qu'aucun traité sur l'implémentation de chaîne à copie sur écriture ne saurait être complet s'il ne couvre pas les problèmes de sécurité des fils.
Je ne me lancerai pas dans une longue discussion sur ce qu'implique en détails l'écriture de code thread-safe ; reportez-vous à un bon livre pour plus de détails.
II-B. 1. Pourquoi Optimized::String n'est-il pas sûr du point de vue de la thread safety ? Donnez des exemples.▲
Il est de la responsabilité du code qui utilise un objet de garantir que l'accès à l'objet sera sauvegardé (sérialisé) comme il faut. Par exemple, si un certain objet chaîne a pu être modifié par deux fils différents, il ne revient pas au malheureux objet chaîne de se défendre contre ce genre d'abus ; c'est le travail du code qui utilise la chaîne de veiller à ce que deux fils n'essayent jamais de modifier le même objet chaîne en même temps.
Le problème avec le code dans GotW n°44 est double : D'abord, l'implémentation par copie sur écriture (COW) est conçue pour cacher le fait que deux objets chaînes visibles différents peuvent partager un état caché commun ; par conséquent, il est de la responsabilité de la classe chaîne de garantir que le code appelant ne modifie jamais une chaîne dont la représentation est partagée. Le code chaîne affiché le fait déjà en effectuant une copie profonde (un "dé-partage" de la représentation) si nécessaire au moment où un appelant essaye de modifier la chaîne. En général, il n'y a pas de problème à ce niveau.
Malheureusement, cela nous amène au deuxième problème : le code dans la chaîne qui "dé-partage" la représentation n'est pas sûr du point de vue des fils. Imaginez qu'on ait deux objets chaînes s1 et s2 :
a) s1 et s2 s'avèrent partager la même représentation cachée (pas de problème, les chaînes sont faites pour ça) ;
b) un fil 1 essaye de modifier s1 (pas de problème, parce que le fil 1 sait que personne d'autre n'est en train de modifier s1) ;
c) un fil 2 essaye de modifier s2 (pas de problème, parce que le fil 2 sait que personne d'autre n'est en train de modifier s2) ;
d) en même temps (erreur).
Le problème est (d) : Au même moment, s1 et s2 vont essayer tous les deux de "dé-partager" la représentation qu'ils partagent, et le code pour faire cela n'est pas thread-safe. Spécifiquement, considérez la toute première ligne de code dans String::AboutToModify() :
void String::AboutToModify(
size_t n,
bool bMarkUnshareable /* = false */
) {
if( data_->refs > 1 && data_->refs != Unshareable ) {
/* ... etc. ... */Cette condition if n'est pas thread-safe. D'une part, évaluer même "data_->refs > 1" peut ne pas être atomique ; si c'est le cas, il est possible que si le fil 1 essaye d'évaluer "data_->refs > 1" pendant que le fil 2 est en train d'actualiser la valeur de refs, la valeur lue à partir de data_->refs puisse être n'importe quoi - 1, 2, ou même quelque chose qui n'est ni la valeur d'origine, ni la nouvelle valeur. Le problème est que cette chaîne ne suit pas les exigences de base de sécurité thread safety comme quoi le code qui utilise un objet doive garantir que l'accès à l'objet est sérialisé comme il faut. Ici, la chaîne doit garantir qu'en aucun cas deux fils s'apprêtent à utiliser la même valeur "refs" d'une façon dangereuse en même temps. La méthode traditionnelle pour ce faire consiste à sérialiser l'accès au StringBuf partagé (ou juste à son membre .refs) en utilisant une section critique ou sémaphore. Dans ce cas, au minimum l'opération "comparer un int" doit être garantie atomique.
Cela nous amène au deuxième problème : Même si la lecture et l'actualisation de "refs" étaient atomiques, il y a deux parties dans la condition if. Le problème est que le fil qui exécute le code ci-dessus pourrait être interrompu après avoir évalué la première partie de la condition mais avant d'avoir évalué la seconde partie. Dans notre exemple :
| Fil 1 | Fil 2 |
| >> entrer AboutToModify() de s1 évaluer "data_->refs > 1" (vrai, parce que data_->refs vaut 2) |
|
| ******** commutation de contexte ******** | |
| >> entrer AboutToModify() de s2 (exécution complète, y compris décrémente data_->refs jusqu'à la valeur 1) << quitter AboutToModify() de s2 |
|
| ******** commutation de contexte ******** | |
| évaluer "data_->refs != Unshareable" (vrai, parce que data_->refs vaut désormais 1) entrer le bloc "I'm shared and need to unshare" de AboutToModify, qui clone la représentation, décrémente data_->refs à la valeur 0, et abandonne le dernier pointeur au StringBuf... ouille ! nous avons une fuite mémoire parce que le StringBuf qui était partagé par s1 et s2 ne peut plus s'effacer ! |
|
Maintenant que nous avons passé ceci en revue, nous sommes prêts à résoudre ces problèmes de sécurité.
II-C. 2. Démontrez comment créer une Optimized::String (à partir de GotW n°44 ) avec thread safety :▲
a) en présumant l'existence d'opérations atomiques pour l'obtention, la mise en place et la comparaison des valeurs entières ; et
b) en présumant qu'il n'y en a pas.
Je répondrai à b) en premier, parce que ce cas est plus général. Ce dont on a besoin ici est un dispositif de gestion de verrouillage tel qu'une section critique ou un mutex. Le code est équivalent dans l'un et l'autre cas, aussi utiliserons-nous ci-dessous une section critique, qui est habituellement un dispositif de synchronisation plus efficace qu'un mutex général. L'élément clef concernant ce que nous sommes sur le point de faire est simple : il s'avère que si nous faisons les choses bien, il nous suffira de verrouiller l'accès au décompte de référence lui-même.
Avant de faire quoi que ce soit d'autre, il nous faut ajouter un objet membre CriticalSection dans Optimized::StringBuf. Appelons ce membre cs :
namespace Optimized {
struct StringBuf {
StringBuf(); // démarrage à vide
~StringBuf(); // effacement du tampon
StringBuf( const StringBuf& other, size_t n = 0 );
// initialisation pour copie d'autres,
// et garantit len >= n
void Reserve( size_t n ); // garantit len >= n
char* buf; // tampon alloué
size_t len; // longueur de tampon
size_t used; // caractères actuellement utilisés
unsigned refs; // comptage de référence
CriticalSection cs; // sérialise le travail sur cet objet
};La seule fonction qui nécessite des opérations sur deux objets StringBuf en même temps est le constructeur de copies. La chaîne se contente d'appeler le constructeur de copie de StringBuf depuis deux endroits (depuis le constructeur de copie de la chaîne elle-même et depuis AboutToModify()). Notez que la chaîne n'a besoin que de sérialiser l'accès au décompte de référence, parce que par définition, aucune chaîne ne fera aucun travail sur un StringBuf qui est déjà partagé (s'il est partagé, il sera lu pour faire une copie, mais nous n'avons pas à nous inquiéter de qui que ce soit essayant de modifier, d'appliquer Reserve() ni de modifier/altérer autrement le tampon).
Le constructeur par défaut n'a besoin d'aucun verrouillage :
String::String() : data_(new StringBuf) { }Le destructeur n'a besoin de verrouiller que son interrogation et sa mise à jour de la copie sur écriture :
String::~String() {
bool bDelete = false;
data_->cs.Lock(); //---------------------------
if( data_->refs == Unshareable || --data_->refs < 1 ) {
bDelete = true;
}
data_->cs.Unlock(); //-------------------------
if( bDelete ) {
delete data_;
}
}Pour le constructeur de copie de chaîne, notez que nous pouvons présumer que l'autre tampon de données de chaîne ne sera pas modifié pendant cette opération, puisqu'il est de la responsabilité de l'appelant de sérialiser l'accès aux objets visibles. Néanmoins nous devons toujours sérialiser l'accès au décompte de référence lui-même, comme nous faisions ci-dessus :
String::String( const String& other )
{
bool bSharedIt = false;
other.data_->cs.Lock(); //---------------------
if( other.data_->refs != Unshareable ) {
bSharedIt = true;
data_ = other.data_;
++data_->refs;
}
other.data_->cs.Unlock(); //-------------------
if( !bSharedIt ) {
data_ = new StringBuf( *other.data_ );
}
}Aussi, rendre le constructeur de copie de chaîne sûr n'a pas été très dur du tout. Cela nous amène à AboutToModify(), qui s'avère être très similaire, mais notez que ce code d'échantillonnage est verrouillé pendant toute l'opération de copie profonde... on n'a vraiment besoin du verrouillage que quand on lit la valeur refs, puis quand on actualise la valeur refs à la fin, mais j'ai décidé de verrouiller toute l'opération plutôt que d'obtenir un traitement en parallèle légèrement meilleur en suspendant le verrouillage pendant la copie profonde puis en la réacquérant juste pour actualiser refs :
void String::AboutToModify(
size_t n,
bool bMarkUnshareable /* = false */
) {
data_->cs.Lock(); //---------------------------
if( data_->refs > 1 && data_->refs != Unshareable ) {
StringBuf* newdata = new StringBuf( *data_, n );
--data_->refs; // maintenant tout le travail est fait,
data_->cs.Unlock(); //-----------------------
data_ = newdata; // alors, prenons possession
}
else {
data_->cs.Unlock(); //-----------------------
data_->Reserve( n );
}
data_->refs = bMarkUnshareable ? Unshareable : 1;
}Aucune des autres fonctions n'a besoin d'être modifiée. Append() et operator[]() n'ont pas besoin d'être verrouillés, parce qu'une fois que AboutToModify() tourne, nous sommes assurés de ne pas utiliser une représentation partagée. Length() n'a pas besoin d'être verrouillé parce que par définition, c'est bon pour nous si notre StringBuf n'est pas partagé (il n'y a personne d'autre pour modifier le décompte utilisé sur nous), et c'est bon pour nous s'il est partagé (l'autre fil ferait sa propre copie avant tout travail, et par conséquent il ne modifierait pas le décompte utilisé sur nous) :
void String::Append( char c ) {
AboutToModify( data_->used+1 );
data_->buf[data_->used++] = c;
}
size_t String::Length() const {
return data_->used;
}
char& String::operator[]( size_t n ) {
AboutToModify( data_->len, true );
return *(data_->buf+n);
}
}à nouveau, notez une chose intéressante dans tout cela : le seul verrouillage dont nous avons eu besoin impliquait la copie sur écriture elle-même.
Forts de cette observation et de la solution générale ci-dessus, revenons à la partie a) de la question :
a) en présumant l'existence d'opérations atomiques pour l'obtention, la mise en place et la comparaison des valeurs entières ; et
Certains systèmes d'exploitation fournissent ces genres de fonctions.
NOTE : Ces fonctions sont habituellement beaucoup plus efficaces que les primitives de synchronisation générale comme les sections critiques et les mutex. Il est néanmoins fallacieux de dire que nous pouvons utiliser les opérations atomiques sur les entiers "à la place des verrouillages" parce que le verrouillage est toujours nécessaire - simplement le verrouillage est généralement moins coûteux que d'autres alternatives, mais pas gratuit.
Voici une implémentation thread-safe de chaîne qui présume que nous avons trois fonctions : une IntAtomicGet, une IntAtomicDecrement et une IntAtomicIncrement qui retourne la nouvelle valeur de façon sûre. Nous ferons essentiellement la même chose que ce que nous avons fait plus haut, mais en n'utilisant que des opérations atomiques sur les entiers pour sérialiser l'accès au décompte refs :
namespace Optimized {
String::String() : data_(new StringBuf) { }
String::~String() {
if( IntAtomicGet( data_->refs ) == Unshareable ||
IntAtomicDecrement( data_->refs ) < 1 ) {
delete data_;
}
}
String::String( const String& other )
{
if( IntAtomicGet( other.data_->refs ) != Unshareable ) {
data_ = other.data_;
IntAtomicIncrement( data_->refs );
}
else {
data_ = new StringBuf( *other.data_ );
}
}
void String::AboutToModify(
size_t n,
bool bMarkUnshareable /* = false */
) {
int refs = IntAtomicGet( data_->refs );
if( refs > 1 && refs != Unshareable ) {
StringBuf* newdata = new StringBuf( *data_, n );
if( IntAtomicDecrement( data_->refs ) < 1 ) {
delete newdata; // juste au cas où deux fils
} // essaieraient cela en même temps
else { // maintenant tout le travail est fait,
data_ = newdata; // alors, prenons possession
}
}
else {
data_->Reserve( n );
}
data_->refs = bMarkUnshareable ? Unshareable : 1;
}
void String::Append( char c ) {
AboutToModify( data_->used+1 );
data_->buf[data_->used++] = c;
}
size_t String::Length() const {
return data_->used;
}
char& String::operator[]( size_t n ) {
AboutToModify( data_->len, true );
return *(data_->buf+n);
}
}3. Quels sont les effets sur les performances ? Discutez.
Sans les opérations atomiques sur les entiers, la copie sur écriture induit généralement une perte significative de performances. Même avec les opérations atomiques sur les entiers, la copie sur écriture peut rendre les opérations courantes sur les chaînes près de 50% plus longues - même dans des programmes à un seul fil.
En général, la copie sur écriture est souvent une mauvaise idée dans un code compatible multi-fil. En bref, la raison en est que le code appelant ne peut plus savoir si deux objets chaîne distincts partagent effectivement la même représentation cachée, aussi la chaîne doit-elle encourir une perte de temps pour effectuer assez de sérialisation pour que le code appelant puisse prendre sa part normale de responsabilité pour la thread safety. En fonction de la disponibilité d'options plus efficaces telles que les opérations atomiques sur les entiers, l'impact sur les performances va de "modéré" à "profond."
III. Quelques résultats empiriques▲
Dans cet environnement de test, j'ai testé six des principales saveurs d'implémentation de chaînes :
Nom Description
--------------- ---------------------------------------
Plain Chaîne sans décompte d'utilisation ; toutes les autres
sont modélisées sur celle-ci (une version raffinée de
la réponse GotW n°43)
COW_Unsafe Plain + COW, non thread-safe (une version raffinée de
la réponse GotW n°44)
COW_AtomicInt Plain + COW + thread-safe (une version raffinée de
la réponse GotW #45 1(a) ci-dessus)
COW_AtomicInt2 COW_AtomicInt + StringBuf dans le même tampon que les
données (une autre version raffinée de la réponse
GotW #45 1(a) ci-dessus)
COW_CritSec Plain + COW + thread-safe (sections critiques Win32)
(une version raffinée de la réponse GotW #45 1(b)
ci-dessus)
COW_Mutex Plain + COW + thread-safe (mutex Win32) (COW_CritSec
avec mutex au lieu de sections critiques)J'ai également introduit une septième saveur pour mesurer le résultat de l'allocation d'optimisation de mémoire au lieu de la copie d'optimisation :
Plain_FastAlloc Plain + un allocateur de mémoire optimiséeJe me suis concentré sur la comparaison de Plain avec COW_AtomicInt. COW_AtomicInt a généralement été l'implémentation de copie sur écriture thread-safe la plus efficace. Les résultats ont été les suivants :
1. Pour toutes les opérations à mutation et à possibilité de mutation, COW_AtomicInt a toujours été plus mauvais que Plain. C'est normal et attendu.
2. La copie sur écriture devrait prévaloir quand il y a de nombreuses copies non modifiées, mais pour une longueur de chaîne moyenne de 50 :
a) Quand 33% de toutes les copies n'ont jamais été modifiées, et quand le reste n'a été modifié qu'une seule fois, COW_AtomicInt est toujours resté plus lent que Plain.
b) Quand 50% de toutes les copies n'ont jamais été modifiées, et quand le reste n'a été modifié que trois fois, COW_AtomicInt est toujours resté plus lent que Plain.
Ce résultat peut être plus surprenant pour beaucoup - en particulier que COW_AtomicInt est plus lent dans les cas où il y a davantage d'opérations de copie que d'opérations de mutation dans tout le système !
Notez que dans les deux cas, la copie sur écriture traditionnelle thread-unsafe marche mieux que l'attribut Plain. Cela montre qu'en fait la copie sur écriture peut être une optimisation pour des environnements mono-fils, mais elle convient moins souvent aux codes thread-safe.
3. C'est un mythe que le principal avantage de la copie sur écriture tienne à ce qu'on évite des allocations de mémoire. En particulier pour des chaînes relativement longues, le principal avantage de la copie sur écriture est qu'elle évite de copier les caractères dans la chaîne.
4. L'allocation optimisée, et non pas la copie sur écriture, a été une vraie optimisation cohérente de vitesse dans tous les cas (mais notez que cela se fait en échange d'espace). C'est peut-être ici la conclusion la plus importante du chapitre Mesures Détaillées :
"* L'essentiel des avantages fondamentaux de la copie sur écriture pour les chaînes courtes pourrait se gagner sans copie sur écriture en utilisant un allocateur plus efficace (bien sûr, on pourrait aussi faire les deux - utiliser la copie sur écriture et un allocateur efficace)"
Q. : Pourquoi mesurer quelque chose d'aussi inefficace que COW_CritSec ?
R. : Parce qu'au moins une implémentation commerciale populaire de basic_string a utilisé cette méthode pas plus tard qu'il y a un an (et peut-être le fait-elle encore - je n'ai pas vu leur code dernièrement), en dépit du fait que COW_CritSec est presque toujours une pessimisation. Vérifiez bien si votre vendeur de librairie le fait, parce que si la librairie est conçue pour un possible usage multi-fil, vous en paierez le prix en termes de performances tout le temps - même si votre programme est mono-fil.
Q. : Qu'est-ce que COW_AtomicInt2 ?
R. : C'est la même chose que COW_AtomicInt, sauf que qu'au lieu d'allouer un StringBuf puis allouer séparément le tampon de données, le StringBuf et les données sont dans le même bloc de mémoire alloué. Notez que toutes les autres variantes COW_* utilisent un allocateur rapide pour l'objet StringBuf (de sorte qu'il n'y a pas de coût injuste de "double allocation"), et le but de COW_AtomicInt2 est essentiellement de démonter que j'ai effectivement traité ce problème... COW_AtomicInt2 est effectivement légèrement plus lent que COW_AtomicInt pour la plupart des opérations (à cause de la logique supplémentaire).
J'ai aussi testé les performances relatives de diverses opérations sur les entiers (incrémentation d'entier, incrémentation d'entier volatil, et incrémentation d'entier par les opérations atomiques sur les entiers de Win32), pour vérifier que les résultats de COW_AtomicInt n'ont pas été biaisées par de mauvaises implémentations ou une perte de temps par suite d'appel de fonction.
III-A. APPROCHE▲
Pour estimer la copie sur écriture, j'ai effectué des mesures sur trois types de fonctions :
- la copie (où la copie sur écriture prévaut, c'est sa raison d'être)
- les opérations de mutation qui ne peuvent pas provoquer de réallocation (représentées par Append, qui allonge graduellement la chaîne ; ceci pour s'assurer que toute conclusion tirée peut prendre en compte la perte de temps périodique de réallocation due à l'utilisation normale de la chaîne)
- les opérations à possibilité de mutation qui ne changent pas assez la longueur de chaîne pour déclencher une réallocation, ou qui ne modifient pas effectivement la chaîne (représentées par operator[]).
Il s'avère que les deux derniers types subissent un coût constant (et similaire, à ~20%) par opération, et peut être grossièrement envisagés ensemble. En présumant, pour des besoins de simplicité, que des opérations de mutation et extension comme Append (perte de temps de 235 ms) et des opérations avec possibilité de mutation comme operator[] (perte de temps de 280 ms) seront à peu près aussi fréquentes les unes que les autres, la perte de temps de COW_AtomicInt pour les opérations à mutation et possibilité de mutation sera d'environ 260 ms pour 1.000.000 d'opérations dans cette implémentation.
Finalement, à chaque fois pour 2(a) et 2(b), j'ai d'abord utilisé le chapitre "Mesures brutes" ci-dessous pour calculer à la main une prédiction grossière des performances relatives attendues, puis j'ai fait tourner le test pour vérifier les performances réelles.
résumé pour le CAS 2(a) :
PRéDICTIONS
Coût de COW_AtomicInt Coût de Plain
------------------------- ----------------------
1M copies profondes 1M copies profondes
et dtors 400 et dtors 1600
667K mutations ??? ???
667K copies profondes 1060
perte de temps supplémentaire sur
667K copies profondes ???
perte de temps supplémentaire sur
667K mutations 175
----- -----
1635+ 1600+
TEST
(programme qui fait des copies dans une boucle, et
en modifie 33% avec un unique Append et
en modifie 33% (autres) avec un unique op[])
Faire tourner 1.000.000 d'itérations avec des chaînes de longueur 50:
Plain_FastAlloc 642ms copies: 1000000 allocs: 1000007
Plain 1726ms copies: 1000000 allocs: 1000007
COW_Unsafe 1629ms copies: 1000000 allocs: 666682
COW_AtomicInt 1949ms copies: 1000000 allocs: 666682
COW_AtomicInt2 1925ms copies: 1000000 allocs: 666683
COW_CritSec 10660ms copies: 1000000 allocs: 666682
COW_Mutex 33298ms copies: 1000000 allocs: 666682
résumé pour le CAS 2(b) :
PRéDICTIONS
Coût de COW_AtomicInt Coût de Plain
------------------------- ----------------------
1M copies profondes 1M copies profondes
et dtors 400 et dtors 1600
1.5M mutations ??? ???
500K copies profondes 800
perte de temps supplémentaire sur
500K copies profondes ???
perte de temps supplémentaire sur
1.5M mutations 390
----- -----
1590+ 1600+
TEST
(programme qui fait des copies dans une boucle, et
en modifie 25% avec trois Append et
en modifie 25% avec trois operator[])
Faire tourner 1.000.000 d'itérations avec des chaînes de longueur 50:
Plain_FastAlloc 683ms copies: 1000000 allocs: 1000007
Plain 1735ms copies: 1000000 allocs: 1000007
COW_Unsafe 1407ms copies: 1000000 allocs: 500007
COW_AtomicInt 1838ms copies: 1000000 allocs: 500007
COW_AtomicInt2 1700ms copies: 1000000 allocs: 500008
COW_CritSec 8507ms copies: 1000000 allocs: 500007
COW_Mutex 31911ms copies: 1000000 allocs: 500007III-B. MESURES BRUTES▲
TEST DE CONST COPYING + DESTRUCTION: Le cas cible de la copie sur écriture
Notes :
- Il a toujours fallu deux fois plus de temps à COW_AtomicInt pour créer et détruire une copie const que la copie sur écriture plain thread-unsafe.
- Pour chaque copie d'une chaîne qui a été ultérieurement modifiée,
COW_AtomicInt a ajouté une perte de temps constante irrécupérable
(400ms pour 1.000.000) sans compter la perte de temps sur les autres opérations.
* L'essentiel des avantages fondamentaux de la copie sur écriture pour les chaînes courtes pourrait se gagner sans copie sur écriture en utilisant un allocateur plus efficace (bien sûr, on pourrait aussi faire les deux - utiliser la copie sur écriture et un allocateur efficace)
* L'essentiel des avantages fondamentaux de la copie sur écriture pour les chaînes longues tient non pas dans le fait d'éviter les allocations, mais dans le fait d'éviter la copie de caractère.
En faisant tourner 1.000.000 itérations avec des chaînes de longueur 10:
Plain_FastAlloc 495ms copies: 1000000 allocs: 1000003
Plain 1368ms copies: 1000000 allocs: 1000003
COW_Unsafe 160ms copies: 1000000 allocs: 3
COW_AtomicInt 393ms copies: 1000000 allocs: 3
COW_AtomicInt2 433ms copies: 1000000 allocs: 4
COW_CritSec 428ms copies: 1000000 allocs: 3
COW_Mutex 14369ms copies: 1000000 allocs: 3
En faisant tourner 1.000.000 itérations avec des chaînes de longueur 50:
Plain_FastAlloc 558ms copies: 1000000 allocs: 1000007
Plain 1598ms copies: 1000000 allocs: 1000007
COW_Unsafe 165ms copies: 1000000 allocs: 7
COW_AtomicInt 394ms copies: 1000000 allocs: 7
COW_AtomicInt2 412ms copies: 1000000 allocs: 8
COW_CritSec 433ms copies: 1000000 allocs: 7
COW_Mutex 14130ms copies: 1000000 allocs: 7
En faisant tourner 1.000.000 itérations avec des chaînes de longueur 100:
Plain_FastAlloc 708ms copies: 1000000 allocs: 1000008
Plain 1884ms copies: 1000000 allocs: 1000008
COW_Unsafe 171ms copies: 1000000 allocs: 8
COW_AtomicInt 391ms copies: 1000000 allocs: 8
COW_AtomicInt2 412ms copies: 1000000 allocs: 9
COW_CritSec 439ms copies: 1000000 allocs: 8
COW_Mutex 14129ms copies: 1000000 allocs: 8
En faisant tourner 1.000.000 itérations avec des chaînes de longueur 250:
Plain_FastAlloc 1164ms copies: 1000000 allocs: 1000011
Plain 5721ms copies: 1000000 allocs: 1000011 [*]
COW_Unsafe 176ms copies: 1000000 allocs: 11
COW_AtomicInt 393ms copies: 1000000 allocs: 11
COW_AtomicInt2 419ms copies: 1000000 allocs: 12
COW_CritSec 443ms copies: 1000000 allocs: 11
COW_Mutex 14118ms copies: 1000000 allocs: 11
En faisant tourner 1.000.000 itérations avec des chaînes de longueur 1000:
Plain_FastAlloc 2865ms copies: 1000000 allocs: 1000014
Plain 4945ms copies: 1000000 allocs: 1000014
COW_Unsafe 173ms copies: 1000000 allocs: 14
COW_AtomicInt 390ms copies: 1000000 allocs: 14
COW_AtomicInt2 415ms copies: 1000000 allocs: 15
COW_CritSec 439ms copies: 1000000 allocs: 14
COW_Mutex 14059ms copies: 1000000 allocs: 14
En faisant tourner 1.000.000 itérations avec des chaînes de longueur 2500:
Plain_FastAlloc 6244ms copies: 1000000 allocs: 1000016
Plain 8343ms copies: 1000000 allocs: 1000016
COW_Unsafe 174ms copies: 1000000 allocs: 16
COW_AtomicInt 397ms copies: 1000000 allocs: 16
COW_AtomicInt2 413ms copies: 1000000 allocs: 17
COW_CritSec 446ms copies: 1000000 allocs: 16
COW_Mutex 14070ms copies: 1000000 allocs: 16
Test pour APPEND: Une opération avec mutation systématique et réallocation périodique
Notes :
- Plain a toujours été plus performant que la copie sur écriture
- La perte de temps de COW_AtomicInt comparé à Plain n'a pas beaucoup varié avec la longueur des chaînes : elle était à peu près constante à environ 235 ms pour 1.000.000 opérations.
- La perte de temps de COW_AtomicInt comparé à COW_Unsafe n'a pas beaucoup varié avec la longueur des chaînes : elle était à peu près constante à environ 110 ms pour 1.000.000 opérations.
* La meilleure performance obtenue pour les chaînes plus longues était due à la stratégie d'allocation (cf. GotW n°43), et pas aux problèmes de comparaison de copie sur écriture contre Plain.
En faisant tourner 1.000.000 itérations avec des chaînes de longueur 10:
Plain_FastAlloc 302ms copies: 0 allocs: 272730
Plain 565ms copies: 0 allocs: 272730
COW_Unsafe 683ms copies: 0 allocs: 272730
COW_AtomicInt 804ms copies: 0 allocs: 272730
COW_AtomicInt2 844ms copies: 0 allocs: 363640
COW_CritSec 825ms copies: 0 allocs: 272730
COW_Mutex 8419ms copies: 0 allocs: 272730
En faisant tourner 1.000.000 itérations avec des chaînes de longueur 50:
Plain_FastAlloc 218ms copies: 0 allocs: 137262
Plain 354ms copies: 0 allocs: 137262
COW_Unsafe 474ms copies: 0 allocs: 137262
COW_AtomicInt 588ms copies: 0 allocs: 137262
COW_AtomicInt2 536ms copies: 0 allocs: 156871
COW_CritSec 607ms copies: 0 allocs: 137262
COW_Mutex 7614ms copies: 0 allocs: 137262
En faisant tourner 1.000.000 itérations avec des chaînes de longueur 100:
Plain_FastAlloc 182ms copies: 0 allocs: 79216
Plain 257ms copies: 0 allocs: 79216
COW_Unsafe 382ms copies: 0 allocs: 79216
COW_AtomicInt 492ms copies: 0 allocs: 79216
COW_AtomicInt2 420ms copies: 0 allocs: 89118
COW_CritSec 535ms copies: 0 allocs: 79216
COW_Mutex 7810ms copies: 0 allocs: 79216
En faisant tourner 1.000.000 itérations avec des chaînes de longueur 250:
Plain_FastAlloc 152ms copies: 0 allocs: 43839
Plain 210ms copies: 0 allocs: 43839
COW_Unsafe 331ms copies: 0 allocs: 43839
COW_AtomicInt 438ms copies: 0 allocs: 43839
COW_AtomicInt2 366ms copies: 0 allocs: 47825
COW_CritSec 485ms copies: 0 allocs: 43839
COW_Mutex 7358ms copies: 0 allocs: 43839
En faisant tourner 1.000.000 itérations avec des chaînes de longueur 1000:
Plain_FastAlloc 123ms copies: 0 allocs: 14000
Plain 149ms copies: 0 allocs: 14000
COW_Unsafe 275ms copies: 0 allocs: 14000
COW_AtomicInt 384ms copies: 0 allocs: 14000
COW_AtomicInt2 299ms copies: 0 allocs: 15000
COW_CritSec 421ms copies: 0 allocs: 14000
COW_Mutex 7265ms copies: 0 allocs: 14000
En faisant tourner 1.000.000 itérations avec des chaînes de longueur 2500:
Plain_FastAlloc 122ms copies: 0 allocs: 6416
Plain 148ms copies: 0 allocs: 6416
COW_Unsafe 279ms copies: 0 allocs: 6416
COW_AtomicInt 380ms copies: 0 allocs: 6416
COW_AtomicInt2 304ms copies: 0 allocs: 6817
COW_CritSec 405ms copies: 0 allocs: 6416
COW_Mutex 7281ms copies: 0 allocs: 6416
Test pour OPERATOR[]: Une opération à possibilité de mutation, aucune mutation
Notes :
- Plain a toujours été largement plus performant que la copie sur écriture
- Les résultats ont été indépendants des longueurs de chaîne
- La perte de temps de COW_AtomicInt comparé à Plain a été constante à environ 280 ms pour 1.000.000 opérations.
- COW_AtomicInt2 a mieux marché dans ce cas de test, mais COW_AtomicInt marche globalement mieux, aussi je me concentre sur sa comparaison avec Plain.
[10x itérations] En faisant tourner 10.000.000 itérations avec des chaînes de longueur 10:
Plain_FastAlloc 3ms copies: 0 allocs: 3 [*]
Plain 2ms copies: 0 allocs: 3 [*]
COW_Unsafe 1698ms copies: 0 allocs: 3
COW_AtomicInt 2833ms copies: 0 allocs: 3
COW_AtomicInt2 2112ms copies: 0 allocs: 4
COW_CritSec 3587ms copies: 0 allocs: 3
COW_Mutex 71787ms copies: 0 allocs: 3
[*] dans la marge d'erreur de mesure, les deux mesures ont varié de 0ms à 9ms
TEST de différentes opérations d'INCRéMENTation/DéCREMENTation d'entiers
Résumé du test :
- "plain" effectue les opérations sur des entiers normaux non-volatiles
- "volatile" est le seul cas où utiliser des entiers volatiles
- "atomic" utilise les opérations Win32 InterlockedXxx
- "atomic_ass" utilise des opérations sur les entiers inline x86 assembler locked
Notes :
- ++atomic n'a pris que trois fois plus de temps que ++volatile et ++plain non-optimisé
- ++atomic ne subit aucune perte de temps par suite d'appel de fonction
[100x iterations] En faisant tourner 100.000.000 itérations avec des opérations sur des entiers :
++plain 2404ms, counter=100000000
--plain 2399ms, counter=0
++volatile 2400ms, counter=100000000
--volatile 2405ms, counter=0
++atomic 7480ms, counter=100000000
--atomic 9340ms, counter=0
++atomic_ass 8881ms, counter=100000000
--atomic_ass 10964ms, counter=0Voici quelques notes supplémentaires sur les chronométrages relatifs de différentes saveurs d'implémentation assembleur x86 de IntAtomicIncrement (ces chronométrages ont été pris dans les mêmes conditions que plus haut et peuvent être directement comparées) :
Instructions Timing
--------------------------- --------
__asm mov eax, 1
__asm lock xadd i, eax
__asm mov result, eax ~11000ms
__asm mov eax, 1
__asm lock xadd i, eax ~10400ms
__asm lock inc i ~8900ms
(c'est celui effectivement utilisé plus haut)Notez que les versions non-atomiques sont bien meilleures et correspondent directement aux chronométrages "plain" :
__asm inc i ~2400msConclusion : Il y a effectivement une perte de temps introduite par l'instruction x86 LOCK, même sur une machine à unité centrale unique. C'est naturel et il fallait s'y attendre, mais j'insiste sur ce point parce que certains ont dit qu'il n'y avait pas de différence.
Je suis très impressionné que InterlockedIncrement de Win32 soit effectivement plus rapide à 765 ms que mon assembleur codé à la main à 900 ms, même si ma version codée à la main fasse en réalité moins de travail (une seule instruction !) parce qu'il ne retourne pas la nouvelle valeur. Bien sûr, je ne suis pas un expert de l'assembleur x86 ; l'explication est certainement que le wrapper d'OS utilise un opcode différent de ma version codée à la main.
Finalement, bien sûr, notez que les fonctions entières atomiques de Win32 n'induisent clairement aucune perte de temps par suite d'appels de fonctions. Ne présumez jamais - mesurez.
Quelques points importants concernant cet équipement de test :
1. ATTENTION : Prenez-le pour ce qu'il est : Une ébauche de matériel de test. Les commentaires et les corrections sont les bienvenues. Je montre des chiffres de performances brutes ; je n'ai pas inspecté le code compilé, et je n'ai pas essayé de déterminer l'impact des cache hits et cache misses et autres effets secondaires (même ainsi, ce GotW a demandé beaucoup plus d'efforts que d'habitude, et je garantis que les prochains numéros présenteront des sujets plus simples !)
2. ("Il n'y a rien de mieux qu'un déjeuner gratuit" - R.A.Heinlein). Même avec des opérations atomiques sur les entiers, il est faux de dire "aucun verrouillage n'est nécessaire" parce que les opérations atomiques sur les entiers opèrent clairement une sérialisation et induisent une perte de temps significative.
3. L'équipement de test lui-même est MONO-FIL. Une implémentation de copie sur écriture thread-safe entraîne une perte de temps même sur des programmes qui ne sont pas eux-mêmes multi-fils. Au mieux, la copie sur écriture ne pourrait être une véritable optimisation que lorsque le code de copie sur écriture n'a pas du tout besoin d'être conçu multi-fil (même alors, reportez-vous au livre de Rob Murray : "C++ Strategies and Tactics", pages 70-72, pour y trouver d'autres tests empiriques qui montrent que la copie sur écriture n'est avantageuse que dans certaines situations). Si la thread safety est nécessaire, la copie sur écriture impose une perte significative de performances à tous les utilisateurs, même à ceux qui n'utilisent que des codes mono-fils.
Cliquez ici pour télécharger le code source de l'équipement de test.
IV. Remerciements▲
Cet article est une traduction en français par l'équipe de la rubrique C++ de l'article de Herb Sutter publié sur Guru of the Week. Vous pouvez retrouver cet article dans sa version originale sur le site de Guru of the Week : Reference Counting - Part III.