Lesen/Schreiben von Speicher Multithreaded

Tyrdal

@It0101 Ist nicht ungewöhlich. Wenn ein spinnender SchreibThread weggescheduled wird, spinnen alle anderen ja ihre komplette Zeitscheiben lang bis der lockende Thread endlich mal dran kommt zum relasen. Das vermindert das yield natürlich.

BTW, das Ganze hier ist natürlich nicht lock free sondern einfach ... naja doch ein lock eben.

hustbaer

@Tyrdal sagte in Lesen/Schreiben von Speicher Multithreaded:

@It0101 Ist nicht ungewöhlich. Wenn ein spinnender SchreibThread weggescheduled wird, spinnen alle anderen ja ihre komplette Zeitscheiben lang bis der lockende Thread endlich mal dran kommt zum relasen. Das vermindert das yield natürlich.

Das ist kein Problem wenn man genug Cores hat. Also wenn du auf nem 4-Core HyperThreading System mit z.B. 3 Threads testest wirst du davon nix merken.

Wovon du schon was merkst ist das Cache-Line Ping-Pong.

Tyrdal

@hustbaer sagte in Lesen/Schreiben von Speicher Multithreaded:

Das ist kein Problem wenn man genug Cores hat. Also wenn du auf nem 4-Core HyperThreading System mit z.B. 3 Threads testest wirst du davon nix merken.

Und wenn nicht, dann doch. Es kommen ja immerhin auch noch alle anderen Prozesse im Rechner dazu. Ist halt ein potentielles Problem.

hustbaer

@Tyrdal
Ich meine nicht es kann kein Problem sein. Ich meine es ist keine Erklärung dafür dass man in einer Messung ein Problem sehen würde.
Glaub mir, ich hab mich ausreichend mit dem Thema beschäftigt und genug solchen Code geschrieben, gebenchmarkt und optimiert. Das Phänomen das hier reinhaut ist der Kampf um die Cache-Line in der die Lock-Variable liegt.

Kann man z.B. schön sehen wenn man statt eines yield(); ein for (size_t i = 0; i < 100; i++) _mm_pause(); verwendet. Was Scheduling angeht bringt dir das nix. Wenn es also daran läge dürfte das nicht helfen. Hilft aber.

It0101

Habe jetzt nochmal das CPU-Verhalten beider Variante untersucht:

Centos7 (VM) 4 Prozessoren
CPU-Angaben unter Linux von "top" ( ich weiß, nicht erste Wahl )
10 Mio Zugriffe, 1 Schreiber, 64 Leser

LockFree 25,6 Sekunden, 370% CPU ( von 400% )
Mutex 43,4 Sekunden, 350% CPU ( von 400% ).

Macht effektiv: 5% mehr CPU-Usage bei LockFree, 40% weniger Laufzeit

Finnegan

@It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

LockFree 25,6 Sekunden, 370% CPU ( von 400% )

Nochmal am Rande: Wenn der Schreiber angehalten wird, während er das Lock hält, dann geht gar nix mehr. Daher ist das nicht "Lock-Free". Das ist eher Userspace-Spinlock vs. Standard-Mutex.

Lock-Free könnte man es vielleicht hinbekommen, wenn der Schreiber z.B. zunächst nur in seine eigene, thread-lokale, unsynchronisierte Kopie schreibt (zum Kopieren muss er ja nur Lesen) und das geteilte synchronisierte Objekt dann mit dieser z.B. in einem atomaren Pointer-Swap austauscht. Dann könnte man jeden beliebigen Thread pausieren und dennoch würden alle anderen weiterarbeiten können. Das sollte dann wirklich "Lock-Free" sein (korrigiert mich, wenn ich da nen Denkfehler drin habe).

It0101

@Finnegan
Es ist nicht lockfree, das ist klar. Ich verwende den Namen einfach nur weiter, damit ich meine Klassen nicht ständig umbenennen muss

Zur Richtigstellung für zukünftige Lesende: Das Konzept ist nicht Lockfree, es ist nur eine andere Herangehensweise als Mutex.

hustbaer

@Finnegan Ich glaube der Autor des verlinkten Artikels der die Formulierung "lock free reader-writer lock" verwendet hat meint damit dass die Implementierung des "reader-writer lock" selbst keinen klassischen "lock" verwendet. Also im Gegensatz zu z.B. "reader-writer lock" Implementierungen die sich einer Mutex + Condition-Variable bedienen.

