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

Question

J'avais cru comprendre que la copie sur l'écriture n'était pas un moyen viable d'implémenter un système conforme. std::string dans C++11, mais lorsque la question a été abordée récemment, je me suis trouvé dans l'incapacité de soutenir directement cette affirmation.

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

Si oui, cette restriction est-elle explicitement indiquée quelque part dans la nouvelle norme (où) ?

Ou bien cette restriction est-elle implicite, en ce sens qu'il s'agit de l'effet combiné des nouvelles exigences en matière de std::string qui empêche une implémentation basée sur COW de std::string . Dans ce cas, je serais intéressé par une dérivation de type chapitre et verset de la phrase "C++11 interdit effectivement la méthode COW". std::string mises en œuvre".

Answer 1

_Est COW basic_string interdite dans C++11 et les versions ultérieures ?_

Concernant

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

Oui.

Concernant

" Si oui, cette restriction est-elle explicitement indiqué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écessiteraient O( n ) la copie physique des données de la chaîne dans une implémentation COW.

Par exemple, pour les fonctions membres

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

ce qui, dans une implémentation COW, déclencherait la copie des données de la chaîne pour dé-partager la valeur de la chaîne, la norme C++11 exige que

C++11 §21.4.5/4 :

" La complexité : temps constant.

ce qui exclut une telle copie de données, et donc, COW.

no ayant ces exigences de complexité constante, et en autorisant, sous certaines conditions restrictives, les appels aux operator[]() , at() , begin() , rbegin() , end() ou rend() pour invalider les références, les pointeurs et les itérateurs se référant aux éléments de la chaîne, c'est-à-dire pour éventuellement subir une copie de données COW. Ce support a été supprimé en C++11.

---

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

Dans une autre réponse qui, à l'heure où nous écrivons ces lignes, a été sélectionnée comme solution, et qui a fait l'objet d'un grand nombre de votes positifs et qui est donc apparemment acceptée, 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 en C++11.

Cette affirmation est incorrecte et trompeuse à deux égards principaux :

• Il indique à tort que seules les personnes non const Les accesseurs d'éléments doivent déclencher une copie de données COW.
  Mais aussi le const Les accesseurs d'éléments doivent 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) à invalider ultérieurement via les opérations qui peuvent déclencher la copie de données COW.
• Il suppose à tort que la copie de données COW peut entraîner l'invalidation des références.
  Mais dans une mise en œuvre correcte, la copie des données COW, le dé-partage de la valeur de la chaîne, se fait à un moment où il n'y a pas de références qui peuvent être invalidées.

Pour voir comment une implémentation correcte de C++11 COW de basic_string fonctionnerait, lorsque les exigences O(1) qui rendent cette méthode invalide sont ignorées, pensez à une implémentation où une chaîne peut passer d'une politique de propriété à une autre. Une instance de chaîne commence avec la politique Sharable. Avec cette politique active, il ne peut y avoir de références externes aux éléments. L'instance peut passer à la politique Unique, et elle doit le faire lorsqu'une référence d'élément est potentiellement créée, comme par exemple avec un appel à .c_str() (du moins si cela produit un pointeur vers le tampon interne). Dans le cas général où plusieurs instances partagent la propriété de la valeur, cela implique de copier les données de la chaîne. Après cette transition vers Unique policy, l'instance ne peut repasser en Sharable que par une opération qui invalide toutes les références, comme une affectation.

Ainsi, si la conclusion de cette réponse, à savoir que les cordes 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 : basic_string les exigences ne permettent 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) pour cette norme internationale.
Effet sur la caractéristique originale : Le code C ++ 2003 valide peut s'exécuter différemment dans cette norme internationale.

Ici, le raisonnement explique le primaire por qué on a décidé de supprimer le support spécial COW de C++03. Ce raisonnement, le por qué n'est pas cómo la norme interdit effectivement l'implémentation de COW. La norme interdit COW via les exigences O(1).

En bref, les règles d'invalidation de C++11 n'excluent pas une implémentation COW de std::basic_string . Mais ils excluent une implémentation C++03 non restreinte et raisonnablement efficace de COW comme celle d'au moins une des implémentations de la bibliothèque standard de g++. La prise en charge spéciale de C++03 COW a permis une efficacité pratique, en particulier l'utilisation de const les accesseurs d'éléments, au prix de règles d'invalidation subtiles et complexes :

C++03 §21.3/5 qui comprend le soutien "first call" du COW :

" Les références, les pointeurs et les itérateurs se rapportant aux éléments d'une basic_string peut être invalidée par les utilisations suivantes de cette séquence basic_string objet :
- En tant qu'argument pour les 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() .
- Appel data() y c_str() les fonctions des membres.
- Non-appelant const les fonctions membres, sauf operator[]() , at() , begin() , rbegin() , end() y rend() .
- Après l'une des utilisations ci-dessus, à l'exception des formes de insert() y erase() qui renvoient des itérateurs, le premier appel à des itérateurs non const fonctions membres operator[]() , at() , begin() , rbegin() , end() ou rend() .

Ces règles sont si complexes et subtiles que je doute que beaucoup de programmeurs, voire aucun, puissent en donner un résumé précis. Je ne le pourrais pas.

---

Que se passe-t-il si les exigences de l'O(1) ne sont pas respectées ?

Si les exigences de C++11 en matière de temps constant sur, par exemple, l operator[] ne sont pas pris en compte, alors COW pour basic_string pourrait être techniquement réalisable, mais difficile à mettre en œuvre.

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

• Concaténation via + .
• Sortie via << .
• Utilisation d'un basic_string comme argument aux fonctions de la bibliothèque standard.

En effet, la bibliothèque standard est autorisée à s'appuyer sur des connaissances et des constructions spécifiques à la mise en œuvre.

En outre, une mise en œuvre pourrait offrir diverses fonctions non standard pour accéder au contenu des chaînes de caractères sans déclencher la copie de données COW.

Un des principaux facteurs de complication est que dans C++11 basic_string L'accès à l'élément doit déclencher la copie des données (dé-partage des données de la chaîne) mais il est nécessaire de ne pas jeter par exemple, C++11 §21.4.5/3 " Les lancers : Rien.". Il ne peut donc pas utiliser l'allocation dynamique ordinaire pour créer un nouveau tampon pour la copie des données COW. Un moyen de contourner ce problème est d'utiliser un tas spécial où la mémoire peut être réservé sans être réellement allouées, puis de réserver le montant requis 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 la quantité que l'on a déjà réservée, peut être noexcept . Afin de se conformer aux exigences de la norme, il semble qu'avec cette approche, il faudrait un tas spécial basé sur la réservation par allocateur distinct.

---

Notes :
¹ Le const déclenche une copie de données COW parce qu'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'accesseur non const l'accesseur de l'élément.

Answer 2

Je me suis toujours interrogé sur les vaches immuables : une fois la vache créée, elle ne peut être modifiée que par affectation d'une autre vache, ce qui la rend conforme à la norme.

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

Avec des chaînes de ~300 octets et N=2000 vaches sont légèrement plus rapides et utilisent presque un ordre de grandeur de mémoire en moins. Voir ci-dessous, les tailles sont en kbs, l'exécution 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