Multithreading und Iterieren



  • Hi, ich habe leider für folgendes Problem immer noch keine Lösung mit der ich mich abfinden kann :). Mal angenommen eure Applikation importiert viele Daten um sie im Speicher vorzuhalten. Dazu kommt, dass die Daten in mehreren "Views" (z.B. map, unordered_map, maps in maps usw.) mit unterschiedlichen Schlüsseln dargestellt werden. Jetzt gibt es auch noch mehrere Threads die mit diesen Daten arbeiten sollen also auch über diese iterieren müssen. Zuweil sogar in verschachtelten Schleifen. Die Daten sind auch nicht statisch d.h. mit der Zeit werden Elemente aus den "Views" gelöscht oder hinzugefügt. Bislang halte ich für jeden Container einen Mutex vor der dann vor dem Zugriff gelockt werden muss. Aber gerade bei verschachtelten Schleifen muss man mehrere Mutexe locken und dann die Reihenfolge beachten usw. Also kurz gesagt es ist kaum noch zu verstehen, extrem fehleranfällig und das Locken der kompletten Container denkbar ungünstig. Aber wie macht man es besser? Das Problem ist doch dass man die std Container "nachträglich" nicht mehr um Threadsicherheit erweitern kann. Das ist immer Murks. Eigentlich müsste der Container selber schon threadsicher sein, damit der Anwender gar nichts mehr falsch machen bzw. vergessen kann.

    Jetzt ist es ja möglich für std Container auch Custom Iteratoren zu schreiben. Ich habe zwar gelesen, dass diese Iteratoren irgendwie deprecated sein sollen, aber es wäre der beste Ansatz der mir einfallen würde, außer die Listen dauernd zu kopieren um über diese zu iterieren oder gar die Daten für jeden Thread doppelt vorzuhalten was aufgrund der vielen Daten wenig attraktiv erscheint. Jemand Erfahrung damit. Kann man custom Iteratoren so implementieren, dass die std container threadsicher sind?

    Falls nicht wie macht man es besser?



  • @Enumerator sagte in Multithreading und Iterieren:

    Aber wie macht man es besser?

    Wenn es irgend wie möglich ist, eine lockfree Datenstruktur nutzen. Wenn Du anfängst auf einzelne Elemente in einem Container Mutexe zu setzen, dann wird die Performance nicht sonderlich gut sein. Dazu musst Du beachten, dass es Cache Lines gibt, d.h. es reicht nicht aus nur einen Wert zu locken, sondern Du musst immer komplette Cache Lines locken.

    Beispiel std::vector<int> mit sizeof(int)==4 bei den üblichen CPUs ist eine Cache Lines 64 Bytes groß. Du musst also den Speicher für std::vector auf eine durch 64 teilbare Adresse legen (Custom Allocator) und dann immer 8 Elemente im std::vector zugleich locken. Dann kann die Performance ok sein. Ich hab's vergessen was im anderen Fall passiert, entweder steht Grütze später im Speicher oder die Performance ist unterirdisch.



  • @Enumerator sagte in Multithreading und Iterieren:

    außer die Listen dauernd zu kopieren um über diese zu iterieren oder gar die Daten für jeden Thread doppelt vorzuhalten was aufgrund der vielen Daten wenig attraktiv erscheint.

    Haste das mal getestet und gemessen? Ich ertappe mich jedenfalls immer wieder dabei wie ich den Aufwand fürs Kopieren überschätze. Das effizienteste Locking ist immer noch das, welches man überhaupt nicht macht. Ich kenne zwar dein konkretes Problem nicht - das muss also nicht zutreffen - aber ich habe da durchaus schon Verarbeitungsgeschwindigkeiten gesehen, die gleich mal eine oder mehr Größenordnungen flotter waren.

    Vielleicht muss man ja auch nicht wirklich alles kopieren. Man kann ja durchaus auch mit Referenzen auf die ursprünglichen "immutable" Daten arbeiten (Referenzen im allgemeinen Sinn, also Indizes, Pointer, Interatoren in einen Container oder was auch immer - nicht zwangsläufig ref&). Vor allem wenn du das Wort "Views" verwendest, muss ich an std::ranges::views in C++20 denken. Auch die kopieren die Daten nicht, sondern stellen nur eine lazy-evaluierte Sicht auf die Ursprungsdaten zur verfügung: Daten sollen aus meinem fetten std::vector gelöscht werden, bevor ich sie weiterverarbeite? Vielleicht spare ich mir das Löschen, lasse den std::vector unangetastet und iteriere stattdessen über einen filter_view(daten, loeschkriterium). Der gibt mir z.B. Iteratoren, die meine gelöschten Elemente einfach überspringen - ohne eine Kopie anzulegen und ohne den Vektor zu "mutieren". Auch wenn man C++20 noch nicht verwenden kann, so kann man sich da eventuell dennoch ein paar Ansätze abgucken - nen simplen filter_view-Iterator könnte man sich durchaus auch noch selbst stricken.

    Das ist aber alles stark von deinem tatsächlichen Problem und dem bereits vorhandenen Code abhängig, das soll nur als Anregung dienen, wie man das Problem eventuell alternativ betrachten kann.



  • Der übliche Satz: Die Problemlösung hängt stark von deiner konkreten Problemstellung ab.
    Aus Erfahrung kann ich nur davon abraten bei häufigen Zugriffen auf Daten mit geschützten Containern zu arbeiten. Wir nutzen firmenintern eine Art BasisFramework für die Serverentwicklung und die Variante die derzeit leider teilweise immer noch im Einsatz ist, ist fast 20 Jahre alt und setzt auch genau auf diese geschützten Listen. Wir bekommen mit diesen alten Anwendungen die CPU nie wirklich unter Dampf, weil es einfach unglaublich viele Kollisionen gibt.
    Ich arbeite jetzt gerade am neuen Framework was keinen einzigen kritischen Bereich verwendet und es ist wunderbar!

    Es taugt freilig nicht für jeden Anwendungsfall aber wenn du viele Daten hast und viele Deltas, dann macht es aus meiner Sicht manchmal tatsächlich Sinn, jedem Modul ein eigene Kopie der Daten zu gönnnen und nur die Deltas dann an alle Module zu verteilen. ( Delta im SInne von: Eintrag wurde gelöscht, Eintrag wurde modifiziert ). Das versetzt dich auch in die Lage nicht immer den kompletten Datensatz zu verteilen sondern auch mal nur einen INT, wenn das ausreichend ist. Du bist flexibel in der Wahl der Waffen, aber die Implementation ist komplexer als eine geschützte Liste.

    Wenn allerdings die Datensätze immer konstant sind und sie höchstens mal gelöscht oder hinzugefügt werden, dann lohnt es sich natürlich die Daten als shared_ptr zu halten und nur den shared_ptr zu vervielfachen und in die verschiedenen Views deiner einzelnen Module zu verschiffen. Da würdest du dann gegenüber der Kopie ne Menge Speicher sparen.

    It depends....

    Wärmstens empfehlen kann ich das Facebook-Framework:
    https://github.com/facebook/folly

    Die haben dort auch sehr schöne Atomic-Container. Vielleicht hilft dir das ja auch für den Anfang.



  • Ich denke es gibt hier zwei sehr unterschiedliche Lösungsklassen:

    1. Locking
    2. Snapshots

    Locking sollte klar sein. Das kann man natürlich unterschiedlich implementieren bezüglich wie feingranular gelockt wird.

    Was Snapshots angeht: konzeptuell wird hier eine Kopie der Daten gemacht. Locks müssen nur gehalten werden während die Kopie erstellt wird. Wie lange das Iterieren über die Daten dann braucht ist egal. Nachteil: es kann sein dass man über Daten iteriert die in der "master copy" bereits geändert wurden bzw. u.U. sogar schon gelöscht.
    Vorteil: die lesenden Threads halten niemanden auf - weder sich gegenseitig andere Threads die schreiben müssen.

    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.

    So kann man eine "Kopie" machen indem man sich einfach den "root" shared_ptr der Datenstruktur kopiert. Man muss das Lock also nur extrem kurz halten.

    Wie gut das funktioniert hängt natürlich davon ab wie die Daten aussehen. Wenn es einfach ein riesen vector<double> ist, funktioniert es nicht so gut. shared_ptr<vector<double>> heisst man muss erst wieder den ganzen vector<double> kopieren wenn man eine Änderung macht. Und vector<shared_ptr<double>> ist ziemlich sicher auch nicht sinnvoll.

    In dem Fall kann das Erstellen einer echte Kopie vielleicht doch der beste Fall sein. Wenn viel häufiger gelesen als geschrieben wird, kann man das auch noch ein wenig optimieren. Denn es reicht ja eine Kopie pro Änderung. Wenn zwischen zwei Änderungen mehrere Leser einen Snapshot wollen, dann können sich diese die Kopie ja teilen. Hier kann man wieder schön shared_ptr<const T> verwenden um die Kopien zu verwalten. Im Gegensatz zur vorhin beschriebenen Methode spart man sich dabei auch das Erstellen von Kopien wenn mehrere Änderungen hintereinander erfolgen, ohne dass in dieser Zeit ein Leser einen Snapshot anfordert.

    ps: Die Variante von @It0101, also Replikation, klingt auch nicht blöd. Das wäre dann eine 3. Klasse.



  • Hi, danke für die Denkanstöße. Die Container haben alle shared_ptr. Vielleicht sollte ich das Kopieren doch mal in Erwägung ziehen. Das hatte ich auch schon durch gesponnen. Evtl. einen Read/Write Mutex verwenden, die Iteratoren besitzen Kopien der Daten. Zudem hat der Container einen Versionszähler genauso wie sich die Iteratoren die Version der Liste zum Zeitpunkt der Kopie merken. Hat sich die Version des Container geändert muss der Iterator wieder eine neue Kopie holen vor dem nächsten Iterieren. Unnötige Kopien würden so vermieden. Aber es sind halt in einigen Szenarien doch häufige Änderungen am Container fällig und wie stellt man sicher, dass bei verschachtelten Schleifen die Listen nicht unterschiedliche Stände haben. Die Lockfree bzw. die ConcurrentHashMap von Facebook hat wohl auch das Problem das beim zeitgleichen Iterieren und Einfügen bzw. Löschen von Daten einzelne Elemente evtl. nicht gesehen werden oder dann unerwartete "zusätzliche" Elemente vorkommen was in manchen Szenarien auch wiederum ungünstig wäre wenn Aufrund der Daten Berechnungen erfolgen. "Die" eine Lösung für alle Anwendungsfälle gibt es wohl nicht :). Vielleicht muss ich auch stattdessen einfach das Applikationsdesign überdenken.



  • @Enumerator sagte in Multithreading und Iterieren:

    Aber es sind halt in einigen Szenarien doch häufige Änderungen am Container fällig und wie stellt man sicher, dass bei verschachtelten Schleifen die Listen nicht unterschiedliche Stände haben.

    Ich weiss nicht genau was du mit Iteratoren meinst.
    Was ich meine hat mit klassischen STL Iteratoren erstmal direkt nichts zu tun. Wenn du mit einer verschachtelten Schleife irgendwo drüber iterieren willst, dann ziehst du dir explizit am Beginn der gesamten Lese-Operation einen Snapshot:

    void iteratorOverStuff() {
        auto snapshot = data.getSnapshot();
        // Hier kannst du beliebig oft über die Daten in `snapshot` iterieren ohne dass sich was ändern kann
    }
    

    Die getSnapshot Funktion kann dann z.B. anhand von Change-Countern prüfen ob die letzte erstellte Kopie wiederverwendet werden kann oder ob eine neue erstellt werden muss. Der Snapshot kann dann gerne Funktionen haben um Iteratoren auf diverse Container rauszugeben.

    Ich würde auf jeden Fall nicht direkt mit Iteratoren arbeiten um einen Snapshot zurückzugeben. Erstmal weil das unnötig fummelig wird (du müsstest dazu eigene Iteratoren implementieren). Und wenn mehr als ein Container benötigt wird funktioniert das schon nicht mehr - zumindest nicht sinnvoll. Du müsstest dann ja mehr als einen Iterator zurückgeben. Und dann kannst du gleich ein eigenes Snapshot Objekt zurückgeben (bzw. einen shared_ptr<Snapshot>).

    Je nachdem was für ein Daten-Set im Snapshot benötigt wird brauchst du dafür ggf. auch unterschiedliche Snapshot-Klassen und getSnapshot Funktionen - damit du nicht Zeugs mit kopierst was gar nicht benötigt wird.

    Bzw. bei der Variante von @It0101 (Replikation) müsstest du das Einpflegen der Daten in die Replikate mit dem Iterieren synchronisieren. Eine Möglichkeit dazu wäre die Daten immer live (synchron) bei jeder Änderung einzupflegen, ausser wenn gerade iteriert wird. Während iteriert wird müssen die Änderungen dann gepuffert werden, und wenn man mit Iterieren fertig ist pflegt man alle gepufferten Daten ein und schaltet wieder auf live updates um.

    Eine andere Möglichkeit wäre die Änderungen asynchron einpflegen zu lassen. In dem Fall wäre jeder Lese-Thread für das Einpflegen der Änderungen in "seine" Kopie zuständig. D.h. er muss dann periodisch die Änderungen-Einpflegen Funktion aufrufen während er nix zu tun hat, und während er iteriert tut er das halt nicht. -> Producer-Consumer Queue.



  • Hatte gerade beim Stichwort "Snapshot" eine interessante Idee für (binär-)baum-basierte Dictionaries. Das ist nichts das man mal "eben so" implementiert - daher schweift das etwas ab (sorry), mich interessiert lediglich, ob schonmal jemand von so einem Ansatz gehört hat:

    Schreiboperationen mutieren den Baum nicht, sondern erzeugen für die veränderten Knoten auf den Pfad(en) von der Wurzel bis runter zu Blattknoten einen eigenen, neuen Baum. Allerdings werden von der Operation nicht betroffene Unterbäume nicht kopiert, sondern lediglich deren Knoten eingehängt (Unterbäume können in mehreren Bäumen vorkommen). Die Operation erzeugt also für alle Knoten, die verändert werden müssen, eine neue, eigene Kopie. Resultat ist ein neuer Wurzelknoten, der eine neue Version des Baums mit der durchgeführten Operation bildet. Da alte Knoten nicht angefasst werden, bleibt die vorherige Version des Baums über den alten Wurzelknoten unverändert und weiterhin gültig. Meine Vermutung ist, dass Schreiboperationen lediglich log(n)\log(n) neue Knoten/Kopien anlegen müssen.

    Die Lebenszeit der Knoten wird über einen atomaren Referenzzähler verwaltet. Das führt natürlich zu Overhead bei Schreiboperationen, z.B. wenn vorhandene Unterbäume in neue Knoten eingehängt werden. Dafür könnten allerdings nicht-mutierende Queries nahezu komplett ohne Locking auskommen, da sie sich nur durch den Baum hangeln und die (atomaren) Referenzzähler nicht verändern müssen. Letzteres wäre lediglich für eine Referenz auf den Wurzelknoten nötig, die sich die Query holen muss, um einen "Snapshot" der aktuellen Version zu erzeugen und die aktuelle Version des Baums am Leben zu halten.

    Frage mich, ob das (gut) funktioniert und ob's das schon irgendwo gibt (bin sicher nicht der erste mit so ner idee 😉 ) - Snapshots wären da jedenfalls extrem billig, ein bisschen wie bei diversen Dateisystemen wie z.B. btrfs u.ä.



  • @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 🙂

    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.

    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.



  • Nochmal eine Frage zum Read/Write bzw. std::shared_mutex. Kann in einem Szenario mit zwei Threads A u. B und zwei Containern C1 u. C2 ein Deadlock entstehen gesetzt, dass Thread A über C1 iteriert und Elemente in C2 einfügen will und Thread B über C2 iteriert und Elemente in C1 einfügen möchte?

    Ja sieht so aus: If one thread has acquired the shared lock (through lock_shared, try_lock_shared), no other thread can acquire the exclusive lock, but can acquire the shared lock.



  • @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) 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 😉 ...


Anmelden zum Antworten