Und natürlich hat so eine "lock free" Variante Vorteile gegenüber Mutex + Condition-Variable, weil sie weniger Nukularoperationen benötigt und daher vor allem im "non contended" Fall deutlich schneller ist.

Aber der Begriff "lock free" im Zusammenhang mit nem Lock ist natürlich komisch, das ist klar
(Und IMO nicht nur komisch sondern Quatsch -- auch wenn ich meine zu verstehen wie es gemeint war.)

Finnegan

@hustbaer sagte in Lesen/Schreiben von Speicher Multithreaded:

@Finnegan Ich glaube der Autor des verlinkten Artikels der die Formulierung "lock free reader-writer lock" verwendet hat meint damit dass die Implementierung des "reader-writer lock" selbst keinen klassischen "lock" verwendet. Also im Gegensatz zu z.B. "reader-writer lock" Implementierungen die sich einer Mutex + Condition-Variable bedienen.

Und natürlich hat so eine "lock free" Variante Vorteile gegenüber Mutex + Condition-Variable, weil sie weniger Nukularoperationen benötigt und daher vor allem im "non contended" Fall deutlich schneller ist.

Ich habe mich noch nicht viel mit den Innereien eines Mutex beschäftigt, aber ist es nicht so, dass die guten Implementierungen sogar erstmal sehr ähnlich arbeiten, wie hier vorgeschlagen? Ich meine gelesen zu haben, dass manche Mutex-Implementierungen erstmal mit ein paar Atomics auf Contention testen und einige sogar eine kurze Zeit spinnen, bevor dann das OS für einen vollwertigen Mutex involviert wird. Das sollte doch eigentlich gerade im Non-Contended-Fall genau so effizient sein (?).

Aber der Begriff "lock free" im Zusammenhang mit nem Lock ist natürlich komisch, das ist klar
(Und IMO nicht nur komisch sondern Quatsch -- auch wenn ich meine zu verstehen wie es gemeint war.)

Nun, "Lock" und "Lock-Free" schliessen sich nicht unbedingt aus, da sich letzteres durch das Verhalten des Algorithmus definiert und ersteres ein konkretes Objekt bescheibt. So könnte ich - wenn ich das richtig verstanden habe - durchaus einen "Lock-Free"-Algorithmus mit einem Standard-Mutex bauen, solange sich die Threads nicht gegenseitig blockieren können. Der Algorithmus könnte z.B. ein try_lock auf eine synchroisierte Ressource machen und wenn das fehlschlägt eben nicht blockieren, sondern einfach auf einer anderen freien Ressource weiterarbeiten.

Ich glaube "Lock-free" bedeutet hier eher "blockadefrei" und nicht "ohne Lock-Objekt".

hustbaer

@Finnegan
Ich glaube du hast mich falsch verstanden
Davon abgesehen hast du mit vielem was du schreibst Recht.

ist es nicht so, dass die guten Implementierungen sogar erstmal sehr ähnlich arbeiten, wie hier vorgeschlagen?

Ja. Eine gute Mutex Implementierung die auf Speed optimiert ist (im Gegensatz z.B. zu einer auf FIFO/Fairness optimierten) tut genau gleich wie nen Spin-Lock -- bis zu dem Zeitpunkt wo sie länger spinnen müsste. Das ganze sleep-Gedöns per Event/Condition-Variable/... kommt erst danach.

Das sollte doch eigentlich gerade im Non-Contended-Fall genau so effizient sein (?).

Gleich effizient wie ein Spin-Lock, ja. Aber das meinte ich nicht.

Ich meinte: wenn man keine "Shared Mutex" (=Reader/Writer Lock) hat, sondern nur ne Mutex + Condition-Variable, dann ist die typische Variante eine Shared Mutex daraus zu basteln diese:

void MySharedMuhTex::lock() {
    std::unique_lock<std::mutex> lk(m_mutex);
    m_condvar.wait(lk, [this](){ return !m_writer; });
    m_writer = true;
    m_condvar.wait(lk, [this](){ return m_readers == 0; });
}
...

Das wäre die "nicht lock free" Variante. Und diese ist logischerweise weniger effizient als ne einfache std::mutex, weil ein lock-unlock Zyklus meiner MySharedMuhTex ja mindestens zwei lock-unlock Zyklen der std::mutex benötigt. Und auch weniger effizient als ein mit Nukularen selbstgebastelter "lock free" Reader/Writer Lock