Comment implémenter Copy-on-Write?

Question

Je veux implémenter une copie sur écriture sur ma classe C++ String personnalisée, et je me demande comment ...

J'ai essayé d'implémenter quelques options, mais elles se sont révélées très inefficaces.

Merci les gars :-)

Answer 1

Dans un environemnt (ce qui est la plupart d'entre eux de nos jours) multi-thread est souvent une CoW énorme performance due plutôt qu'un gain. Et avec une utilisation prudente des références const, ce n'est pas vraiment un gain de performance, même dans un environnement à un seul thread.

Cet ancien article DDJ explique just how bad CoW can be in a multithreaded environment, even if there's only one thread.

En outre, comme d'autres personnes l'ont fait remarquer, les chaînes CoW sont très délicates à mettre en œuvre, et il est facile de faire des erreurs. Cela ajouté à leur mauvaise performance dans les situations de threading me fait vraiment douter de leur utilité en général. Cela devient encore plus vrai une fois que vous commencez à utiliser la construction de déplacement C++ 11 et l'affectation de déplacement.

Mais, pour répondre à votre question ....

Voici quelques techniques de mise en œuvre qui peuvent aider à la performance.

D'abord, stockez la longueur dans la chaîne elle-même. La longueur est accédée assez fréquemment et l'élimination du déréférencement du pointeur aiderait probablement. Je voudrais, par souci de cohérence, mettre la longueur allouée là aussi. Cela vous coûtera en termes de vos objets chaîne étant un peu plus gros, mais la surcharge dans l'espace et le temps de copie est très faible, d'autant plus que ces valeurs deviendront alors plus faciles pour le compilateur avec des astuces d'optimisation intéressantes.

Cela vous laisse avec une classe de chaîne qui ressemble à ceci:

class MyString { 
    ... 
private: 
    class Buf { 
     ... 
    private: 
     ::std::size_t refct_; 
     char *data_; 
    }; 

    ::std::size_t len_; 
    ::std::size_t alloclen_; 
    Buf *data_; 
}; 

Maintenant, il y a d'autres optimisations que vous pouvez effectuer. La classe Buf a l'air de ne pas contenir ou faire beaucoup, et c'est vrai. De plus, il faut allouer à la fois une instance de Buf et un buffer pour contenir les caractères. Cela semble plutôt inutile. Alors, nous allons maintenant passer à une technique de mise en œuvre commune C, tampons extensible:

class MyString { 
    ... 
private: 
    struct Buf { 
     ::std::size_t refct_; 
     char data_[1]; 
    }; 

    void resizeBufTo(::std::size_t newsize); 
    void dereferenceBuf(); 

    ::std::size_t len_; 
    ::std::size_t alloclen_; 
    Buf *data_; 
}; 

void MyString::resizeBufTo(::std::size_t newsize) 
{ 
    assert((data_ == 0) || (data_->refct_ == 1)); 
    if (newsize != 0) { 
     // Yes, I'm using C's allocation functions on purpose. 
     // C++'s new is a poor match for stretchy buffers. 
     Buf *newbuf = ::std::realloc(data_, sizeof(*newbuf) + (newsize - 1)); 
     if (newbuf == 0) { 
     throw ::std::bad_alloc(); 
     } else { 
     data_ = newbuf_; 
     } 
    } else { // newsize is 0 
     if (data_ != 0) { 
     ::std::free(data_); 
     data_ = 0; 
     } 
    } 
    alloclen_ = newsize; 
} 

Lorsque vous faites les choses de cette façon, vous pouvez alors traiter data_->data_ comme si elle contenait alloclen_ octets au lieu de seulement 1.

Gardez à l'esprit que dans tous ces cas, vous devrez vous assurer que vous ne l'utiliserez jamais dans un environnement multithread, ou que vous vous assurerez que refct_ est un type que vous avez à la fois un incrément atomique et un atome décrémenter et tester les instructions pour.

Il existe une technique d'optimisation encore plus avancée qui consiste à utiliser une union pour stocker des chaînes courtes dans les bits de données que vous utiliseriez pour décrire une chaîne plus longue. Mais c'est encore plus complexe, et je ne pense pas que je serai enclin à l'éditer pour mettre un exemple simplifié plus tard, mais on ne sait jamais.

Answer 2

Il n'y a pas grand-chose à CoW. Fondamentalement, vous copiez quand vous voulez le changer, et laissez quiconque qui ne veut pas le changer garde la référence à l'ancienne instance. Vous aurez besoin du comptage des références pour garder une trace de qui référence toujours l'objet, et puisque vous créez une nouvelle copie, vous devez diminuer le nombre sur l'ancienne instance.Un raccourci serait de ne pas faire une copie quand ce compte est un (vous êtes la seule référence). À part cela, il n'y a pas grand chose à dire, à moins qu'il y ait un problème spécifique auquel vous êtes confronté.

Answer 3

Il y a une série d'articles sur exactement cela sur le livre More Exceptional C++ de Herb Sutter. Si vous n'y avez pas accès, vous pouvez essayer de suivre les articles Internet: part 1, part 2 et part 3.

Answer 4

Vous pouvez émuler la chaîne 'immutable' que possèdent les autres langages (Python, C# pour autant que je sache). L'idée est que chaque chaîne est immuable, donc tout travail sur une chaîne crée une nouvelle chaîne immuable ... ou c'est l'idée de base, pour éviter l'explosion, il ne faudrait pas en créer une autre s'il y en a une similaire .

Answer 5

template <class T> struct cow { 
    typedef boost::shared_ptr<T> ptr_t; 
    ptr_t _data; 

    ptr_t get() 
    { 
    return boost::atomic_load(&_data); 
    } 

    void set(ptr_t const& data) 
    { 
    boost::atomic_store(&_data, data); 
    } 
} 

Answer 6

Je suggère que si l'on veut mettre en œuvre copie sur écriture efficace (pour les chaînes ou autre), on doit définir un type d'emballage qui se comporte comme une chaîne mutable, et qui tiendra à la fois un nullable référence à une chaîne mutable (aucune autre référence à cet élément n'existera jamais) et une référence nullable à une chaîne "immuable" (références à ce qui n'existera jamais en dehors des choses qui ne tenteront pas de le faire muter). Les wrappers seront toujours créés avec au moins une de ces références non nulles; Une fois que la référence de l'élément modifiable est définie sur une valeur non nulle (pendant ou après la construction), elle se rapportera toujours à la même cible. Chaque fois que les deux références sont non nulles, la référence immuable pointera vers une copie de l'article qui a été faite quelque temps après la mutation complète la plus récente (lors d'une mutation, la référence immuable peut ou non contenir une référence à une valeur de pré-mutation).

Pour lire un objet, vérifiez si la référence "mutable-item" est non nulle. Si oui, utilisez-le. Sinon, vérifiez si la référence "immutable-item" est non nulle. Si oui, utilisez-le. Sinon, utilisez la référence "mutable item" (qui sera désormais non nulle).

Pour muter un objet, vérifiez si la référence "mutable-item" est non nulle. Sinon, copiez la cible de la référence "élément immuable" et CompareExchange une référence au nouvel objet dans la référence "élément modifiable". Ensuite, muter la cible de la référence "mutable item" et invalider la référence "immutable item".

Pour cloner un objet, si le clone doit être cloné à nouveau avant d'être muté, récupérez la valeur de la référence "immutable-item". Si c'est null, faites une copie de la cible "mutable item" et CompareExchange une référence à ce nouvel objet dans la référence de l'élément immuable. Créez ensuite un nouveau wrapper dont la référence "mutable-item" est null, et dont la référence "immutable-item" est soit la valeur récupérée (si elle n'était pas nulle) ou le nouvel élément (si c'était le cas).

Pour cloner un objet, si le clone doit être muté avant d'être cloné, récupérez la valeur de la référence "immutable-item". Si null, récupérez la référence "mutable-item". Copiez la cible de la référence récupérée et créez un nouveau wrapper dont la référence "mutable-item" pointe vers la nouvelle copie et dont la référence "immutable-item" est null.

Les deux méthodes de clonage seront sémantiquement identiques, mais choisir la mauvaise pour une situation donnée entraînera une opération de copie supplémentaire. Si l'on choisit systématiquement l'opération de copie correcte, on obtiendra la plupart des avantages d'une approche "agressive" de copie sur écriture, mais avec beaucoup moins de frais généraux. Chaque objet de stockage de données (par exemple une chaîne de caractères) sera soit mutable sans partage, soit partagé de manière immuable, et aucun objet ne basculera jamais entre ces états.Par conséquent, on peut, si on le souhaite, éliminer tout "surcharge de threading/synchronisation" (en remplaçant les opérations CompareExchange par des mémoires directes) à condition qu'aucun objet wrapper ne soit utilisé simultanément dans plus d'un thread. Deux objets wrapper peuvent contenir des références au même détenteur de données immuable, mais ils pourraient être inconscients de l'existence des uns et des autres.

Notez que quelques opérations de copie supplémentaires peuvent être requises lors de l'utilisation de cette approche que lorsque vous utilisez une approche "agressive". Par exemple, si un nouveau wrapper est créé avec une nouvelle chaîne et que ce wrapper est muté et copié six fois, le wrapper d'origine contiendra des références au porteur de chaîne d'origine et une référence immuable contenant une copie des données. Les six enveloppes copiées contiendraient juste une référence à la chaîne immuable (deux chaînes au total, bien que si la chaîne originale n'était jamais mutée après que la copie ait été faite, une implémentation agressive pourrait s'en sortir avec un). Si le wrapper d'origine était muté, avec cinq des six copies, alors toutes les références à la chaîne immuable sauf une seraient invalidées. À ce stade, si la sixième copie de l'encapsuleur était mutée, une implémentation agressive de copie à l'écriture pouvait se rendre compte qu'elle contenait la seule référence à sa chaîne, et donc décider qu'une copie était inutile. L'implémentation que je décris, cependant, créerait une nouvelle copie mutable et abandonnerait l'immuable. Malgré le fait qu'il y ait quelques opérations de copie supplémentaires, cependant, la réduction du surdébit de filetage devrait, dans la plupart des cas, plus que compenser le coût. Si la majorité des copies logiques produites ne sont jamais mutées, cette approche peut être plus efficace que de toujours faire des copies de chaînes.