Warum verbringt meine Anwendung 24% ihres Lebens damit, eine Nullprüfung durchzuführen?

Ich habe einen leistungskritischen binären Entscheidungsbaum und möchte diese Frage auf eine einzelne Codezeile konzentrieren. Der Code für den Binärbaum-Iterator ist unten mit den Ergebnissen der laufenden Leistungsanalyse aufgeführt.

        public ScTreeNode GetNodeForState(int rootIndex, float[] inputs)
        {
0.2%        ScTreeNode node = RootNodes[rootIndex].TreeNode;

24.6%       while (node.BranchData != null)
            {
0.2%            BranchNodeData b = node.BranchData;
0.5%            node = b.Child2;
12.8%           if (inputs[b.SplitInputIndex] <= b.SplitValue)
0.8%                node = b.Child1;
            }

0.4%        return node;
        }

BranchData ist ein Feld, keine Eigenschaft. Ich habe dies getan, um zu verhindern, dass das Risiko besteht, dass es nicht inline wird.

Die BranchNodeData-Klasse lautet wie folgt:

public sealed class BranchNodeData
{
    /// <summary>
    /// The index of the data item in the input array on which we need to split
    /// </summary>
    internal int SplitInputIndex = 0;

    /// <summary>
    /// The value that we should split on
    /// </summary>
    internal float SplitValue = 0;

    /// <summary>
    /// The nodes children
    /// </summary>
    internal ScTreeNode Child1;
    internal ScTreeNode Child2;
}

Wie Sie sehen können, ist die while-Schleife / Null-Prüfung ein massiver Leistungseinbruch. Der Baum ist massiv, daher würde ich erwarten, dass die Suche nach einem Blatt eine Weile dauert, aber ich würde gerne verstehen, wie viel Zeit unverhältnismäßig viel Zeit in dieser einen Zeile verbracht wird.

Ich habe es versucht:

• Trennen Sie den Null-Check von der Weile - es ist der Null-Check, der den Treffer darstellt.
• Das Hinzufügen eines booleschen Feldes zum Objekt und das Abgleichen davon machte keinen Unterschied. Es ist egal, was verglichen wird, es ist der Vergleich, der das Problem ist.

Ist dies ein Problem mit der Verzweigungsvorhersage? Wenn ja, was kann ich dagegen tun? Wenn überhaupt?

Ich werde nicht so tun , als würde ich die CIL verstehen , aber ich werde sie für jeden veröffentlichen, der dies tut, damit er versuchen kann, einige Informationen daraus herauszukratzen.

.method public hidebysig
instance class OptimalTreeSearch.ScTreeNode GetNodeForState (
    int32 rootIndex,
    float32[] inputs
) cil managed
{
    // Method begins at RVA 0x2dc8
    // Code size 67 (0x43)
    .maxstack 2
    .locals init (
        [0] class OptimalTreeSearch.ScTreeNode node,
        [1] class OptimalTreeSearch.BranchNodeData b
    )

    IL_0000: ldarg.0
    IL_0001: ldfld class [mscorlib]System.Collections.Generic.List`1<class OptimalTreeSearch.ScRootNode> OptimalTreeSearch.ScSearchTree::RootNodes
    IL_0006: ldarg.1
    IL_0007: callvirt instance !0 class [mscorlib]System.Collections.Generic.List`1<class OptimalTreeSearch.ScRootNode>::get_Item(int32)
    IL_000c: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.ScRootNode::TreeNode
    IL_0011: stloc.0
    IL_0012: br.s IL_0039
    // loop start (head: IL_0039)
        IL_0014: ldloc.0
        IL_0015: ldfld class OptimalTreeSearch.BranchNodeData OptimalTreeSearch.ScTreeNode::BranchData
        IL_001a: stloc.1
        IL_001b: ldloc.1
        IL_001c: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.BranchNodeData::Child2
        IL_0021: stloc.0
        IL_0022: ldarg.2
        IL_0023: ldloc.1
        IL_0024: ldfld int32 OptimalTreeSearch.BranchNodeData::SplitInputIndex
        IL_0029: ldelem.r4
        IL_002a: ldloc.1
        IL_002b: ldfld float32 OptimalTreeSearch.BranchNodeData::SplitValue
        IL_0030: bgt.un.s IL_0039

        IL_0032: ldloc.1
        IL_0033: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.BranchNodeData::Child1
        IL_0038: stloc.0

        IL_0039: ldloc.0
        IL_003a: ldfld class OptimalTreeSearch.BranchNodeData OptimalTreeSearch.ScTreeNode::BranchData
        IL_003f: brtrue.s IL_0014
    // end loop

    IL_0041: ldloc.0
    IL_0042: ret
} // end of method ScSearchTree::GetNodeForState

