wake-up-neo.net

Warum kombinieren Compiler keine redundanten std :: atomic-Schreibvorgänge?

Ich frage mich, warum keine Compiler bereit sind, aufeinanderfolgende Schreibvorgänge desselben Werts mit einer einzigen atomaren Variablen zusammenzuführen, z.

#include <atomic>
std::atomic<int> y(0);
void f() {
  auto order = std::memory_order_relaxed;
  y.store(1, order);
  y.store(1, order);
  y.store(1, order);
}

Jeder Compiler, den ich ausprobiert habe, wird den obigen Schreibvorgang dreimal ausgeben. Welcher legitime, rassenfreie Beobachter konnte mit einem einzigen Schreibvorgang einen Unterschied zwischen dem obigen Code und einer optimierten Version erkennen (d. H. Gilt die "wenn-wenn" -Regel)?

Wenn die Variable flüchtig war, ist offensichtlich keine Optimierung möglich. Was hindert es in meinem Fall?

Hier ist der Code im Compiler Explorer .

47
PeteC

Die C++ 11/C++ 14-Standards wie geschrieben erlauben es, die drei Speicher zu einem Speicher des Endwerts zu falten/zusammenzuführen. Selbst in einem solchen Fall:

y dreht (mit Atomlast oder CAS),   y.store(1, order);
  y.store(2, order);
  y.store(3, order); // inlining + constant-folding could produce this in real code
 jemals sehen wird. Ein Programm, das davon abhängt, hätte einen Datenrennenfehler, aber nur die Art der Gartenartensorte, nicht aber das C++ Undefined Behavior-Datenrennen. (Es ist nur UB mit nicht-atomaren Variablen). Ein Programm, das manchmal erwartet, muss nicht unbedingt fehlerhaft sein. (Siehe unten: Fortschrittsbalken.)

Jede Bestellung, die auf der abstrakten C++ - Maschine möglich ist, kann (zur Kompilierzeit) als die Reihenfolge ausgewählt werden, die immer passieren wird. Dies ist die Ist-Regel in Aktion. In diesem Fall ist es als ob alle drei Speicher fanden in der globalen Reihenfolge hintereinander statt, und es wurden keine Ladungen oder Speicher von anderen Threads zwischen y == 2 und y=1 ausgeführt.

Es hängt nicht von der Zielarchitektur oder -hardware ab. genau wie Kompilierzeitumordnung von entspannten atomaren Operationen sind erlaubt, selbst wenn stark geordnetes x86 anvisiert wird. Der Compiler muss nicht alles bewahren, was Sie von der Hardware, für die Sie kompilieren möchten, erwarten können. Daher benötigen Sie Barrieren. Die Barrieren können sich zu Null-ASM-Anweisungen zusammenstellen.


Warum machen Compiler diese Optimierung nicht?

Dies ist ein Problem mit der Qualität der Implementierung und kann die beobachtete Leistung/das Verhalten auf echter Hardware ändern.

Der offensichtlichste Fall, in dem es ein Problem ist, ist ein Fortschrittsbalken. Wenn Sie die Läden aus einer Schleife herausnehmen (die keine anderen atomaren Operationen enthält) und sie alle zu einer einzigen zusammenfassen, würde ein Fortschrittsbalken auf 0 bleiben und dann am Ende auf 100% steigen.

Es gibt keinen C++ 11 y=3-Weg, um stop von ihnen in Fällen zu tun, in denen Sie es nicht möchten. Daher entscheiden sich Compiler für jetzt, niemals mehrere atomare Operationen zu einer zu verschmelzen. (Wenn Sie alle zu einer Operation zusammenführen, ändert sich ihre Reihenfolge nicht relativ zueinander.)

Compiler-Writer haben richtig gemerkt, dass Programmierer erwarten, dass ein atomarer Speicher bei jeder y.store()-Quelle tatsächlich im Speicher ausgeführt wird. (Siehe die meisten anderen Antworten auf diese Frage, die behaupten, die Geschäfte müssten separat ausgeführt werden, da möglicherweise Leser auf einen Zwischenwert warten.) Das heißt, es verstößt gegen das Prinzip der kleinsten Überraschung.

