Antwort auf die Frage.

Historie

Moderne CPUs verwenden Cache-Kohärenzprotokolle wie MESI, um Daten zwischen privaten L1-Caches verschiedener Kerne zu synchronisieren. Wenn unabhängige Threads auf unterschiedliche Speicherorte schreiben, die zufällig auf derselben Cache-Zeile (typischerweise 64 oder 128 Bytes) liegen, serialisiert die Hardware diese Operationen, indem sie kontinuierlich diese Zeile ungültig macht und deren Besitz überträgt, ein Phänomen, das als false sharing bezeichnet wird. C++17 führte std::hardware_destructive_interference_size ein, um die Cache-Zeilenbreite der Architektur offenzulegen, sodass Entwickler veränderliche Daten trennen können, damit die heißen Variablen jedes Threads auf unterschiedlichen Zeilen liegen und diese Synchronisationsüberheads vermeiden.

Problem

Die Anwendung von alignas(std::hardware_destructive_interference_size) auf eine Variable mit automatischer Speicherdauer stellt sicher, dass die Startadresse des Objekts ein Vielfaches der Cache-Zeilen-Größe innerhalb des speziellen Stack-Frames seines Threads ist. Diese Ausrichtung ist jedoch nur lokal für die Sicht des Threads auf den Speicher und garantiert nicht die ausschließliche Belegung der physischen Cache-Zeile. Wenn das Objekt kleiner ist als die Cache-Zeile, können benachbarte Variablen im selben Stack - oder Variablen in den Stacks verschiedener Threads, die zufällig an physischen Adressen zugewiesen sind, die sich um Vielfache der Zeilengröße unterscheiden - auf dieselbe physische Cache-Zeile abgebildet werden. Folglich erfährt die Hardware weiterhin Kohärenzverkehr, wenn ein anderer Thread auf eine andere Variable in derselben Zeile schreibt, wodurch die alignas-Spezifikation unzureichend für die Isolation bleibt.

Lösung

Um false sharing zu vermeiden, muss die Datenstruktur so gepolstert werden, dass sie die gesamte Cache-Zeile ausfüllt, um sicherzustellen, dass keine anderen Daten die physische Speicherung teilen, unabhängig von der Laufzeitadresslage. Dies wird erreicht, indem eine Struktur definiert wird, die sowohl an std::hardware_destructive_interference_size ausgerichtet als auch nach dieser Größe dimensioniert ist.

#include <new>
#include <cstddef>
#include <atomic>

struct alignas(std::hardware_destructive_interference_size) PaddedCounter {
    std::atomic<int> value;
    // Padding füllt den Rest der Cache-Zeile aus, um das Teilen zu verhindern
    char padding[std::hardware_destructive_interference_size - sizeof(std::atomic<int>)];
};

// Array garantiert, dass jedes Element auf einer unterschiedlichen Cache-Zeile liegt
PaddedCounter thread_counters[8];

Lebenssituation

Problembeschreibung

Ein latenzarmer Marktdatenprozessor verwendete acht Arbeits-Threads, von denen jeder einen thread-spezifischen Tick-Zähler in einem globalen Array von std::atomic<int> stats[8] verwaltete. Jeder Thread erhöhte ausschließlich seinen eigenen Index ohne Sperren, doch Profilierung zeigte, dass der Durchsatz auf einem Bruchteil des theoretischen Maximums stagnierte, während die CPU-Zähler übermäßige Cache-Kohärenzzyklen anzeigten statt Benutzer-Modus-Berechnungen. Eine Untersuchung bestätigte, dass die atomaren Ganzzahlen, trotz ihrer logischen Unabhängigkeit, kontiguer in einer einzigen 64-Byte-Cache-Zeile gepackt waren, was zerstörerische Interferenz zwischen den Kernen verursachte.

Lösung 1: Lokale ausgerichtete Variablen

Das Team versuchte zunächst, alignas(64) std::atomic<int> local_stat innerhalb der Ausführungsfunktion jedes Threads zu deklarieren und Zeiger an einen Überwachungs-Thread zu übergeben. Dieser Ansatz erforderte minimale Umgestaltungen und vermied globalen Zustand. Er erwies sich jedoch als unzuverlässig, da der Compiler andere automatische Variablen neben local_stat innerhalb derselben Cache-Zeile platzieren konnte, und die Stapelzuweisungen verschiedener Threads durch exakte Vielfache von 64 Bytes getrennt waren, was dazu führte, dass die ausgerichteten Variablen auf dieselbe physische Zeile abgebildet wurden und das false sharing fortbestand.

