Lese-/Schreib-Unterschiedung beim []-Operator, die 2.

Finnegan

Nathan schrieb:

Copy on write? Wenn ja, das ist out.

Ist das eine allgemeingültige Aussage oder bezieht sich das nur auf diverse std::string -Implementierungen, die man mit COW nur schwer oder nur ineffizent standardkonform hinbekommt?

Im Multithreaded-Umfeld fand ich das bei großen Objekten (nehen wir mal extremerweise Bilder/Texturen) bisher immer einen nicht so verkehrten Ansatz, da man die Synchronisation der schreibenden und Lesenden Threads auf das atomare Austauschen der Pointer zu den dicken Daten beschränken kann. Während die Threads durch die Megabytes rattern und mit den Daten rumrechnen muss also kein Lock gehalten werden. Wenn sowas aus irgendeinem Grund auch out sein sollte, wäre ein Hinweis in die richtige Richtung nicht verkehrt. Interessiert mich, ob ich da vielleicht einen Aspekt übersehen habe.

Finnegan

SeppJ

Finnegan schrieb:

Nathan schrieb:

Copy on write? Wenn ja, das ist out.

Ist das eine allgemeingültige Aussage oder bezieht sich das nur auf diverse std::string -Implementierungen, die man mit COW nur schwer oder nur ineffizent standardkonform hinbekommt?

COW ist nicht schwierig, sonder geht gar nicht mehr standardkonform in Strings, weil man es mit C++11 bewusst verboten hat (davor war es der Quasistandard). Man hat es verboten, weil es out ist. Und zwar ist es gerade deswegen out, weil es in Multithreaded-Umfeld eine Anti-Optimierung darstellt. Merkwürdig, dass du das genau anders herum siehst. Eine ausführliche Erklärung findest du hier:
http://www.gotw.ca/publications/optimizations.htm

Nathan

Finnegan schrieb:

Nathan schrieb:

Copy on write? Wenn ja, das ist out.

Ist das eine allgemeingültige Aussage oder bezieht sich das nur auf diverse std::string -Implementierungen, die man mit COW nur schwer oder nur ineffizent standardkonform hinbekommt?

Ich beziehe mich hierrauf: http://www.gotw.ca/publications/optimizations.htm

Spaghettimann schrieb:

Das wäre alles total überflüssig, wenn es z.B. einen []=-Operator gäbe!!!

Und dann als nächstes dann die Operatoren []++ und []-- oder was? AFAIK ist es nicht möglich einen Proxy für beliebtige Typen zu bauen, der sich in allen Situationen exakt wie der Typ selbst verhält außer, dass er dabei merkt wann gelesen und wann geschrieben wird. Angenommen dein Proxy Objekt speichert ein int und du rufst eine externe Funktion auf welche eine int Referenz akzeptiert. Ist das jetzt ein Lese- oder Schreibvorgang?

Finnegan

SeppJ schrieb:

... Man hat es verboten, weil es out ist. Und zwar ist es gerade deswegen out, weil es in Multithreaded-Umfeld eine Anti-Optimierung darstellt. Merkwürdig, dass du das genau anders herum siehst. Eine ausführliche Erklärung findest du hier:
http://www.gotw.ca/publications/optimizations.htm

Leider erklärt der Artikel nicht, weshalb COW generell "out" sein sollte, sondern lediglich dass die Strategie die interne Repräsentation von Strings eher ungeeignet ist.
Der zentrale Punkt des Artikels ist, dass mit COW-Strings eine zusätzliche Synchronisation mit einer zu feinen Granularität notwendig wird.

Bei einem COW-String muss z.B. der operator+= intern synchronisiert was z.B. wenn man mehrere String-Konkatenationen macht zu einem Overhead führt,
da die Konkatenationen als ganzes ebenfalls nochmal synchronisiert werden müssen, um das beschriebene "interleaving" zu vermeiden.

Das ist allerdings kein allgemeingültiges Argument gegen COW, sondern eher dafür, dass das Locking an der richtigen Granularität ansetzen,
und so wenig (und kurz) wie möglich gemacht werden sollte.

Und genau hier setzt mein Einsatz der COW-Strategie auch an. Lass mich dazu ein Beispiel anbringen:
Ein Bild/Textur, einen Rendering-Thread (1) und ein "Analyse-Thread" (2, Live-Histogramm) die beide das Bild nur lesen, sowie einen Manipulations-Thread,
der das Bild mit einem COW-Ansatz neu skaliert und einen Filter darauf anwendet (=teure Operation, lass sie um die Sinnhaftigkeit von COW hier zu verdeutlichen länger dauern als Thread 1 Zeit hat einen Frame zu rendern):