Es gibt jedoch Fälle, in denen dies sehr hilfreich sein könnte, z. B., um unnötige std::atomic ref count inc/dec in einer Schleife zu vermeiden.

Natürlich kann eine Neuordnung oder Zusammenlegung nicht gegen andere Bestellregeln verstoßen. Zum Beispiel müsste shared_ptr immer noch eine vollständige Barriere für die Laufzeit- und Kompilierzeitumstellung sein, auch wenn der Speicher bei num nicht mehr berührt wurde.


Die Diskussion ist im Gange, um die num++; num--;-API zu erweitern, um dem Programmierer die Kontrolle über solche Optimierungen zu geben. Ab diesem Zeitpunkt können Compiler optimieren, wenn dies sinnvoll ist. Dies kann sogar in sorgfältig geschriebenem Code geschehen, der nicht absichtlich ineffizient ist. Einige Beispiele für nützliche Fälle zur Optimierung werden in den folgenden Verknüpfungen/Vorschlägen für Arbeitsgruppen erwähnt:

Siehe auch die Diskussion zu diesem Thema zu Richard Hodges 'Antwort auf Kann num ++ für' int num 'atomar sein? (siehe die Kommentare). Siehe auch den letzten Abschnitt von meiner Antwort zur gleichen Frage, wo ich ausführlicher argumentiere, dass diese Optimierung erlaubt ist. (Lassen Sie es hier kurz, da diese C++ - Arbeitsgruppenverbindungen bereits erkennen, dass der aktuelle Standard, wie geschrieben, dies zulässt und dass aktuelle Compiler nicht absichtlich optimieren.)


Im aktuellen Standard wäre std::atomic eine Möglichkeit, um sicherzustellen, dass das Speichern von Inhalten nicht optimiert werden kann. (As Herb Sutter weist in einer Antwort von SO darauf hin , volatile und atomic haben bereits einige Anforderungen, die jedoch unterschiedlich sind). Siehe auch die Beziehung von volatile atomic<int> y ZU volatile auf cppreference.

Zugriffe auf volatile-Objekte dürfen nicht wegoptimiert werden (da es sich beispielsweise um speicherzugeordnete IO -Register) handeln kann.

Die Verwendung von std::memory_order behebt meistens das Fortschrittsbalkenproblem, aber es ist ziemlich hässlich und kann in einigen Jahren dumm aussehen, wenn C++ eine andere Syntax für die Steuerung der Optimierung wählt, sodass Compiler dies in der Praxis tun können.Ich denke, wir können sicher sein, dass Compiler erst dann mit dieser Optimierung beginnen, wenn es eine Möglichkeit gibt, sie zu steuern. Hoffentlich wird es eine Art Opt-In (wie ein volatile atomic<T>) sein, das das Verhalten des vorhandenen Code C++ 11/14 nicht ändert, wenn er als C++ kompiliert wird. Es könnte jedoch wie in dem Vorschlag in wg21/p0062 aussehen: Tag nicht optimieren Fälle mit memory_order_release_coalesce.

wg21/p0062 warnt davor, dass auch [[brittle_atomic]] nicht alles löst, und rät von seiner Verwendung ab. Es gibt dieses Beispiel:.

__Code-Auszug__

volatile atomic darf ein Compiler die y.store() aus dem if(x) {
    foo();
    y.store(0);
} else {
    bar();
    y.store(0);  // release a lock before a long-running loop
    for() {...} // loop contains no atomics or volatiles
}
// A compiler can merge the stores into a y.store(0) here.

volatile beendet zwar das in der Frage diskutierte Zusammenfließen, weist jedoch darauf hin, dass andere Optimierungen bei if/else für die tatsächliche Leistung ebenfalls problematisch sein können.

.


Andere Gründe für die Nichtoptimierung sind: Niemand hat den komplizierten Code geschrieben, der es dem Compiler ermöglicht, diese Optimierungen sicher durchzuführen (ohne dass er jemals falsch gemacht wurde). Dies reicht nicht aus, da laut N4455 bereits mehrere der genannten Optimierungen von LLVM implementiert werden oder leicht implementiert werden könnten.