Bearbeiten: Ich habe mich für einen Verzweigungstest entschieden. Ich habe innerhalb der Zeit einen identischen hinzugefügt, also haben wir

while (node.BranchData != null)

und

if (node.BranchData != null)

darin. Ich habe dann eine Leistungsanalyse durchgeführt, und es dauerte sechsmal länger, um den ersten Vergleich auszuführen, als um den zweiten Vergleich auszuführen, der immer true zurückgab. Es sieht also so aus, als wäre es tatsächlich ein Problem mit der Branchenvorhersage - und ich vermute, ich kann nichts dagegen tun?!

Noch eine Bearbeitung

Das obige Ergebnis würde auch auftreten, wenn node.BranchData für die while-Prüfung aus dem RAM geladen werden müsste - es würde dann für die if-Anweisung zwischengespeichert.

Dies ist meine dritte Frage zu einem ähnlichen Thema. Dieses Mal konzentriere ich mich auf eine einzelne Codezeile. Meine anderen Fragen zu diesem Thema sind:

• Könnte ich dafür eine schnellere Datenstruktur als einen Baum verwenden?
• Mikrooptimierungen, die in C # durch einen Baum iterieren

Der Baum ist massiv

Das mit Abstand teuerste, was ein Prozessor jemals tut, ist, keine Anweisungen auszuführen, sondern auf den Speicher zuzugreifen. Der Ausführungskern einer modernen CPU ist um ein Vielfaches schneller als der Speicherbus. Ein Problem in Bezug auf die Entfernung : Je weiter sich ein elektrisches Signal bewegen muss, desto schwieriger wird es, dieses Signal an das andere Ende des Kabels zu liefern, ohne dass es beschädigt wird. Die einzige Lösung für dieses Problem besteht darin, es langsamer zu machen. Ein großes Problem mit den Leitungen, die die CPU in den RAM in Ihrem Computer verbinden, können Sie den Fall Pop und sehen Sie die Drähte.

Prozessoren haben eine Gegenmaßnahme für dieses Problem. Sie verwenden Caches , Puffer, die eine Kopie der Bytes im RAM speichern. Ein wichtiger ist der L1-Cache , normalerweise 16 Kilobyte für Daten und 16 Kilobyte für Anweisungen. Klein, damit es sich in der Nähe der Ausführungs-Engine befindet. Das Lesen von Bytes aus dem L1-Cache dauert normalerweise 2 oder 3 CPU-Zyklen. Als nächstes kommt der L2-Cache, größer und langsamer. Gehobene Prozessoren haben auch einen L3-Cache, der noch größer und langsamer ist. Wenn sich die Prozesstechnologie verbessert, benötigen diese Puffer weniger Platz und werden automatisch schneller, wenn sie sich dem Kern nähern. Dies ist ein wichtiger Grund, warum neuere Prozessoren besser sind und wie sie es schaffen, immer mehr Transistoren zu verwenden.

Diese Caches sind jedoch keine perfekte Lösung. Der Prozessor blockiert weiterhin einen Speicherzugriff, wenn die Daten in einem der Caches nicht verfügbar sind. Es kann nicht fortgesetzt werden, bis der sehr langsame Speicherbus die Daten geliefert hat. Der Verlust von fetten hundert CPU-Zyklen ist mit einem einzigen Befehl möglich.

