Lesen/Schreiben von Speicher Multithreaded
-
@firefly sagte in Lesen/Schreiben von Speicher Multithreaded:
Dadurch kann man nicht vollständig (Data-)Races verhindern.
Magst du erklären? In dem verlinkten Beitrag ist von Data Races nicht die Rede.
-
Kann gut sein das mit dem Data Races falsch verstanden habe oder miss interpretiert habe.
-
@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.
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-oneDas Mutex kommt dabei gar nicht gut weg. Allerdings sind die Umstände des Tests nicht bekannt.
-
@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.
-
@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.
-
@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.
-
@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.
-
@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.
-
@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-oneDas 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 mitstd::mutex
nixe zu tun. Wo findet ihr Kids bloss immer diese total sinnfreien Vergleiche?
-
@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
-
@hustbaer sagte in Lesen/Schreiben von Speicher Multithreaded:
Wo findet ihr Kids bloss immer diese total sinnfreien Vergleiche?
Ihr Kids? Ich bin fast vierzig
-
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.
-
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-lockSzenario:
- 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...
-
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.
-
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.
-
@It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:
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.)
-
@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.
-
@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
-
@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?
-
@hustbaer War mir schon vorher klar. Du hast meinen Joke nicht verstanden, aber egal.