Est-ce que cette optimisation dans la mise en œuvre de std :: string autorisé?

Question

Je pensais juste à la mise en œuvre de std::string::substr. Elle retourne un nouvel objet std::string, ce qui me semble un gaspillage de peu à. Pourquoi ne pas renvoyer un objet qui fait référence au contenu de la chaîne d'origine et peut être attribué implicitement à un std::string? Une sorte d'évaluation paresseuse de la copie réelle. Une telle classe pourrait ressembler à ceci:

template <class Ch, class Tr, class A>
class string_ref {
public:
    // not important yet, but *looks* like basic_string's for the most part

private:
    const basic_string<Ch, Tr, A> &s_;
    const size_type pos_;
    const size_type len_;    
};

L'interface publique de cette classe serait mimer toutes les opérations en lecture seule d'un vrai std::string, de sorte que l'utilisation serait transparente. std::string pourrait alors avoir un nouveau constructeur qui prend string_ref afin que l'utilisateur ne sera jamais le plus sage. Au moment où vous essayez de « stocker » le résultat, vous finissez par créer une copie, donc pas des problèmes réels avec la référence indiquant les données, puis l'avoir modifié derrière le dos.

L'idée étant que le code comme ceci:

std::string s1 = "hello world";
std::string s2 = "world";
if(s1.substr(6) == s2) {
    std::cout << "match!" << std::endl;
}

ne pas avoir plus de deux std::string objets construits au total. Cela semble être une optimisation utile pour le code qui qui effectue beaucoup de manipulations de cordes. Bien sûr, cela ne vaut pas seulement pour std::string, mais à tout type qui peut renvoyer un sous-ensemble de son contenu.

Pour autant que je sache, aucune mise en oeuvre font.

Je suppose que le cœur de la question est:

Étant donné une classe qui peut être serait-il implicitement converti en std::string au besoin, conforme à la norme pour un écrivain bibliothèque pour changer le prototype de retourner le type d'un membre? Ou plus généralement, faire les écrivains bibliothèque ont la marge de manœuvre pour revenir « objets proxy » au lieu d'objets réguliers dans ces types de cas comme une optimisation?

Mon instinct est que ce n'est pas permis et que les prototypes doivent correspondre exactement. Étant donné que vous ne pouvez pas surcharger le type de retour seul, cela ne laisserait pas de place pour les écrivains bibliothèque pour profiter de ces types de situations. Comme je l'ai dit, je pense que la réponse est non, mais je pensais que je demande: -.)

Answer 1

Cette idée est copy-on-write , mais au lieu de COW'ing le tampon entier, vous garder une trace de quel sous-ensemble de la mémoire tampon est la chaîne « réelle ». (COW, sous sa forme normale, était (est?) Utilisé dans certaines implémentations bibliothèque.)

Vous n'avez pas besoin d'un objet proxy ou changement de l'interface du tout parce que ces détails peuvent être complètement interne. Conceptuellement, vous devez garder une trace de quatre choses: un tampon de source, un compte de référence pour le tampon, et le début et la fin de la chaîne dans ce tampon

.

Chaque fois qu'une modifie opération la mémoire tampon du tout, il crée sa propre copie ( depuis le début et délimiteurs fin ), diminue l'ancien compteur de référence de tampon par un, et définit la référence du nouveau tampon comptage à un. Le reste des règles de comptage de référence sont les mêmes: la copie et le nombre d'augmentation par un, un nombre de détruisent la chaîne et la diminution par un, zéro et atteindre supprimer, etc

.

substr fait juste une nouvelle instance de chaîne, sauf avec le début et la fin délimiteurs explicitement spécifié.

Answer 2

Ceci est une optimisation très bien connu qui est relativement largement utilisé, appelé copie-sur-écriture ou COW. La chose fondamentale est même pas à faire avec des sous-chaînes, mais avec quelque chose d'aussi simple que

s1 = s2;

Maintenant, le problème avec cette optimisation est que pour les bibliothèques C qui sont censés être utilisés sur des cibles à l'appui de plusieurs threads, le nombre de référence de la chaîne doit être accessible à l'aide d'opérations atomiques (ou pire, protégé par un mutex en cas la plate-forme cible ne fournit pas des opérations atomiques). Ceci est assez cher que dans la plupart des cas, la mise en oeuvre simple chaîne non-COW est plus rapide.

Voir GotW # 43-45:

http://www.gotw.ca/gotw/043.htm

http://www.gotw.ca/gotw/044.htm

