Ich hatte verstanden, dass Copy-on-Write kein praktikabler Weg ist, um eine Konformität std::string
in C ++ 11 zu implementieren , aber als es kürzlich in der Diskussion auftauchte, war ich nicht in der Lage, diese Aussage direkt zu unterstützen.
Stimmt es, dass C ++ 11 keine COW-basierten Implementierungen von zulässt std::string
?
Wenn ja, wird diese Einschränkung ausdrücklich irgendwo in der neuen Norm angegeben (wo)?
Oder ist diese Einschränkung impliziert, in dem Sinne , dass es die kombinierte Wirkung der neuen Anforderungen an ist , std::string
dass verbietet eine KUH - basierte Implementierung von std::string
. In diesem Fall würde mich eine Kapitel- und Versstilableitung von "C ++ 11 verbietet COW-basierte std::string
Implementierungen" interessieren .
Antworten:
Dies ist nicht zulässig, da gemäß Standard 21.4.1 p6 die Ungültigmachung von Iteratoren / Referenzen nur zulässig ist
Für eine COW-Zeichenfolge würde das Aufrufen von non-const
operator[]
das Erstellen einer Kopie (und das Ungültigmachen von Verweisen) erfordern, was im obigen Absatz nicht zulässig ist. Daher ist es in C ++ 11 nicht mehr legal, eine COW-Zeichenfolge zu haben.quelle
std::string a("something"); char& c1 = a[0]; std::string b(a); char& c2 = a[1];
c1 ist eine Referenz auf a. Sie "kopieren" dann a. Wenn Sie dann versuchen, die Referenz das zweite Mal zu übernehmen, muss eine Kopie erstellt werden, um eine nicht konstante Referenz zu erhalten, da zwei Zeichenfolgen auf denselben Puffer verweisen. Dies müsste die erste Referenz ungültig machen und widerspricht dem oben zitierten Abschnitt.operator[]
(1) eine Kopie erstellen muss und dass (2) dies illegal ist. Mit welchem dieser beiden Punkte sind Sie nicht einverstanden? Wenn Sie sich Ihren ersten Kommentar ansehen, scheint es, dass eine Implementierung die Zeichenfolge zumindest unter dieser Anforderung bis zum Zeitpunkt des Zugriffs gemeinsam nutzen könnte, aber dass sowohl Lese- als auch Schreibzugriffe die Freigabe aufheben müssten. Ist das deine Argumentation?Die Antworten von Dave S und gbjbaanb sind richtig . (Und Luc Dantons ist auch richtig, obwohl es eher ein Nebeneffekt des Verbots von COW-Strings ist als die ursprüngliche Regel, die es verbietet.)
Aber um einige Verwirrung zu beseitigen, werde ich eine weitere Darstellung hinzufügen. Verschiedene Kommentare verweisen auf einen meiner Kommentare zum GCC-Bugzilla, der das folgende Beispiel enthält:
In diesem Beispiel soll gezeigt werden, warum die COW-Zeichenfolge (Reference Counted) von GCC in C ++ 11 nicht gültig ist. Der C ++ 11-Standard erfordert, dass dieser Code ordnungsgemäß funktioniert. Nichts im Code erlaubt
p
es, das in C ++ 11 ungültig zu machen.Mit GCC alten Referenzzählung
std::string
Implementierung hat , dass Code nicht definiertes Verhalten, dap
wird für ungültig erklärt, zu einem baumelnden Zeiger. (Was passiert ist, dass, wenn es erstellts2
wird, es die Daten mit teilts
, aber um eine nicht konstante Referenz über zu erhalten,s[0]
müssen die Daten nicht freigegeben werden, ebensos
wie eine "Kopie beim Schreiben", da die Referenzs[0]
möglicherweise zum Schreiben verwendet werden könntes
, und danns2
geht außerhalb des Gültigkeitsbereichs, Zerstörung des Arrays, auf das durch gezeigt wirdp
).Der C ++ 03-Standard erlaubt dieses Verhalten explizit in 21.3 [lib.basic.string] p5, wo er besagt, dass nach einem Aufruf
data()
des ersten Aufrufs anoperator[]()
Zeiger, Referenzen und Iteratoren ungültig werden können. Die COW-Zeichenfolge von GCC war also eine gültige C ++ 03-Implementierung.Der C ++ 11-Standard erlaubt dieses Verhalten nicht mehr , da kein Aufruf von
operator[]()
Zeigern, Referenzen oder Iteratoren ungültig machen kann, unabhängig davon, ob sie einem Aufruf von folgendata()
.Das obige Beispiel muss also in C ++ 11 funktionieren, funktioniert jedoch nicht mit der Art der COW-Zeichenfolge von libstdc ++. Daher ist diese Art der COW-Zeichenfolge in C ++ 11 nicht zulässig.
quelle
.data()
(und bei jeder Rückgabe von Zeiger, Referenz oder Iterator) die Freigabe aufhebt , leidet nicht unter diesem Problem. Das heißt (invariant), dass ein Puffer jederzeit nicht freigegeben oder ohne externe Verweise freigegeben wird. Ich dachte, Sie hätten den Kommentar zu diesem Beispiel als informellen Fehlerbericht als Kommentar gedacht. Es tut mir sehr leid, dass Sie ihn falsch verstanden haben! Wie Sie jedoch sehen können, wenn Sie die hier beschriebene Implementierung in Betracht ziehen, die in C ++ 11 gut funktioniert, wennnoexcept
Anforderungen ignoriert werden, sagt das Beispiel nichts über das Formale aus. Ich kann Code bereitstellen, wenn Sie möchten.std::string
, und ich bezweifle aufrichtig, dass Sie eine nützliche, performante COW-Zeichenfolge demonstrieren können, die die C ++ 11-Ungültigkeitsanforderungen erfüllt. Daher behaupte ich, dass dienoexcept
Spezifikationen, die in letzter Minute hinzugefügt wurden, eine Folge des Verbots von COW-Zeichenfolgen sind und nicht der zugrunde liegende Grund. N2668 scheint völlig klar zu sein, warum bestreiten Sie weiterhin die eindeutigen Beweise für die dort skizzierte Absicht des Ausschusses?data()
eine const-Member-Funktion ist. Sie müssen also sicher sein, gleichzeitig mit anderen const-Mitgliedern aufzurufen und beispielsweisedata()
gleichzeitig mit einem anderen Thread aufzurufen , der eine Kopie der Zeichenfolge erstellt. Sie benötigen also den gesamten Overhead eines Mutex für jede Zeichenfolgenoperation, auch für konstante, oder die Komplexität einer sperrenfreien, veränderbaren Struktur mit Referenzzählung, und schließlich erhalten Sie nur dann eine Freigabe, wenn Sie nie Änderungen vornehmen oder darauf zugreifen Ihre Zeichenfolgen, so viele, viele Zeichenfolgen, haben eine Referenzanzahl von eins. Bitte geben Sie Code an, ignorieren Sienoexcept
Garantien.basic_string
Mitgliedsfunktionen und freie Funktionen gibt. Abstraktionskosten: Dieser nicht optimierte frische nullte Versionscode von der Stange ist sowohl mit g ++ als auch mit MSVC 50 bis 100% langsamer. Es bietet keine Thread-Sicherheit (shared_ptr
ich denke, es ist einfach genug, es zu nutzen ) und es reicht gerade aus, um das Sortieren eines Wörterbuchs zum Zwecke des Timings zu unterstützen, aber Modulo-Fehler beweisen, dass eine gezählte Referenzbasic_string
zulässig ist, mit Ausnahme der C ++ -noexcept
Anforderungen. github.com/alfps/In-principle-demo-of-ref-counted-basic_stringCoW ist ein akzeptabler Mechanismus, um schnellere Strings zu erstellen ... aber ...
Dadurch wird Multithreading-Code langsamer (all diese Sperren, um zu überprüfen, ob Sie der einzige sind, der die Leistung beeinträchtigt, wenn viele Zeichenfolgen verwendet werden). Dies war der Hauptgrund, warum CoW vor Jahren getötet wurde.
Die anderen Gründe sind, dass der
[]
Operator Ihnen die Zeichenfolgendaten zurückgibt, ohne dass Sie eine Zeichenfolge überschreiben müssen, von der jemand anderes erwartet, dass sie sich nicht ändert. Gleiches gilt fürc_str()
unddata()
.Laut Quick Google ist das Multithreading im Grunde der Grund, warum es effektiv nicht zugelassen wurde (nicht explizit).
Der Vorschlag lautet:
gefolgt von
Seile sind Teil von STLPort und SGIs STL.
quelle
Ab 21.4.2 basic_string Konstruktoren und Zuweisungsoperatoren [string.cons]
Tabelle 64 dokumentiert hilfreich, dass nach der Erstellung eines Objekts über diesen (Kopier-) Konstruktor folgender
this->data()
Wert vorliegt:Es gibt ähnliche Anforderungen für andere ähnliche Konstruktoren.
quelle
Da jetzt garantiert ist, dass Zeichenfolgen zusammenhängend gespeichert werden und Sie jetzt einen Zeiger auf den internen Speicher einer Zeichenfolge nehmen dürfen (dh & str [0] funktioniert wie bei einem Array), ist es nicht möglich, eine nützliche COW zu erstellen Implementierung. Sie müssten eine Kopie für viel zu viele Dinge machen. Selbst wenn nur
operator[]
oderbegin()
eine nicht konstante Zeichenfolge verwendet wird, ist eine Kopie erforderlich.quelle
c_str()
), muss O (1) sein und darf nicht werfen und darf keine Datenrennen einführen. Daher ist es sehr schwierig, diese Anforderungen zu erfüllen, wenn Sie träge verketten. In der Praxis besteht die einzig sinnvolle Option darin, immer zusammenhängende Daten zu speichern.Ist COW
basic_string
in C ++ 11 und höher verboten?Hinsichtlich
Ja.
Hinsichtlich
Fast direkt durch Anforderungen konstanter Komplexität für eine Reihe von Operationen, die ein O ( n ) physisches Kopieren der Zeichenfolgendaten in einer COW-Implementierungerfordern würden.
Zum Beispiel für die Mitgliedsfunktionen
… Was in einer COW-Implementierung ¹ sowohl das Kopieren von Zeichenfolgendaten auslösen würde, um die Freigabe des Zeichenfolgenwerts aufzuheben, erfordert der C ++ 11-Standard
C ++ 11 §21.4.5 / 4 :… Was ein solches Kopieren von Daten und damit COW ausschließt.
C ++ 03 unterstützt COW Implementierungen nicht diese ständigen Komplexitätsanforderungen haben, und durch unter bestimmten restriktiven Bedingungen, so dass Anrufe
operator[]()
,at()
,begin()
,rbegin()
,end()
, oderrend()
ungültig zu machen , Referenzen, Zeiger und Iteratoren auf die Zeichenfolge Posten beziehen, dh auf möglicherweise incur a Kopieren von COW-Daten. Diese Unterstützung wurde in C ++ 11 entfernt.Ist COW auch über die C ++ 11-Ungültigkeitsregeln verboten?
In einer anderen Antwort, die zum Zeitpunkt des Schreibens als Lösung ausgewählt wurde und die stark positiv bewertet und daher anscheinend geglaubt wird, wird dies behauptet
Diese Behauptung ist in zweierlei Hinsicht falsch und irreführend:
const
Item-Accessoren eine COW-Datenkopie auslösen müssen.Aber auch die
const
Elementzugriffsberechtigten müssen das Kopieren von Daten auslösen, da sie es dem Clientcode ermöglichen, Referenzen oder Zeiger zu bilden, die (in C ++ 11) später nicht über die Vorgänge ungültig gemacht werden dürfen, die das Kopieren von COW-Daten auslösen können.Bei einer korrekten Implementierung erfolgt das Kopieren von COW-Daten, wobei die Freigabe des Zeichenfolgenwerts aufgehoben wird, zu einem Zeitpunkt, bevor Referenzen vorhanden sind, die ungültig gemacht werden können.
Um zu sehen, wie eine korrekte C ++ 11 COW-Implementierung von
basic_string
funktionieren würde, wenn die O (1) -Anforderungen, die dies ungültig machen, ignoriert werden, stellen Sie sich eine Implementierung vor, bei der eine Zeichenfolge zwischen Eigentumsrichtlinien wechseln kann. Eine Zeichenfolgeninstanz beginnt mit der Richtlinie Sharable. Wenn diese Richtlinie aktiv ist, können keine externen Elementreferenzen vorhanden sein. Die Instanz kann zu einer eindeutigen Richtlinie übergehen und muss dies tun, wenn möglicherweise eine Elementreferenz erstellt wird, z. B. bei einem Aufruf von.c_str()
(zumindest, wenn dadurch ein Zeiger auf den internen Puffer erzeugt wird). Im allgemeinen Fall, dass mehrere Instanzen das Eigentum an dem Wert teilen, müssen die Zeichenfolgendaten kopiert werden. Nach diesem Übergang zur Richtlinie "Eindeutig" kann die Instanz nur durch einen Vorgang, der alle Verweise ungültig macht, z. B. die Zuweisung, wieder zu "Freigabefähig" zurückkehren.Obwohl die Schlussfolgerung dieser Antwort, dass COW-Zeichenfolgen ausgeschlossen sind, richtig ist, ist die angebotene Argumentation falsch und stark irreführend.
Ich vermute, die Ursache für dieses Missverständnis ist ein nicht normativer Hinweis in Anhang C von C ++ 11:
C ++ 11 §C.2.11 [diff.cpp03.strings], ungefähr §21.3:Hier erklärt die Begründung den Hauptgrund, warum man sich entschied, die spezielle COW-Unterstützung für C ++ 03 zu entfernen. Diese Begründung, das Warum , ist nicht, wie der Standard die COW-Implementierung effektiv verbietet. Der Standard verbietet COW über die O (1) -Anforderungen.
Kurz gesagt, die C ++ 11-Ungültigkeitsregeln schließen eine COW-Implementierung von nicht aus
C ++ 03 §21.3 / 5 mit COW-Unterstützung für den ersten Anruf:std::basic_string
. Sie schließen jedoch eine einigermaßen effiziente, uneingeschränkte COW-Implementierung im C ++ 03-Stil aus, wie sie in mindestens einer der Standardbibliotheksimplementierungen von g ++ enthalten ist. Die spezielle COW-Unterstützung für C ++ 03 ermöglichte eine praktische Effizienz, insbesondere unter Verwendung vonconst
Elementzugriffsmethoden, auf Kosten subtiler, komplexer Regeln für die Ungültigmachung:Diese Regeln sind so komplex und subtil, dass ich bezweifle, dass viele Programmierer, wenn überhaupt, eine genaue Zusammenfassung geben könnten. Ich könnte nicht.
Was ist, wenn O (1) -Anforderungen nicht berücksichtigt werden?
Wenn die konstanten
operator[]
Zeitanforderungen für C ++ 11 für z. B. nicht berücksichtigt werden, ist COW forbasic_string
möglicherweise technisch machbar, aber schwierig zu implementieren.Zu den Vorgängen, die auf den Inhalt einer Zeichenfolge zugreifen können, ohne dass COW-Daten kopiert werden müssen, gehören:
+
.<<
.basic_string
als Argument für Standardbibliotheksfunktionen.Letzteres, weil die Standardbibliothek sich auf implementierungsspezifische Kenntnisse und Konstrukte stützen darf.
Zusätzlich könnte eine Implementierung verschiedene nicht standardmäßige Funktionen für den Zugriff auf Zeichenfolgeninhalte bieten, ohne das Kopieren von COW-Daten auszulösen.
Ein Hauptkomplikationsfaktor ist, dass in C ++ 11 der Elementzugriff das
basic_string
Kopieren von Daten auslösen muss (Aufheben der Freigabe der Zeichenfolgendaten), jedoch nicht ausgelöst werden muss , z. B. C ++ 11 §21.4.5 / 3 „ Throws: Nothing“. Daher kann keine normale dynamische Zuordnung verwendet werden, um einen neuen Puffer für das Kopieren von COW-Daten zu erstellen. Eine Möglichkeit, dies zu umgehen, besteht darin, einen speziellen Heap zu verwenden, in dem Speicher reserviert werden kann, ohne tatsächlich zugewiesen zu werden, und dann den erforderlichen Betrag für jede logische Referenz auf einen Zeichenfolgenwert zu reservieren . Das Reservieren und Aufheben der Reservierung in einem solchen Haufen kann eine konstante Zeit sein, O (1), und das Zuweisen des Betrags, den man bereits reserviert hat, kann seinnoexcept
. Um die Anforderungen des Standards zu erfüllen, scheint es bei diesem Ansatz einen solchen speziellen reservierungsbasierten Heap pro eindeutigem Allokator zu geben.Hinweise:
¹ Der
const
Elementzugriffsauslöser löst eine COW-Datenkopie aus, da der Clientcode einen Verweis oder Zeiger auf die Daten erhalten kann, die durch eine spätere Datenkopie, die beispielsweise vom Nicht-const
Artikelzugriffsgeber ausgelöst wird, nicht ungültig werden dürfen .quelle
std::string
unter Missachtung der O (1) -Anforderungen ineffizient wäre, ist Ihre Meinung. Ich weiß nicht, wie die Aufführung aussehen könnte, aber ich denke, dass diese Behauptung mehr für das Gefühl, für die Stimmung, die sie vermittelt, als für irgendeine Relevanz für diese Antwort vorgebracht wird.Ich habe mich immer über unveränderliche Kühe gewundert: Sobald eine Kuh geschaffen wurde, konnte ich nur durch Zuweisung von einer anderen Kuh geändert werden, daher wird sie dem Standard entsprechen.
Ich hatte heute Zeit, es für einen einfachen Vergleichstest zu versuchen: eine Karte der Größe N, die mit einer Zeichenfolge / Kuh verschlüsselt ist, wobei jeder Knoten eine Reihe aller Zeichenfolgen in der Karte enthält (wir haben eine NxN-Anzahl von Objekten).
Mit Strings mit einer Größe von ~ 300 Bytes und N = 2000 Kühen sind die Kühe etwas schneller und verbrauchen fast eine Größenordnung weniger Speicher. Siehe unten, Größen sind in kbs angegeben, Lauf b ist mit Kühen.
quelle