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

Considérez la classe String simplifiée suivante :

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.

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 ») :

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.

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.

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

Voici une implémentation directe :

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 :

    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 ?▲

  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)

               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

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).

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 :

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.

    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.

    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;
    }
}