Indexer in C # unter der Haube: Indizierung besser als Dow Jones

Guten Tag. In diesem Artikel schlage ich vor, Indexer verschiedener Typen kennenzulernen. Sehen wir uns den Assembler-Sprachcode für diese Indexer und die Eigenschaften jedes Befehls in seiner Geschwindigkeit an. Ich werde auch einige offensichtliche Schlussfolgerungen ziehen. Aber was genau Sie in Ihrer speziellen Situation verwenden sollen, liegt bei Ihnen, ob Sie die Bequemlichkeit für die Geschwindigkeit opfern oder umgekehrt.

Metriken

Assembler-Code wird für 64-Bit-Systeme angegeben. Die folgenden Metriken wurden als Metriken für jeden Befehl ausgewählt: die Anzahl der zusammengeführten Mikrooperationen, die Gesamtzahl der Mikrooperationen, die Verzögerung, der Durchsatz und natürlich die Anzahl der Befehle. Ich habe für den Indexer keine Zahlen als Ganzes angegeben, weil Die Situation kann variieren, je nachdem, wie Sie mit dem indizierten Typ arbeiten und den Cache unterschiedlich beeinflussen.

Nachfolgend finden Sie eine kurze Zusammenfassung der Terminologie, ohne tiefer zu gehen, nur konzeptionelle Konzepte. Mein Ziel war es, alles so einfach wie möglich zu beschreiben, um ein gemeinsames Verständnis zu erreichen.

Mikrooperation (uop) ist eine bestimmte Operation, aus der jeder Befehl besteht. Das Konzept der Mikrooperationen wird für Optimierungen wie Zusammenführen, Zwischenspeichern und Neuordnen verwendet. So besteht der MOV-Befehl beispielsweise aus 1 Mikrooperation, während der XCHG-Befehl in zwei Registern aus 3 Mikrooperationen besteht (der Ansatz erfolgt über eine „temporäre Variable“, dh ein internes Register, danke leotsarev für die Aktualisierung), dem XCHG-Befehl über dem Register und Speicher besteht aus 8 Mikrooperationen.

Zusammengeführte Mikrooperationen (Fused Uops) - Wie oben erwähnt, ist das Zusammenführen von Mikrooperationen eine der Optimierungen. Es besteht darin, zwei Mikrooperationen durch eine komplexere zu ersetzen.

Die Latenz ist die Anzahl der Maßnahmen, nach denen die in dieser Anweisung verwendeten Daten für die Verwendung durch eine andere Anweisung verfügbar werden.

Durchsatz (reziproker Durchsatz) - Die Anzahl der Taktzyklen, die zum Ausführen eines Befehls erforderlich sind, vorausgesetzt, eine Folge identischer Befehle wird ausgeführt und sie arbeiten mit unabhängigen Daten.

Anhand dieser Indikatoren können Sie die Leistung eines bestimmten Befehlssatzes bewerten. Bitte beachten Sie, dass wir nur "bewerten" können. Die tatsächliche Leistung hängt von vielen Faktoren ab, wie z. B. Treffer- oder Fehler-Cache, Datenabhängigkeit usw.

Diese Zahlen gelten für die Intel-Prozessorarchitektur Skylake-X. Dies entspricht meinem Intel Core i7-6700 Prozessor.

Es ist auch zu beachten, dass Fastcall für 64-Bit-Systeme die Übertragung von nicht 2, sondern 4 Parametern in Registern (rcx, rdx, r8, r9) ermöglicht.

Indexer in Zahlen

1. Array-Indexer

Wir werden die folgenden Methoden als Beispiel betrachten:

public int IndexerArray(int index, int[] array) { return array[index]; } 

Betrachten Sie den Assembler-Sprachcode für dieses Snippet.

 1. cmp edx,dword ptr [r8+8] 2. jae 00007ff9`07288c78 3. movsxd rax,edx 4. mov eax,dword ptr [r8+rax*4+10h] 

Die erste Zeile prüft, ob der Index die Grenzen des Arrays überschreitet. Die zweite Zeile löst eine Ausnahme aus, wenn sie beendet wird. Als nächstes berechnen wir die Position des Elements im Array. Die ersten Felder im Array sind Dienstinformationen, daher müssen sie übersprungen werden (zusätzliche 10 Stunden = 16 Byte).

2. Favoritenliste <>

Tintencode:

 public int IndexerList(int index, List<int> list) { return list[index]; } 

Assembler-Code:

 1. cmp edx,dword ptr [r8+10h] 2. jae M00_L00 3. mov rax,qword ptr [r8+8] 4. cmp edx,dword ptr [rax+8] 5. jae 00007ff9`07268f56 6. movsxd rdx,edx 7. mov eax,dword ptr [rax+rdx*4+10h] ret M00_L00 call System.ThrowHelper.ThrowArgumentOutOfRange_IndexException() 

