Guru Of the Week n° 45 : copie sur écriture - troisième partie

| Herb Sutter | Traduction par l'équipe de la rubrique C++ |

Difficulté : 9 / 10
Dans ce dernier chapitre de cette mini-série, nous envisagerons les effets de la thread safety (sécurité des fils d'exécution) sur les chaînes à copie sur écriture. La copie sur écriture est-elle vraiment une optimisation ? La réponse va sûrement vous surprendre.

Retrouver l'ensemble des Guru of the Week sur la page d'index.

N'hésitez pas à commenter cet article ! Commentez

- Titre : Guru Of the Week n° 45 : copie sur écriture - troisième partie

- Auteurs : Herb Sutter, Traduction par l'équipe de la rubrique C++

- Parution : 13 septembre 2012

- Licence : Copyright ® 2009 Herb Sutter. 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.

Sommaire

- I. Problème

- I-A. Question JG

- I-B. Questions Guru

- II. Solution

- II-A. Introduction

- II-B. 1. Pourquoi Optimized::String n'est-il pas sûr du point de vue de la thread safety ? Donnez des exemples.

- II-C. 2. Démontrez comment créer une Optimized::String (à partir de GotW n°44 ) avec thread safety :

- III. Quelques résultats empiriques

- III-A. APPROCHE

- III-B. MESURES BRUTES

- IV. Remerciements

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ée

Je 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:  500007

III-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=0

Voici 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                      ~2400ms

Conclusion : 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.