std::shared_ptr<Image> shared_image("fettes_bild.jpg");

Thread 1 (lesen):
    auto image = std::atomic_load(&shared_image);
    render_image(image);

Thread 2 (lesen):
    auto image = std::atomic_load(&shared_image);
    calculate_histogram(image);

Thread 3 (COW-schreiben):
    auto copied_image = std::make_shared<Image>(*std::atomic_load(&shared_image));
    rescale_and_filter_image(copied_image);
    std::atomic_store(&shared_image, copied_image);

Ich würde so etwas trotz "COW" durchaus als Optimierung ansehen, da die Locks trotz teurer Operationen nur sehr kurz gehalten werden ( atomic ) und die Threads
mehr tatsächliche Arbeit verrichten als dass sie darauf warten müssen, endlich auf das shared_image zuzugreifen.

Es mag sein, dass ich hier noch etwas Wichtiges übersehe, aber in meinen Augen ist die Kuh noch lange nicht tot!

Finnegan

P.S.: Hoffe ich habe nicht zu sehr vom Thema abgelenkt , aber ich habe das mit dem "COW" ist böse schon oft gehört, und die einzige Erklärung,
die ich bisher dazu finden konnte war eben auch dieser antike Sutter-Artikel. Will nicht trollen, sondern lediglich herausfinden, ob mir in meinem Bild etwas fehlt.

Nathan

Das was du zeigst ist jetzt nicht COW. Das ist ein Doublebuffer. Oder man kann es Write-on-Copy* nennen. Du erstellst eine Kopie, arbeitest auf der und tauschst das dann in einem einzigen Schritt auf. Doublebuffer-Pattern, siehe hier: http://gameprogrammingpatterns.com/double-buffer.html

COW, Copy-on-Write, ist: Wenn du ein Objekt kopierst haben erst einmal alle Kopien einen Zeiger auf dieselbe Resource. Erst wenn eine der Kopien etwas ändern will, wird für dieses Objekt die tiefe Kopie durchgeführt.

*Im Sinne von "Schreiben auf Kopie", COW ist hingegen "Kopie wenn geschrieben wird"

Finnegan

Nathan schrieb:

Das was du zeigst ist jetzt nicht COW. Das ist ein Doublebuffer. Oder man kann es Write-on-Copy* nennen. Du erstellst eine Kopie, arbeitest auf der und tauschst das dann in einem einzigen Schritt auf. Doublebuffer-Pattern, siehe hier: http://gameprogrammingpatterns.com/double-buffer.html

COW, Copy-on-Write, ist: Wenn du ein Objekt kopierst haben erst einmal alle Kopien einen Zeiger auf dieselbe Resource. Erst wenn eine der Kopien etwas ändern will, wird für dieses Objekt die tiefe Kopie durchgeführt.

*Im Sinne von "Schreiben auf Kopie", COW ist hingegen "Kopie wenn geschrieben wird"

Ich frage mich wo man da die Genze der beiden Definitionen zieht. Meines erachtens führt ein COW-String die selben Operationen auf seinem internen char* durch, wie ich in meinem Beispiel mit dem shared_image .
Wenn ich den Code von Thread 3 jetzt in einen Member-Funktion von Image packe, und dessen andere non- const Member-Funktionen nach dem gleichen Schema implementiere, habe ich dann ein COW-Image oder DoubleBuffer-Image
Ist der Unterschied dass es intern und transparent geschieht, oder liegt der woanders?

Auch bei "intern und transparent" sehe ich die Vorgehensweise als Optimierung bei Operationen auf dem gesamten Bild - natürlich ist das ändern eines einzelnen Pixels kein guter Kanditat dafür (was wieder in Richtung des operator[] des eigentlich Themas geht).

Finnegan

Nathan

Nein, der Unterschied liegt in der Anwendung:
Du willst eine Änderung allen Usern bekannt machen, COW eine Änderung nur für einen User.

Das Gebiet auf dem ich mich momentan bewege, scheint ein brenzliches Pflaster zu sein. Hier gehts ja immer rund...

Ich dachte COW und ref-counting gehörten zusammen.. Ich wüsste zumindest nicht, wozu ich sonst ref-counting benötigen würde.

sebi707 schrieb:

Und dann als nächstes dann die Operatoren []++ und []-- oder was?

Gibt doch nichts was wirklich dagegen spricht. Das Programm würde nicht langsamer und es zu schreiben würde wesentlich schneller gehen.
Es muss ja nicht gleich der "[]=-OP" sein. Ich denke, es wäre aber schon von Vorteil, wenn man direkt sagen könnte welches xyz-value man mit seinen selbst definierten OPs meint. Der Compiler weiß das schließlich normalerweise auch.
Wenn man am Ende etwas hat, das wirklich wie gewünscht funktioniert, ist mir egal, wieviele OPs noch dazu kommen.
Am einfachsten wären evtl. zusätzliche Spezifizierer wie "read"/"write", aber das ist eh graue Theorie...

