F
@hustbaer sagte in Multithreading und Iterieren:
@Finnegan
Ja, so war das gemeint:
Dazu sollte man noch sagen dass "Kopie" hier nur ein Konzept ist. Man kann das so implementieren dass man wirklich die gesamten Daten kopiert. Es gibt aber noch andere Möglichkeiten. Eine ist z.B. dass man mit shared_ptr<const T> arbeitet. D.h. man hält alle Daten über shared_ptr auf Objekte die dann nicht mehr verändert werden. Statt das Objekt zu ändern, macht man ein neues verändertes Objekt. Wird das geänderte Objekt von einem anderen Objekt aus referenziert, dann macht man für dieses wieder ein neues verändertes Objekt usw. Bis man beim "root" der Datenstruktur angekommen ist.
War nicht os ganz gut beschrieben, aber das war der Gedanke. Also nicht unbedingt mit einem binären Baum, das geht mit jeder Baum-Struktur. z.B. auch mit B-Bäumen. Da muss man dann vermutlich etwas experimentieren welche Node-Grösse ideal ist. Und BTW: ich hab das auch nicht erfunden, hab's wo gelesen
Habe deine Beschreibung als allgemeinen Ansatz verstanden, ob jetzt Baum, zusammenhängendes Array oer was auch immer. Meine Idee ist da schon eine sehr spezielle Lösung für Bäume, wo das "snapshotten" schon etwas schwieriger ist, da man die ja nicht so einfach in einem Rutsch kopieren kann wie nen Array - naives Kopieren wäre da viel zu umständlich. So bezahlt man zwar die Atomics in den Nodes extra, das Kopieren selbst ist dann aber quasi "kostenlos". Auch ist die Idee nicht komplett von mir, ich erinnere mich noch vage an ne ähnliche Baumstruktur aus der Uni, die O(n)O(n)O(n) Platz benötigte und mit der man ähnlich wie in einem Git-Tree jede vorangegangene Version abfragen konnte. Habe diesen Ansatz aber bisher noch nicht im Kontext von billigen Snapshots für Threads gesehen, um Locks einzusparen.
Was man bei Bilddaten gut machen kann ist das Bild in Kacheln aufzuteilen. Je nachdem wie gross das Bild ist kann man dann einfach ein flaches 2D Array der Kacheln (also halt Array von shared_ptr auf die Kacheln) erstellen, oder auch mit mehreren Ebenen. So ähnlich wie ein 2-dimensionaler B-Baum.
Ich denke da kann man sich gut bei der Echtzeit-Computergrafik inspirieren was effizientes Multithreading angeht. Da hat mans ja oft mit ein paar tausend Threads zu tun, die garantiert nicht jeden Pixel mit nem Mutex synchronisieren ... in dem Bereich sind aber auch die meisten Probleme gut parallelisierbar. Bei Bilddaten kann man wahrscheinlich meist einfach mehrere Threads ohne Locking auf unterscheidliche Bereiche des Bilddaten-Arrays losjagen und muss dabei höchstens auf solche Dinge wie False Sharing achten.
Und statt manuellem Referenzzähler würde ich halt shared_ptr verwenden. Wobei... mit manuellem Reference-Count kann man eine nette Optimierung machen: wenn man den "root lock" angezogen hat (=es können keine neuen Referenzen entstehen), und der Reference-Count eines Knotens + aller seiner Parents 1 ist, dann kann man sicher sein dass es keine anderen Referenzen auf diesen gibt - und kann einfach "in place" modifizieren.
Mit shared_ptr wäre das auf Grund der nicht ausreichenden thread-safety von use_count nicht thread-safe.
Ist nicht gerade der Kontrollblock mit dem use_count das einzige, was bei einem puren shared_ptr threadsicher ist? Meines erachtens braucht es da sowieso keinen atomic<shared_ptr>, da einmal eingefügte Knoten nicht mehr verändert werden (kein "umhängen" und sowas, lediglich Kopien des Pointers via shared_ptr-Konstruktor durch neu erzeugte Knoten aus verschiedenen Threads heraus). Die einzige nicht-const-Memberfunktion die dann noch aufgerufen wird, ist ein (implizites) reset() für den linken und rechten Kindknoten im Knoten-Destruktor. Das kann zwar in einem beliebigen Thread passieren, aber immer nur in einem einzigen (ist ja die letzte Referenz). Es gibt also keine konkurrierenden Aufrufe von nicht-const-Memberfunktionen.
Dass die Kindknoten-Pointer über die gesamte Lebenszeit des Knotens unverändert bleiben ist übrigens eventuell auch noch ein Grund, den Referenzzähler selbst zu implementieren. Die Pointer im Knoten sind const-Data, und da will ich eigentlich keine Atomics für verwenden. Ich denke da muss man vielleicht irgendein Hexenwerk mit std::atomic_thread_fence oder sowas machen um sicherzustellen, dass der Pointer auf einen neuen Knoten für andere Threads nicht vor den Kindknoten-Pointern sichtbar ist. Dann müsste das auch mit nackten, nicht-atomic Pointern und entsprechend weniger Overhead gehen. Eine eigene Referenzzähler-Implementierung bietet da vielleicht mehr Kontrolle, was da genau passieren soll. Nagel mich da aber bitte nicht fest - würde ich das implementieren, müsste ich erstmal ne menge Zeug auffrischen und nachlesen ...
