Guru Of the Week n° 43 : copie sur écriture - première partie

Difficulté : 4 / 10
La copie sur écriture est une optimisation courante (également appelée « lazy copy » et « copy on write »). Savez-vous comment la mettre en œuvre ?

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

N'hésitez pas à commenter cet article ! 6 commentaires Donner une note à l'article (5)

Article lu   fois.

Les deux auteurs

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

I. Problèmes

I-A. Question Junior

Considérez la classe String simplifiée suivante :

 
Sélectionnez
namespace Original {
    class String {
    public:
        String();                   // création avec tampon vide
        ~String();                  // effacement du tampon
        String( const String& );    // fait une copie complète
        void Append( char );        // ajoute un caractère
    private:
        char*    buf_;              // tampon alloué
        size_t   len_;              // taille du tampon
        size_t   used_;             // nombre de caractères actuellement utilisés
    };
}

C'est une simple classe String qui ne contient aucune optimisation spéciale. Quand vous copiez un Original::String, le nouvel objet alloue immédiatement son propre tampon et vous avez immédiatement deux objets complètements distincts.

Votre tâche : implémentez Original::String.

I-B. Question Guru

Malheureusement, il arrive que des copies de chaines soient faites, utilisées sans modification, puis supprimées. « Ça paraît dommage » pourrait maugréer l'implémenteur de Original::String, « que je fasse toujours tout le travail d'allocation du nouveau tampon (ce qui peut être coûteux) quand il s'avère que je n'en ai jamais besoin, si tout ce que fait l'utilisateur consiste à lire la nouvelle chaîne puis la détruire. Je pourrais me contenter de laisser les deux chaînes partager un même tampon sans le révéler, éviter la copie un moment, et ne vraiment faire une copie que quand je sais que j'en ai besoin, parce qu'un de ces objets est sur le point d'essayer de modifier la chaîne. De cette façon, si l'utilisateur ne modifie jamais la copie, je n'aurai jamais besoin de faire ce travail supplémentaire ! »

Avec un sourire sur son visage et de la détermination dans les yeux, l'implémenteur conçoit une Optimized::String qui utilise une implémentation avec copie sur écriture (également appelée « lazy copy » ou « copy on write ») :

 
Sélectionnez
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;              // nombre de 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
    private:
        StringBuf* data_;
    };
}

Votre tâche : implémenter Optimized::StringBuf et Optimized::String. Vous pourriez ajouter une fonction d'aide privée String::AboutToModify() pour simplifier la logique.

I-C. Notes de l'auteur

1. Je ne montre pas operator= parce que c'est essentiellement pareil à la construction de copie.

2. Le problème de ce GotW illustre incidemment un autre usage des espaces de noms, à savoir la clarté des exposés. Écrire le code ci-dessus a été beaucoup plus simple qu'écrire à propos de classes OriginalString et OptimizedString avec des noms différents (ce qui aurait rendu la lecture et l'écriture du code exemple un peu plus difficile). Par ailleurs, la syntaxe des espaces de noms est très naturelle ici dans les paragraphes d'exposition. Utiliser judicieusement les espaces de nom peut de la même façon améliorer la lisibilité de votre code de production et la possibilité d'en parler pendant les réunions et les passages en revue du code.

II. Solutions

II-A. Question Junior

Votre tâche : implémentez Original::String.

Voici une implémentation directe :

 
Sélectionnez
namespace Original {
 
    String::String() : buf_(0), len_(0), used_(0) { }
 
    String::~String() { delete[] buf_; }
 
    String::String( const String& other )
        : buf_(new char[other.len_]),
        len_(other.len_),
        used_(other.used_)
    {
        copy( other.buf_, other.buf_ + used_, buf_ );
    }

J'ai choisi d'implémenter une fonction d'aide supplémentaire Reserve pour plus de clarté, car d'autres mutateurs en auront besoin à côté de Append. Reserve garantit que notre tampon interne est long d'au moins n octets et alloue de l'espace supplémentaire en utilisant une stratégie de croissance exponentielle :

 
Sélectionnez
    void String::Reserve( size_t n ) {
        if( len_ < n ) {
            size_t newlen = max( len_ * 1.5, n );
            char*  newbuf = new char[ newlen ];
            copy( buf_, buf_+used_, newbuf );
 
            delete[] buf_;  // maintenant tout le travail est fait,
            buf_ = newbuf;  // alors, prenons la responsabilité
            len_ = newlen;
        }
    }
 