http://www.gotw.ca/gotw/045.htm

Pour aggraver les choses, les bibliothèques qui ont VACHE utilisé, comme la bibliothèque GNU C, ne peut pas simplement à la mise en œuvre revert simple puisque cela briser l'ABI. (Bien que, C ++ 0x à la rescousse, comme cela exigera une bosse ABI quand même! :))

Answer 3

Depuis retourne substr std::string, il n'y a aucun moyen de retourner un objet proxy, et ils ne peuvent pas simplement changer le type de retour ou d'une surcharge sur elle (pour les raisons que vous avez mentionnées).

Ils pourraient le faire en faisant string lui-même susceptible d'être sous d'une autre chaîne. Cela signifierait une peine de mémoire pour tous les usages (pour tenir une chaîne supplémentaire et deux size_types). En outre, chaque opération aurait besoin de vérifier pour voir si elle a des caractères ou un proxy. Peut-être que cela pourrait se faire avec un pointeur de mise en œuvre -. Le problème est, maintenant, nous faisons une classe d'usage général plus lent pour un cas limite possible

Si vous avez besoin de cela, la meilleure façon est de créer une autre classe, substring, qui construit à partir d'une chaîne, pos, et la longueur et à la chaîne caudales. Vous ne pouvez pas l'utiliser comme s1.substr(6), mais vous pouvez le faire

 substring sub(s1, 6);

Il vous faudrait également créer des opérations communes qui prennent une sous-chaîne et la chaîne pour éviter la conversion (puisque c'est le point entier).

Answer 4

En ce qui concerne votre exemple spécifique, cela a fonctionné pour moi:

if (&s1[6] == s2) {
    std::cout << "match!" << std::endl;
}

Cela ne peut pas répondre à votre question pour une solution polyvalente. Pour cela, vous aurez besoin CoW sous-chaîne, comme le suggère @GMan.

Answer 5

Qu'est-ce que vous parlez est de (ou était) l'une des caractéristiques de base de la classe java.lang.String Java ( http://fishbowl.pastiche.org/2005/04/27/the_string_memory_gotcha/ ). À bien des égards, les conceptions de la classe String de Java et le modèle C ++ 's basic_string sont similaires, donc j'imagine que la rédaction d'une mise en œuvre du modèle de basic_string utilisant cette « optimisation sous-chaîne » est possible.

Une chose que vous devez considérer est comment écrire la mise en œuvre de l'organe de c_str() const. En fonction de l'emplacement d'une chaîne comme une sous-chaîne d'une autre, il devra peut-être créer une nouvelle copie. Il aurait certainement de créer une nouvelle copie du tableau interne si la chaîne pour laquelle il a été demandé la c_str n'est pas une sous-chaîne de fuite. Je pense que cela nécessite en utilisant le mot-clé mutable sur la plupart, sinon la totalité, des membres de données de la mise en œuvre de basic_string, ce qui complique considérablement la mise en œuvre d'autres méthodes de const parce que le compilateur est plus en mesure d'aider le programmeur avec exactitude const.

EDIT: En fait, pour accueillir c_str() const et data() const, vous pouvez utiliser un seul champ mutable de type const charT*. Dans un premier temps mis à NULL, il pourrait être par instance, initialisé à un pointeur vers un nouveau tableau de charT chaque fois c_str() const ou data() const sont appelés, et supprimé dans le destructor de basic_string si non NULL.

Answer 6

Si et seulement si vous avez vraiment besoin plus de performances que std :: string fournit alors quelque chose aller de l'avant et d'écriture qui fonctionne de la façon dont vous avez besoin. Je travaille avec des variantes de chaînes avant.

Ma préférence est d'utiliser des chaînes non-mutables plutôt que la copie en écriture, et à stimuler l'utilisation :: shared_ptr ou équivalent, mais seulement lorsque la chaîne est en fait au-delà de 16 de longueur, de sorte que la classe de chaîne a également privé tampon pour les chaînes courtes.

Cela ne signifie pas que la classe de chaîne peut porter un peu de poids.

J'ai aussi dans ma liste de collection d'une classe « tranche » qui peut regarder un « sous-ensemble » d'une classe qui vit ailleurs aussi longtemps que la durée de vie de l'objet d'origine est intact. Donc, dans votre cas, je pouvais couper la chaîne pour voir une sous-chaîne. Bien sûr, il ne serait pas terminée par zéro, et il n'y a aucune façon de le rendre tel sans le copier. Et ce n'est pas une classe de chaîne.