C/C++ Forum :: Muss der Vektor in diesem Fall durch ein Mutex geschützt werden?

curry-king Mitglied 12:04:41 02.02.2012 Titel:

Hallo zusammen,

Gegeben ist ein globaler vector<>. Mehrere Threads greifen auf unterschiedliche Indizes dieses vector<>s "gleichzeitig" schreibend zu. Wenn garantiert ist, dass das pro Thread auf unterschiedliche Indizes passiert - müssen dann die Zugriffe durch ein Mutex geschützt werden?

Danke :-)

knivil Mitglied 12:07:02 02.02.2012 Titel:

Muss ein blankes C-Array geschuetzt werden, wenn nur ueber unterschiedliche Indizes auf die Objekte zugegriffen wird?

Btw. Selber denken, Glueck verschenken.

curry-king Mitglied 12:11:12 02.02.2012 Titel:

Na eigentlich nicht, da nie zwei threads eine Schreiboperation auf die gleiche Speicherstelle gleichzeitig durchführen. Aber vielleicht gibt es ja höhere Mechanismen (Speicherverwaltung...), die dem widersprechen !?

Edit: Oder gibt es die nicht ?

DrakoXP Mitglied 12:27:02 02.02.2012 Titel:

Wenn kein Thread auf die Idee kommt, dem Vector ein neues Element hinzuzufügen,
was eine Reallokation zur Folge haben kann, dann eigentlich nicht.
Intern verhält sich der Vektor wie ein Array und ein Array ist im Grunde nichts anderes als eine Reihe von unabhängigen Objekten, die eben hintereinander im Speicher liegen. Wenn immer nur ein Thread auf eines dieser Objekte zugreift, passiert da gar nichts.

krümelkacker Mitglied 12:27:21 02.02.2012 Titel:

Zitat:

Wenn [...] müssen dann die Zugriffe durch ein Mutex geschützt werden?

Ich hoffe nicht. Denn dann hätte ich auf der Arbeit Mist gebaut. ;-)

curry-king Mitglied 12:32:20 02.02.2012 Titel:

Dann hab ich wohl auch Glück gehabt :o)

hustbaer Mitglied 12:45:55 02.02.2012 Titel:

Man könnte auch einen Zeiger auf das erste Element irgendwo ablegen, und die Elemente dann über diesen ansprechen.
Damit ist vector<> aus dem Spiel - die einzige Anforderung ist dann dass nicht zwei Elemente von unterschiedlichen Threads verwendet werden, und dass keiner eine Reallocation vom vector<> auslöst.

Ansonsten müsste man mal sehen wie der non-const operator [] definiert ist. Wenn der als Leseoperation definiert ist, dann müsste der Standard auch mit direktem Zugriff garantieren dass es funktioniert.

Q Mitglied 13:01:39 02.02.2012 Titel:

Also bei Java ist es zumindest so, dass wenn mindestens 1 thread auf etwas schreibt und es zusätzlich noch andere leser gibt, synchronisiert werden muss (volatile oder lock).

Ich weiß nicht genau, ob das bei c++ auch so ist.

Der Grund ist wohl, dass es beim schreiben sein kann, dass erstmal nur in den cache geschrieben wird oder vielleicht auch erstmal nur in ein register und das geschriebene deswegen für andere unter umständen noch nicht sichtbar ist.

Korrigiert mich bitte, falls das falsch ist. Aber bei "Java Concurrency in Practie" wurde das so gelehrt, wenn ich das nicht ganz falsch verstanden habe.
Und dieses Problem sollte ja eigentlich Sprachunabhängig vorhanden sein.

SeppJ Moderator 13:13:08 02.02.2012 Titel:

Q schrieb:

Also bei Java ist es zumindest so, dass wenn mindestens 1 thread auf etwas schreibt und es zusätzlich noch andere leser gibt, synchronisiert werden muss (volatile oder lock).

Ich weiß nicht genau, ob das bei c++ auch so ist.

Das ist richtig, aber hier nicht gefragt.

Unregistrierter

krümelkacker schrieb:

Zitat:

Wenn [...] müssen dann die Zugriffe durch ein Mutex geschützt werden?

Ich hoffe nicht. Denn dann hätte ich auf der Arbeit Mist gebaut. ;-)

Dann hast du Mist gebaut. Da je nach Prozessor möglicherweise mehr Bits geschrieben werden, als du eigentlich verändert hast (z.B. änderst du ein Bool, der Prozessor schreibt aber 64 Bit), können benachbarte Werte überschrieben werden. Das hängt vermutlich auch vom Compiler ab, da C++ ja erst im neusten Standard Threads kennt.
Herb Sutter hatte das mal in einem seiner Thread Artikel für Dr. Dobb's beschrieben (leider kann ich spontan keinen Link liefern). In "Programming with POSIX Threads" von Butenhof werden die Probleme ebenfalls erläutert.