Tja leider muss man es erst implementieren, bevor man es testen kann. Ich glaube, ich schmeiße die Geschichte mit dem []-Proxy-OP wieder übern Haufen und nehmen statt dessen get()- und set()-Methoden.
Ich dachte ja, ich würde hier etwas halbwegs professionelles machen, indem ich dann den altbekannten Syntax verwenden könnte, aber so wie es aussieht ist es wirklich nicht mehr als ein Workaround - also Murks!
Mit Funktionen, die eine nicht-konstante Referenz erwarten, kommt der Proxy überhaupt nicht klar, und sonst muss man an fast jeder Ecke zwischendurch casten, selbst wenn man auf Methoden der Element-Klassen zugreifen will.
Sowas wie
array[3].machSchon(); //( "Proxy hat kein machSchon()" ) geht nur als
((elementKlasseMitExtraLangemNamenUndNochAls<TemplateVom<Template> >)array[3]).machSchon();

Das sieht doch echt nicht mehr professionell/schön aus, oder?!
Ich hatte mir erhofft, dass der Compiler den Cast eigenständig ausführt, wenn er nicht weiter weiß - sieht aber nicht so aus..
Also da hätte ich von der Maschine aber etwas mehr eigenständiges Denken erwartet...

Wenn ich darf, hier noch eine Frage zum eigentlichen Thema ;):
Kennt jemand eine Möglichkeit, wie man es irgendwie doch hinbekommt, oder kann mir bestätigen, dass es wirklich nicht besser geht?!

Denn, wenns nicht besser wird, geht die Idee übern Jordan.

Vielleicht erzählst du uns endlich mal was du mit der Unterscheidung zwischen Lesen und Schreiben überhaupt erreichen willst. Vielleicht gibts dafür eine viel bessere Lösung. Mit get() und set() Methoden kommst du übrigens auch nicht weit oder was machst du dann wenn eine Funktion eine nicht konstante Referenz nimmt? get() geht nicht weil es eine konstante Referenz/Kopie zurückgibt und set() geht auch nicht.

Und mit deinem Cast sieht wirklich nicht schön aus. Was für Objekte soll dein Proxy überhaupt speichern? Scheinbar irgendwelche Klassen weil du Memberfunktionen aufrufen willst? Da auch wieder die Frage: Zählt der Aufruf einer Memberfunktion als Lesen oder Schreiben? Du könntest hier vielleicht den operator-> Überladen um den Cast loszuwerden. Statt

array[3].machSchon();

hättest du dann

array[3]->machSchon();

hustbaer

@Finnegan
Ich würde das auch nicht COW nennen. Ich würde hier den Begriff "latch" verwenden - und zwar für den shared_ptr<Image> shared_image .

Vielleicht erzählst du uns endlich mal was du mit der Unterscheidung zwischen Lesen und Schreiben überhaupt erreichen willst.

Naja für die COW-Geschichte/Ref-Counting eben.. Ich will ja nicht "copy-on-read-or-write" haben.

Mit get() und set() Methoden kommst du übrigens auch nicht weit

Dass das mit den get()/set() und "nicht-const &" auch nicht geht, ist mir schon klar. Aber da geht man dann erst garnicht davon aus, dass es gehen könnte, einfach schon wegen des Syntax'.

Was für Objekte soll dein Proxy überhaupt speichern?

Der Proxy soll alles mögliche speichern können, nen Template eben..
Wenn es etwas bestimmtes wäre, gäbe es deutlich weniger Probleme.

Das mit dem "->"-OP müsste gehen.. Aber so richtig konsistent mit dem üblichen Code ist das auch nicht, wenn nicht sogar irreführend. Leider gibts keinen "."-OP..
Irgendwie werde ich das Gefühl nicht los, dass man hier so schnell nicht aus dem "Around-worken" raus kommt, wenn man erstmal damit begonnen hat.

Nathan

Spaghettimann schrieb:

Vielleicht erzählst du uns endlich mal was du mit der Unterscheidung zwischen Lesen und Schreiben überhaupt erreichen willst.

Naja für die COW-Geschichte/Ref-Counting eben.. Ich will ja nicht "copy-on-read-or-write" haben.

Wenn du COW willst: COW macht keinen Sinn bei Multithreading, a.k.a. lass es.

Was für Objekte soll dein Proxy überhaupt speichern?

