Wenn eine Datenstruktur mehrere Elemente enthält, kann die atomare Version nicht (immer) sperrfrei sein. Mir wurde gesagt, dass dies für größere Typen gilt, da die CPU die Daten nicht atomar ändern kann, ohne eine Art Sperre zu verwenden.
zum Beispiel:
#include <iostream>
#include <atomic>
struct foo {
double a;
double b;
};
std::atomic<foo> var;
int main()
{
std::cout << var.is_lock_free() << std::endl;
std::cout << sizeof(foo) << std::endl;
std::cout << sizeof(var) << std::endl;
}
Die Ausgabe (Linux / gcc) ist:
0
16
16
Da das Atom und foo
die gleiche Größe haben, glaube ich nicht, dass ein Schloss im Atom gespeichert ist.
Meine Frage ist:
Wenn eine atomare Variable eine Sperre verwendet, wo wird sie gespeichert und was bedeutet das für mehrere Instanzen dieser Variablen?
is_lock_free()
zu seintrue.
lock cmpxchg16b
falls verfügbar, aber gcc7 und höher geben immer noch false zurückis_lock_free
, obwohl dies technisch gesehen der Fall ist. Aber reine Ladungen und reine Speicher sind langsam und reine Ladungen konkurrieren miteinander. Unter is_lock_free (), das nach dem Upgrade auf MacPorts gcc 7.3 false zurückgegeben hat, finden Sie Links zu weiteren Details zu dieser Entwurfsentscheidung.Antworten:
Der einfachste Weg, solche Fragen zu beantworten, besteht im Allgemeinen darin, sich die resultierende Baugruppe anzusehen und sie von dort zu übernehmen.
Kompilieren Sie Folgendes (Ich habe Ihre Struktur vergrößert, um schlauen Compiler-Spielereien auszuweichen):
#include <atomic> struct foo { double a; double b; double c; double d; double e; }; std::atomic<foo> var; void bar() { var.store(foo{1.0,2.0,1.0,2.0,1.0}); }
In Clang 5.0.0 ergibt sich unter -O3 folgendes: siehe auf Godbolt
bar(): # @bar() sub rsp, 40 movaps xmm0, xmmword ptr [rip + .LCPI0_0] # xmm0 = [1.000000e+00,2.000000e+00] movaps xmmword ptr [rsp], xmm0 movaps xmmword ptr [rsp + 16], xmm0 movabs rax, 4607182418800017408 mov qword ptr [rsp + 32], rax mov rdx, rsp mov edi, 40 mov esi, var mov ecx, 5 call __atomic_store
Großartig, der Compiler delegiert an ein intrinsic (
__atomic_store
), das sagt uns nicht, was hier wirklich los ist. Da der Compiler jedoch Open Source ist, können wir die Implementierung des Intrinsic leicht finden (ich habe sie unter https://github.com/llvm-mirror/compiler-rt/blob/master/lib/builtins/atomic.c gefunden ):void __atomic_store_c(int size, void *dest, void *src, int model) { #define LOCK_FREE_ACTION(type) \ __c11_atomic_store((_Atomic(type)*)dest, *(type*)dest, model);\ return; LOCK_FREE_CASES(); #undef LOCK_FREE_ACTION Lock *l = lock_for_pointer(dest); lock(l); memcpy(dest, src, size); unlock(l); }
Es scheint, als ob die Magie in passiert
lock_for_pointer()
, also schauen wir uns das an:static __inline Lock *lock_for_pointer(void *ptr) { intptr_t hash = (intptr_t)ptr; // Disregard the lowest 4 bits. We want all values that may be part of the // same memory operation to hash to the same value and therefore use the same // lock. hash >>= 4; // Use the next bits as the basis for the hash intptr_t low = hash & SPINLOCK_MASK; // Now use the high(er) set of bits to perturb the hash, so that we don't // get collisions from atomic fields in a single object hash >>= 16; hash ^= low; // Return a pointer to the word to use return locks + (hash & SPINLOCK_MASK); }
Und hier ist unsere Erklärung: Die Adresse des Atoms wird verwendet, um einen Hash-Schlüssel zur Auswahl eines vorab zugewiesenen Schlosses zu generieren.
quelle
Die übliche Implementierung ist eine Hash-Tabelle mit Mutexen (oder auch nur einfachen Spinlocks ohne Rückgriff auf OS-unterstütztes Sleep / Wakeup), wobei die Adresse des atomaren Objekts als Schlüssel verwendet wird . Die Hash-Funktion ist möglicherweise so einfach wie die Verwendung der niedrigen Bits der Adresse als Index für ein Array mit einer Potenz von 2, aber die Antwort von @ Frank zeigt, dass die std :: atomic-Implementierung von LLVM XOR in einigen höheren Bits ausführt, sodass Sie dies nicht tun. t erhält automatisch ein Aliasing, wenn Objekte durch eine große Zweierpotenz getrennt sind (was häufiger vorkommt als bei jeder anderen zufälligen Anordnung).
Ich denke (aber ich bin nicht sicher), dass g ++ und clang ++ ABI-kompatibel sind; Das heißt, sie verwenden dieselbe Hash-Funktion und Tabelle, sodass sie sich darauf einigen, welche Sperre den Zugriff auf welches Objekt serialisiert. Das Sperren erfolgt jedoch vollständig in
libatomic
. Wenn Sie also dynamisch verknüpfen, verwendet derlibatomic
gesamte Code innerhalb desselben Programms, das aufgerufen__atomic_store_16
wird, dieselbe Implementierung. clang ++ und g ++ sind sich definitiv einig, welche Funktionsnamen aufgerufen werden sollen, und das ist genug. (Beachten Sie jedoch, dass nur sperrfreie atomare Objekte im gemeinsam genutzten Speicher zwischen verschiedenen Prozessen funktionieren: Jeder Prozess verfügt über eine eigene Hash-Tabelle mit Sperren . Sperrenfreie Objekte sollen (und tatsächlich) nur im gemeinsam genutzten Speicher auf einer normalen CPU arbeiten Architekturen, auch wenn die Region unterschiedlichen Adressen zugeordnet ist.)Hash-Kollisionen bedeuten, dass zwei atomare Objekte möglicherweise dieselbe Sperre verwenden. Dies ist kein Korrektheitsproblem, aber es könnte ein Leistungsproblem sein : Anstatt zwei Threadpaare, die separat um zwei verschiedene Objekte miteinander konkurrieren, könnten alle vier Threads um den Zugriff auf eines der beiden Objekte kämpfen. Vermutlich ist das ungewöhnlich, und normalerweise möchten Sie, dass Ihre atomaren Objekte auf den Plattformen, die Sie interessieren, frei von Sperren sind. Aber die meiste Zeit hat man nicht wirklich Pech und es ist im Grunde in Ordnung.
Deadlocks sind nicht möglich, da es keine
std::atomic
Funktionen gibt, die versuchen, zwei Objekte gleichzeitig zu sperren. Der Bibliothekscode, der die Sperre übernimmt, versucht also niemals, eine andere Sperre zu aktivieren, während er eine dieser Sperren hält. Zusätzliche Konflikte / Serialisierungen sind kein Korrektheitsproblem, sondern nur die Leistung.x86-64 16-Byte-Objekte mit GCC vs. MSVC :
Als Hack können Compiler das
lock cmpxchg16b
Laden / Speichern von 16-Byte-Atomen sowie tatsächliche Lese-, Änderungs- und Schreibvorgänge implementieren.Dies ist besser als das Sperren, weist jedoch im Vergleich zu 8-Byte-Atomobjekten eine schlechte Leistung auf (z. B. konkurrieren reine Lasten mit anderen Lasten). Dies ist der einzige dokumentierte sichere Weg, um mit 16 Bytes 1 atomar etwas zu tun .
AFAIK, MSVC verwendet niemals
lock cmpxchg16b
für 16-Byte-Objekte und sie sind im Grunde die gleichen wie ein 24- oder 32-Byte-Objekt.gcc6 und früher
lock cmpxchg16b
beim Kompilieren-mcx16
inline (cmpxchg16b ist leider keine Basis für x86-64; AMD K8-CPUs der ersten Generation fehlen es.)gcc7 hat beschlossen,
libatomic
16-Byte-Objekte immer aufzurufen und niemals als sperrenfrei zu melden, obwohl libatomische Funktionenlock cmpxchg16b
auf Computern, auf denen die Anweisung verfügbar ist, weiterhin verwendet werden. Siehe is_lock_free () hat nach dem Upgrade auf MacPorts gcc 7.3 false zurückgegeben . Die gcc-Mailinglistennachricht, die diese Änderung erklärt, ist hier .Sie können einen Union-Hack verwenden, um einen relativ billigen ABA-Zeiger + Zähler auf x86-64 mit gcc / clang zu erhalten: Wie kann ich einen ABA-Zähler mit c ++ 11 CAS implementieren? .
lock cmpxchg16b
für Aktualisierungen von Zeiger und Zähler, aber einfachesmov
Laden nur des Zeigers. Dies funktioniert jedoch nur, wenn das 16-Byte-Objekt tatsächlich sperrenfreilock cmpxchg16b
ist.Fußnote 1 : Das
movdqa
Laden / Speichern von 16 Byte ist in der Praxis auf einigen (aber nicht allen) x86-Mikroarchitekturen atomar , und es gibt keine zuverlässige oder dokumentierte Methode, um zu erkennen, wann es verwendbar ist. Siehe Warum ist die Ganzzahlzuweisung für eine natürlich ausgerichtete Variable auf x86 atomar? und SSE-Anweisungen: Welche CPUs können atomare 16B-Speicheroperationen ausführen? Ein Beispiel, bei dem K10 Opteron mit HyperTransport nur zwischen Sockets an 8B-Grenzen reißt.Compiler-Writer müssen also auf Nummer sicher gehen und können
movdqa
die Art und Weise, wie sie SSE2movq
für das Laden / Speichern von 8-Byte-Atomen in 32-Bit-Code verwenden, nicht verwenden. Es wäre großartig, wenn CPU-Anbieter einige Garantien für einige Mikroarchitekturen dokumentieren oder CPUID-Feature-Bits für das Laden / Speichern von atomaren Vektoren mit 16, 32 und 64 Byte (mit SSE, AVX und AVX512) hinzufügen könnten. Vielleicht könnten die Mobo-Anbieter die Firmware auf funky Maschinen mit vielen Sockeln deaktivieren, die spezielle Kohärenz-Klebechips verwenden, die nicht ganze Cache-Zeilen atomar übertragen.quelle
Ab 29.5.9 des C ++ - Standards:
Es ist vorzuziehen, die Größe eines Atoms an die Größe seines Argumenttyps anzupassen, obwohl dies nicht erforderlich ist. Der Weg, dies zu erreichen, besteht darin, entweder Schlösser zu vermeiden oder die Schlösser in einer separaten Struktur zu speichern. Wie die anderen Antworten bereits klar erklärt haben, werden alle Sperren in einer Hash-Tabelle gespeichert. Dies ist die speichereffizienteste Methode zum Speichern einer beliebigen Anzahl von Sperren für alle verwendeten atomaren Objekte.
quelle
ATOMIC_VAR_INIT
Makro (was für zusammengesetzte Typen nicht gut funktioniert) und erfordert auch, dass die statische Nullinitialisierung eines atomaren Objekts funktioniert. Und C11 bietet keine Destruktoren, um Betriebssystemressourcen in Objektsperren freizugeben. Siehe auch developer.redhat.com/blog/2016/01/14/… für eine Diskussion der im C11-Standard entdeckten Probleme.