C++ Gemeinsamer fixer Container beim Threading

Hallo,

ich würde gerne Daten für unterschiedliche Threads in eine gemeinsame Datenstruktur legen.
Beispielsweise eine std::map oder std::vector enthält dann pro Eintrag die Daten für jeweils einen Thread.
Am Beispiel des Vectors:


Jedem Thread gehört also ein Vectoreintrag in dem wiederum die eigentlichen Daten im inneren Vector sind.
Die äusseren Vectoren werden fix erzeugt bevor die Threads gestartet werden.
Jeder Thread greift nur auf seine eigenen Daten zu.

Die Daten im inneren Vector werden wie geschildert ausschließlich vom jeweiligen Thread benutzt, insofern sollte es theoretisch kein Konflikt geben.
Jetzt zur eigentlichen Frage. Ich bin mir nicht sicher ob durch den gemeinsame Übergeordnete Vector (oder Map) Konflikte ausgeschlossen sind, denn die Daten sind zwar völlig getrennt aber der Verweis darauf läuft ja immer über den selben übergeordneten vector was ja wahrscheinlich irgendwie ein Zeiger ist. Daher die Frage, ist der Zugriff über den selben äussere Vector Threadsave?

Gruß

ja ist es. Da du auf den äußeren vector nur lesend zugreifst, gibt es kein Problem.

Ja gleichzeitiges lesen ohne Synchronisierung auf konstanten Daten ist natürlich kein Problem. Ich würde sogar einen Schritt weiter gehen:
Auch das schreibende ersetzen/verändern vorhandener Werte innerhalb der Vektoren ist sicher, solange es um konstant-große Typen geht wie in deinem Beispiel 'int' (und natürlich solange niemals mehrere Threads das selbe Element zugreifen - wie es bei dir ja sichergestellt ist).
Siehe auch hier vector[] unter "Data races".
Die vectoren dürfen aber von den jeweiligen Threads ansonsten nicht verändert werden! Dh push_back oder emplace_back oder reserve oder resize ist definitiv ein Problem.

kann leider kein c++

ist deine uebergeordnete datenstruktur ein einfaches array oder ist es ein objekt, welches mittels einer methode die eintraege vornimmt?
bei letzterem sollte die methode "atomar" sein.

Sehr gut das ist prima

@ protossgamer
Die Datenstruktur lief hinaus auf eine der genannten c++ Standardcontainer aber die Frage zum OOP ist trotzdem sehr interessant.
Wenn ich eine Klasse schreiben würde wo die Objekte das Array beinhaltet, dann wäre es denke ich mal auch kein Problem solange die Threads nur auf eigene Bereiche in den inneren Arrays (bei 2D Array) zugreifen.
Eine Methode glaube ich dürfte dann auch kein Problem darstellen solang auf unterschiedlichen Daten das read/write stattfindet. Eine Methode ist ja in gewisser Weise auch nur eine Funktion.
Man könnte auch ein Struct oder eine Klasse in das äussere Array legen und das innere Array kommt ins Struct.
da kann man dann noch weitere Dinge für die Threads reinpacken und so schön Ordnung halten, sollte auch gehen.

Falls du auf der etwas experimentellerer Seite bist: https://msdn.microsoft.com/en-us/library/dd504906.aspx . Ist für VS und bietet dir ein subset der nötigen Standardcontainer als Thread-Safe-Variante (für die angegeben Methoden).

​Bedenke, liegen die Daten, auf die du (schreibend) zugreifst, näher als 64 Byte aneinander, gibt das in modernen Rechnern ein Cache-Konflikt und die Performance geht in die Knie. Insgesamt: Mach kein Multithreading, falls es nicht nötig ist.

Bedenke, liegen die Daten, auf die du (schreibend) zugreifst, näher als 64 Byte aneinander, gibt das in modernen Rechnern ein Cache-Konflikt und die Performance geht in die Knie.

Zum Vergrößern anklicken....

Dagegen kann man ja (bei sinnvoll parallelisierbaren Problemen) etwas tun: Für jeden Thread lokale Datenstrukturen benutzen, die die anderen Threads gar nicht zu sehen bekommen. Also wenn beispielsweise irgendwelche Sachen gezählt werden sollen, lieber pro Thread eine Zähler-Struktur benutzen und die dann am Ende aufaddieren, statt auf einer globalen Struktur zu arbeiten.