krümelkacker Mitglied 13:47:24 02.02.2012 Titel:

manni66, das, was Du meinst, nennt sich "false sharing". Da geht es im Wesentlichen um ein ungeschicktes Speicherlayout und/oder einer ungeschickten Arbeitsaufteilung, die sich Cache-bedingt typischerweise negativ in der Ausführungsgeschwindigkeit auswirkt. Bis auf Unterschiede in der Ausführungsgeschwindigkeit ist der Cache aber transparent und es macht für die Korrektheit keinen Unterschied, wie groß eine Cache-Line ist. Die Geschwindigkeitseinbußen kommen gerade daher, dass die Caches sich wegen false sharing aufwendig synchronisieren müssen (per Cache-Kohärenz-Protokoll). Das wär ja sonst ein ziemlich blödes Speichermodell. Ich bin mir ziemlich sicher, dass im C++2011 Speichermodell der gleichzeitige Zugriff auf benachbarte Bytes (also thread 1 -> byte 1, thread 2 -> byte 2) kein Datenrennen darstellt.

Da ich in meinem Fall jedem Thread einen kontinuierlichen Bereich des Vektors zuordne, kann es höchstens an den Intervallgrenzen zu false sharing kommen. Und selbst da ist es unwahrscheinlich, weil jeder Thread linear forwärts durch sein eigenes Intervall des Vektors läuft.

Ich bin jetzt kein multi-CPU-/Cache-Profi, der auf unterster Ebene weiß, was genau passiert. Das muss man aber auch nicht sein, um korrekt programmieren zu können. Da reichen Speichermodelle. Die Caches sich im Fall von false sharing unterhalten, ist mir echt egal.

hustbaer Mitglied 17:00:24 02.02.2012 Titel:

@krümelkacker:
"False sharing" nennt man das wenn es die Performance drückt, aber alles korrekt funktioniert.
Wenn es zu unerwünschtem/unerwartetem Verhalten führt, dann nennt man es Scheissendreck. (Ne, sorry, keine Ahnung wie man dann sagt

)

krümelkacker Mitglied 17:06:05 02.02.2012 Titel:

Herb Sutter redet ganz gerne von "false sharing" in diesem Kontext. Ich denke, das ist es, was manni66 im Gedächtnis hatte.

Unregistrierter

krümelkacker schrieb:

Herb Sutter redet ganz gerne von "false sharing" in diesem Kontext. Ich denke, das ist es, was manni66 im Gedächtnis hatte.

Nein

krümelkacker Mitglied 17:40:24 02.02.2012 Titel:

Sorry, es sieht für mich immer noch so aus, als ob Du das mit dem Chache falsch verstanden hast. Da hat das "Nein" nichts dran geändert, fürchte ich.

Unregistrierter

krümelkacker schrieb:

Sorry, es sieht für mich immer noch so aus, als ob Du das mit dem Chache falsch verstanden hast. Da hat das "Nein" nichts dran geändert, fürchte ich.

Naja, mindestens einer von uns liegt falsch

hustbaer Mitglied 21:04:02 02.02.2012 Titel:

BTW: Das Speichermodell von C++0x erlaubt diesbezüglich soweit ich weiss kein unerwartetes Verhalten.

Unregistrierter

hustbaer schrieb:

BTW: Das Speichermodell von C++0x erlaubt diesbezüglich soweit ich weiss kein unerwartetes Verhalten.

IMHO muss man dann aber std::atomic<> (oder so ähnlich) verwenden. Ob man dann bei einem Array aber die Elemente auch als atomic definieren muss?

Shade Of Mine Moderator 22:20:53 02.02.2012 Titel:

manni66 schrieb:

hustbaer schrieb:

BTW: Das Speichermodell von C++0x erlaubt diesbezüglich soweit ich weiss kein unerwartetes Verhalten.

IMHO muss man dann aber std::atomic<> (oder so ähnlich) verwenden. Ob man dann bei einem Array aber die Elemente auch als atomic definieren muss?

Nein.
Lass es sein, bitte, und hoer auf krümelkacker.

atomic ist wieder was ganz anderes.

camper Mitglied 23:33:23 02.02.2012 Titel:

1.7/3

Unregistrierter

vector<bool> kann zu Data Races führen, aber der ist bekanntlich ein Sonderfall.

Zitat:

23.2.2 Container data races
...
2 Notwithstanding (17.6.5.9), implementations are required to avoid data races when the contents of the contained
object in different elements in the same sequence, excepting vector<bool>, are modified concurrently.

3 [ Note: For a vector<int> x with a size greater than one, x[1] = 5 and *x.begin() = 10 can be executed
concurrently without a data race, but x[0] = 5 and *x.begin() = 10 executed concurrently may result in
a data race. As an exception to the general rule, for a vector<bool> y, y[0] = true may race with y[1]= true. —end note ]