Lösung 2: Heap-Zuweisung mit Rohzeigern

Ein anderer betrachteter Ansatz bestand darin, jeden Zähler über new std::atomic<int> zuzuweisen, in der Hoffnung, dass der Heap-Allocator die Zuweisungen über entfernte Speicheradressen streuen würde. Während dies manchmal die Konkurrenz verringert, führte es zu nicht deterministischen Leistungen, da kleine Zuweisungen oft aus zusammenhängenden Blöcken bedient werden, und die Metadaten des Allocators unterschiedliche Objekte auf der gleichen Cache-Zeile platzieren können. Darüber hinaus erforderte dies manuelles Speichermanagement und bot keine Compilerzeitgarantien für Ausrichtung oder Padding.

Ausgewählte Lösung und Ergebnis

Die endgültige Implementierung übernahm die oben definierte Struktur PaddedCounter, wobei Instanzen in einem statischen Array gespeichert wurden. Diese Lösung wurde ausgewählt, weil sie deterministisch die Trennung der Cache-Zeilen durch Kompilierungszeit-Padding und -Ausrichtung durchsetzte, wodurch hardwaremäßige Konkurrenz unabhängig von der Laufzeit-Speicheranordnung ausgeschlossen wurde. Der Speicherverbrauch stieg von 32 Bytes auf 512 Bytes, was für den Leistungsvorteil akzeptabel war. Das Ergebnis war eine zwölfmalige Steigerung des Durchsatzes und eine Reduzierung der Latenzvariabilität, wodurch die Anforderungen an die Verarbeitung unter einer Mikrosekunde erfüllt wurden.

Was Kandidaten oft übersehen

Warum verhindert die Anwendung von alignas(std::hardware_destructive_interference_size) auf ein kleines Objekt nicht das false sharing mit anderen Daten im selben Thread?

alignas steuert nur die Ausrichtung der Startadresse des Objekts, nicht dessen Ausdehnung. Wenn das Objekt kleiner als die Cache-Zeile ist (z.B. eine 4-Byte-Ganzzahl auf einer 64-Byte-Zeile), können die verbleibenden Bytes dieser Cache-Zeile andere Variablen halten. Wenn der Compiler eine andere Variable auf derselben Zeile platziert oder wenn eine Variable eines anderen Threads auf diese physische Zeile abgebildet wird, tritt false sharing auf. Echte Isolation erfordert, dass das Objekt die gesamte Zeile durch Padding einnimmt, und nicht nur an seinem Anfang ausgerichtet ist.

Was ist der Unterschied zwischen std::hardware_destructive_interference_size und std::hardware_constructive_interference_size, und wann würde das Gruppieren von Daten zur Anpassung an die letztere Größe die Leistung verbessern?

std::hardware_destructive_interference_size ist die minimale Trennung, die erforderlich ist, um false sharing zu vermeiden, während std::hardware_constructive_interference_size die maximale Größe von Daten ist, die von räumlicher Lokalitität auf einer einzelnen Cache-Zeile profitiert. Das Gruppieren verwandter häufig zugegriffener Felder (z.B. die x-, y-, z-Koordinaten eines Punktes) in eine Struktur, die innerhalb der konstruktiven Größe passt, stellt sicher, dass sie sich auf derselben Zeile befinden, was die Cache-Trefferquoten und die Vorhersageeffizienz maximiert, während die destruktive Größe verwendet wird, um nicht zusammenhängende veränderliche Daten zu trennen.

Wie wirkt sich false sharing auf std::atomic-Operationen unter Verwendung von memory_order_relaxed aus, und warum löst die entspannte Speicherausrichtung nicht die Leistungsverschlechterung?

Selbst mit memory_order_relaxed, das keine Ordnungseinschränkungen auf umgebende Speicheroperationen auferlegt, erfordert ein atomarer Schreibvorgang, dass der CPU-Kern den exklusiven Besitz der Cache-Zeile erwerben muss (ein Lese-von-Besitz-Zyklus). Wenn ein anderer Thread kürzlich eine andere Variable auf derselben Zeile geändert hat, zwingt das Cache-Kohärenzprotokoll die Zeile, zwischen den Kernen zu springen. Diese hardwarebasierte Synchronisation erfolgt unabhängig von den logischen Garantien des C++-Speichermodells, was bedeutet, dass false sharing die vollständige Latenzzeit bei Cache-Fehlzugriffen verursacht, unabhängig von der angegebenen Speicherordnung.