Das lässt sich natürlich nicht mit allen Datenstrukturen ohne weiteres machen und man muss schon etwas erfinderisch sein, wenn das ganze am Ende effizient sein soll.

Hancock schrieb:

​Bedenke, liegen die Daten, auf die du (schreibend) zugreifst, näher als 64 Byte aneinander, gibt das in modernen Rechnern ein Cache-Konflikt und die Performance geht in die Knie.

Zum Vergrößern anklicken....

Gut zu wissen, gibt es für das Phänomen eine Bezeichnung? konnte dazu nichts finden.

Würde das in meinem Fall überhaupt zu einem Problem führen wenn Beispielsweise jeder Thread nur in seiner eigenen Map agiert?
Die Threads teilen sich ja keine Arrays oder ähnliches, sondern der einzige Schnittpunkt wäre eben der Übergeordnete Container wo jeder Thread sein eigenen Map oder Vectoreintrag hat indem sich dann die Daten befinden. Allerdings vielleicht liegt der letzte Inhalt in einem Mapeintrag zu nah (weniger als 64 byte) am ersten Inhalt des darauf folgenden Mapeintrag. Das könnte natürlich passieren...

VikingGe schrieb:

Für jeden Thread lokale Datenstrukturen benutzen, die die anderen Threads gar nicht zu sehen bekommen.

Zum Vergrößern anklicken....

Das wäre natürlich möglich. Ich hatte erst an eine global liegende Datenstruktur gedacht, da ich so in Zukunft auch bespielsweise einer anderen Logik wie einer GUI einfach ermöglichen kann ein Array darzustellen oder so.

Wenn allerdings die Datenstruktur lokal (wegen der 64 Byte Problematik) mehr Vorteile und Performance bietet und man doch mal von aussen (zB GUI) Daten will, könnte man vielleicht auch eine globale Zeigerliste auf die inneren Datenstrukturen anlegen. So wäre alles lokal im Thread aber über Zeiger kann man auch mal von aussen reingucken. Vielleicht macht das sogar am meisten Sinn denn dann muss man sich über 64 Byte Themen keine Sorgen machen.

Das Phänomen heißt Cache Line Sharing Conflict/Hazard/Invalidation oder so. Einfach mal etwas einlesen in die Funktionsweise von Caches.

Falls du dir Sorgen um das False Sharing machst, könntest du ein Hilfsstruct erstellen welches ein Vielfaches von 64 Byte groß ist. zB

Geht auch einfacher:

striker159 schrieb:

Code:

struct alignas(64) Helper{
    std::vector<int> data;
};

Zum Vergrößern anklicken....

Aber solange kein Thread schreibt, gibt es auch kein False Sharing, denn rein lesend können Daten durchaus auch in mehreren Caches vorliegen.

Gute Tipps danke!, wenn ich es richtig verstanden habe, sollte die manuelle Speicherausrichtung auch nichts verschlechtern ausser das eben das Struct ein wenig größer ist. Dachte kurz erst das führt zu sowas wie pragma pack (exaktes fitting mit Performanceverlust) aber die Annahme ist wohl falsch denn die Positionierung der Variablen im Struct finden trotz der 64 nur dort statt wo ein Vielfaches der eigenen Variablengröße ist. Insofern sollte es wahrscheinlich kein Einfluss auf die Performance haben... (die 2er, 4er und 8er Sprünge bleiben, je nach Variablen im Struct)


Wenn jetzt jeder Eintrag im Vector StructVector die Daten für jeweils einen Thread bereithalten soll und das 64er Struct dafür sorgt, dass von unterschiedlichen Threads nichts in die gleiche Cacheline gelegt wird, welche Elemente werden dann genau in welchen Cache gelegt?
Denn der Vector stellt ja nur die Zieladresse der Struktur dar und die Struktur ist nur der Container für die eigentlichen Daten (dem inneren Vector). Werden die Hüllen also hier äusserer Vector und Struct überhaupt in den Cache gelegt? oder wie funktioniert das bei solchen komplexeren Datenstrukturen, wer kommt überhaupt in den Cache?