Hier gibt es deutlich mehr Anweisungen. Es ist deutlich zu sehen, dass der Blattindexer den Arrayindexer umschließt. Ein interessanter Punkt ist, dass zweimal überprüft wird, ob die Grenzen des Arrays überschritten werden. Die erste Anweisung prüft also, ob der Index die Grenzen des Blattes überschreitet. Wenn dies der Fall ist, springen wir (Befehl 2) zu einem sehr offensichtlichen Aufruf und lösen eine Ausnahme aus, wenn sie die Grenzen des Arrays überschreitet. Diese Rahmenprüfung verwendet das innere Feld des Blatts, das das zweite in der Reihenfolge ist (Versatz von 10h (16) Bytes vom Anfang des Typs, 8 zum Zeiger auf die Methodentabelle und 8 zum Link zum internen Array - dem ersten Feld). In der dritten Zeile geben wir die Adresse des internen Arrays in das Rax-Register ein - das erste Feld (analog ist ein Offset von 8 Bytes ein Zeiger auf die Methodentabelle). Darauf folgt der bereits bekannte Abschnitt - die Indexreferenz für das Array (Zeilen 4 - 7). Hier wird zur Überprüfung der Grenzen das interne Feld des Arrays verwendet.
Ich habe versucht, Dinge zu entfernen, die nicht direkt mit der Indizierung zusammenhängen, aber hier lohnt es sich, ret zu verlassen, damit es nicht so aussieht, als ob am Ende jedes Aufrufs des Blattelements eine Ausnahme auftritt: D.

Übrigens, um Sie nicht mit Spekulationen zu quälen, machen Sie sich bitte mit der Umsetzung des Blattes durch Bezugnahme vertraut. Das Typgießen auf vorzeichenlose Ints wird verwendet, um die Anzahl der Vergleiche zu verringern.

Als Ergebnis erhalten wir 7 Anweisungen für den erfolgreichen Zugriff auf den Index, 3 mehr als im Array.

Neu - Spanne <>

Disc:

 public int IndexerSpan(int index, Span<int> span) { return span[index]; } 

