Feldzugriff über Array ist langsamer für Typen mit mehreren Feldern

Question

Die folgende kurze aber vollständige Beispielprogramm

const long iterations = 1000000000; 

T[] array = new T[1 << 20]; 
for (int i = 0; i < array.Length; i++) 
{ 
    array[i] = new T(); 
} 

Stopwatch sw = Stopwatch.StartNew(); 
for (int i = 0; i < iterations; i++) 
{ 
    array[i % array.Length].Value0 = i; 
} 

Console.WriteLine("{0,-15} {1} {2:n0} iterations/s", 
    typeof(T).Name, sw.Elapsed, iterations * 1000d/sw.ElapsedMilliseconds); 

mit T durch folgende Typen ersetzt

class SimpleClass     struct SimpleStruct 
{         { 
    public int Value0;     public int Value0; 
}         } 

class ComplexClass     struct ComplexStruct 
{         { 
    public int Value0;     public int Value0; 
    public int Value1;     public int Value1; 
    public int Value2;     public int Value2; 
    public int Value3;     public int Value3; 
    public int Value4;     public int Value4; 
    public int Value5;     public int Value5; 
    public int Value6;     public int Value6; 
    public int Value7;     public int Value7; 
    public int Value8;     public int Value8; 
    public int Value9;     public int Value9; 
    public int Value10;     public int Value10; 
    public int Value11;     public int Value11; 
}         } 

folgende interessante Ergebnisse auf meiner Maschine ergibt (Windows 7 .NET 4.5 32-Bit)

 
SimpleClass  00:00:10.4471717 95,721,260 iterations/s 
ComplexClass  00:00:37.8199150 26,441,736 iterations/s 
SimpleStruct  00:00:12.3075100 81,254,571 iterations/s 
ComplexStruct 00:00:32.6140182 30,661,679 iterations/s 

Frage 1: Warum ist ComplexClass so viel langsamer als SimpleClass? Die verstrichene Zeit scheint linear mit der Anzahl der Felder in der Klasse zu steigen. Das Schreiben in das erste Feld einer Klasse mit vielen Feldern sollte nicht viel anders sein als das Schreiben in das erste Feld einer Klasse mit nur einem Feld, nein?

Frage 2: Warum ist ComplexStruct langsamer als SimpleStruct? Ein Blick auf den IL-Code zeigt, dass i direkt in das Array geschrieben wird, nicht in eine lokale Instanz von ComplexStruct, die dann in das Array kopiert wird. Es sollte also keinen Overhead geben, der durch das Kopieren weiterer Felder verursacht wird.

Bonusfrage: Warum ist ComplexStruct schneller als ComplexClass?

---

Edit: Aktualisiert Testergebnisse mit einem kleineren Array, T[] array = new T[1 << 8];:

 
SimpleClass  00:00:13.5091446 74,024,724 iterations/s 
ComplexClass  00:00:13.2505217 75,471,698 iterations/s 
SimpleStruct  00:00:14.8397693 67,389,986 iterations/s 
ComplexStruct 00:00:13.4821834 74,172,971 iterations/s 

So praktisch keinen Unterschied zwischen SimpleClass und ComplexClass, und nur ein kleiner Unterschied zwischen SimpleStruct und ComplexStruct. Die Leistung ist jedoch für SimpleClass und SimpleStruct deutlich gesunken.

---

Edit: Und jetzt mit T[] array = new T[1 << 16];:

 
SimpleClass  00:00:09.7477715 102,595,670 iterations/s 
ComplexClass  00:00:10.1279081 98,745,927 iterations/s 
SimpleStruct  00:00:12.1539631 82,284,210 iterations/s 
ComplexStruct 00:00:10.5914174 94,419,790 iterations/s 

Das Ergebnis für 1<<15 ist wie 1<<8 und das Ergebnis für 1<<17 ist wie 1<<20.

Answer 1

Mögliche Antwort auf Frage 1:

Ihre CPU liest Speicher in seinem Cache, eine Seite zu einem Zeitpunkt.

Mit dem größeren Datentyp können Sie weniger Objekte auf jede Cacheseite anpassen. Obwohl Sie nur einen 32-Bit-Wert schreiben, benötigen Sie die Seite immer noch im CPU-Cache. Mit den kleineren Objekten können Sie mehr Schleifen durchlaufen, bevor Sie als nächstes aus dem Hauptspeicher lesen müssen.

Answer 2

Ich habe keine Dokumentation, um es zu beweisen, aber ich nehme an, dass es eine Frage der Lokalität sein könnte. Da die komplexen Klassen in Bezug auf den Speicher breiter sind, würde es länger dauern, bis der Kernel auf entfernte Bereiche des Speichers, auf dem Heap oder auf dem Stapel, zugreift. Um objektiv zu sein, muss ich jedoch sagen, dass der Unterschied zwischen Ihren Maßnahmen wirklich hoch ist, weil das Problem das System ist.Über den Unterschied zwischen Klassen und Strukturen kann ich das auch nicht dokumentieren, aber vielleicht liegt es daran, dass der Stapel nach dem gleichen Prinzip wie im Cache häufiger zwischengespeichert wird als in Heap-Regionen, was zu weniger Cache-Misses führt.

