♪
I. Problème▲
Considérons la classe copiée sur écriture Optimized::String de GotW n°43, mais avec deux nouvelles fonctions : Length() et operator[].
namespace Optimized {
struct StringBuf {
StringBuf(); // démarrage à vide
~StringBuf(); // effacement du tampon
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
};
class String {
public:
String(); // démarrage à vide
~String(); // décrément du comptage de référence
// (efface le tampon si refs==0)
String( const String& ); // pointe sur le même tampon et
// incrémente le comptage de référence
void Append( char ); // ajoute un caractère
size_t Length() const; // longueur de chaîne
char& operator[](size_t);// accès élément
private:
void AboutToModify( size_t n );
// lazy copy, garantit len>=n
StringBuf* data_;
};
}Cela permet des codes comme le suivant :
if( s.Length() > 0 ) {
cout << s[0];
s[0] = 'a';
}II. Questions Guru▲
1. Implémentez les nouveaux membres de Optimized::String.
2. Faut-il changer un des autres membres à cause des fonctions du nouveau membre ? Expliquez.
III. Solution▲
Considérons la classe copiée sur écriture Optimized::String de Guru Of the Week n° 43 : copie sur écriture - première partie, mais avec deux nouvelles fonctions : Length() et operator[].
L'objet de ce Guru Of the Week est de démontrer pourquoi ajouter operator[] change assez la sémantique de Optimized::String pour avoir un impact sur d'autres parties de la classe. Mais pour commencer :
III-A. Implémentez les nouveaux membres de Optimized::String.▲
La fonction Length() est simple :
namespace Optimized {
size_t String::Length() const {
return data_->used;
}Néanmoins, il n'y a pas que operator[] qui attire l'œil. Dans ce qui suit, ce que je veux que vous remarquiez est que ce que operator[] fait (il retourne une référence dans la chaîne) n'est vraiment pas différent de ce que font begin() et end() aux chaînes standards (qui retournent des itérateurs qui « pointent sur » la chaîne). Toute implémentation de copie sur écriture de std::basic_string sera l'objet des mêmes considérations que ce que nous faisons ci-dessous.
III-A-1. Écrire operator[] pour des chaînes partageables▲
Voici une première tentative naïve :
// mauvaise : tentative naïve n° 1 sur operator[]
//
char& String::operator[]( size_t n ) {
return *(data_->buf+n);
}Ce n'est pas assez bon à long terme. Considérons :
// exemple 1a : pourquoi la tentative n° 1 ne marche pas
//
void f( Optimized::String& s ) {
Optimized::String s2( s ); // fait une copie de la chaîne
s[0] = 'x'; // oups : modifie aussi s2 !
}Vous pourriez penser que le pauvre programmeur de l'exemple 1a serait un peu malheureux de cet effet secondaire. Vous auriez raison.
Aussi, en définitive, nous aurions intérêt à nous assurer que la chaîne n'est pas partagée, sinon celui qui l'appellera risque de modifier par inadvertance ce qui lui semblera être deux chaînes sans rapport l'une avec l'autre. « Ah ah » pensera le programmeur naïf. « Je vais appeler AboutToModify() pour m'assurer que j'utilise une représentation non partagée » :
// mauvais : tentative inadéquate n° 2 sur operator[]
//
char& String::operator[]( size_t n ) {
AboutToModify( data_->len );
return *(data_->buf+n);
}Cela a l'air bon, mais pas encore assez. Le problème est que nous avons besoin de réarranger que légèrement le code de l'exemple 1a pour revenir à la même situation qu'avant :
// exemple 2a : pourquoi la tentative n° 2 ne marche pas non plus
//
void f( Optimized::String& s ) {
char& rc = s[0]; // prend une référence au premier caractère
Optimized::String s2( s ); // fait une copie de la chaîne
rc = 'x'; // oups : modifie aussi s2 !
}Vous pensez peut-être que le pauvre programmeur de l'exemple 2a serait un peu perturbé par cette surprise, là aussi. Vous auriez raison, mais en ce qui concerne cette écriture, certaines implémentations populaires de basic_string comportent précisément ce bug lié à la copie sur écriture.
Le problème est que la référence a été extraite alors que la chaîne d'origine n'était pas partagée, mais ensuite la chaîne est devenue partagée et l'actualisation unique par la référence a modifié l'état visible des deux objets chaîne.
III-A-2. Notion clef : une chaîne « impartageable »▲
Quand on appelle operator[], en plus de l'extraction d'une copie non partagée de StringBuf, on a aussi besoin de marquer la chaîne comme « impartageable », juste au cas où l'utilisateur se souviendrait de la référence (et essaierait de l'utiliser par la suite).
Maintenant, marquer la chaîne « impartageable tout le temps » fonctionnera, mais en fait c'est un peu excessif : il s'avère que tout ce dont nous avons vraiment besoin est de marquer la chaîne « impartageable pour un moment ». Pour voir où je veux en venir, considérez qu'il est déjà vrai que les références retournées par operator[] dans la chaîne doivent être considérées comme invalides après la prochaine opération de mutation. Cela veut dire qu'un code comme celui-ci :
// exemple 3 : pourquoi les références sont invalidées
// par les opérations de mutation
//
void f( Optimized::String& s ) {
char& rc = s[0];
s.Append( 'i' );
rc = 'x'; // erreur : oups, le tampon pourrait avoir changé
} // si s a fait une réallocationdevrait déjà être documenté comme invalide, que la chaîne utilise ou non la copie sur écriture. En bref, appeler un mutateur invalide clairement des références dans la chaîne parce qu'on ne sait jamais si la mémoire sous-jacente ne risque pas de bouger (de façon invisible, du point de vue du code appelant).
Ceci étant, dans l'exemple 2a, rc serait invalidé de toute façon par l'opération de mutation suivante sur s. Ainsi, au lieu de marquer s comme « impartageable tout le temps » juste parce que quelqu'un pourrait y avoir rappelé une référence, nous pourrions juste le marquer « impartageable jusqu'après la prochaine opération de mutation » quand le rappel d'une telle référence serait invalidé de toute façon. Pour l'utilisateur, le comportement documenté est le même.
III-B. Faut-il changer un des autres membres à cause des fonctions du nouveau membre ? Expliquez.▲
Comme on peut le voir maintenant, la réponse est oui.
D'abord, nous avons besoin de pouvoir nous souvenir si une chaîne donnée est actuellement « impartageable » (afin que nous n'utilisions pas la copie sur écriture quand nous la copierons). Nous pourrions insérer un flag booléen, mais pour éviter une perte de temps, contentons-nous d'encoder directement l'état « impartageable » dans le compteur refs en convenant que « refs est le plus grand entier non signé qu'il puisse y avoir » signifie « impartageable ». Nous ajouterons également un registre à AboutToModify() pour dire s'il faut marquer la chaîne comme « impartageable ».
// bon : tentative correcte n°3 sur operator[]
//
// Ajoutez un nouveau membre statique par commodité et
// changez AboutToModify de façon appropriée. Parce que
// maintenant nous allons avoir besoin de cloner un StringBuf
// dans plus d'une fonction (cf. le constructeur de copies de
// chaînes, ci-dessous), nous allons aussi porter cette
// logique dans une fonction unique... il était temps pour
// StringBuf d'avoir son propre constructeur de copie, de
// toute façon
//
size_t String::Unshareable = numeric_limits<unsigned>::max();
StringBuf::StringBuf( const StringBuf& other, size_t n )
: buf(0), len(0), used(0), refs(1)
{
Reserve( max( other.len, n ) );
copy( other.buf, other.buf+other.used, buf );
used = other.used;
}
void String::AboutToModify(
size_t n,
bool bMarkUnshareable /* = false */
) {
if( data_->refs > 1 && data_->refs != Unshareable ) {
StringBuf* newdata = new StringBuf( *data_, n );
--data_->refs; // maintenant, le vrai travail est fait,
data_ = newdata; // alors récupérons la responsabilité
} else {
data_->Reserve( n );
}
data_->refs = bMarkUnshareable ? Unshareable : 1;
}
char& String::operator[]( size_t n ) {
AboutToModify( data_->len, true );
return *(data_->buf+n);
}Notez que tous les autres appels à AboutToModify() continuent à fonctionner comme il a été écrit à l'origine.
Maintenant, tout ce dont nous avons besoin est de faire en sorte que le constructeur de copies de la chaîne respecte l'état « impartageable », quand il est établi :
String::String( const String& other )
{
// Si possible, utilisez la copie sur écriture.
// Sinon, faites une copie profonde immédiatement.
//
if( other.data_->refs != Unshareable ) {
data_ = other.data_;
++data_->refs;
} else {
data_ = new StringBuf( *other.data_ );
}
}Le destructeur a besoin d'un petit coup de pouce :
String::~String() {
if( data_->refs == Unshareable || --data_->refs < 1 ) {
delete data_;
}
}Toutes les autres fonctions (les deux !) fonctionnent comme elles ont été écrites à l'origine :
String::String() : data_(new StringBuf) { }
void String::Append( char c ) {
AboutToModify( data_->used+1 );
data_->buf[data_->used++] = c;
}
}Et c'est tout (!). Dans le GotW final de cette minisérie sur la copie sur écriture, nous envisagerons comment le multithreading affecte notre chaîne avec copie sur écriture. Voir Guru Of the Week n° 45 : copie sur écriture - troisième partie pour les détails croustillants.
Voilà le code tout entier.
Notez que j'ai aussi saisi l'occasion d'implémenter un léger changement à StringBuf::Reserve(). À présent, il arrondit la « nouvelle taille de tampon » choisie au multiple de quatre supérieur, afin de garantir que la taille de la mémoire tampon sera toujours un multiple de quatre bytes. Ceci au nom de l'efficacité : beaucoup de systèmes d'exploitation parmi les plus populaires n'allouent pas la mémoire en fragments plus petits que cela de toute façon et ce code est plus rapide que le code d'origine, en particulier pour les petites chaînes (le code d'origine allouerait un tampon de 1 byte, puis un tampon de 2 bytes, puis un tampon de 3 bytes, puis un tampon de 4 bytes, puis un tampon de 6 bytes avant que la stratégie de croissance exponentielle puisse vraiment démarrer. Le code ci-dessous va directement au tampon de 4 bytes, puis au tampon de 8 bytes, etc.)
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
};
class String {
public:
String(); // démarrage à vide
~String(); // décrément du comptage de référence
// (efface le tampon si refs==0)
String( const String& ); // pointe sur le même tampon et
// incrémente le comptage de référence
void Append( char ); // ajoute un caractère
size_t Length() const; // longueur de chaîne
char& operator[](size_t);// accès élément
private:
void AboutToModify( size_t n, bool bUnshareable = false );
// lazy copy, garantit len>=n
// et marque si impartageable
static size_t Unshareable;// ref-count flag pour "impartageable"
StringBuf* data_;
};
StringBuf::StringBuf() : buf(0), len(0), used(0), refs(1) { }
StringBuf::~StringBuf() { delete[] buf; }
StringBuf::StringBuf( const StringBuf& other, size_t n )
: buf(0), len(0), used(0), refs(1)
{
Reserve( max( other.len, n ) );
copy( other.buf, other.buf+other.used, buf );
used = other.used;
}
void StringBuf::Reserve( size_t n ) {
if( len < n ) {
// Même code de croissance que dans GotW n°43, sauf que l'on
// arrondit la nouvelle taille au plus proche multiple supérieur
// de 4 bytes.
size_t needed = max<size_t>( len*1.5, n );
size_t newlen = needed ? 4 * ((needed-1)/4 + 1) : 0;
char* newbuf = newlen ? new char[ newlen ] : 0;
if( buf ) {
copy( buf, buf+used, newbuf );
}
delete[] buf; // maintenant tout le travail est fait,
buf = newbuf; // alors, prenons possession
len = newlen;
}
}
size_t String::Unshareable = numeric_limits<unsigned>::max();
String::String() : data_(new StringBuf) { }
String::~String() {
if( data_->refs == Unshareable || --data_->refs < 1 ) {
delete data_;
}
}
String::String( const String& other )
{
// Si possible, utilisez la copie sur écriture.
// Sinon, faites une copie profonde immédiatement.
//
if( other.data_->refs != Unshareable ) {
data_ = other.data_;
++data_->refs;
} else {
data_ = new StringBuf( *other.data_ );
}
}
void String::AboutToModify(
size_t n,
bool bMarkUnshareable /* = false */
) {
if( data_->refs > 1 && data_->refs != Unshareable ) {
StringBuf* newdata = new StringBuf( *data_, n );
--data_->refs; // 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);
}
}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 II.
Merci à Torgar pour sa relecture orthographique.