Légalité de l'implémentation COW std :: string en C ++ 11

117

J'avais cru comprendre que la copie sur écriture n'était pas un moyen viable d'implémenter une conformité std::stringen C ++ 11, mais lors de la discussion récente, je me suis retrouvé incapable de soutenir directement cette déclaration.

Ai-je raison de dire que C ++ 11 n'admet pas les implémentations basées sur COW std::string?

Si tel est le cas, cette restriction est-elle explicitement énoncée quelque part dans la nouvelle norme (où)?

Ou est-ce que cette restriction est implicite, en ce sens que c'est l'effet combiné des nouvelles exigences sur ce std::stringqui empêche une mise en œuvre basée sur le COW de std::string. Dans ce cas, je serais intéressé par une dérivation de style chapitre et vers de «C ++ 11 interdit effectivement les std::stringimplémentations basées sur COW ».

acm
la source
5
Le bogue GCC pour leur chaîne COW est gcc.gnu.org/bugzilla/show_bug.cgi?id=21334#c45 . L'un des bogues de suivi d'une nouvelle implémentation compilante C ++ 11 de std :: string dans libstdc ++ est gcc.gnu.org/bugzilla/show_bug.cgi?id=53221
user7610

Réponses:

120

Ce n'est pas autorisé, car selon la norme 21.4.1 p6, l'invalidation des itérateurs / références n'est autorisée que pour

- comme argument de toute fonction de bibliothèque standard prenant une référence à chaîne_basique non const comme argument.

- Appel de fonctions membres non const, à l'exception de l'opérateur [], at, front, back, begin, rbegin, end et rend.

Pour une chaîne COW, l'appel non-const operator[]nécessiterait de faire une copie (et d'invalider les références), ce qui est interdit par le paragraphe ci-dessus. Par conséquent, il n'est plus légal d'avoir une chaîne COW dans C ++ 11.

Dave S
la source
4
Quelques justifications: N2534
MM
8
-1 La logique ne tient pas la route. Au moment d'une copie COW, il n'y a pas de références ou d'itérateurs qui peuvent être invalidés, tout l'intérêt de faire la copie est que de telles références ou itérateurs sont maintenant en cours d'obtention, donc une copie est nécessaire. Mais il se peut que C ++ 11 n'autorise pas les implémentations COW.
Acclamations et hth. - Alf
11
@ Cheersandhth.-Alf: La logique peut être vue dans ce qui suit si COW était autorisé: std::string a("something"); char& c1 = a[0]; std::string b(a); char& c2 = a[1]; c1 est une référence à a. Vous «copiez» ensuite un fichier. Ensuite, lorsque vous essayez de prendre la référence la deuxième fois, il doit effectuer une copie pour obtenir une référence non-const car il y a deux chaînes qui pointent vers le même tampon. Cela devrait invalider la première référence prise et va à l'encontre de la section citée ci-dessus.
Dave S
9
@ Cheersandhth.-Alf, d'après cela , au moins l'implémentation COW de GCC fait exactement ce que DaveS dit. Donc au moins ce style de VACHE est interdit par la norme.
Tavian Barnes
4
@Alf: Cette réponse soutient que non-const operator[](1) doit faire une copie et que (2) il est illégal de le faire. Lequel de ces deux points êtes-vous en désaccord? En regardant votre premier commentaire, il semble qu'une implémentation pourrait partager la chaîne, au moins selon cette exigence, jusqu'au moment où elle est accédée, mais que les accès en lecture et en écriture devraient la retirer. Est-ce votre raisonnement?
Ben Voigt
48

Les réponses de Dave S et gbjbaanb sont correctes . (Et celle de Luc Danton est correcte aussi, bien que ce soit plus un effet secondaire de l'interdiction des cordes COW plutôt que la règle originale qui l'interdit.)

Mais pour dissiper une certaine confusion, je vais ajouter un exposé supplémentaire. Divers commentaires renvoient à un de mes commentaires sur le bugzilla GCC qui donne l'exemple suivant:

std::string s("str");
const char* p = s.data();
{
    std::string s2(s);
    (void) s[0];
}
std::cout << *p << '\n';  // p is dangling