Der Proxy soll alles mögliche speichern können, nen Template eben..
Wenn es etwas bestimmtes wäre, gäbe es deutlich weniger Probleme.

Das mit dem "->"-OP müsste gehen.. Aber so richtig konsistent mit dem üblichen Code ist das auch nicht, wenn nicht sogar irreführend. Leider gibts keinen "."-OP..

Es gibt einen Proposal für operator., kenn den Status nicht.

Spaghettimann schrieb:

Naja für die COW-Geschichte/Ref-Counting eben.. Ich will ja nicht "copy-on-read-or-write" haben.

Ich fürchte es ist nicht Möglich mit den aktuellen C++ Möglichkeiten aus jedem beliebigem Typ ein Typ mit COW zu machen. Fürs Reference Counting gibts shared_ptr.

Leider gibts keinen "."-OP..

Gibts schon, kann man aber nicht überladen.

Nathan schrieb:

Wenn du COW willst: COW macht keinen Sinn bei Multithreading, a.k.a. lass es.

Och aber damit umgehe ich doch das lästige kopieren. Ich habe mir den alten Artikel nicht wirklich durchgelesen, schon alleine, weil sich hier nicht alle einig waren, aber wenn ich jetzt nicht 'multithreadde' ist das doch schon ein Vorteil oder?

Spontan fällt mir z.B. dies ein:

array<int> ai;
ai.InitAlleInts();

array<array<int> > aai;
aai.SetzeAnIdx0(ai);

Wen ich das jetzt ohne COW mache, habe ich nachher 2 ais. 1 (im Array-Array) wäre mir aber genug. Aber fürs Init muss ich ja i.A. immer erst ein "echtes" Objekt erstellen..

Nathan schrieb:

Es gibt einen Proposal für operator., kenn den Status nicht.

So lange (wie lange?) kann ich nicht warten..

sebi707 schrieb:

Ich fürchte es ist nicht Möglich mit den aktuellen C++ Möglichkeiten aus jedem beliebigem Typ ein Typ mit COW zu machen. Fürs Reference Counting gibts shared_ptr.

Hmhmhm, dann werde ich mir den mal ansehen..

sebi707 schrieb:

Gibts schon, kann man aber nicht überladen.

So wie z.B. in
((elementKlasseMitExtraLangemNamenUndNochAls<TemplateVom<Template> >)array[3]).machSchon();
? -Höhöö

Nathan

Spaghettimann schrieb:

Nathan schrieb:

Wenn du COW willst: COW macht keinen Sinn bei Multithreading, a.k.a. lass es.

Och aber damit umgehe ich doch das lästige kopieren. Ich habe mir den alten Artikel nicht wirklich durchgelesen, schon alleine, weil sich hier nicht alle einig waren, aber wenn ich jetzt nicht 'multithreadde' ist das doch schon ein Vorteil oder?

Spontan fällt mir z.B. dies ein:
array<int> ai;
ai.InitAlleInts();

array<array<int> > aai;
aai.SetzeAnIdx0(ai);
Wen ich das jetzt ohne COW mache, habe ich nachher 2 ais. 1 (im Array-Array) wäre mir aber genug. Aber fürs Init muss ich ja i.A. immer erst ein "echtes" Objekt erstellen..

Wie viele Stunden hängst du da jetzt schon dran?
Und die Optimierung wirst du im seltensten Fall merken.
Lass es einfach, wenn du wirklich Performanceprobleme hast, die an zu vielen Kopien liegen, komm nochmal.

Wie viele Stunden hängst du da jetzt schon dran?

Jaaa - zu viele, besonders an der Proxy(-Proxy)-Geschichte. Vor allem, wenn man mal davon ausgeht, dass ich es jetzt wohl doch 'billig' machen werde, oder doch gleich nen vector nehme (...leider...;) )..

Und die Optimierung wirst du im seltensten Fall merken.

Das war mir schon bewusst. Mir ging es eher ums Prinzip. Zur Übung sozusagen.. Viel mehr werde ich leider aus der Geschichte auch nicht mitnehmen können, wies aussieht.

hustbaer

Nathan schrieb:

Wenn du COW willst: COW macht keinen Sinn bei Multithreading, a.k.a. lass es.

Wieso denn das?
Klar macht COW auch Sinn bei MT. Über shared_ptr geht das sogar recht schön.

void write()
{
   if (!m_guts.unique())
      m_guts.reset(new Guts(*m_guts));

   m_guts->write();
}

Ist einzig doof wenn die write Operationen ziemlich billig und ziemlich häufig sind. Dann könnte der Overhead des threadsicheren shared_ptr bemerkbar werden.