Der für Programmierer verwirrende Grund ist jedoch durchaus plausibel. Lock-Free-Code ist schwer genug, um überhaupt erst richtig zu schreiben.

Seien Sie beim Umgang mit Atomwaffen nicht beiläufig: Sie sind nicht billig und optimieren nicht viel (derzeit überhaupt nicht). Es ist nicht immer leicht, redundante atomare Operationen mit seq_cst zu vermeiden, da es keine nicht-atomare Version davon gibt (obwohl eine der Antworten hier eine einfache Möglichkeit gibt, einen atomic<> für gcc zu definieren).

Don't be casual in your use of atomic weapons: they aren't cheap and don't optimize much (currently not at all). It's not always easy easy to avoid redundant atomic operations with std::shared_ptr<T>, though, since there's no non-atomic version of it (although one of the answers here gives an easy way to define a shared_ptr_unsynchronized<T> for gcc).

34
Peter Cordes

Sie beziehen sich auf die Beseitigung von Dead-Stores. 

Es ist nicht verboten, einen atomaren Totspeicher zu beseitigen, aber es ist schwieriger zu beweisen, dass ein Atomladen als solcher qualifiziert ist.

Herkömmliche Compiler-Optimierungen, z. B. die Beseitigung von Deadstores, können für atomare Operationen durchgeführt werden, sogar für sequentiell konsistente.
Optimierer müssen darauf achten, dies nicht über Synchronisation -Punkte zu vermeiden, da ein anderer Thread der Ausführung den Speicher beobachten oder ändern kann. Dies bedeutet, dass die traditionellen Optimierungen mehr intervenierende Anweisungen berücksichtigen müssen, als dies bei Optimierungen für atomare Systeme der Fall wäre Operationen.
Im Falle der Dead-Store-Eliminierung reicht es nicht aus, den Nachweis zu erbringen, dass ein Atom-Store einen anderen dominiert und einen anderen Aliase setzt, um den anderen Store zu eliminieren.

von N4455 Kein vernünftiger Compiler würde Atomics optimieren

Das Problem der atomaren DSE besteht im allgemeinen Fall darin, dass nach Synchronisationspunkten gesucht wird. In diesem Verständnis bedeutet dieser Begriff Punkte im Code, an denen zufälliges Vorher eine Beziehung zwischen einer Anweisung auf einem Thread A besteht und Anweisung auf ein anderer Thread B. 

Betrachten Sie diesen Code, der von einem Thread A ausgeführt wird:

y.store(1, std::memory_order_seq_cst);
y.store(2, std::memory_order_seq_cst);
y.store(3, std::memory_order_seq_cst);

Kann es als y.store(3, std::memory_order_seq_cst) optimiert werden?

Wenn ein Thread B auf y = 2 wartet (z. B. mit einem CAS), würde er niemals feststellen, dass der Code optimiert wird, wenn der Code optimiert wird. 

In meinem Verständnis ist jedoch B-Looping und CASsing bei y = 2 ein Datenrennen, da zwischen den Anweisungen der beiden Threads keine Gesamtreihenfolge besteht.
Eine Ausführung, bei der die Anweisungen von A vor der Schleife von B ausgeführt werden, ist beobachtbar (d. H. Zulässig), und der Compiler kann daher auf y.store(3, std::memory_order_seq_cst) optimieren.

Wenn die Threads A und B auf irgendeine Weise zwischen den Speichern in Thread A synchronisiert werden, ist die Optimierung nicht zulässig (eine Teilreihenfolge würde induziert, was möglicherweise dazu führt, dass B möglicherweise y = 2 beachtet). 

Der Nachweis, dass es keine solche Synchronisation gibt, ist schwierig, da ein breiterer Umfang und alle Macken einer Architektur berücksichtigt werden müssen.

Meines Verständnis nach können Compiler aufgrund des relativ geringen Alters der atomaren Operationen und der Schwierigkeit, über Reihenfolge, Sichtbarkeit und Synchronisierung von Speicher nachzudenken, nicht alle möglichen Optimierungen der Atomik durchführen, bis ein robusterer Rahmen zum Erkennen und Verstehen des Notwendigen vorhanden ist Bedingungen sind gebaut.