Le but de cet exemple est de démontrer pourquoi la chaîne de référence comptée (COW) de GCC n'est pas valide en C ++ 11. La norme C ++ 11 nécessite que ce code fonctionne correctement. Rien dans le code ne permet pd'invalider le dans C ++ 11.

En utilisant l'ancienne std::stringimplémentation comptée par référence de GCC , ce code a un comportement indéfini, car il p est invalidé, devenant un pointeur pendant. (Ce qui se passe, c'est que lorsqu'il s2est construit, il partage les données avec s, mais l'obtention d'une référence non-const via s[0]nécessite que les données ne soient pas partagées, de même squ'une "copie à l'écriture" car la référence s[0]pourrait potentiellement être utilisée pour écrire s, puis s2va hors de portée, détruisant le tableau pointé par p).

Le standard C ++ 03 autorise explicitement ce comportement dans 21.3 [lib.basic.string] p5 où il dit que suite à un appel au data()premier appel àoperator[]() peut invalider les pointeurs, références et itérateurs. La chaîne COW de GCC était donc une implémentation C ++ 03 valide.

La norme C ++ 11 n'autorise plus ce comportement, car aucun appel à ne operator[]()peut invalider les pointeurs, références ou itérateurs, qu'ils suivent ou non un appel à data().

Ainsi, l'exemple ci-dessus doit fonctionner en C ++ 11, mais ne fonctionne pas avec le type de chaîne COW de libstdc ++, par conséquent, ce type de chaîne COW n'est pas autorisé dans C ++ 11.

Jonathan Wakely
la source
3
Une implémentation qui se libère lors de l'appel à .data()(et à chaque retour de pointeur, référence ou itérateur) ne souffre pas de ce problème. Ie (invariant) un buffer est à tout moment non partagé, ou bien partagé sans refs externes. Je pensais que vous aviez prévu le commentaire sur cet exemple comme un rapport de bogue informel sous forme de commentaire, désolé de l'avoir mal compris! Mais comme vous pouvez le voir en considérant une telle implémentation que je décris ici, qui fonctionne bien en C ++ 11 lorsque les noexceptexigences sont ignorées, l'exemple ne dit rien sur le formel. Je peux fournir du code si vous le souhaitez.
Acclamations et hth. - Alf
7
Si vous annulez le partage sur presque tous les accès à la chaîne, vous perdez tous les avantages du partage. Une implémentation COW doit être pratique pour qu'une bibliothèque standard se soucie de l'utiliser comme std::string, et je doute sincèrement que vous puissiez démontrer une chaîne COW utile et performante qui répond aux exigences d'invalidation C ++ 11. Je soutiens donc que les noexceptspécifications qui ont été ajoutées à la dernière minute sont une conséquence de l'interdiction des chaînes COW, pas la raison sous-jacente. N2668 semble parfaitement clair, pourquoi continuez-vous à nier la preuve claire de l'intention du comité qui y est exposée?
Jonathan Wakely
Souvenez-vous également qu'il data()s'agit d'une fonction membre const, il doit donc être sûr d'appeler simultanément avec d'autres membres const, et par exemple d'appeler data()simultanément avec un autre thread effectuant une copie de la chaîne. Donc, vous allez avoir besoin de toute la surcharge d'un mutex pour chaque opération de chaîne, même celles const, ou de la complexité d'une structure comptée de références mutables sans verrouillage, et après tout cela vous n'obtiendrez le partage que si vous ne modifiez ou n'accédez jamais vos chaînes, tant, beaucoup de chaînes auront un nombre de références de un. Veuillez fournir le code, n'hésitez pas à ignorer les noexceptgaranties.
Jonathan Wakely
2
Je viens de bricoler du code maintenant, j'ai découvert qu'il y avait 129 basic_stringfonctions membres, plus des fonctions gratuites. Coût d'abstraction: ce code de version zéro frais non optimisé prêt à l'emploi est 50 à 100% plus lent avec g ++ et MSVC. Cela ne fait pas la sécurité des threads (assez facile à exploiter shared_ptr, je pense) et c'est juste assez pour prendre en charge le tri d'un dictionnaire à des fins de synchronisation, mais modulo bogues, cela prouve le fait qu'une référence comptée basic_stringest autorisée, sauf pour les noexceptexigences C ++ . github.com/alfps/In-principle-demo-of-ref-counted-basic_string
Acclamations et hth. - Alf
1
Continuons cette discussion en chat .
Jonathan Wakely
20