Baumstrukturen sind ein Problem, sie sind nicht cachefreundlich. Ihre Knoten neigen dazu, über den Adressraum verstreut zu sein. Der schnellste Weg, auf den Speicher zuzugreifen, ist das Lesen von sequentiellen Adressen. Die Speichereinheit für den L1-Cache beträgt 64 Byte. Mit anderen Worten, sobald der Prozessor ein Byte liest , sind die nächsten 63 sehr schnell, da sie im Cache vorhanden sind.

Das macht ein Array bei weitem zur effizientesten Datenstruktur. Auch der Grund, dass die .NET List <> -Klasse überhaupt keine Liste ist, verwendet ein Array zum Speichern. Das Gleiche gilt für andere Auflistungstypen wie Dictionary, die strukturell nicht remote einem Array ähnlich sind, sondern intern mit Arrays implementiert werden.

Daher ist es sehr wahrscheinlich, dass Ihre while () -Anweisung unter CPU-Blockierungen leidet, da sie einen Zeiger für den Zugriff auf das BranchData-Feld dereferenziert. Die nächste Anweisung ist sehr billig, da die while () -Anweisung bereits das Abrufen des Werts aus dem Speicher schwer gemacht hat. Das Zuweisen der lokalen Variablen ist billig, ein Prozessor verwendet einen Puffer für Schreibvorgänge.

Es ist nicht einfach, ein anderes Problem zu lösen. Das Abflachen Ihres Baums in Arrays ist sehr wahrscheinlich unpraktisch. Nicht zuletzt, weil Sie normalerweise nicht vorhersagen können, in welcher Reihenfolge die Knoten des Baums besucht werden. Ein rot-schwarzer Baum könnte helfen, das geht aus der Frage nicht hervor. Eine einfache Schlussfolgerung ist, dass es bereits so schnell läuft, wie Sie es sich erhoffen können. Und wenn es schneller gehen soll, benötigen Sie bessere Hardware mit einem schnelleren Speicherbus. DDR4 wird dieses Jahr zum Mainstream.

Um Hans 'großartige Antwort zu Speicher-Cache-Effekten zu ergänzen, füge ich der physischen Speicherübersetzung und den NUMA-Effekten eine Diskussion über den virtuellen Speicher hinzu.

Bei einem virtuellen Speichercomputer (allen aktuellen Computern) muss bei einem Speicherzugriff jede virtuelle Speicheradresse in eine physische Speicheradresse übersetzt werden. Dies erfolgt durch die Speicherverwaltungshardware unter Verwendung einer Übersetzungstabelle. Diese Tabelle wird vom Betriebssystem für jeden Prozess verwaltet und selbst im RAM gespeichert. Für jede Seite des virtuellen Speichers gibt es einen Eintrag in dieser Übersetzungstabelle, der eine virtuelle Seite einer physischen Seite zuordnet . Erinnern Sie sich an Hans 'Diskussion über teure Speicherzugriffe: Wenn jede virtuelle zu physische Übersetzung eine Speichersuche erfordert, würde jeder Speicherzugriff doppelt so viel kosten. Die Lösung besteht darin, einen Cache für die Übersetzungstabelle zu haben, der als Translations-Lookaside-Puffer bezeichnet wird(Kurz TLB). TLB sind nicht groß (12 bis 4096 Einträge), und die typische Seitengröße in der x86-64-Architektur beträgt nur 4 KB, was bedeutet, dass höchstens 16 MB direkt mit TLB-Treffern zugänglich sind (es ist wahrscheinlich sogar weniger als das, der Sandy Brücke mit einer TLB-Größe von 512 Elementen ). Um die Anzahl der TLB-Fehler zu verringern, können Sie das Betriebssystem und die Anwendung zusammenarbeiten lassen, um eine größere Seitengröße wie 2 MB zu verwenden, was zu einem viel größeren Speicherplatz führt, auf den mit TLB-Treffern zugegriffen werden kann. Auf dieser Seite wird erläutert, wie Sie große Seiten mit Java verwenden, um den Speicherzugriff erheblich zu beschleunigen .

