Lesen/Schreiben von Speicher Multithreaded

It0101

@Tyrdal sagte in Lesen/Schreiben von Speicher Multithreaded:

@It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

@manni66 sagte in Lesen/Schreiben von Speicher Multithreaded:

@It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

daher ist mir die Performance wichtig

Und Spinlocks sind da besser als Mutexes?

Letztendlich wird auch beim Mutex oder bei einer CritSect gewartet. Mag sein, dass das dort effizienter geschieht. Keine Ahnung.

Ja klar geht das da effizienter. Deswegen direkt zu Anfang meine Frage. Ein Spinlock ist ja quasi die Nutzung der CPU als Heizung, ein wartender Mutex jedoch gibt die Kontrolle an den OS-Scheduler zurück, verbraucht während der Wartezeit also keine CPU Leistung.

Naja letztendlich muss man wissen, was das Ziel ist. Das Mutex braucht deutlich länger, um die Kontrolle zurückzubekommen als z.b. ein Atomic mit Spinlock. Dafür bezahlt man mit CPU-Usage.

Ich werde ohnehin verschiedene Varianten testen, auch mit Mutex und dann mal ein paar Messwerte aufnehmen. Da für mich aber die Zugriffszeiten im Vordergrund stehen ist mir eben an der Lock-Free-Variante mit atomics gelegen. Herausforderungen braucht der Mensch

Das gute am Mutex ist: Wenn es keine Kollision gibt, kann man den Zeitaufwand für Lock und Unlock mit 0 annehmen.

hustbaer

@It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

@hustbaer sagte in Lesen/Schreiben von Speicher Multithreaded:

Der Trick ist ein einziges Atomic zu verwenden indem man ein Bit für "gibt es einen Writer" und die restlichen Bits für den Leser-Zähler verwendet.

Klingt eigentlich gut, nur es bleibt halt immer das Problem, dass man Abprüfen bis gewünschtem Zustand und Setzen des neuen Zustands ( Z.b. Lese-Zähler erhöht um 1 ) in einem Rutsch erledigen muss, ohne dass ein anderer Thread die Möglichkeit hat zwischen die Lese und die Schreib-Instruktion zu kommen.

Allergrundlegendste Grundoperation bei Atomics: Compare-And-Swap.

hustbaer

@It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

Das gute am Mutex ist: Wenn es keine Kollision gibt, kann man den Zeitaufwand für Lock und Unlock mit 0 annehmen.

Du kannst annehmen was du willst, bloss stimmen tut es deswegen nicht. Gerade wenn es keine Kollisionen gibt sind Spin-Locks ideal. Wobei ideal != "0 Kosten". Und der Unterschied zu einer guten Mutex Implementierung ist nicht gross.

hustbaer

@It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

Hier hat scheinbar jemand Performance-Tests mit verschiedenen Lock-Varianten gemacht:
https://stackoverflow.com/questions/13206414/why-slim-reader-writer-exclusive-lock-outperformance-the-shared-one

Das Mutex kommt dabei gar nicht gut weg. Allerdings sind die Umstände des Tests nicht bekannt.

Das was dort "mutex" genannt wird ist wohl ein Windows Mutex: https://docs.microsoft.com/en-us/windows/win32/api/synchapi/nf-synchapi-createmutexw
Hat mit std::mutex nixe zu tun. Wo findet ihr Kids bloss immer diese total sinnfreien Vergleiche?

It0101

@hustbaer das Internet bietet halt auch viel Schund an. Deswegen schrieb ich ja auch, dass man die Hintergründe der PerformanceMessung nicht kennt, geschweige denn den Quellcode.

Das hier ist wohl vermutlich eine Implementation von dem Lock-Free-Ding, was du erwähnt hast, mit einem INT welches ein WriteAccess-Bit enthält.
https://yizhang82.dev/lock-free-rw-lock

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();
    }
}