C'est vrai, CoW est un mécanisme acceptable pour faire des cordes plus rapides ... mais ...

cela rend le code multithreading plus lent (tout ce verrouillage pour vérifier si vous êtes le seul à écrire tue les performances lorsque vous utilisez beaucoup de chaînes). C'était la principale raison pour laquelle CoW a été tué il y a des années.

Les autres raisons sont que l' []opérateur vous renverra les données de chaîne, sans aucune protection pour vous permettre d'écraser une chaîne que quelqu'un d'autre s'attend à ne pas changer. Il en va de même pour c_str()et data().

Quick google dit que le multithreading est essentiellement la raison pour laquelle il a été effectivement interdit (pas explicitement).

La proposition dit:

Proposition

Nous proposons de rendre toutes les opérations d'accès aux itérateurs et aux éléments exécutables simultanément en toute sécurité.

Nous augmentons la stabilité des opérations même en code séquentiel.

Cette modification interdit effectivement les implémentations de copie sur écriture.

suivi par

La plus grande perte potentielle de performances due à un abandon des implémentations de copie sur écriture est la consommation accrue de mémoire pour les applications avec de très grandes chaînes de lecture principalement. Cependant, nous pensons que pour ces applications, les cordes sont une meilleure solution technique et nous recommandons qu'une proposition de corde soit envisagée pour inclusion dans la bibliothèque TR2.

Les cordes font partie de STLPort et SGIs STL.

gbjbaanb
la source
2
Le problème de l'opérateur [] n'est pas vraiment un problème. La variante const offre une protection, et la variante non const a toujours la possibilité de faire le CoW à ce moment-là (ou d'être vraiment fou et de configurer une erreur de page pour la déclencher).
Christopher Smith
+1 Va aux problèmes.
Acclamations et hth. - Alf
5
c'est juste idiot qu'une classe std :: cow_string ne soit pas incluse, avec lock_buffer (), etc. il y a beaucoup de fois que je sais que le threading n'est pas un problème. le plus souvent, en fait.
Erik Aronesty
J'aime la suggestion d'une alternative, les cordes ig. Je me demande s'il existe d'autres types d'alternatives et implémentations disponibles.
Voltaire
5

Depuis 21.4.2 constructeurs basic_string et opérateurs d'affectation [string.cons]

basic_string(const basic_string<charT,traits,Allocator>& str);

[...]

2 Effets : Construit un objet de classe basic_stringcomme indiqué dans le Tableau 64. [...]

Le tableau 64 documente utilement qu'après la construction d'un objet via ce constructeur (copie), this->data()a pour valeur:

pointe sur le premier élément d'une copie allouée du tableau dont le premier élément est pointé par str.data ()

Il existe des exigences similaires pour d'autres constructeurs similaires.

Luc Danton
la source
+1 Explique comment C ++ 11 (au moins partiellement) interdit COW.
Acclamations et hth. - Alf
Désolé, j'étais fatigué. Cela n'explique rien de plus qu'un appel de .data () doit déclencher la copie COW si le tampon est actuellement partagé. C'est toujours des informations utiles, alors je laisse le vote favorable.
Acclamations et hth. - Alf
1

Comme il est maintenant garanti que les chaînes sont stockées de manière contiguë et que vous êtes maintenant autorisé à prendre un pointeur vers le stockage interne d'une chaîne, (c'est-à-dire que & str [0] fonctionne comme il le ferait pour un tableau), il n'est pas possible de créer une COW utile la mise en oeuvre. Vous auriez à faire une copie pour beaucoup trop de choses. Même simplement utiliser operator[]ou begin()sur une chaîne non const exigerait une copie.

