Leistung von ADT-orientiertem Code mit einfacher Zuweisung auf modernen CPUs

Das Arbeiten mit unveränderlichen Daten mit einzelnen Zuweisungen hat den offensichtlichen Effekt, dass mehr Speicher benötigt wird, da Sie ständig neue Werte erstellen (obwohl Compiler unter der Decke Zeigertricks ausführen, um dies weniger problematisch zu machen).

Aber ich habe jetzt ein paar Mal gehört, dass die Performance-Verluste durch die Gewinne in der Art aufgewogen werden, wie die CPU (speziell ihr Speichercontroller) die Tatsache ausnutzen kann, dass der Speicher nicht (so sehr) mutiert.

Ich hatte gehofft, jemand könnte etwas Licht ins Dunkel bringen, wie das wahr ist (oder wenn es nicht so ist?).

In einem Kommentar zu einem anderen Beitrag wurde erwähnt, dass abstrakte Datentypen (ADTs) damit zu tun haben, was mich weiter neugierig machte, wie sich ADTs speziell auf die Art und Weise auswirken, wie die CPU mit Speicher umgeht. Dies ist jedoch eine Randbemerkung. Hauptsächlich interessiert mich, wie sich die Reinheit der Sprache notwendigerweise auf die Leistung der CPU und ihrer Caches usw. auswirkt.

Die CPU (speziell ihr Speichercontroller) kann die Tatsache ausnutzen, dass der Speicher nicht mutiert ist

Dies erspart dem Compiler die Verwendung von Membar- Anweisungen, wenn auf Daten zugegriffen wird.

Eine Speicherbarriere, die auch als Membar-, Speicherzaun- oder Zaunanweisung bezeichnet wird, ist eine Art von Sperranweisung, die eine Zentraleinheit (CPU) oder einen Compiler veranlasst, eine Ordnungsbeschränkung für Speicheroperationen durchzusetzen, die vor und nach der Sperranweisung ausgegeben werden. Dies bedeutet normalerweise, dass bestimmte Vorgänge garantiert vor der Barriere und andere nach der Barriere ausgeführt werden.

Speicherbarrieren sind erforderlich, da die meisten modernen CPUs Leistungsoptimierungen verwenden, die zu einer nicht ordnungsgemäßen Ausführung führen können. Diese Neuordnung von Speicheroperationen (Laden und Speichern) bleibt normalerweise innerhalb eines einzelnen Ausführungsthreads unbemerkt, kann jedoch zu unvorhersehbarem Verhalten bei gleichzeitigen Programmen und Gerätetreibern führen, sofern nicht sorgfältig gesteuert wird ...

Sie sehen, wenn auf Daten von verschiedenen Threads aus zugegriffen wird, geschieht dies auf einer Multi-Core-CPU wie folgt: Verschiedene Threads werden auf verschiedenen Kernen ausgeführt, wobei jeder seinen eigenen Cache (lokal zu ihrem Kern) verwendet - eine Kopie eines globalen Caches.

Wenn die Daten veränderlich sind und der Programmierer sie zwischen verschiedenen Threads konsistent haben muss, müssen Maßnahmen ergriffen werden, um die Konsistenz zu gewährleisten. Für Programmierer bedeutet dies, Synchronisationskonstrukte zu verwenden, wenn sie auf Daten in einem bestimmten Thread zugreifen (z. B. diese lesen).

Für den Compiler bedeutet das Synchronisationskonstrukt im Code, dass ein Membar-Befehl eingefügt werden muss, um sicherzustellen, dass Änderungen an der Kopie der Daten auf einem der Kerne ordnungsgemäß weitergegeben ("veröffentlicht") werden, um sicherzustellen, dass die Caches auf anderen Kernen gespeichert werden habe die gleiche (aktuelle) Kopie.

Etwas vereinfachend ^{siehe Hinweis unten} , hier ist, was bei Multi-Core-Prozessor für Membar passiert:

1. Alle Kerne stoppen die Verarbeitung , um ein versehentliches Schreiben in den Cache zu vermeiden.
2. Alle an lokalen Caches vorgenommenen Aktualisierungen werden in den globalen Cache zurückgeschrieben, um sicherzustellen, dass der globale Cache die neuesten Daten enthält. Dies dauert einige Zeit.
3. Aktualisierte Daten werden vom globalen Cache in lokale zurückgeschrieben, um sicherzustellen, dass die lokalen Caches die neuesten Daten enthalten. Dies dauert einige Zeit.
4. Alle Kerne werden wieder ausgeführt.

Sie sehen, alle Kerne tun nichts, während Daten zwischen globalen und lokalen Caches hin und her kopiert werden . Dies ist erforderlich, um sicherzustellen, dass veränderbare Daten ordnungsgemäß synchronisiert sind (threadsicher). Wenn 4 Kerne vorhanden sind, werden alle 4 angehalten und warten, während die Caches synchronisiert werden. Wenn es 8 gibt, stoppen alle 8. Wenn es 16 gibt ... nun, Sie haben 15 Kerne, die genau nichts tun, während Sie auf das warten, was an einem dieser Kerne erledigt werden muss.

Nun wollen wir sehen, was passiert, wenn Daten unveränderlich sind. Egal welcher Thread darauf zugreift, es ist garantiert derselbe. Für Programmierer bedeutet dies keine Notwendigkeit zum Einfügen von Synchronisationskonstrukten , wenn sie Zugriff (Lesen) von Daten in bestimmten Thread.

Für Compiler bedeutet dies wiederum keine Notwendigkeit , eine einfügen Membar Anweisung .

Infolgedessen muss der Zugriff auf Daten nicht die Prozessorkerne anhalten und warten, während Daten zwischen globalen und lokalen Caches hin und her geschrieben werden. Das ist ein Vorteil der Tatsache, dass der Speicher nicht mutiert ist .

Beachten Sie die etwas vereinfachende Erklärung oben, die einige kompliziertere negative Auswirkungen von Daten, die veränderlich sind, zum Beispiel auf das Pipelining, fallen lässt . Um die erforderliche Bestellung zu gewährleisten, muss die CPU von Datenänderungen betroffene Pilotlinien ungültig machen - das ist ein weiterer Leistungsnachteil. Wenn dies durch eine einfache (und damit zuverlässige) Ungültigmachung aller Pipelines implementiert wird, wird der negative Effekt weiter verstärkt.