    void String::Append( char c ) {
        Reserve( used_+1 );
        buf_[used_++] = c;
    }
}

II-A-1. Incidemment : quelle est la meilleure stratégie de croissance de tampon ?

Quand un objet String devient trop gros pour le tampon auquel il est alloué à un moment donné, il lui faut demander l'allocation d'un tampon plus grand. La question clef est : « quelle taille doit avoir le nouveau tampon ? » [Note : L'analyse qui suit reste valable pour d'autres structures et containers qui utilisent des tampons alloués, comme le vector<> standard.]

Il existe plusieurs stratégies populaires. Je noterai la complexité de chaque stratégie en termes de nombre d'allocations requises et de nombre moyen de fois où un caractère donné doit être copié pour une chaîne de longueur éventuelle N.

II-A-1-a. Croissance exacte

Dans cette stratégie, le nouveau tampon est créé exactement aussi grand que nécessaire pour l'opération en cours. Par exemple, ajouter un caractère puis ajouter un autre forcera deux allocations ; d'abord, un nouveau tampon est alloué avec l'espace pour la chaîne existante et le premier nouveau caractère ; ensuite, un nouveau tampon est alloué avec l'espace pour la première allocation et le second nouveau caractère.

Avantage
Aucun espace perdu.

Inconvénient
Faible performance. Cette stratégie nécessite O(N) allocations et une moyenne de O(N) opérations de copie par caractère, mais avec un facteur constant élevé dans le plus mauvais cas (comme pour (b) avec une taille d'incrément de 1). Le contrôle du facteur constant est entre les mains du code d'utilisateur et n'est pas contrôlé par l'implémenteur de String.

II-A-1-b. Croissance par incrément fixe

Le nouveau tampon doit être plus grand d'un incrément fixe par rapport au tampon actuel. Par exemple, un incrément de 64 octets signifie que tous les tampons de chaîne seront longs d'un entier multiple de 64.

Avantage
Peu d'espace perdu. La quantité d'espace perdu dans le tampon est liée à la taille de l'incrément et ne varie pas avec la longueur de la chaîne.

Inconvénient
Performance modérée. Cette stratégie nécessite à la fois O(N) allocations et une moyenne de O(N) opérations de copie par caractère. Cela veut dire qu'à la fois le nombre d'allocations et le nombre moyen de fois où un caractère donné est copié varient linéairement avec la longueur de la chaîne. Toutefois, le contrôle du facteur constant est entre les mains de l'implémenteur de String.

II-A-1-c. Croissance exponentielle

Le nouveau tampon est un facteur F fois plus grand que le tampon actuel. Par exemple, avec F=0,5, ajouter un caractère à une chaîne entière déjà longue de 100 bytes allouera un nouveau tampon long de 150 bytes.

Avantage
Bonne performance. Cette stratégie nécessite O(logN) allocations et une moyenne de O(k) opérations de copie par caractère. Cela veut dire que le nombre d'allocations varie linéairement avec la longueur de la chaîne, mais que le nombre moyen de fois où un caractère donné est copié est constant (!), ce qui signifie que la quantité de travail de copie pour créer une chaîne en utilisant cette stratégie est supérieure d'au moins un facteur constant à la quantité de travail qui aurait été nécessaire si la taille de la chaîne avait été connue à l'avance.

Inconvénient
Perte d'espace. La quantité d'espace non utilisée dans le tampon sera toujours strictement inférieure à N*F octets, mais cela représente toujours une perte d'espace moyenne de O(N).

II-A-1-d. Tableau résumé

Le tableau suivant résume les termes :

 
Sélectionnez

  Stratégie de croissance  Allocations  Copies car.  Espace perdu
  -----------------------  -----------  -----------  ------------
 
  Exact                    O(N) avec    O(N) avec    aucun
                           const. élev. const. élev.
 
  Incrément fixe           O(N)         O(N)         O(k)
 
  Exponentielle            O(logN)      O(k)         O(N)

En général, la stratégie la plus performante est la croissance exponentielle. Considérez une chaîne qui débute vide et croît jusqu'à 1200 caractères. Une croissance à incrément fixe nécessite O(N) allocations et nécessite en moyenne de copier chaque caractère O(N) fois (dans ce cas, utiliser des incréments de 32 bytes, c'est-à-dire 38 allocations et une moyenne de 19 copies de chaque caractère). La croissance exponentielle nécessite O(logN) allocations mais en moyenne seulement O(k) - une ou deux - copies de chaque caractère (si, si, vraiment ! Voyez les références ci-dessous) ; dans ce cas, en utilisant un facteur de 1,5, cela donne 10 allocations et en moyenne 2 copies de chaque caractère.

 
Sélectionnez

               chaîne de 1200 carac.      chaîne de 12000 carac.
               ======================     =======================
               Croissance Croissance      Croissance  Croissance
               fixe       exponentielle   fixe       exponentielle
               (32 bytes)   (1.5x)        (32 bytes)    (1.5x)
               ---------- -----------     ----------  -----------
 
  allocations      38         10          380          16
  de mémoire
 
  nbre moyen       19          2          190           2
  de copies pour
  chaque caractère