Wenn Ihr Computer über viele Sockets verfügt, handelt es sich wahrscheinlich um eine NUMA- Architektur. NUMA bedeutet ungleichmäßiger Speicherzugriff. In diesen Architekturen kosten einige Speicherzugriffe mehr als andere. Beispiel: Bei einem Computer mit 2 Sockeln und 32 GB RAM verfügt jeder Socket wahrscheinlich über 16 GB RAM. Auf diesem Beispielcomputer sind lokale Speicherzugriffe billiger als Zugriffe auf den Speicher eines anderen Sockets (der Fernzugriff ist 20 bis 100% langsamer, möglicherweise sogar länger). Wenn auf einem solchen Computer Ihr Baum 20 GB RAM verwendet, sich mindestens 4 GB Ihrer Daten auf dem anderen NUMA-Knoten befinden und wenn die Zugriffe für den Remotespeicher 50% langsamer sind, verlangsamen NUMA-Zugriffe Ihre Speicherzugriffe um 10%. Wenn Sie nur freien Speicher auf einem einzelnen NUMA-Knoten haben, wird allen Prozessen, die Speicher auf dem ausgehungerten Knoten benötigen, Speicher vom anderen Knoten zugewiesen, dessen Zugriffe teurer sind. Schlimmer noch, das Betriebssystem könnte denken, dass es eine gute Idee ist, einen Teil des Speichers des ausgehungerten Knotens auszutauschen.Dies würde noch teurere Speicherzugriffe verursachen . Dies wird ausführlicher unter Das MySQL-Problem „Swap Insanity“ und die Auswirkungen der NUMA-Architektur erläutert, in der einige Lösungen für Linux angegeben sind (Verteilen von Speicherzugriffen auf alle NUMA-Knoten, Beissen bei Remote-NUMA-Zugriffen, um einen Austausch zu vermeiden). Ich kann mir auch vorstellen, einem Socket mehr RAM zuzuweisen (24 und 8 GB statt 16 und 16 GB) und sicherzustellen, dass Ihr Programm auf dem größeren NUMA-Knoten geplant ist, aber dies erfordert physischen Zugriff auf den Computer und einen Schraubendreher ;-) .

Dies ist keine Antwort an sich, sondern eine Betonung dessen, was Hans Passant über Verzögerungen im Speichersystem schrieb.

Wirklich leistungsstarke Software - wie Computerspiele - wurde nicht nur zur Implementierung des Spiels selbst geschrieben, sondern auch so angepasst, dass Code- und Datenstrukturen das Beste aus den Cache- und Speichersystemen herausholen, dh sie als begrenzte Ressource behandeln. Wenn ich mich mit Cache-Problemen befasse, gehe ich normalerweise davon aus, dass der L1 in 3 Zyklen liefert, wenn die Daten dort vorhanden sind. Wenn dies nicht der Fall ist und ich zu L2 gehen muss, gehe ich von 10 Zyklen aus. Für L3 30 Zyklen und für RAM-Speicher 100.

Es gibt eine zusätzliche speicherbezogene Aktion, die - wenn Sie sie verwenden müssen - eine noch größere Strafe nach sich zieht, und das ist eine Bussperre. Bussperren werden als kritische Abschnitte bezeichnet, wenn Sie die Windows NT-Funktionalität verwenden. Wenn Sie eine selbst angebaute Sorte verwenden, können Sie sie als Spinlock bezeichnen. Unabhängig vom Namen wird es mit dem langsamsten Bus-Mastering-Gerät im System synchronisiert, bevor die Sperre aktiviert ist. Das langsamste Bus-Mastering-Gerät ist möglicherweise eine klassische 32-Bit-PCI-Karte, die mit 33 MHz verbunden ist. 33 MHz ist ein Hundertstel der Frequenz einer typischen x86-CPU (bei 3,3 GHz). Ich gehe davon aus, dass nicht weniger als 300 Zyklen erforderlich sind, um eine Bussperre abzuschließen, aber ich weiß, dass sie ein Vielfaches so lange dauern können. Wenn ich also 3000 Zyklen sehe, bin ich nicht überrascht.

Anfänger, die Multithreading-Software entwickeln, werden überall Bussperren verwenden und sich dann fragen, warum ihr Code langsam ist. Der Trick - wie bei allem, was mit Speicher zu tun hat - besteht darin, Zugriffe zu sparen.