Die gesamte Cache-Diskussion macht echt überhaupt garkeinen Sinn an dieser Stelle.. soweit bist du lange nicht.
Versuch erstmal zu verstehen oder wenigstens überhaupt als Frage für hier zu formulieren, ob du den Container locken musst oder nicht. Das ist bis jetzt immer noch nicht eindeutig und 1000x wichtiger.
Auch steht durch deine unterschiedlichen Formulierungen/Antworten bisher immer noch nicht fest, ob die Container oder die darin enthaltenen Daten nun von den Threads verändert werden oder eben nicht.

Dieser Beitrag ist wieder typisch für dieses Programmier-Forum. 99% aller Beiträge gehen komplett am Thema vorbei und es werden Probleme diskutiert/gelöst von denen noch nichtmal klar ist ob sie überhaupt existieren

kuddlmuddl schrieb:

Die gesamte Cache-Diskussion macht echt überhaupt garkeinen Sinn an dieser Stelle.. soweit bist du lange nicht.

Zum Vergrößern anklicken....

Doch macht Sinn, die Beträge haben bisher sehr geholfen Hancock hat auf ein Phänomen hingewiesen, dass ich beim Threading bisher nicht beachtet hatte. Mutexe, locks, atomics ist ja alles bekannt. Das Spannende ist doch, dass man beim False Sharing aufgrund der Cachelines auch ohne Syncronisierungsbedarf sich trotzdem ein Threadingproblem einfangen kann.

kuddlmuddl schrieb:

Versuch erstmal zu verstehen oder wenigstens überhaupt als Frage für hier zu formulieren, ob du den Container locken musst oder nicht. Das ist bis jetzt immer noch nicht eindeutig und 1000x wichtiger.
Auch steht durch deine unterschiedlichen Formulierungen/Antworten bisher immer noch nicht fest, ob die Container oder die darin enthaltenen Daten nun von den Threads verändert werden oder eben nicht.

Zum Vergrößern anklicken....

Das steht alles im ersten Beitrag

T_55 schrieb:

Jedem Thread gehört also ein Vectoreintrag in dem wiederum die eigentlichen Daten im inneren Vector sind.
Die äusseren Vectoren werden fix erzeugt bevor die Threads gestartet werden.
Jeder Thread greift nur auf seine eigenen Daten zu.

Die Daten im inneren Vector werden wie geschildert ausschließlich vom jeweiligen Thread benutzt, ...

Zum Vergrößern anklicken....

Daher keine Syncronisierung notwendig. Und GUI würde erst nach der Thread-Arbeit lesen.

Inzwischen hab ich auch rausgefunden, dass natürlich alles mögliche im Cache landen kann daher hat sich die vorige Frage auch geklärt.
Durch die Eigenschaft der Cache-Kohärenz muss man eben aufpassen das es keine konkurrierenden Zugriffen auf die gleiche
cache line gibt was sich durch das Alignment lösen lässt.

Das Einzige was ich noch überlege ist ob in meinem Fall der äussere Vector überhaupt auf L1 oder L2 landen würde oder höchstens nur auf L3 bleibt. Bei L1/L2 müsste er für jeden Core zur Verfügung stehen also mehrfach und gleichzeitig. Denn die Cores haben eigene L1/L2 und die Daten befinden sich eh in den inneren Vectoren die cachefreundlich kompakt in Zeilen (nicht in Spalten) liegen. Oder die Cores interessieren sich dann gar nicht mehr für den äusseren Vector und haben nur die Zeiger auf die zu behandelnden Inneren Daten im L1/L2. Kann man wahrscheinlich dann einfach der CPU alles überlassen, aber die Sache mit der Cacheline ist schon wichtig zu beachten

