Ich habe das Java-Speichermodell untersucht und sah Probleme bei der Neuordnung. Ein einfaches Beispiel:
%Vor%Das Umsortieren ist sehr unberechenbar und seltsam. Außerdem ruiniert es Abstraktionen. Ich nehme an, dass Prozessor-Architekturen einen guten Grund haben müssen, etwas zu tun, das für Programmierer so unbequem ist. Was sind das für Gründe?
Es gibt eine Menge Informationen darüber, wie die Nachbestellung gehandhabt wird, aber ich kann nichts finden über warum es benötigt wird. Überall sagen die Leute einfach etwas wie "es ist wegen einiger Leistungsvorteile". Was sind die Leistungsvorteile beim Speichern von second vor first , zum Beispiel?
Können Sie einen Artikel, ein Papier oder ein Buch dazu empfehlen oder selbst erklären?
TL; DR : Dies gibt dem Compiler und der Hardware mehr Raum, um die as-if -Regel zu nutzen, da sie nicht das gesamte Verhalten der ursprünglichen Quelle beibehalten muss , nur das Ergebnis des einzelnen Threads selbst.
Wenn man die extern beobachtbaren (von anderen Threads) Ordnungen von Ladungen / Speichern aus dem Bild als etwas betrachtet, das Optimierungen erhalten müssen, gibt der Compiler viel Raum, um Dinge in weniger Operationen zusammenzuführen. Für die Hardware ist die Verzögerung von Speichern der große, aber für Compiler kann jede Art von Neuordnung helfen.
(Siehe Abschnitt unten für einen Abschnitt, warum es dem Compiler hilft)
Hardware, die frühere Speicher mit späteren Ladungen neu anordnet ( StoreLoad-Neuordnung ) Die CPU ist für die Out-of-Order-Ausführung unerlässlich. (Siehe unten).
Andere Arten der Neuanordnung (z. B. die StoreStore-Neuordnung, die Gegenstand Ihrer Frage ist) sind nicht unbedingt erforderlich, und Hochleistungs-CPUs können nur mit der StoreLoad-Neuordnung erstellt werden, nicht mit den anderen drei Arten. (Das wichtigste Beispiel ist tag: x86, wobei jeder Store ein Release-Store ist, wobei jeder Ladevorgang ein Acquise-Load ist x86 Tag-Wiki für weitere Details.)
Einige Leute, wie Linus Torvalds, argumentieren, dass die Neuordnung von Geschäften mit anderen Geschäften der Hardware nicht viel hilft, weil die Hardware bereits die Speicherreihenfolge überwachen muss, um die Ausführung eines einzelnen Threads außerhalb der Reihenfolge zu unterstützen . (Ein einzelner Thread läuft immer so, als ob alle seine eigenen Speicher / Ladevorgänge in der Programmreihenfolge passieren würden.) Sehen Sie sich die anderen Beiträge in diesem Thread auf realworldtech an, wenn Sie neugierig sind. Und / oder wenn Sie Linus 'Mischung aus Beleidigungen und sinnvollen technischen Argumenten unterhaltend finden: P
Für Java besteht das Problem darin, dass Architekturen existieren, wo die Hardware diese Bestellgarantien nicht bietet. Schwache Speicherordnung ist ein gemeinsames Merkmal von RISC-ISAs wie ARM, PowerPC und MIPS. (Aber nicht SPARC-TSO). Die Gründe für diese Design-Entscheidung sind die gleichen, die im real- worldtech-Thread, den ich verlinkt habe, diskutiert werden: die Hardware einfacher zu machen und die Software bei Bedarf die Bestellung anfordern zu lassen.
So hatten Javas Architekt (e) keine große Wahl: Die Implementierung einer JVM für eine Architektur mit einem schwächeren Speichermodell als dem Java-Standard würde nach jedem einzelnen Geschäft eine Store-Barriere-Anweisung und eine Lastschranke erfordern vor jeder Ladung. (Außer wenn der JIT-Compiler der JVM beweisen kann, dass kein anderer Thread einen Verweis auf diese Variable haben kann.) Die Ausführung von Barrier-Anweisungen ist langsam.
Ein starkes Speichermodell für Java würde effiziente JVMs auf ARM (und anderen ISAs) unmöglich machen. Der Nachweis, dass Barrieren nicht benötigt werden, ist nahezu unmöglich und erfordert KI-Ebenen des globalen Programmverständnisses. (Dies geht viel weiter als normale Optimierer).
(siehe auch den hervorragenden Blogbeitrag von Jeff Preshing auf C ++ - Neuordnungsreihenfolge zur Kompilierung Grundsätzlich gilt für Java, wenn Sie JIT-Compiling als Teil des Prozesses in nativen Code integrieren.)
Ein weiterer Grund dafür, dass die Java- und C / C ++ - Speichermodelle schwach bleiben, besteht darin, mehr Optimierungen zuzulassen. Da andere Threads (nach dem Modell mit schwachem Speicher) unsere Speicher und Ladevorgänge in beliebiger Reihenfolge beobachten können, sind aggressive Transformationen auch dann zulässig, wenn der Code Speicher in den Speicher einbezieht.
z.B. in einem Fall wie Davides Beispiel:
%Vor% Es ist nicht erforderlich, dass andere Threads die Zwischenzustände beobachten können. Also kann ein Compiler das zu c.a = 2; c.b = 2; kompilieren, entweder zur Java-Kompilierzeit oder wenn der Bytecode JIT-kompiliert ist, um Maschinencode zu kompilieren.
Es ist üblich, dass eine Methode das Inkrementieren von Dingen, die mehrmals aufgerufen werden, von einer anderen Methode inkrementiert. Ohne diese Regel könnte das Umwandeln in c.a += 4 nur erfolgen, wenn der Compiler beweisen könnte, dass kein anderer Thread den Unterschied beobachten kann.
C ++ - Programmierer machen manchmal den Fehler zu denken, dass sie, da sie für x86 kompilieren, std::atomic<int> nicht benötigen, um einige Bestellgarantien für eine gemeinsame Variable zu erhalten. Dies ist falsch, da Optimierungen auf der Grundlage der Als-ob-Regel für das Sprachspeichermodell und nicht der Zielhardware erfolgen.
Sobald ein Speicher im Cache festgeschrieben ist, wird er für Threads, die auf anderen Kernen ausgeführt werden, global sichtbar (über das Cache-Kohärenz-Protokoll).An diesem Punkt ist es zu spät, um es zurückzurollen (ein anderer Kern könnte bereits eine Kopie des Wertes erhalten haben). Es kann also nicht passieren, bis bekannt ist, dass der Laden keine Fehler machen wird, und auch keine Anweisung davor. und die Daten des Ladens sind fertig. Und dass es zu einem früheren Zeitpunkt keine Verzweigungsfehlvorhersage gegeben hat etc. usw., d. H. Wir müssen alle Fälle von Fehlspekulationen ausschließen, bevor wir eine Geschäftsanweisung zurückziehen können.
Ohne StoreLoad-Neuordnung müsste jede Ladung warten, bis alle vorhergehenden Speicher beendet sind (dh die Ausführung vollständig beendet wurde, nachdem die Daten in den Cache gespeichert wurden), bevor sie einen Wert aus dem Cache für spätere Anweisungen lesen konnten Wert geladen. (Der Zeitpunkt, zu dem ein Ladevorgang einen Wert aus dem Cache in ein Register kopiert, ist der Fall, wenn er für andere Threads global sichtbar ist.)
Da Sie nicht wissen können, was auf anderen Kernen passiert, glaube ich nicht, dass die Hardware diese Verzögerung beim Starten von Lasten verbergen kann, indem sie spekuliert, dass dies kein Problem ist, und dann Miss-Spekulationen nach der Tat entdeckt. (Und behandeln Sie es wie einen Verzweigungsfehler: Werfen Sie alle Arbeiten, die von dieser Last abhängen, weg und geben Sie sie erneut aus.) Ein Kern könnte spekulative frühe Lasten von Cache-Zeilen zulassen, die in Exclusive oder Modified Zustand, da sie in anderen Kernen nicht vorhanden sein können. (Erkennen von Fehlspekulationen, wenn eine Cache-Kohärenzanforderung für diese Cache-Zeile von einer anderen CPU kam, bevor der letzte Speicher vor der spekulativen Ladung zurückgenommen wurde.) Dies ist offensichtlich eine große Menge an Komplexität, die für nichts anderes benötigt wird.
Beachten Sie, dass ich Cache-Misses für Stores nicht einmal erwähnt habe. Dies erhöht die Latenz eines Geschäfts von einigen Zyklen auf Hunderte von Zyklen.
Ich habe einige Links als Teil einer kurzen Einführung in die Computerarchitektur im ersten Teil meiner Antwort auf Optimieren eines Programms für die Pipeline in Intel Sandybridge-Familien-CPUs . Das könnte hilfreich oder verwirrend sein, wenn Sie das schwer zu befolgen finden.
CPUs vermeiden Speicherwarteschlange , bis die Speicheranweisungen bereit sind, in den Ruhestand zu gehen. Lasten aus demselben Kern müssen die Speicherwarteschlange überprüfen (um das Erscheinungsbild der Ausführung in der richtigen Reihenfolge für einen einzelnen Thread zu erhalten, andernfalls würden Sie Anweisungen zur Speicherschranke benötigen, bevor Sie etwas laden, das möglicherweise kürzlich gespeichert wurde!). Die Speicherwarteschlange ist für andere Threads unsichtbar. Speicher werden nur dann global sichtbar, wenn der Speicherbefehl in den Ruhestand geht, aber Ladevorgänge werden global sichtbar, sobald sie ausgeführt werden. (Und kann Werte verwenden, die vorab in den Cache geladen wurden.)
Siehe auch Wikipedia-Artikel über die klassische RISC-Pipeline .
Eine Out-of-Order-Ausführung ist daher für Stores möglich, sie werden jedoch nur in der Store-Warteschlange neu angeordnet. Da Instruktionen in den Ruhestand gehen müssen, um präzise Ausnahmen zu unterstützen, scheint es keinen großen Vorteil zu geben, dass die Hardware die StoreStore-Anordnung erzwingt.
Da Ladevorgänge bei ihrer Ausführung global sichtbar werden, kann das Erzwingen der LoadLoad-Reihenfolge möglicherweise eine Verzögerung der Ladevorgänge nach einem Ladevorgang erfordern, der im Cache fehlschlägt. Natürlich würde die CPU in der Realität die folgenden Lasten spekulativ ausführen und eine Fehlordnung der Speicherreihenfolge erkennen, falls sie auftritt. Dies ist nahezu unerlässlich für eine gute Leistung: Ein großer Teil der Vorteile der Out-of-Order-Ausführung besteht darin, weiterhin nützliche Arbeit zu leisten und die Latenz von Cache-Fehlern zu verbergen.
Eines der Argumente von Linus ist, dass schwach geordnete CPUs Multi-Threaded-Code benötigen, um viele Speicherbarriere-Anweisungen zu verwenden, so dass sie für Multi-Thread-Code billig sein müssen, um nicht zu saugen. Das ist nur möglich, wenn die Hardware die Abhängigkeitsreihenfolge von Lasten und Speichern verfolgt.
Aber wenn Sie diese Hardware-Verfolgung von Abhängigkeiten haben, können Sie nur die Hardware zwingen, die ganze Zeit zu ordern, so dass die Software nicht so viele Sperranweisungen ausführen muss. Wenn Sie Hardware-Unterstützung haben, um Barrieren billig zu machen, warum sollten Sie sie nicht einfach bei jedem Laden / Laden implizit machen, wie bei x86.
Sein anderes Hauptargument ist, dass die Speicherordnung HARD ist und eine große Fehlerquelle darstellt. Es ist besser als jedes Software-Projekt, es richtig zu machen. (Dieses Argument funktioniert nur, weil es in Hardware ohne großen Leistungsaufwand möglich ist.)
Stellen Sie sich vor, Sie hätten folgenden Code:
%Vor%Eine mögliche Optimierung mit Memory Reorder ist
%Vor%Die Leistung ist besser, weil die Daten im Register angezeigt werden.
Beachten Sie, dass es viele verschiedene Optimierungsebenen gibt, aber Sie erhalten dadurch eine Vorstellung davon, warum eine Neuordnung die Leistung verbessern kann.
Auf einem modernen Prozessorchip kann der Prozessor typischerweise Register durchführen, um Operationen um eine Größenordnung (oder mehr) schneller als diejenige aus dem Hauptspeicher zu registrieren. Operationen, die die L1- oder L2-Caches betreffen, sind schneller als der Hauptspeicher, langsamer als das zu registrierende Register. Die andere Sache zu beachten ist, dass moderne Prozessoren-Chips in der Regel eine -Pipeline verwenden, die es ermöglicht, dass verschiedene Teile verschiedener Befehle gleichzeitig ausgeführt werden.
Vor diesem Hintergrund wird die Neuanordnung von Operationen in der Regel durchgeführt, um Situationen zu vermeiden, in denen die Pipeline (schnell) auf eine Operation im Hauptspeicher (langsam) warten muss:
Davides Beispiel zeigt eine Neuordnung, die Speicherlese- und schreibvorgänge vollständig vermeidet. (Zumindest ist das seine Absicht. In Wirklichkeit wird die Neuordnung auf der Ebene der nativen Befehle durchgeführt, nicht auf der Quellcode- oder Bytecodeebene.)
In anderen Fällen werden Sie möglicherweise feststellen, dass die Anweisungen für a = a + 1 und b = b + 1 verschachtelt werden. z.B.
In einer Pipeline-Architektur könnte dies die gleichzeitige Ausführung von 2) und 3), 4) und 5) zur gleichen Zeit usw. ermöglichen.
Schließlich ist zu beachten, dass ein moderner Prozessorchip / Befehlssatz das Lesen aus dem Hauptspeicher und das Schreiben in den Hauptspeicher so weit wie möglich vermeidet. Tatsächlich ist es üblich, dass ein Schreibbefehl in den L1- oder L2-Cache schreibt und das (langsame) Schreiben in den Hauptspeicher verzögert, bis die Cache-Zeile geleert ist. Dies führt zu einer anderen Art von "Speicheranomalie" ... wo ein separater Thread, der auf einem anderen Kern läuft, keine Speicheraktualisierungen sieht, weil die entsprechenden Schreibvorgänge (noch) nicht geleert wurden.
Das Java-Speichermodell soll es dem Compiler / Prozessor ermöglichen, die Leistung einer Multithread-Anwendung wie oben zu optimieren. Es macht deutlich, wenn ein Thread garantiert Speicheränderungen von einem anderen Thread sehen kann. Der Compiler / Prozessor darf in den Fällen, in denen keine Sichtbarkeitsgarantien bestehen, neu anordnen. Diese Neuordnung kann die Gesamtleistung erheblich verbessern.
Gehen Sie in ein Café und fragen Sie nach einem Drink und einem Sandwich. Die Person hinter dem Schalter gibt Ihnen das Sandwich (welches direkt neben ihm liegt) und geht dann zum Kühlschrank, um Ihr Getränk zu holen.
Ist es dir wichtig, dass er sie dir in der "falschen" Reihenfolge gegeben hat? Würdest du lieber den langsamen zuerst machen, nur weil du so den Befehl gegeben hast?
Nun, vielleicht ist es dir egal. Vielleicht möchtest du das nicht gegessene Sandwich in deinen leeren Trinkbecher füllen (du bezahlst für sie, also warum nicht, wenn du willst). Du bist frustriert darüber, dass du das Sandwich halten musst, während dein Getränk geholt wird - du hättest diese Zeit nutzen können, um dein Getränk zu trinken, und du würdest nicht mit Schluckauf enden, weil du es eilig hast!
Aber das passiert, wenn Sie ein paar Dinge bestellen, ohne die Reihenfolge anzugeben, in der sie passieren müssen. Der Server ist sich Ihrer ungewöhnlichen Sandwich-Cup-Füllung nicht bewusst, und so scheint es ihnen, als wäre die Reihenfolge egal.
Wir haben Konstrukte in natürlicher Sprache, um die Reihenfolge zu spezifizieren ("Bitte gib mir einen Drink, dann gib mir ein Sandwich") oder nicht ("Bitte gib mir einen Drink und ein Sandwich"). Wenn Sie nicht eher den ersteren als den letzteren verwenden, wird angenommen, dass Sie nur das Endergebnis wollen, und die verschiedenen Schritte können der Bequemlichkeit halber neu geordnet werden.
Wenn Sie im JMM nicht genau über die Reihenfolge der Operationen Bescheid wissen, wird davon ausgegangen, dass die Operationen neu geordnet werden können.
Tags und Links java optimization multithreading compiler-optimization cpu-architecture