Haben Sie das Programm mit aktiven Optimierungen ausgeführt?

EDIT: Ich habe einen kleinen Test auf ComplexStruct gemacht haben und verwendet, um die StructLayoutAttribute mit LayoutKind.Explicit als Parameter hinzugefügt dann eine FieldOffsetAttribute mit 0 als Parameter für jedes Feld der Struktur. Die Zeiten wurden erheblich verkürzt, und ich denke, sie waren ungefähr die gleichen wie die der . Ich habe es im Debug-Modus, Debugger eingeschaltet, keine Optimierungen. Während die Struktur ihre Felder beibehielt, wurde ihre Größe im Speicher verringert und so waren die Zeiten.

Answer 3

Antwort 1: ComplexClass ist langsamer als SimpleClass, da die Cache der CPU eine feste Größe so weniger ComplexClass Objekte im Cache passen zu einer Zeit ist. Grundsätzlich sehen Sie einen Anstieg aufgrund der Zeit, die zum Abrufen aus dem Speicher benötigt wird. Dies kann deutlicher sein (extream), wenn Sie in den Cache gehen und die Geschwindigkeit Ihres RAM reduzieren.

Antwort 2: Wie Answer1.

Bonus: Ein Array von Strukturen ist ein fortlaufender Block der Strukturen, auf den nur vom Array-Zeiger verwiesen wird. Ein Array von Klassen ist ein fortlaufender Block von Verweisen auf die Klasseninstanzen, auf die der Array-Zeiger verweist. Da Klassen auf dem Heap erstellt werden (grundsätzlich wo auch immer Platz ist), befinden sie sich nicht in einem kontinuierlichen und geordneten Block. Dies ist zwar ideal, um den Platz zu optimieren, ist jedoch schlecht für das CPU-Caching. Als Ergebnis gibt es bei der Iteration durch ein Array (in der Reihenfolge) mehr CPU-Cache-Misses mit einem großen Array von Zeigern auf große Klassen, dann gibt es eine In-Iteration eines Arrays von Strukturen.

Warum SimpleStruct ist langsamer als SimpleClass: Von dem, was ich dort zu verstehen, ist eine Menge von Overhead zu structs (irgendwo um 76 Bisse Ich habe gesagt). Ich bin nicht sicher, was ist oder warum es dort ist, aber ich erwarte, dass, wenn Sie den gleichen Test mit nativem Code (C++ kompiliert) ausführen würden, Sie sehen würden, dass das SimpleStruct Array besser funktioniert. Das ist nur eine Vermutung.

---

Wie auch immer, das sieht interessant aus. Ich werde es heute Abend ausprobieren. Ich werde meine Ergebnisse veröffentlichen. Ist es möglich, Ihren vollständigen Code zu erhalten?

Answer 4

Ich habe Ihren Benchmark ein wenig modifiziert, um den Modulus zu entfernen, der wahrscheinlich für einen großen Teil der Zeit verantwortlich ist, und Sie scheinen Feldzugriffszeiten zu vergleichen, nicht Int-Modularithmetik.

const long iterations = 1000; 
    GC.Collect(); 
    GC.WaitForPendingFinalizers(); 
    //long sMem = GC.GetTotalMemory(true); 
    ComplexStruct[] array = new ComplexStruct[1 << 20]; 
    for (int i = 0; i < array.Length; i++) { 
     array[i] = new ComplexStruct(); 
    } 
    //long eMem = GC.GetTotalMemory(true); 
    //Console.WriteLine("memDiff=" + (eMem - sMem)); 
    //Console.WriteLine("mem/elem=" + ((eMem - sMem)/array.Length)); 
    Stopwatch sw = Stopwatch.StartNew(); 
    for (int k = 0; k < iterations; k++) { 
     for (int i = 0; i < array.Length; i++) { 
      array[i].Value0 = i; 
     } 
    } 
    Console.WriteLine("{0,-15} {1} {2:n0} iterations/s", 
     typeof(ComplexStruct).Name, sw.Elapsed, (iterations * array.Length) * 1000d/sw.ElapsedMilliseconds); 

(ersetzt den Typ für jeden Test). Ich erhalte diese Ergebnisse (in Millionen inneren Schleife Zuweisungen/sec):

SimpleClass 357.1 
SimpleStruct 411.5 
ComplexClass 132.9 
ComplexStruct 159.1 

Diese Zahl näher an, was ich würde vs Struct Versionen bis Klasse erwartet. Ich denke, die langsameren Zeiten für die Complex-Versionen werden durch den CPU-Cache-Effekt größerer Objekte/Strukturen erklärt. Die Verwendung des auskommentierten Speichermesscodes zeigt, dass die Struct-Versionen weniger Gesamtspeicher verbrauchen. Ich fügte GC.Collect hinzu, nachdem ich festgestellt hatte, dass der Speichermesscode die relativen Zeiten von Struct vs. class Versionen beeinflusste.