title image


Smiley Re: deepcopy / shallowcopy / reference counting
Ich versuch's mal anhand eines Beispiels:

In C++ (und auch in anderen Sprachen) werden oftmals Objekte verwendet, die sich um das Reservieren bzw. Freigeben von Speicher selbst kümmern, man nennt das dann RAII (Resource Aquisition is Initialization).



class Foo {

public:

Foo () : bar_ (new Bar) {}

~Foo () { delete bar_; }

private:

Bar *bar_;

};



Hier ist die Klasse selbst Foo zuständig für das Bereitstellen bzw. Entsorgen von Speicher für die Klasse Bar (und natürlich auch für deren Konstruktion bzw. Destruktion). Die Klasse Bar ist also die Ressource.

Wenn Instanzen der Klasse Foo kopiert werden sollen, gibt es mehrere Möglichkeiten:



1) Die Klasse Foo reserviert bei jeder Kopie ihren eigenen Speicher für die Ressource "Bar", das nennt man dann "deep-copy".



class Foo {

public:

// ... wie oben, zusätzlich:

Foo (const Foo &rhs) : bar_ (new (rhs.bar_)) {}

Foo& operator = (const Foo &rhs) {

if (this != &rhs) {

Foo tmp (rhs);

swap (this->bar_, tmp.bar_);

}

return *this;

}

};



Foo foo1;

Foo foo2(foo1); // -> tiefe Kopie (deep-copy)



Das wird bei vielen Kopien sehr teuer, da jedesmal neuer Speicher reserviert werden muß, vor Allem dann, wenn die Instanz "bar_" nach deren Erzeugung niemals verändert wird.



2)Solange auf die Ressource bar_ nur lesend zugegriffen wird, könnten sich mehrere Foo-Instanzen denselben Speicherbereich für die Bar-Instanz teilen. Beim Erzeugen von Foo-Instanzen reicht es also, nur einmal ein Bar-Objekt dynamisch zu erzeugen. Alle nachfolgenden Kopien kopieren nur den Pointer auf die Bar-Instanz (-> "shallow-copy"). Erst wenn ein Schreibzugriff erfolgt, also "bar_" im oberen Beispiel durch irgeneine Instanz von Foo verändert wird, muß die entspr. Foo-Instanz eine neue Kopie von Bar erzeugen. Man nennt das auch copy-on-write (oder kurz COW). hier ein Beispiel ohne COW:



class Foo {

public:

// wie 1.Beispiel, _o_h_n_e_ eigenen copy-c'tor und Zuweisungsoperator !!!!

void changeBar (const Bar& bar) {

Bar *tmp = new Bar (bar);

delete bar_;

bar_ = tmp;

};

};



Foo foo1; // hier wird ein Bar-Objekt dynamisch erzeugt.

Foo foo2 = foo1; // nur Lesezugriff (shallow-copy)

Bar b;

foo1.changeBar (b); // jetzt haben wir ein Problem



In der letzten Zeile wird nicht nur das Bar-Objekt von foo1, sondern auch von foo2 verändert !

Ein weiteres Problem ergibt sich, wenn foo1 bzw foo2 zerstört werden. Im Destruktor der Klasse Foo wird der Speicherbereich von "bar_" mit delete freigegeben. Die "bar_" - Instanz wurde nur einmal dynamisch erzeugt, soll aber jetzt zweimal gelöscht werden. Resultat: Absturz des Programmes.

Hier kommt "reference-counting" ins Spiel. Die Klasse Foo könnte einen Zähler verwalten, der die Anzahl der Kopien von "bar_" hält. Bei jeder Kopie einer Foo-Instanz wird der Zähler um 1 erhöht, und bei jeder Zerstörung eines Foo-Objektes um 1 vermindert. Wenn der Zähler auf 0 vermindert wurde, wird die "bar_"-Instanz zerstört.



Hier ein einfaches Pseudo-Beispiel mit reference-counting (ohne COW):



struct Bar {}; // die Ressource



// Der Referenzzähler ist oftmale als eigene Klasse implementiert.

// Das erleichtert die Realisierung von reference-counting in

// Multithreaded-Umgebungen. In diesem Beispiel würde auch ein

// einfacher pointer auf size_t genügen.



struct RefCounter {



RefCounter () : i_ (1) {}

size_t i_;

};



class Foo {



public:



Foo () : bar_ (new Bar), counter_ (new RefCounter) {}

Foo (const Foo &rhs) : bar_ (rhs.bar_),

counter_ (rhs.counter_) {

counter_->i_++;

}



~Foo () {

if (--counter_->i_ == 0) {

delete bar_;

delete counter_;

}

}



private:



Foo& operator = (const Foo &rhs); // Hausaufgabe ;-)



Bar *bar_;

mutable RefCounter *counter_;

};



int main()

{

Foo f1;

Foo f2;

Foo f3 (f1);

Foo f4 (f2);

Foo f5 (f1);

return 0;

}



Zuweisungen der Art f1=f2; habe ich absichtlich nicht implementiert. Bleibt also Dir überlassen ;-)

Weitere (und vor Allem bessere) Beispiele zu dem Thema liefert Dir Google (C++, reference-counting).

Hier findest Du ein Beispiel für eine string-Klasse mit COW und reference-couting:

http://www.gotw.ca/gotw/index.html

(die Items #43 bis #45).



Im Buch "More Effective C++" von Scott Meyers wird COW ebenfalls ausführlich beschrieben.



Cheers,

BF



geschrieben von

Login

E-Mail:
  

Passwort:
  

Beitrag anfügen

Symbol:
 
 
 
 
 
 
 
 
 
 
 
 
 

Überschrift: