Geschwindigkeit atomarer Operationen



  • @Flodul sagte in Geschwindigkeit atomarer Operationen:

    Naja ich weiss nicht ob ein Test wo cmpxchg schon 80% Kollisionen hat wirklich Sinn macht.

    Es geht darum zu schauen, wie lange ein Kern eine Cachezeile halten kann ehe ein anderer Thread dazwischenfunkt und die sich klaut.

    Naja so lange bis es passiert. TSX "lockt" die Cache-Line ja nicht irgendwie. Die wird sofort geklaut sobald ein anderer Core committed (oder ohne Transaktion reinschreibt).

    Also ja, klar, wenn du mit genau so einer hohen Kollisionswahrscheinlichkeit rechnest, dann schon. Aber dass TSX dafür nicht geeignet ist, hätte ich dir auch so sagen können 😉

    Hätte ich nicht so per-se gesagt.

    Tjo weil du nicht verstanden hast wie TSX funktioniert 😉

    Und ja, der Sinn ist natürlich dass man kompliziertere Dinge damit macht die man mit Atomics gar nicht oder nur mega umständlich machen könnte. Kombiniert mit einer nicht mega-hohen Kollisionswahrscheinlichkeit macht das dann voll Sinn.

    Naja, wenn man eh keine hohe Kollisions-Wahrscheinlichkeit hat, dann kann man auch bei normalen Mutexen bleiben.

    Nö. Z.B. schonmal weil TSX halt in vielen Fällen schneller ist als normales Mutex Gefummel. Vermutlich oft sogar schneller als Atomics Gefummel.



  • Es geht darum zu schauen, wie lange ein Kern eine Cachezeile halten kann ehe ein anderer Thread dazwischenfunkt und die sich klaut.

    Naja so lange bis es passiert. TSX "lockt" die Cache-Line ja nicht irgendwie. Die wird sofort geklaut sobald ein anderer Core committed (oder ohne Transaktion reinschreibt).

    Ja, aber ansich sind zumindest die LOCK XADD und LOCK CMPXCHG Operationen ansich recht schnell, dass nicht unbedingt gesagt ist, dass in dem Intervall in dem die arbeiten schon die Cachezeile invalidiert ist.

    Also ja, klar, wenn du mit genau so einer hohen Kollisionswahrscheinlichkeit rechnest, dann schon. Aber dass TSX dafür nicht geeignet ist, hätte ich dir auch so sagen können 😉

    Hätte ich nicht so per-se gesagt.

    Tjo weil du nicht verstanden hast wie TSX funktioniert 😉

    Du sicher auch nicht. Bzw. keiner bis auf die Leute bei Intel.

    Naja, wenn man eh keine hohe Kollisions-Wahrscheinlichkeit hat, dann kann man auch bei normalen Mutexen bleiben.

    Nö. Z.B. schonmal weil TSX halt in vielen Fällen schneller ist als normales Mutex Gefummel. Vermutlich oft sogar schneller als Atomics Gefummel.

    TSX macht sicher selten Sinn, das zeigt schon der enorme Overhead beim Tauschen eines size_t durch einen einzelnen Thread ohne Kollision.



  • @Flodul sagte in Geschwindigkeit atomarer Operationen:

    Ja, aber ansich sind zumindest die LOCK XADD und LOCK CMPXCHG Operationen ansich recht schnell, dass nicht unbedingt gesagt ist, dass in dem Intervall in dem die arbeiten schon die Cachezeile invalidiert ist.

    Ich versteh nicht was du meinst. LOCK XADD verhindert einfach dass die Cache-Line invalidiert wird bevor es fertig wird. Andere Cores die die Cache-Line wieder laden wollen werden einfach verzögert bis es fertig ist. Dass das passiert sieht man ja recht schön daran dass die Sache mit jedem beteiligten Core langsamer wird - und zwar massiv.

    Und was LOCK CMPXCHG angeht... was meinst du wo die ganzen "misses" sonst herkommen als davon dass die Cache-Line von einem anderen Core zwischenzeitlich geändert wurde?

    Und denk auch daran dass du in deinem Benchmark die wahren Kosten verschleierst indem du durch die Anzahl der Threads dividierst. D.h. wenn da steht

    xadd-thread:
    threads: 1 cycles: 14.7678 misses-ratio: 0%
    threads: 2 cycles: 15.3087 misses-ratio: 0%
    

    dann heisst das dass es mit zwei Threads doppelt so langsam ist. Ja, du machst die doppelte Anzahl an XADD in der doppelten Zeit. Aber auch mit doppelt so viel Threads. Ein XADD in einem Thread braucht also in der Variante mit zwei Threads bereits 30 Zyklen und nicht 15.

    Davon abgesehen: Natürlich nimmst du XADD wenn du nicht mehr brauchst als XADD. TSX statt XADD zu verwenden wäre ziemlich bekloppt.

    Du sicher auch nicht. Bzw. keiner bis auf die Leute bei Intel.

    Kommt jetzt glaub ich drauf an wie genau man "verstanden haben" auslegt. Weiss ich wie es genau implementiert ist? Nö. Aber in Grundzügen ist mir schon klar was passiert. Im speziellen eben auch dass dabei nie irgendwo irgendwas verzögert wird, sondern alle Cores arbeiten volle Kanne drauf los und der der als erster committed hat dann halt gewonnen. Und alle anderen haben Pech gehabt.

    TSX macht sicher selten Sinn, das zeigt schon der enorme Overhead beim Tauschen eines size_t durch einen einzelnen Thread ohne Kollision.

    Ich glaube das kommt darauf an was man unter "selten" versteht. Wenn du Datenstrukturen hast die sehr häufig und massiv parallel gelesen werden, aber nur selten geschrieben werden, dann wird TSX glaube ich recht oft Sinn machen. Und solche Datenstrukturen sind meiner Erfahrung nach jetzt nicht gerade selten. Bzw. auch Datenstrukturen die zwar vielleicht öfter mal geschrieben werden, aber wo es dennoch relativ selten zu Cache-Line Kollisionen kommt. Beispielsweise passend implementierte Hash-Tables wo ja nicht andauernd



  • Ich versteh nicht was du meinst. LOCK XADD verhindert einfach dass die Cache-Line invalidiert wird bevor es fertig wird.

    Ne, aber es ist recht schnell und der interconnect zwischen den Caches ist recht langsam.

    Andere Cores die die Cache-Line wieder laden wollen werden einfach verzögert bis es fertig ist.

    Ne, eben nicht. Die anderen Kerne kommen an die Cachezeile eher ran und im Extremfall muss der Thread es bei mir bis zu 5,5 mal erneut versuchen, bis das LOCK CMPXCHG erfolgreich vollzogen wird.

    Dass das passiert sieht man ja recht schön daran dass die Sache mit jedem beteiligten Core langsamer wird - und zwar massiv.

    Lass dir mal durch den Kopf gehen, warum es einen gravierenden Unterschied zwischen dem LOCK-XADD- und dem LOCK-CMPXCHG-Thread gibt.

    Und was LOCK CMPXCHG angeht... was meinst du wo die ganzen "misses" sonst herkommen als davon dass die Cache-Line von einem anderen Core zwischenzeitlich geändert wurde?

    Hab ich das jemals bestritten? Zitat?

    Und denk auch daran dass du in deinem Benchmark die wahren Kosten verschleierst indem du durch die Anzahl der Threads dividierst. D.h. wenn da steht
    xadd-thread:
    threads: 1 cycles: 14.7678 misses-ratio: 0%
    threads: 2 cycles: 15.3087 misses-ratio: 0%

    Wieso soll ich da die "wahren Kosten" verschleiern? Das Dividieren durch die Anzahl der Threads ist das einzig richtige.



  • @Flodul sagte in Geschwindigkeit atomarer Operationen:

    Ich versteh nicht was du meinst. LOCK XADD verhindert einfach dass die Cache-Line invalidiert wird bevor es fertig wird.

    Ne, aber es ist recht schnell und der interconnect zwischen den Caches ist recht langsam.

    Andere Cores die die Cache-Line wieder laden wollen werden einfach verzögert bis es fertig ist.

    Ne, eben nicht. Die anderen Kerne kommen an die Cachezeile eher ran und im Extremfall muss der Thread es bei mir bis zu 5,5 mal erneut versuchen, bis das LOCK CMPXCHG erfolgreich vollzogen wird.

    Hm. Also wenn ich im einen Satz von XADD schreibe und im nächsten dann ein rückbezügliches "es" verwende, dann nimmst du an dass ich mich mit "es" auf LOCK CMPXCHG beziehe. Ja, klar, macht voll Sinn. 🤦🏻♂

    Dass das passiert sieht man ja recht schön daran dass die Sache mit jedem beteiligten Core langsamer wird - und zwar massiv.

    Lass dir mal durch den Kopf gehen, warum es einen gravierenden Unterschied zwischen dem LOCK-XADD- und dem LOCK-CMPXCHG-Thread gibt.

    Wieder: Ich beziehe mich hier von XADD und nicht von CMPXCHG. Sinnergreifend Lesen scheint schwer zu sein.

    Wieso soll ich da die "wahren Kosten" verschleiern? Das Dividieren durch die Anzahl der Threads ist das einzig richtige.

    Weil wenn da 2x 15 steht man annimmt dass das XADD/... halt in beiden Fällen 15 Zyklen braucht, was aber nicht stimmt, weil es 1x 15 und 1x 30 braucht. Also ja, klar, das einzig richtige. 🤦🏻♂



  • @Flodul sagte in Geschwindigkeit atomarer Operationen:

    Ein Ansatz könnte z.B. sein, die Cache-Objekte nicht bei jedem Zugriff zu aktualisieren, sondern erst wenn mindestens eine gewisse Zeit seit dem letzten Zugriff verstrichen ist.

    Wie soll das gehen? Wenn eine Notwendigkeit besteht, ein Mutex zu locken und wieder zu entsperren, was minimum zwei atomare Operationen kostet, dann kann ich das nicht verschieben.

    Ein Zugriff auf Cache-Objekt selbst ist nicht dasselbe wie ein Zugriff auf die Cache-Datenstruktur, in welche dieses eingelagert ist. Diese kann und sollte man auch getrennt synchronisieren - schliesslich muss mit einem Zugriff auf ein individuelles Objekt eben nur dieses Objekt synchronisiert werden und nicht gleich alle Objekte an einem einzigen Synchronisationspunkt (ganz vorne in der LRU-Datenstruktur, wo jedes Objekt, auf das zugegriffen wird, gerne sein möchte und es deshalb zu Gerangel kommt).

    Wenn das Objekt z.B. nur gelesen wird, oder man bei Modifikation einen Copy-on-Write-Ansatz wählt, bei dem jeder Thread erstmal nur auf seiner eigenen Kopie des Objekts arbeitet, dann ist für Zugriffe auf die Objekte selbst keine Synchronisation notwendig. Diese benötigt man erst dann, wenn auch auf die Cache-Datenstruktur zugegriffen wird, weil für diese mehrere schreibende und lesende Threads exisitieren können.

    Wenn man nun ein Objekt aus dem Cache holt, dann könnte man z.B. so etwas wie eine Cache-Referenz zurückbekommen:

    struct CacheReference
    {
        const T*       object;
        Timestamp      last_lru_update;
        CacheEntry*    cache_entry;
        ...
    };
    

    Zugriffe auf diese Referenz wie auch auf object müssten nicht synchronisiert werden, da für dasselbe Objekt jeder Thread eine eigene CacheReference bekommt und objekt nur gelesen werden kann.

    Der Cache wird nur dann aktualisiert, wenn ein Thread bei einem nicht-synchronisierten, rein thread-lokalen Zugriff auf object feststellt, dass das letzte Update des LRU-Caches schon eine Weile her ist. Dann passt er den zugrunde liegenden Cache-Eintrag im Cache gemäss LRU-Schema an, indem er ihn in der Cache-Datenstruktur nach vorne schiebt - natürlich synchronisiert. Aktualisiert man so den Cache z.B. im Schnitt nur bei jedem zweiten Zugriff, hat man so die Kollisionen halbiert.

    Spontan schwebt mir auch noch sowas wie eine weitere Cache-Ebene pro Thread vor, die dort, wo die Threads hauptsächlich auf die Datenstruktur hämmern und die Kollisionen statfinden, quasi ohne Synchronisation auskommt.

    Dort wo Kollisionen stattfinden soll keine Synchronisation stattfinden???

    Man kann die Idee, die ich oben angerissen habe, auch noch weiterspinnen, indem jeder Thread nicht nur eine CacheReference für ein einzelnes Objekt hält, sondern gleich einen eigenen thread-lokalen LRU-Cache. Synchronisiert wird dann nur im hinteren Teil bei den Objekten, die aus dem thread-lokalen Cache herausfallen und in den übergeordneten (synchronisierten) Cache für alle Threads eingelagert werden.

    Wenn der Cache überhaupt einen Sinn machen soll, dann wird man wohl nicht ausschliesslich Cache-Misses haben. Das bedeutet, dass im Allgemeinen mehr "Bewegung" im vorderen Teil der LRU-Datenstruktur stattfindet, als im hinteren, wo die Objekte herausfallen.

    Wenn man es schafft, diese "Bewegung" in eine thread-lokale Datenstruktur auszulagern, dann sollte man damit die Kollisionen deutlich reduzieren können.

    Das muss aber wie gesagt noch etwas "ausgeformt" werden, da man für die Umsetzung noch einige Probleme lösen muss, wie dass z.B. ein Thread meint, ein Objekt könnte aus dem Cache herausfallen, weil lange kein Zugriff mehr erfolgte, währed dasselbe Objekt bei einem anderen Thread weit vorne in der Liste steht (eventuell mit atomic-Zählern lösbar ähnlich Reference Counting, wo ein Objekt nur dann aus dem übergeordneten Cache fallen kann, wenn es auch aus allen thread-lokalen Caches gefallen ist).

    Das wird aber schnell recht kompliziert, daher möchte ich jetzt hier nicht ein komplettes Konzept ausarbeiten. Das ist nur ne Art Brainstorming.

    Eine Ebene darunter dann ein zwischen den Threads synchronisierter Cache, in dem die Eviction-Kandidaten verwaltet werden, die aus den einzelnen Pro-Thread-Caches herausgefallen sind. Das aber nur als grobe Idee - für einen tatsächlichen Lösungsansatz müsste die noch weiter ausgeformt werden.

    Irgendwie hast Du echt wilde Phantasien.

    Du sitzt vor einer Maschine, die auch mal eine wilde Phantasie war 😉



  • Wie soll das gehen? Wenn eine Notwendigkeit besteht, ein Mutex zu locken und wieder zu entsperren, was minimum zwei atomare Operationen kostet, dann kann ich das nicht verschieben.

    Ein Zugriff auf Cache-Objekt selbst ist nicht dasselbe wie ein Zugriff auf die Cache-Datenstruktur, in welche dieses eingelagert ist. Diese kann und sollte man auch getrennt synchronisieren - schliesslich muss mit einem Zugriff auf ein individuelles Objekt eben nur dieses Objekt synchronisiert werden und nicht gleich alle Objekte an einem einzigen Synchronisationspunkt (ganz vorne in der LRU-Datenstruktur, wo jedes Objekt, auf das zugegriffen wird, gerne sein möchte und es deshalb zu Gerangel kommt).

    Nochmal: wenn die Notwendigkeit besteht, einen Zugriff zu locken, dann kann ich mir das nicht sparen.

    Wenn das Objekt z.B. nur gelesen wird, oder man bei Modifikation einen Copy-on-Write-Ansatz wählt, bei dem jeder Thread erstmal nur auf seiner eigenen Kopie des Objekts arbeitet, dann ist für Zugriffe auf die Objekte selbst keine Synchronisation notwendig. Diese benötigt man erst dann, wenn auch auf die Cache-Datenstruktur zugegriffen wird, weil für diese mehrere schreibende und lesende Threads exisitieren können.

    Erstens kommst Du hier vom Thema ab, denn das steht in dem Zusammenhang nicht zur Debatte.
    Und zweitens macht sowas keinen Sinn, denn dann verwende ich besser einen Multiple-Reader-One-Writer-Mutex.

    Wenn man nun ein Objekt aus dem Cache holt, dann könnte man z.B. so etwas wie eine Cache-Referenz zurückbekommen:

    struct CacheReference
    {
        const T*       object;
        Timestamp      last_lru_update;
        CacheEntry*    cache_entry;
        ...
    };
    

    ...

    Du denkst dir da völlig unsinnige Ideen an. Denk das mal zuende und implementier das. Da sind schon einige dran gescheitert, eine LRU-Liste zu implementieren die skaliert.

    Man kann die Idee, die ich oben angerissen habe, auch noch weiterspinnen, indem jeder Thread nicht nur eine CacheReference für ein einzelnes Objekt hält, sondern gleich einen eigenen thread-lokalen LRU-Cache.

    Das ist Quatsch. Wenn Du einen Cache in einem Betriebssystem oder in einer Datenbank hast, dann hast Du eine LRU-Liste. Wenn Du mehrere hast dann kriegst Du kein sauberes Verwerfen des ältesten Eintrags hin.

    Synchronisiert wird dann nur im hinteren Teil bei den Objekten, die aus dem thread-lokalen Cache herausfallen und in den übergeordneten (synchronisierten) Cache für alle Threads eingelagert werden.

    Das dumme an deiner Idee ist, dass ein Cache-Eintrag in LRU-Listen anderer Caches stecken kann und Du ihn verschrieben musst. D.h Du musst diese anderen LRU-Listen doch locken. Da kannste gleich eine globale Liste nehmen.

    Irgendwie hast Du echt wilde Phantasien.

    Du sitzt vor einer Maschine, die auch mal eine wilde Phantasie war 😉

    Ne, Du denkst reihenweise Blödsinn an den man nicht sinnvoll zuendendenken kann weil man dann zwangsläufig auf Probleme stößt aufgrund derer man die Idee verwerfen kann.

    Für mich bestand auch kein Bedarf daran, mögliche Lösungen für das parallele LRU-Problem zu diskutieren. Ich habe das Problem größtenteils lock-frei gelöst, also so, dass mehrere Threads fast immer gleichzeitig die LRU-Liste aktualisieren können ohne, dass sich irgendein Thread schlafen legen muss.
    Meine Frage war die eingangs gestellte nach der Effizienz von RTM, das war alles. Zu der Frage mit dem LRU-Cache kann ich hier ernsthafterweise keine sinnvolle Antwort erwarten - wie Du unter Beweis stellst.



  • This post is deleted!


  • @Flodul sagte in Geschwindigkeit atomarer Operationen:

    Erstens kommst Du hier vom Thema ab, denn das steht in dem Zusammenhang nicht zur Debatte.

    Du hast doch selbst die Fragen dazu gestellt, da brauchst du dich nicht zu beschweren, dass ich diese auch beantworte. Aus eigenem Antrieb hätte ich es bei den zwei Sätzen vor zwei Tagen belassen, mit denen ich mögliche Ansätze, die Contention zu reduzieren, zunächst lediglich angerissen habe.

    Für mich bestand auch kein Bedarf daran, mögliche Lösungen für das parallele LRU-Problem zu diskutieren. Ich habe das Problem größtenteils lock-frei gelöst, also so, dass mehrere Threads fast immer gleichzeitig die LRU-Liste aktualisieren können ohne, dass sich irgendein Thread schlafen legen muss.

    Dann stell keine Fragen mit drei (!) Fragezeichen dazu, wenn du es eigentlich gar nicht wissen willst.

    Meine Frage war die eingangs gestellte nach der Effizienz von RTM, das war alles. Zu der Frage mit dem LRU-Cache kann ich hier ernsthafterweise keine sinnvolle Antwort erwarten - wie Du unter Beweis stellst.

    Mit diesem unhöflichen, unterschwellig aggressiven Ton kann ich ruhigen Gewissens sagen, dass das auf Gegenseitigkeit beruht und erfreut bin, diese Diskussion ebenfalls für beendet zu erklären.



  • Erstens kommst Du hier vom Thema ab, denn das steht in dem Zusammenhang nicht zur Debatte.

    Du hast doch selbst die Fragen dazu gestellt, da brauchst du dich nicht zu beschweren, dass ich diese auch beantworte.

    Nein, Du hast eine unsinnige Antwort zu einer Frage die ich nicht gestellt habe gegeben.

    Dann stell keine Fragen mit drei (!) Fragezeichen dazu, wenn du es eigentlich gar nicht wissen willst.

    Da wo ich hier drei Fragezeichen geschrieben habe hat es sich nicht um die Frage gehandelt die Du verkehrt beantwortet hstz.


Log in to reply