Lesen/Schreiben von Speicher Multithreaded

hustbaer

@Tyrdal sagte in Lesen/Schreiben von Speicher Multithreaded:

Du hast meinen Joke nicht verstanden, aber egal.

Korrekt. Ich hatte nicht verstanden dass du scherztest

Finnegan

@It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

(Messwerte in millisekunden)
Fazit für mich: Überraschenderweise performt das std::mutex deutlich besser als die LockFree-Variante mit SpinLock...

Kann es sein, dass hier eventuell auch noch der Effekt mit reinspielt, der in dem Artikel erwähnt wurde, den @firefly gepostet hat?

Dass ein Thread, der ein solches Lock hält, vom OS-Scheduler auf Eis gelegt wird, weil die Zeitscheibe aufgebraucht ist, kann ja durchaus schonmal vorkommen. Wenn du auch noch in einem engen Loop ausschlieslich den Lock selbst testet, dürfte die Wahrscheinlichkeit dafür sogar relativ hoch sein.

Das würde ich vielleicht mal unter die Lupe nehmen und die Threads mal mitzählen lassen, wie oft sie bei all den Zugriffen keinen Lock bekommen konnten.

Ich habe das schon richtig verstanden, dass ein Lese-Lock ein Schreib-Lock blockiert und umgekehrt, und auch, dass ein vom OS eingefrorener Thread andere blockieren kann? Meines erachtens kann man das in dem Fall nämlich auch nicht "Lock-Free" nennen. Wenn ich mich recht entsinne erfordert das nämlich, dass die anderen Threads weiterarbeiten können, wenn man einen Thread auf Eis legt (auch irgendwo "mittendrin zwischen den Codezeilen").

firefly

Hier noch mehr lesestoff bezüglich der massiven probleme von userspace spinlocks. Besonders mit einem OS welches Multitasking/Multithreading im scheduler untersützt.

Es ist auf Linux bezogen, welches für solche fälle eine kernel API anbietet damit das mit dem locking/unlocking sauber funktioniert auch im zusammenspiel mit dem scheduler.

https://linuxplumbersconf.org/event/4/contributions/286/attachments/225/398/LPC-2019-OptSpin-Locks.pdf

Und hier ein blogpost über einen test wo mutexe schneller sind als userspace spinlocks:

https://matklad.github.io/2020/01/04/mutexes-are-faster-than-spinlocks.html

It0101

Erstmal vielen Dank für eure Hilfe und Diskussionsbereitschaft

Mir ist beim Zählen der Kollisionen der LockFree-Variante noch etwas aufgefallen, was für mich nicht plausibel ist:

Szenario: 1 Schreiber, 2 Leser, 5 Mio Zugriffe pro Thread
RdrLockColl = 13354862
RdrUnLockColl = 0
WrtLockColl = 8474222
WrtUnLockColl = 1723348

Es gibt beim *UnLock" des Schreibers Kollisionen... Theoretisch sollte der Schreiber aber zum Zeitpunkt des "unlock" immer der einzige sein, denn Leser sind ja während des Schreibens nicht zugelassen. Daher verstehe ich die Kollisionen nicht.~~

Edit: Vertauschung bei der Messwertaufnahme... Es gibt keine Kollisionen bei Write-Unlock

It0101

Interesssant:

Ich habe jetzt mal in sämtlichen Spinlocks ein "yield" bei jeder Kollision angebaut und plötzlich wird das Ding schneller.

Windows:

R Mutex LockFree
1 78 95
2 110 153
4 220 299
8 760 855
16 2101 1635
32 4308 3091
64 4317 6208

D.h. die Laufzeiten haben sich deutlich verbessert, sind aber nachwievor nicht besser als die Mutex-Variante.

Centos6 (VM):
R Mutex LockFree
1 80 47
2 110 74
4 181 121
8 375 214
16 698 424
32 1364 816
64 2724 1614

Ist die gleiche Variante schneller als das Mutex... Interessant.

Centos7 (VM)
R Mutex LockFree
1 216 89
2 365 273
4 453 937
8 920 1226
16 1734 2183
32 3395 4196
64 6661 6510

da sind beide ungefähr gleich schnell.

Centos8 (VM)
R Mutex LockFree
1 103 51
2 146 111
4 284 233
8 625 413
16 1218 762
32 2287 1501
64 4542 2856

hier ist dann das "LockFree" ( tyrdal hat natürlich recht, es ist nicht lockfree ) wieder 40% schneller bei 64 Lesern.

Centos7 (VM) anderes System
R Mutex LockFree
1 82 81
2 194 190
4 271 200
8 574 386
16 1135 721
32 2383 1343
64 4251 2808

"lockWrite" sieht dann quasi so aus:


void DataAccessControlLockFree::lockWrite()
{
    while ( 1 )
    {
        uint32_t prevAccessControl = AccessControl;
        if ( prevAccessControl == 0 )
        {
            if ( AccessControl.compare_exchange_weak( prevAccessControl, HAS_WRITER ) )
                return;

        }
        std::this_thread::yield();
    }
}

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