Ich glaube, Ihr Beispiel ist eine Vereinfachung des oben angegebenen Zähl-Threads, da er keinen anderen Thread oder Synchronisationspunkt hat. Was ich sehen kann, könnte der Compiler die drei Stores optimiert haben.

41
Margaret Bloom

Während Sie den Wert eines Atoms in einem Thread ändern, wird dieser möglicherweise von einem anderen Thread überprüft und basierend auf dem Wert des Atoms ausgeführt. Das Beispiel, das Sie gegeben haben, ist so spezifisch, dass Compiler-Entwickler es nicht für sinnvoll erachten, es zu optimieren. Wenn jedoch ein Thread z. aufeinanderfolgende Werte für ein Atom: 0, 1, 2 usw. Der andere Thread kann etwas in die durch den Atomwert angegebenen Slots einfügen.

9
Serge Rogatch

Kurz gesagt, weil der Standard (zum Beispiel die Paragaraphien um und unter 20 in [intro.multithread]) dafür nicht zulässig ist.

Es gibt Garantien, die erfüllt werden müssen und die unter anderem eine Neuordnung oder Zusammenlegung von Schreibweisen ausschließen (Paragraph 19 sagt sogar ausdrücklich die Neuordnung aus).

Wenn Ihr Thread nacheinander drei Werte in den Speicher schreibt (beispielsweise 1, 2 und 3), wird der Wert möglicherweise von einem anderen Thread gelesen. Wenn Ihr Thread beispielsweise unterbrochen ist (oder auch wenn er gleichzeitig ausgeführt wird) und ein anderer Thread also - an diesen Speicherort schreibt, muss der beobachtende Thread die Operationen in genau derselben Reihenfolge sehen, in der sie vorkommen (entweder durch Zeitplanung oder Zufall oder aus welchem ​​Grund auch immer). Das ist eine Garantie. 

Wie ist das möglich, wenn Sie nur die Hälfte (oder auch nur eine einzige) schreiben? Es ist nicht.

Was ist, wenn Ihr Thread stattdessen 1 -1 -1 ausschreibt, ein anderer jedoch sporadisch 2 oder 3 ausschreibt? Was ist, wenn ein dritter Thread die Position beobachtet und auf einen bestimmten Wert wartet, der einfach nie angezeigt wird, weil er optimiert wurde?

Es ist nicht möglich, die Garantien zu geben, die gegeben werden, wenn das Speichern (und auch Laden) nicht wie gewünscht ausgeführt wird. Alle und in derselben Reihenfolge.

5
Damon

NB: Ich wollte das kommentieren, aber es ist etwas zu wortreich.

Eine interessante Tatsache ist, dass dieses Verhalten in Bezug auf C++ kein Datenrennen ist.

Anmerkung 21 auf S.14 ist interessant: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3690.pdf (meine Hervorhebung):

Die Ausführung eines Programms enthält ein Datenrennen, wenn es zwei .__ enthält. widersprüchliche Aktionen in verschiedenen Threads, von denen mindestens eine davon ist nicht atomar

Ebenfalls auf S.11 Anmerkung 5:

"Entspannte" atomare Operationen sind auch keine Synchronisationsoperationen Wie Synchronisierungsvorgänge können sie jedoch nicht zu .__ beitragen. Datenrennen.

Eine widersprüchliche Aktion auf einem Atom ist also niemals ein Datenrennen - im Sinne des C++ - Standards.

Diese Operationen sind alle atomar (und speziell entspannt), aber es gibt kein Datenrennen hier Leute!

Ich stimme zu, dass es auf jeder (vernünftigen) Plattform keinen zuverlässigen/vorhersagbaren Unterschied zwischen diesen beiden gibt:

include <atomic>
std::atomic<int> y(0);
void f() {
  auto order = std::memory_order_relaxed;
  y.store(1, order);
  y.store(1, order);
  y.store(1, order);
}

und 

include <atomic>
std::atomic<int> y(0);
void f() {
  auto order = std::memory_order_relaxed;
  y.store(1, order);
}

Innerhalb der Definition des C++ - Speichermodells handelt es sich jedoch nicht um ein Datenrennen.