Und in Assemblersprache:

 1. cmp edx,dword ptr [r8+8] 2. jae 00007ff9`07278f69 3. mov rax,qword ptr [r8] 4. movsxd rdx,edx 5. mov eax,dword ptr [rax+rdx*4] 

Als die Spannweiten angekündigt wurden, versprachen sie uns, dass sie mit Unterstützung der Laufzeit mit Bedacht erstellt wurden. Und sie haben nicht gelogen, was sie sagen sollten. Tatsächlich unterscheidet es sich vom klassischen Array nur in einem Befehl, einem zusätzlichen Schritt des Zugriffs auf die Adresse. Nach diesem Code zu urteilen, ist die Adresse des Speicherorts innerhalb des Bereichs verborgen, in dem sich die Elemente befinden, die wir in Zeile 3 erhalten. Dies kann eine Adresse an eine bestimmte Stelle in einem Array, einer Zeile oder einem Speicherelement auf dem Stapel sein.
Klicken Sie hier, um zum Spaß eine Einführung in den Span-Indexer zu erhalten. Möglicherweise stellen Sie fest, dass es je nach Umgebungsvariable zwei verschiedene Implementierungen gibt. PROJECTN ist der Codename der ersten Version von .NET Native für UWP. Daher interessieren wir uns mehr für die zweite Version des Indexers. Sie ist mit [Intrinsic] gekennzeichnet . Wenn Sie sich außerdem die statische unsichere Klasse ansehen, die bei der Implementierung dieses Indexers verwendet wird, finden Sie Informationen darüber, dass die Implementierungen der meisten Methoden in dieser Datei als intrinsisch dargestellt werden .

Methodenaufrufe oder Verweise auf Felder, die mit dem Attribut [Intrinsic] gekennzeichnet sind, werden von der Laufzeit unterstützt.

In CoreCLR werden die Körper solcher Methoden durch EE (Execution Engine) durch unsicheren Code (unsicher) ersetzt. Wenn Sie weitere Details benötigen, können Sie mit der Methode getILIntrinsicImplementationForUnsafe mit dem Graben beginnen .

Informationen darüber, wie dies in CoreRT funktioniert (was mich ein wenig interessiert),
Sie können sich Internal.IL.Stubs.UnsafeIntrinsics ansehen .

Angesichts dieser Unterstützung durch raintime ist es sinnvoll, die Anweisungen in der Assembler-Sprache zu lesen, die wir gemacht haben, um zu verstehen, was genau hinter den Kulissen passieren wird.


Alle Indexer sind stark von Daten abhängig: Anweisungen verwenden die Ergebnisse der vorherigen. Hier gibt es keine ungewöhnlichen Ergebnisse, und das sollte es auch nicht geben. Aber jetzt ist der Overhead, der in diesem oder jenem Fall auftritt, klar. Einige offensichtliche Ergebnisse. Wenn der Algorithmus sehr häufige Zugriffe nach Index beinhaltet, ist es sinnvoll, das Blatt durch ein Array zu ersetzen. Wenn der Aufruf nicht sehr häufig ist, ist es möglicherweise bequemer, ein Blatt zu verwenden, das eine sehr praktische API bietet und keinen so großen Overhead hat (ich erinnere Sie daran, die Erweiterungen des internen Arrays zu überwachen).

Lassen Sie uns nun versuchen, die verschiedenen Möglichkeiten zu betrachten, mit denen wir ein zweidimensionales Array angeben können: ein Array von Arrays (gezacktes Array) und ein mehrdimensionales Array (mehrdimensionales Array).

4. Mehrdimensionales Array

Scharfer Code:

 public int IndexerDimensionalArray(int index1, int index2, int[,] demensionalArray) { return demensionalArray[index1, index2]; } 

Assemblersprache:

 1. mov eax,edx 2. sub eax,dword ptr [r9+18h] 3. cmp eax,dword ptr [r9+10h] 4. jae 00007ff9`00098fe6 5. mov edx,r8d 6. sub edx,dword ptr [r9+1Ch] 7. cmp edx,dword ptr [r9+14h] 8. jae 00007ff9`00098fe6 9. mov ecx,dword ptr [r9+14h] 10. imul rcx,rax 11. mov rax,rdx 12. add rax,rcx 13. mov eax,dword ptr [r9+rax*4+20h] 

Grundsätzlich ist alles verständlich - 2 prüft die Grenzen des Arrays, berechnet dann den Index und kehrt um. Dieses Array wird in einem Fragment gespeichert.

5. Array von Arrays (gezacktes Array)

 public int IndexerJaggedArray(int index, int index2, int[][] jaggedArray) { return jaggedArray[index][index2]; } 

Assembler:

 1. cmp edx,dword ptr [r9+8] 2. jae 00007ff9`00098f95 3. movsxd rax,edx 4. mov rax,qword ptr [r9+rax*8+10h] 5. cmp r8d,dword ptr [rax+8] 6. jae 00007ff9`00098f95 7. movsxd rdx,r8d 8. mov eax,dword ptr [rax+rdx*4+10h] 

Und das Interessanteste: Wir haben weniger Anweisungen als mit einem speziell für Mehrdimensionalität hergestellten Typ.


Aber zu den letzten beiden Beispielen rate ich Ihnen, nicht zu Schlussfolgerungen zu eilen. Aufgrund der Tatsache, dass ein zweidimensionales Array ein einzelner Typ ist, der einmal initialisiert wird, wird der Speicher für das gesamte Array in einem großen Fragment zugewiesen. Dies bietet einen besseren Cache, der die Situation grundlegend ändern kann. In einem Array von Arrays wird der Speicher für jedes Array separat zugewiesen, sodass es wahrscheinlich ist, dass die Arrays im Speicher zugewiesen und an den für sie am besten geeigneten Stellen eingegeben werden.

Für einige ist dieses Verhalten jedoch möglicherweise akzeptabler. Vielleicht ist in einigen Situationen bekannt, dass die Lebensdauer dieses Exemplars nur von kurzer Dauer ist. Und um nicht in eine Menge großer Objekte zu fallen (was für den Müllsammler eine Art zweite Generation ist), wo es eine Chance gibt, lange zu bleiben, viel mehr als wir möchten. Oder nach einiger Zeit möchten wir nur mit bestimmten Zeilen arbeiten, und alles andere kann gelöscht werden. Außerdem ist geplant, mit dem Typ zu arbeiten, indem auf zufällige inkonsistente Elemente verwiesen wird, wenn der Cache nicht normal funktionieren kann.

Wenn Sie ein Array von Arrays verwenden, ist es auch wahrscheinlicher, dass der Garbage Collector nicht zum Komprimieren provoziert wird, sondern dass es sich um einen Sweep handelt. Erinnerung: Beim Fragmentieren des Speichers kann die Gesamtmenge an freiem Speicherplatz für ein neues Objekt ausreichend sein, es gibt jedoch keinen durchgehenden freien Bereich mit der erforderlichen Menge. In diesem Fall wird eine Verdichtung durchgeführt - Objekte mit dem Ziel der Defragmentierung bewegen. Wenn wir in der Lage sind, eine kontinuierliche Strecke des freien Speichers für ein neues Objekt aufzunehmen, können wir das Objekt einfach in diesen freien Raum eingeben. Dies wird als Sweep bezeichnet.

Ich hoffe, diese Informationen helfen Ihnen, die richtigen Schlussfolgerungen zu ziehen und Ihre Meinung in der Diskussion über die Verwendung zu untermauern.