Geschwindigkeit atomarer Operationen



  • Ich habe einen LRU-Cache geschrieben wie man ihn in Datenbanken findet. Ansich ist dabei ja das Problem, dass immer nur ein Thread die Links des LRU-Caches aktulalisieren kann. Ich habe dazu mehrere Lösungen im Netz gefunden und zwei US-Patente dazu gelesen, aber nichts war wirklich optimal. Ich hab aber ne Lösung gefunden wie mehrere Threads in einer ungewöhnlichen Kombination aus gelockter und lock-freier Programmierung die LRU-Links gleichzeitig aktualisieren können ohne, dass irgendein Thread sich durch einen Betriebssystem-Aufruf schlafen legen muss bis er dran ist.
    Dazu sind im optimalen Fall drei atomare Speicher-Operationen nötig wenn keine Kollision mit einem anderen Thread passiert. Da dachte ich mir, dass es vielleicht mal interessant wäre zu messen, wie teuer denn so eine Kollision ist. Interessant ist für mich vor allem, ob es Sinn machen würde die LOCK CMPXCHGs (auf denen std:atomic<inttype>::compare_exchange_weak / ::compare_exchange_strong basiert) mit dem TSX-RTM von Intel, also transaktionalem Speicher, zu ersetzen. Nur habe ich nur einen Ryzen 1800X sowie einen älteren Xeon, also beides Rechner ohne TSX. Da habe ich nun ein kleines Programm für Windows und Linux (gcc / clang) geschrieben, dass diese atomaren Updates (auf denen jegliche Thread-Synchronisation beruht) misst, und zwar in drei Variabten: 1. LOCK XADD, 2. LOCK CMPXCHG, 3. TSX-RTM / XBEGIN, XEND. Das habe ich alles mit den jeweils Compiler-spezifischen Intrinsics gemacht.
    Mir wäre daran gelegen, dass das jemand hier mal auf seinem Intel-System mit TSX (Skylake oder neuer, Haswell oder Broadwell hatten ja einen TSX-Bug in der CPU) kompiliert, durchlaufen lässt und hier die Ausgabe veröffentlicht. Mit MSVC gibt's da keine Probleme, bei gcc und clang muss man noch den Code mit -mrtm kompilieren.

    Also hier ist der Code:

    #if defined(_MSC_VER)
    	#include <Windows.h>
    	#include <intrin.h>
    #elif defined(__unix__)
    	#include <sys/sysinfo.h>
    	#include <sched.h>
    	#include <pthread.h>
    	#include <immintrin.h>
    #endif
    #include <iostream>
    #include <thread>
    #include <cstddef>
    #include <atomic>
    #include <functional>
    #include <chrono>
    #include <vector>
    #include <cstdlib>
    #include <cmath>
    #include <array>
    
    bool hasTSX();
    
    using namespace std;
    using namespace chrono;
    
    inline
    size_t fetchAdd( size_t volatile &v, size_t a )
    {
    #if defined(_MSC_VER)
    	#if defined(_M_X64)
    	return (size_t)_InterlockedExchangeAdd64( &(__int64 &)v, (__int64)a );
    	#elif defined(_M_IX86)
    	return (size_t)_InterlockedExchangeAdd( &(long &)v, (long)a );
    	#else
    		#error unsupported architecture
    	#endif
    #elif defined(__GNUC__) || defined(__clang__)
    	return __sync_fetch_and_add( &v, a );
    #else
    		#error unsupported architecture
    #endif
    }
    
    inline
    bool rtmFetchAdd( size_t volatile &v, size_t a )
    {
    	if( _xbegin() == _XBEGIN_STARTED )
    	{
    		v += a;
    		_xend();
    		return true;
    	}
    	else
    		return false;
    }
    
    inline
    size_t compareExchange( size_t volatile &v, size_t c, size_t x )
    {
    #if defined(_MSC_VER)
    	#if defined(_M_X64)
    	return (size_t)_InterlockedCompareExchange64( &(__int64 &)v, (__int64)x, (__int64)c );
    	#elif defined(_M_IX86)
    	return (size_t)_InterlockedCompareExchange( &(long &)v, (long)x, (long)c );
    	#else
    		#error unsupported architecture
    	#endif
    #elif defined(__GNUC__) || defined(__clang__)
    	return __sync_val_compare_and_swap( &v, c, x );
    #else
    		#error unsupported architecture
    #endif
    }
    
    int main( int argc, char **argv )
    {
    	if( argc < 2 )
    		return -1;
    	double nsPerClockCycle = 1.0 / (atof( argv[1] ) * 1.0e9);
    
    	auto thrXadd = []( uint8_t volatile &run, size_t adds, size_t volatile &atm, atomic<size_t> &misses )
    	{
    		while( !run );
    		for( size_t i = adds; i; --i )
    			fetchAdd( atm, 1 );
    	};
    	auto thrXchg = []( uint8_t volatile &run, size_t adds, size_t volatile &atm, atomic<size_t> &misses )
    	{
    		while( !run );
    		size_t missed = 0;
    		for( size_t i = adds, cmp = atm; i; --i )
    		{
    			for( size_t res; ; )
    				if( (res = compareExchange( atm, cmp, cmp + 1 )) == cmp )
    				{
    					cmp = cmp + 1;
    					break;
    				}
    				else
    					cmp = res,
    					++missed;
    		}
    		misses.fetch_add( missed );
    	};
    	auto rtmAdd = []( uint8_t volatile &run, size_t adds, size_t volatile &atm, atomic<size_t> &misses )
    	{
    		while( !run );
    		size_t missed = 0;
    		for( size_t i = adds; i; --i )
    			while( !rtmFetchAdd( atm, 1 ) )
    				++missed;
    		misses.fetch_add( missed );
    	};
    	using threadfunc = void (*)( uint8_t volatile &, size_t, size_t volatile &, atomic<size_t> & );
    	array<threadfunc, 3>   atf;
    	array<char const *, 3> threadDescr;
    	size_t                 nTests;
    	size_t const           ADDS = 10'000'000;
    	unsigned               nProcessors = thread::hardware_concurrency();
    
    	atf[0]         = thrXadd;
    	atf[1]         = thrXchg;
    	atf[2]         = rtmAdd;
    	threadDescr[0] = "xadd-thread";
    	threadDescr[1] = "cmpxchge-thread";
    	threadDescr[2] = "rtm-thread";
    	nTests         = hasTSX() ? atf.size() : atf.size() - 1;
    
    	for( size_t m = 0; m != nTests; ++m )
    	{
    		cout << threadDescr[m] << ":" << endl;
    		for( unsigned nThreads = 1; nThreads <= nProcessors; ++nThreads )
    		{
    			atomic<size_t> misses( 0 );
    			uint8_t        run = false;
    			size_t         atm;
    			vector<thread> threads;
    			for( unsigned i = 0; i != nThreads; ++i )
    			{
    				threads.emplace_back( atf[m], ref( run ), ADDS, ref( atm ), ref( misses ) );
    #if defined(_MSC_VER)
    				SetThreadAffinityMask( threads[i].native_handle(), (DWORD_PTR)1 << i );
    #elif defined(__unix__)
    				cpu_set_t cpuset;
    				CPU_ZERO(&cpuset);
    				CPU_SET(i, &cpuset);
    				pthread_setaffinity_np( threads[i].native_handle(), sizeof cpuset, &cpuset );
    #endif
    			}
    			time_point<high_resolution_clock> start = high_resolution_clock::now();
    			run = true;
    			for( unsigned i = 0; i != nThreads; ++i )
    				threads[i].join();
    			uint64_t ns = (uint64_t)duration_cast<nanoseconds>( high_resolution_clock::now() - start ).count();;
    
    			double nsPerAdd = (double)ns / nThreads / ADDS / 1.0e9;
    			cout << "threads: " << nThreads << " cycles: " << nsPerAdd / nsPerClockCycle << " misses-ratio: " << (int)(100.0 * (size_t)misses / nThreads / ADDS) << "%" << endl;
    		}
    		cout << endl;
    	}
    }
    
    bool hasTSX()
    {
    #if defined(_MSC_VER)
    	int regs[4];
    	__cpuidex( regs, 7, 0 );
    	return regs[1] & (1 << 11);
    #else
    	return true;
    #endif
    }
    

    Mit MSVC gibt's da kein Problem, aber bei gcc und clang muss der Code mit -mrtm kompiliert werden.
    Danke schon mal im Voraus.
    Der Code ermittelt übrigens nur mit dem MSVC, ob die CPU TSX kann oder nicht. Mit gcc / clang nimmt die das einfach so an und crasht im driten Test wenn die CPU kein TSX kann.
    Das Programm muss mit der Angabe des Basistakts der CPU in GHz gestartet werden; für 4.0GHz muss man also "4" oder "4.0" angeben".



  • Hallo,

    Ich habs mal getestet. Der dritte Test hat so lange gedauert, das ich den abgebrochen habe. Somit ist die Ausgabe nicht vollständig.

    xadd-thread:
    threads: 1 cycles: 14.7678 misses-ratio: 0%
    threads: 2 cycles: 15.3087 misses-ratio: 0%
    threads: 3 cycles: 47.5778 misses-ratio: 0%
    threads: 4 cycles: 62.0834 misses-ratio: 0%
    threads: 5 cycles: 61.0066 misses-ratio: 0%
    threads: 6 cycles: 60.6975 misses-ratio: 0%
    threads: 7 cycles: 61.5217 misses-ratio: 0%
    threads: 8 cycles: 61.1497 misses-ratio: 0%
    
    cmpxchge-thread:
    threads: 1 cycles: 15.9961 misses-ratio: 0%
    threads: 2 cycles: 29.8152 misses-ratio: 80%
    threads: 3 cycles: 64.2867 misses-ratio: 110%
    threads: 4 cycles: 202.931 misses-ratio: 258%
    threads: 5 cycles: 191.266 misses-ratio: 230%
    threads: 6 cycles: 238.988 misses-ratio: 307%
    threads: 7 cycles: 228.119 misses-ratio: 284%
    threads: 8 cycles: 261.769 misses-ratio: 338%
    
    rtm-thread:
    threads: 1 cycles: 129.299 misses-ratio: 0%
    threads: 2 cycles: 481.353 misses-ratio: 285%
    threads: 3 cycles: 8129.25 misses-ratio: 7697%
    
    

    Ach so. Das war ein Core i7 6100H mit 2,7GHz



  • @Braunstein sagte in Geschwindigkeit atomarer Operationen:

    Ich habs mal getestet. Der dritte Test hat so lange gedauert, das ich den abgebrochen habe. Somit ist die Ausgabe nicht vollständig.

    Ok, danke.
    Sieht wirklich katastrophal aus für TSX/RTM. Das performt schon single-threaded nicht, und multithreaded geht die Performance voll in den Keller. Das performt wohl nur bei a) geringer Kollisions-Wahrscheinlichkeit und b) größeren Datenstrukturen die in der Transaktion geändert werden.



  • Naja ich weiss nicht ob ein Test wo cmpxchg schon 80% Kollisionen hat wirklich Sinn macht. 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 😉

    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.



  • Hat das schon jemand in der Praxis verwendet? Evtl. abseits wissenschaftlicher Anwendungen? Finde das eigentlich schon interessant, aber in einer 0815 Software, die nicht in einer gesonderten Umgebung, sondern bei verschiedenen Kunden laufen soll, ist es wohl nicht praktikabel. Und wenn man unterschiedliche Codevarianten baut, ist das umständlich und nicht wartbar...



  • Ich denke der Trick sowas wirklich schnell zu bekommen dürfte wohl an dem Punkt ansetzten, die Kollisionen zu reduzieren. Mir scheint Atomics sind hier vorerst das Ende der Fahnenstange.

    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. Das könnte die Kollisionen für Objekte mit hoher Zugriffsfrequenz deutlich reduzieren, während der Algorithmus für die Eviction-Kandidaten am Ende der Liste immer noch genau genug sein könnte - auch wenn die Gefahr besteht, dass bei vielen neuen Cache-Objekten hinten welche herausfallen, die bei dem strikteren Algorithmus im Cache verblieben wären.

    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. 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.



  • 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.

    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.

    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.



  • 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.

    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???

    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.



  • @Mechanics sagte in Geschwindigkeit atomarer Operationen:

    denen Kunden laufen soll, ist es wohl nicht praktikabel. Und wenn man unterschiedliche Codevarianten baut, ist das umständlich und nicht wartbar...

    Ich hab mal gelesen, dass TSX selten vorteilhaft ist. Aber ein Beispiel dafür, dass TSX es auch bringen kann soll SAP HANA sein, dass seine Performance durch TSX nach Aussagen von SAP wohl verdoppelt. Müssen die wohl synthetisch getestet haben, denn es gibt keine offiziellen Builds von HANA für Nicht-TSX-CPUs. D.h. auf AMD-CPUs läuft das einfach nicht.



  • @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.



  • Dieser Beitrag wurde gelöscht!


  • @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.


Anmelden zum Antworten