Ich kann nicht leicht verstehen, warum diese Definition bereitgestellt wird, aber es gibt dem Entwickler ein paar Karten, um eine zufällige Kommunikation zwischen Threads zu betreiben, von denen sie wissen, dass sie (auf ihrer Plattform) statistisch funktionieren.

Wenn Sie zum Beispiel einen Wert dreimal einstellen und ihn dann zurücklesen, wird ein gewisses Maß an Konkurrenz für diesen Ort angezeigt. Solche Ansätze sind nicht deterministisch, aber viele effektive gleichzeitige Algorithmen sind nicht deterministisch. Zum Beispiel ist ein Zeitlimit try_lock_until() immer eine Race-Bedingung, bleibt aber eine nützliche Technik.

Was der C++ - Standard zu bieten scheint, gibt Ihnen Gewissheit in Bezug auf "Datenrennen", ermöglicht aber bestimmte Spiel- und Spaßbedingungen mit Rennbedingungen, die abschließend verschiedene Aspekte betreffen.

Kurz gesagt, der Standard scheint zu spezifizieren, dass wo andere Threads den 'Hammering'-Effekt eines dreimal gesetzten Wertes sehen können, andere Threads diesen Effekt sehen müssen (auch wenn sie manchmal nicht!). Es ist der Fall, wo so ziemlich alle modernen Plattformen, dass andere Threads unter bestimmten Umständen das Hämmern sehen können.

5
Persixty

Ein praktischer Anwendungsfall für das Muster, wenn der Thread etwas Wichtiges zwischen Aktualisierungen durchführt, die nicht von y abhängen oder diese modifizieren, könnte Folgendes sein: * Thread 2 liest den Wert von y, um zu überprüfen, wie viel Fortschritt Thread 1 erzielt hat.`

Vielleicht soll Thread 1 die Konfigurationsdatei als Schritt 1 laden, seine geparsten Inhalte als Schritt 2 in eine Datenstruktur einfügen und das Hauptfenster als Schritt 3 anzeigen, während Thread 2 auf Schritt 2 wartet, um den Vorgang abzuschließen Führen Sie parallel eine andere Aufgabe aus, die von der Datenstruktur abhängt. (Zugegeben, in diesem Beispiel wird Semantik erwerben/freigeben, nicht in lockerer Reihenfolge gefordert.)

Ich bin mir ziemlich sicher, dass eine konforme Implementierung es Thread 1 nicht erlaubt, y in einem Zwischenschritt zu aktualisieren - obwohl ich den Sprachstandard nicht eingehend untersucht habe, wäre ich schockiert, wenn er keine Hardware unterstützt, auf der y von einem anderen Thread-Abruf möglicherweise nicht angezeigt wird der Wert 2.

Dies ist jedoch ein hypothetischer Fall, in dem es möglicherweise pessimal ist, die Statusaktualisierungen zu optimieren. Vielleicht kommt ein Compiler-Entwickler hierher und sagt, warum sich dieser Compiler nicht entschieden hat, aber ein möglicher Grund ist, dass Sie sich in den Fuß schießen lassen oder sich zumindest in den Zeh stecken.

2
Davislor

Gehen wir etwas weiter weg von dem pathologischen Fall, dass die drei Geschäfte unmittelbar nebeneinander liegen. Nehmen wir an, es wird eine nicht triviale Arbeit zwischen den Stores geleistet, und diese Arbeit erfordert y nicht (so dass die Analyse des Datenpfads feststellen kann, dass die drei Stores tatsächlich zumindest innerhalb dieses Threads redundant sind) Sie selbst führen keine Speicherbarrieren ein (damit die Speicher nicht durch etwas anderes für andere Threads sichtbar werden). Nun ist es durchaus möglich, dass andere Threads die Möglichkeit haben, Arbeit zwischen den Stores zu erledigen, und diese anderen Threads möglicherweise y bearbeiten und dass dieser Thread einen Grund hat, sie auf 1 (den zweiten Store) zurückzusetzen. Wenn die ersten beiden Geschäfte fallen gelassen würden, würde sich das Verhalten ändern.

0
Andre Kostur