Dirk Holsopple
la source
1
Je pense que les chaînes en C ++ 11 sont garanties d'être stockées de manière contiguë.
mfontanini
4
Dans le passé, vous deviez faire les copies dans toutes ces situations et ce n'était pas un problème ...
David Rodríguez - dribeas
@mfontanini oui, mais ils ne l'étaient pas auparavant
Dirk Holsopple
3
Bien que C ++ 11 garantisse que les chaînes sont contiguës, c'est orthogonal à l'interdiction des chaînes COW. La chaîne COW de GCC est contiguë, donc clairement votre affirmation selon laquelle "il n'est pas possible de faire une implémentation COW utile" est faux.
Jonathan Wakely
1
@supercat, demander le magasin de sauvegarde (par exemple en appelant c_str()) doit être O (1) et ne peut pas lancer, et ne doit pas introduire de courses de données, il est donc très difficile de répondre à ces exigences si vous concaténez paresseusement. En pratique, la seule option raisonnable est de toujours stocker des données contiguës.
Jonathan Wakely
1

COW est-il basic_stringinterdit dans C ++ 11 et versions ultérieures?

En ce qui concerne

Ai-je raison de dire que C ++ 11 n'admet pas les implémentations basées sur COW std::string?

Oui.

En ce qui concerne

» Si tel est le cas, cette restriction est-elle explicitement énoncée quelque part dans la nouvelle norme (où)?

Presque directement, par des exigences de complexité constante pour un certain nombre d'opérations qui nécessiteraientune copie physiqueO ( n ) des données de chaîne dans une mise en œuvre COW.

Par exemple, pour les fonctions membres

auto operator[](size_type pos) const -> const_reference;
auto operator[](size_type pos) -> reference;

… Qui, dans une implémentation COW, déclencherait à la fois la copie de données de chaîne pour annuler le partage de la valeur de chaîne, le standard C ++ 11 exige

C ++ 11 §21.4.5 / 4 :

« Complexité: temps constant.

… Qui exclut une telle copie de données, et donc COW.

C ++ 03 pris en charge les implémentations COW par ne pas avoir ces exigences de complexité constante, et par, sous certaines conditions restrictives, ce qui permet des appels à operator[](), at(), begin(), rbegin(), end()ou rend()d'invalider les références, les pointeurs et les itérateurs se référant aux éléments de chaîne, à savoir éventuellement subir une Copie de données COW. Cette prise en charge a été supprimée dans C ++ 11.


COW est-il également interdit via les règles d'invalidation C ++ 11?

Dans une autre réponse qui, au moment de la rédaction de cet article, est choisie comme solution, et qui est fortement votée et donc apparemment crue, il est affirmé que

