Lesen/Schreiben von Speicher Multithreaded

It0101

@hustbaer sagte in Lesen/Schreiben von Speicher Multithreaded:

Wo findet ihr Kids bloss immer diese total sinnfreien Vergleiche?

Ihr Kids? Ich bin fast vierzig

It0101

Ich werde jetzt mal verschiedene Variaten implementieren und dann mal 10 Schreib-Threads und 100 Lese-Threads losschicken und die Laufzeit messen. Mal gucken was rauskommt.

It0101

So ich habe mal eine Messung durchgeführt:

Variante 1: Mutex welches sich Leser und Schreiber teilen, d.h. insgesamt hat immer nur einer Zugriff.
Variante 2: LockFree, diese Implementation hier: https://yizhang82.dev/lock-free-rw-lock

Szenario:

1 Schreiber
Variable Anzahl an lesenden Threads ( R=1 -> 64 )
5 Mio Zugriffe pro Thread ( jeweils mit lock/unlock), der langsamste Thread bestimmt den Messwert
Compiler gcc 9.2, getestet auf Centos6 als VM (!!!)

R Mutex LockFree
1 422 896
2 625 993
4 971 2204
8 1901 4019
16 3743 7476
32 7256 14755
64 14255 30840
(Messwerte in millisekunden)
Fazit für mich: Überraschenderweise performt das std::mutex deutlich besser als die LockFree-Variante mit SpinLock...

Tyrdal

Es gibt auch Mutexe für deine obigen Anforderungen. Also mehrere Leser aber nur ein Schreiber.

Ansonsten wundert mich das Ergebnis nicht.Mutexe wachen auf wenn sie drann sind. Spinlocks spinnen halt vor sich hin und können damit den Thread der den Lock( halt deinen LockFreeLock ) hat von der Ausführung abhalten.

Wenn LockFree automatisch besser wäre würden es alle nur noch so machen.

Ach ja, die Implementierung aus deinem Link kann übrigens die Schreiber verhungern lassen.

It0101

Ich bin noch nicht ganz glücklich, weil die Messung ja auf einer VM stattfand. Ich habe leider kein physisches System gefunden, welches ich mal so richtig unter Dampf setzen konnte, weil bei uns der Trend zur Virtualisierung geht...

Ich denke aber dass die Unterschied zwischen physisch und VM dann am Ende vermutlich keinen extremen Unterschied mehr machen werden.

@Tyrdal sagte in Lesen/Schreiben von Speicher Multithreaded:

Ach ja, die Implementierung aus deinem Link kann übrigens die Schreiber verhungern lassen.

Ja das kann passieren. Durch diesen Read-Counter ist das im Grund schwer zu vermeiden, es sie denn man priorisiert die Schreiber, über eine zusätzliche geschützte Variable, aber ich befürchte dass das am Ende noch mehr an Performance kostet.

Ich werde mal noch schauen, welche Variante wieviele Kollisionen hat.

hustbaer

@It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

https://yizhang82.dev/lock-free-rw-lock

Achherrjeh ja den Artikel hab ich auch gesehen. Das ist schon so ne typische Facepalm Sache, nen. Ich meine, alleine schon der Titel. "a lock-free reader/writer lock" - soll das Satire sein?

@Tyrdal
Dass der "reader writer spin-lock" langsamer ist liegt nicht daran dass er spinnt. In einem Test mit nur einem Thread spinnt er ja nie.

Ich vermute mal der Unterschied kommt daher, dass ne normale Mutex mit einem CAS zum Locken und einem normalen store-release (was viel billiger ist) zum Unlocken auskommt.

Wohingegen so ein Reader-Writer Lock maximal den "write unlock" mit store-release machen kann. Alle anderen Operationen inklusive "read unlock" benötigen CAS. Und in dem Beispiel ist sowieso alles über CAS gemacht.
(Nochdazu CAS-seq_cst. Was mit x86 jetzt keinen Unterschied macht, aber mit anderen Architekturen durchaus.)

hustbaer

@It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

Durch diesen Read-Counter ist das im Grund schwer zu vermeiden, es sie denn man priorisiert die Schreiber, über eine zusätzliche geschützte Variable, aber ich befürchte dass das am Ende noch mehr an Performance kostet.

Nein. Das geht sehr einfach mit nur einer Variable und auch ohne weitere Performanceeinbussen.

Und zwar so: Der Writer setzt sein Writer-Bit sobald das Writer-Bit 0 ist. Unabhängig davon ob es noch Reader gibt. Und dann wartet er mit gesetztem Writer-Bit einfach so lange bis es keine Reader mehr gibt. Und dann hat er den Write-Lock.

Und der Reader inkrementiert den Reader-Count bloss dann, wenn das Writer-Bit nicht gesetzt ist.
Und schon ist Bob dein Onkel.

Tyrdal

@hustbaer sagte in Lesen/Schreiben von Speicher Multithreaded:

@Tyrdal
Dass der "reader writer spin-lock" langsamer ist liegt nicht daran dass er spinnt. In einem Test mit nur einem Thread spinnt er ja nie.

Stimmt, aber bein nur einem Thread braucht man auch keinen LockFreeLock

hustbaer

@Tyrdal sagte in Lesen/Schreiben von Speicher Multithreaded:

@hustbaer sagte in Lesen/Schreiben von Speicher Multithreaded:

@Tyrdal
Dass der "reader writer spin-lock" langsamer ist liegt nicht daran dass er spinnt. In einem Test mit nur einem Thread spinnt er ja nie.

Stimmt, aber bein nur einem Thread braucht man auch keinen LockFreeLock

Hä? Bei nur einem Thread braucht man gar keine Locks. Aber darum geht's ja nicht. @It0101 hat Zahlen mit unterschiedlicher Thread-Anzahl gepostet, darunte rauch eine Zeile mit Thread-Count=1. Und auch da war der RW-SpinLock langsamer. Bloss da spinnt er nicht. D.h. es kann nicht am spinnen liegen. Klar jetzt?

Tyrdal

@hustbaer War mir schon vorher klar. Du hast meinen Joke nicht verstanden, aber egal.

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