Le résultat peut paraître surprenant. Pour plus d'informations, voyez l'article d'Andrew Koenig dans le numéro de septembre 1998 du JOOP (Journal of Object-Oriented Programming). Koenig montre également pourquoi, là aussi en général, le meilleur facteur de croissance n'est pas 2 mais plus probablement aux alentours de 1,5. Il montre aussi pourquoi le nombre moyen de fois où un caractère donné est copié est constant – c'est-à-dire ne dépend pas de la longueur de la chaîne.

II-B. Question Guru

Votre tâche : implémenter Optimized::StringBuf et Optimized::String. Vous pourriez ajouter une fonction d'aide privée String::AboutToModify() pour simplifier la logique.

D'abord, considérons StringBuf. Notez que la copie et l'assignation par défaut membre à membre n'ont pas de sens pour StringBuf, aussi les deux opérations doivent aussi être supprimées (déclarées comme privées et non définies).

 
Sélectionnez
namespace Optimized {
    StringBuf::StringBuf() : buf(0), len(0), used(0), refs(1) { }
 
    StringBuf::~StringBuf() { delete[] buf; }
 
    void StringBuf::Reserve( size_t n ) {
            if( len < n ) {
            size_t newlen = max( len * 1.5, n );
            char*  newbuf = new char[ newlen ];
            copy( buf, buf+used, newbuf );
 
            delete[] buf;   // maintenant tout le travail est fait,
            buf = newbuf;   // alors, prenons la responsabilité
            len = newlen;
        }
    }

Ensuite, considérons la classe String elle-même. Le constructeur et le destructeur par défaut sont faciles à mettre en œuvre :

 
Sélectionnez
String::String() : data_(new StringBuf) { }
 
    String::~String() {
        if( --data_->refs < 1 ) {
            delete data_;
        }
    }

Ensuite, nous écrivons le constructeur de copie pour implémenter la sémantique de « lazy copy » simplement en actualisant une copie sur écriture. Nous nous contenterons de séparer la représentation partagée si nous découvrons que nous avons besoin de modifier l'une des chaînes qui partagent ce tampon.

 
Sélectionnez
    String::String( const String& other )
        : data_(other.data_)
    {
        ++data_->refs;
    }

J'ai choisi d'implémenter une fonction d'aide supplémentaire AboutToModify pour plus de clarté, car d'autres mutateurs en auront besoin à côté de Append. AboutToModify garantit que nous avons une copie non partagée du tampon interne, c'est-à-dire qu'il effectue la « lazy copy » si elle n'a pas déjà été effectuée. Par commodité, AboutToModify prend une taille de tampon minimale, de sorte que nous ne prendrons pas inutilement notre propre copie d'une chaîne entière juste pour effectuer immédiatement une seconde allocation pour obtenir plus d'espace.

 
Sélectionnez
    void String::AboutToModify( size_t n ) {
        if( data_->refs > 1 ) {
            auto_ptr<StringBuf> newdata( new StringBuf );
            newdata.get()->Reserve( max( data_->len, n ) );
            copy( data_->buf, data_->buf + data_->used, newdata.get()->buf );
            newdata.get()->used = data_->used;
 
            --data_->refs;             // maintenant tout le travail est fait,
            data_ = newdata.release(); // alors, prenons la responsabilité
        }
        else {
            data_->Reserve( n );
        }
    }
 
    void String::Append( char c ) {
        AboutToModify( data_->used+1 );
        data_->buf[data_->used++] = c;
    }
}

III. 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 IReference Counting - Part I.

Merci à _Max_ pour sa relecture orthographique.

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

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.