Pour une chaîne COW, appeler non- const operator[]nécessiterait de faire une copie (et d'invalider les références), ce qui est interdit par le paragraphe [cité] ci-dessus [C ++ 11 §21.4.1 / 6]. Par conséquent, il n'est plus légal d'avoir une chaîne COW dans C ++ 11.

Cette affirmation est incorrecte et trompeuse de deux manières principales:

  • Cela indique à tort que seuls les constaccesseurs non- item doivent déclencher une copie de données COW.
    Mais les constaccesseurs d'élément doivent également déclencher la copie de données, car ils permettent au code client de former des références ou des pointeurs qu'il n'est pas autorisé (en C ++ 11) d'invalider ultérieurement via les opérations qui peuvent déclencher la copie de données COW.
  • Il suppose à tort que la copie des données COW peut provoquer l'invalidation de la référence.
    Mais dans une mise en œuvre correcte, la copie des données COW, le partage de la valeur de la chaîne, est effectuée à un moment avant qu'il n'y ait des références qui peuvent être invalidées.

Pour voir comment une implémentation COW correcte de C ++ 11 basic_stringfonctionnerait, lorsque les exigences O (1) qui rendent ce paramètre invalide sont ignorées, pensez à une implémentation où une chaîne peut basculer entre les stratégies de propriété. Une instance de chaîne commence par une stratégie partageable. Avec cette stratégie active, il ne peut y avoir aucune référence d'élément externe. L'instance peut passer à la stratégie Unique, et elle doit le faire lorsqu'une référence d'élément est potentiellement créée, par exemple avec un appel à.c_str() (du moins si cela produit un pointeur vers le tampon interne). Dans le cas général de plusieurs instances partageant la propriété de la valeur, cela implique la copie des données de chaîne. Après cette transition vers la stratégie Unique, l'instance ne peut revenir à la règle partageable que par une opération qui invalide toutes les références, comme l'affectation.

Ainsi, bien que la conclusion de cette réponse, selon laquelle les chaînes COW sont exclues, est correcte, le raisonnement proposé est incorrect et fortement trompeur.

Je soupçonne que la cause de ce malentendu est une note non normative dans l'annexe C de C ++ 11:

C ++ 11 §C.2.11 [diff.cpp03.strings], à propos du §21.3:

Changement : les basic_stringexigences n'autorisent plus les chaînes comptées par référence.
Justification: L' invalidation est subtilement différente avec les chaînes comptées par référence. Ce changement régularise le comportement (sic) de la présente Norme internationale.
Effet sur la caractéristique d'origine: un code C ++ 2003 valide peut s'exécuter différemment dans la présente Norme internationale

Ici, la justification explique la principale raison pour laquelle on a décidé de supprimer le support COW spécial C ++ 03. Cette justification, le pourquoi , n'est pas de savoir comment la norme interdit effectivement la mise en œuvre de la GC. La norme interdit COW via les exigences O (1).

En bref, les règles d'invalidation C ++ 11 n'excluent pas une implémentation COW de std::basic_string. Mais ils excluent une implémentation COW de style C ++ 03 sans restriction raisonnablement efficace comme celle d'au moins une des implémentations de bibliothèque standard de g ++. Le support spécial C ++ 03 COW a permis une efficacité pratique, notamment en utilisant des constaccesseurs d'élément, au prix de règles subtiles et complexes d'invalidation:

C ++ 03 §21.3 / 5 qui inclut le support COW «premier appel»:

»Les références, pointeurs et itérateurs faisant référence aux éléments d'une basic_stringséquence peuvent être invalidés par les utilisations suivantes de cet basic_stringobjet:
- En tant qu'argument de fonctions non membres swap()(21.3.7.8), operator>>()(21.3.7.9) et getline()(21.3. 7.9).
- Comme argument pour basic_string::swap().
- Fonctions d' appel data()et de c_str()membre.
- Appel non constfonctions membres, à l' exception operator[](), at(), begin(), rbegin(), end()et rend().
- A la suite de l'une quelconque des utilisations ci - dessus à l' exception des formes de insert()et erase()qui renvoient les itérateurs, le premier appel à la non constfonctions membres operator[](), at(), begin(), , ourbegin() ,end()rend().

Ces règles sont si complexes et subtiles que je doute que de nombreux programmeurs, le cas échéant, puissent en donner un résumé précis. Je ne pouvais pas.


Que faire si les exigences O (1) ne sont pas respectées?

Si les exigences de temps constant C ++ 11 sur par exemple operator[]ne sont pas prises en compte, alors COW pour basic_stringpourrait être techniquement faisable, mais difficile à mettre en œuvre.

Les opérations qui pourraient accéder au contenu d'une chaîne sans encourir la copie de données COW incluent:

  • Concaténation via +.
  • Sortie via <<.
  • Utilisation d'un basic_stringcomme argument pour les fonctions de bibliothèque standard.

Ce dernier parce que la bibliothèque standard est autorisée à s'appuyer sur des connaissances et des constructions spécifiques à l'implémentation.

De plus, une implémentation pourrait offrir diverses fonctions non standard pour accéder au contenu des chaînes sans déclencher la copie des données COW.

Un facteur de complication principal est qu'en C ++ 11, basic_stringl'accès aux éléments doit déclencher la copie des données (annulation du partage des données de chaîne) mais doit ne pas lancer , par exemple C ++ 11 §21.4.5 / 3 « Throws: Nothing.». Et donc il ne peut pas utiliser l'allocation dynamique ordinaire pour créer un nouveau tampon pour la copie de données COW. Une solution consiste à utiliser un tas spécial où la mémoire peut être réservée sans être réellement allouée, puis à réserver la quantité requise pour chaque référence logique à une valeur de chaîne. Réserver et dé-réserver dans un tel tas peut être un temps constant, O (1), et allouer le montant que l'on a déjà réservé, peut êtrenoexcept. Afin de se conformer aux exigences de la norme, avec cette approche, il semble qu'il devrait y avoir un tel tas spécial basé sur les réservations par allocateur distinct.


Remarques:
¹ L' constaccesseur d'élément déclenche une copie de données COW car il permet au code client d'obtenir une référence ou un pointeur vers les données, qu'il n'est pas autorisé à invalider par une copie de données ultérieure déclenchée par exemple par l' constaccesseur non- élément.

Bravo et hth. - Alf
la source
3
" Votre exemple est un bon exemple d'implémentation incorrecte pour C ++ 11. Peut-être était-elle correcte pour C ++ 03." Oui, c'est le but de l'exemple . Il montre une chaîne COW qui était légale en C ++ 03 car elle ne rompt pas les anciennes règles d'invalidation d'itérateur et n'est pas légale en C ++ 11 car elle enfreint les nouvelles règles d'invalidation d'itérateur. Et cela contredit également la déclaration que j'ai citée dans le commentaire ci-dessus.
Jonathan Wakely
2
Si tu avais dit partageable n'était pas initialement partagé, je n'aurais pas discuté. Dire que quelque chose est initialement partagé est tout simplement déroutant. Partagé avec lui-même? Ce n'est pas ce que le mot veut dire. Mais je le répète: votre tentative d'argumenter que les règles d'invalidation de l'itérateur C ++ 11 n'interdisent pas une chaîne COW hypothétique qui n'a jamais été utilisée dans la pratique (et aurait des performances inacceptables), alors qu'elles interdisent très certainement le type de chaîne COW qui a été utilisé dans la pratique, est quelque peu théorique et inutile.
Jonathan Wakely
5
Votre chaîne COW proposée est intéressante, mais je ne sais pas comment utilité . Le but d'une chaîne COW est de copier uniquement les données de chaîne dans le cas où les deux chaînes sont écrites. Votre implémentation suggérée nécessite une copie lorsqu'une opération de lecture définie par l'utilisateur se produit. Même si le compilateur ne connaît qu'une lecture, il doit quand même copier. De plus, la copie d'une chaîne Unique se traduira par une copie de ses données de chaîne (probablement dans un état partageable), ce qui rend encore COW plutôt inutile. Donc, sans les garanties de complexité, vous pourriez écrire ... une chaîne COW vraiment merdique .
Nicol Bolas
2
Donc, bien que vous ayez techniquement raison de dire que les garanties de complexité sont ce qui vous empêche d'écrire toute forme de COW, c'est vraiment [basic.string] / 5 qui vous empêche d'écrire des éléments réellement utiles forme de chaîne COW.
Nicol Bolas
4
@JonathanWakely: (1) Votre devis n'est pas la question. Voici la question: «Ai-je raison de dire que C ++ 11 n'admet pas les implémentations basées sur COW de std :: string? Si tel est le cas, cette restriction est-elle explicitement énoncée quelque part dans la nouvelle norme (où)? » (2) Votre opinion selon laquelle une vache std::string, en ne tenant pas compte des exigences O (1), serait inefficace, est votre opinion. Je ne sais pas ce que pourrait être la performance, mais je pense que cette affirmation est davantage mise en avant pour la sensation de celle-ci, pour les vibrations qu'elle véhicule, que pour toute pertinence par rapport à cette réponse.
Acclamations et hth. - Alf
0

Je m'interrogeais toujours sur les vaches immuables: une fois que la vache est créée, je ne pourrais être changé que par l'affectation d'une autre vache, donc elle sera conforme à la norme.

J'ai eu le temps de l'essayer aujourd'hui pour un simple test de comparaison: une carte de taille N indexée par chaîne / vache avec chaque nœud contenant un ensemble de toutes les chaînes de la carte (nous avons un nombre d'objets NxN).

Avec des chaînes de taille ~ 300 octets et N = 2000 vaches sont légèrement plus rapides et utilisent presque un ordre de grandeur moins de mémoire. Voir ci-dessous, les tailles sont en kbs, la course b est avec les vaches.

~/icow$ ./tst 2000
preparation a
run
done a: time-delta=6 mem-delta=1563276
preparation b
run
done a: time-delta=3 mem-delta=186384
zzz777
la source