Das mit den Cachelines ist unter x86/x64 tatsächlich nur für die Performance relevant (unter ARM sieht's anders aus). Zuerst mal sollte dein Code korrekt sein (daher mutex/...). Wenn der Algorithmus dann zu langsam ist, dann können wir mal richtig über solche Mikrooptimierungen reden.

Sorry, es sollte nicht so unfreundlich klingen.

Ich hatte deinen ersten Beitrag sehr genau und gründlich gelesen, wie du ja an meiner frühen Antwort auch gesehen hast, nur widersprichst du ihm mehrfach.
zB in #5 "Eine Methode glaube ich dürfte dann auch kein Problem darstellen solang auf unterschiedlichen Daten das read/write stattfindet."
Also doch write?
Und in #8 "Wenn allerdings die Datenstruktur lokal (wegen der 64 Byte Problematik) mehr Vorteile und Performance bietet und man doch mal von aussen (zB GUI) Daten will"
Also lesen gleichzeitig doch auch andere Threads und die Daten sind nicht Thread-exklusiv? Das beantwortest du ja dann in #14, dass die GUI nur hinterher liest aber der Beitrag war gestern noch nicht da.

Auch andere Antworten hier passen nich zu deinem ersten Beitrag und du hast es nie korrigiert, daher meine Vermutung, dass hier noch vieles unklar ist.
zB in #4 mit dem überflüssigem "atomar"

Da (wie Hanckock ja gerade sagt) das Caching nur ein Performance-Ding ist macht es wenig Sinn darüber zu reden anstatt mit nem profiler zu messen oder Cachegrind einzusetzen. Jetzt irgendwo sinnlos Datenmüll einzufügen, weil man denkt damit irgendwelche Cache-Nutzung zu verbessern ist im bestenfall nur Premature optimization und wahrscheinlich eher die Ursache von schwer zu findenen Bugs. Ich sehe ständig, dass Entwickler mit sowas anfangen weil sie denken sie wüssten was der Compiler oder die CPU macht und es ist eigtl. immer Unsinn die Zeit zu investieren und sehr oft die Ursache von vermurksten Projekten

Dein eingefügter Datenmüll verringert automatisch die Effizienz von jedem Cachelevel (=mehr Cachemisses), weil dort ja dann auch der Müll mit reinpassen muss. Geh mal davon aus, dass Compiler daraufhin geschrieben sind aus 'normalem' bzw. sauberem Code das beste zu machen und das CPUs darauf hin entwickelt wurden für normale software möglichst gut zu funktionieren. Da jetzt ungemessen einfach sowas zu machen ist wirklich Unsinn - auch wenn es natürlich was bringen kann.

Genau wie Hancock sagt: Mach nicht einfach irgendwas mit Threads weil du denkst dadurch schneller zu werden. Multithreading zur Performance-Steigerung auf einem einzigen PC ist selten der Weg mit nem vernünftigen Verhältnis aus Arbeitszeit zu Laufzeitgewinn. Außerdem muss immer der erste Schritt sein: Messen wo und was überhaupt das Bottleneck ist und nur evtl. dann der zweite: Automatisierte Tests programmieren, welche sicherstellen, dass vor und nach der Optimierung (zB deine Umstellung auf mehrere Threads, aber evtl auch beheben des eigentlichen Bottlenecks oder ändern der Algorithmen-Logik) die Rechenergebnisse noch stimmen. Irgendwas machen ist dann immer erst der dritte Schritt.

False Sharing ist keineswegs eine Optimierung!
Dies kann in bestimmten kombinationen (Zwei Threads teilen sich eine Cacheline, was z.b. by Hyperthreading der Fall ist) zu falschen Ergebnissen führen: https://www.youtube.com/watch?v=WDIkqP4JbkE (ab Minute ~30).

Optimierte Datenstrukturen arbeiten immer mit manuellem Padding, um False Sharing von vorne rein zu vermeiden:
http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue

Übrigens, 1024cores.net ist ne feine Seite um Kernkonzepte von Multithreading zu lernen - kann ich jeden nur empfehlen.

(Zwei Threads teilen sich eine Cacheline, was z.b. by Hyperthreading der Fall ist) zu falschen Ergebnissen führen: ​

Zum Vergrößern anklicken....

​Hat er nicht gemeint, dass falsche Ergebnisse (solange man nicht auf die selben(!) Daten zugreift) nicht passieren können, wenn unterschiedliche Core auf die selbe Cacheline zugreifen? Insbesondere, bei Hyperthreading nicht, da die Threads dort auf den selben Core laufen?

x86 garantiert für MOV (Standard Schreib/Lesebefehl) Aquire/Release Semantik, was vollkommen ausreichend ist. Das gilt nicht für (fast alle) andere Architekturen.

​Optimierte Algorithmen haben einen/mehrere Test-Case(s), auf die optimiert wird. Alles andere ist nicht-wartbares Voodoo.