2D Array vs Array von Arrays in engen Schleife Leistung C#

Question

Ich hatte einen Blick und konnte nichts ganz meine Frage zu beantworten.

Ich bin nicht gerade am besten bei der Erstellung von genauen 'echten' Tests, also bin ich mir nicht sicher, ob das das Problem ist. Im Grunde möchte ich ein paar einfache neuronale Netze erstellen, um etwas mit der Wirkung von Gridworld zu erstellen. Die Leistung dieser neuronalen Netzwerke wird kritisch sein, und ich möchte nicht, dass die versteckte Schicht so viel wie möglich ein Flaschenhals ist.

Ich würde lieber mehr Speicher verwenden und schneller sein, also habe ich mich dafür entschieden, Arrays anstelle von Listen zu verwenden (aufgrund von Listen, die eine zusätzliche Begrenzung über Arrays haben). Die Arrays sind nicht immer voll, aber da die if-Anweisung (prüfen Sie, ob das Element null ist) bis zum Ende gleich ist, kann sie vorhergesagt werden, und es gibt überhaupt keine Leistungseinbuße.

Meine Frage kommt davon, wie ich die Daten für das Netzwerk speichern verarbeitet. Ich dachte, aufgrund von 2D-Arrays, die alle Daten zusammen speichern, wäre es besser Cache-weise und würde schneller laufen. Aber von meinem Mock-up-Test, dass ein Array von Arrays in diesem Szenario viel besser schneidet.

Einige Code:

private void RunArrayOfArrayTest(float[][] testArray, Data[] data) 
    { 
     for (int i = 0; i < testArray.Length; i++) { 
      for (int j = 0; j < testArray[i].Length; j++) { 
       var inputTotal = data[i].bias; 

       for (int k = 0; k < data[i].weights.Length; k++) { 
        inputTotal += testArray[i][k]; 
       } 
      } 
     } 
    } 

    private void Run2DArrayTest(float[,] testArray, Data[] data, int maxI, int maxJ) 
    { 
     for (int i = 0; i < maxI; i++) { 
      for (int j = 0; j < maxJ; j++) { 
       var inputTotal = data[i].bias; 

       for (int k = 0; k < maxJ; k++) { 
        inputTotal += testArray[i, k]; 
       } 
      } 
     } 
    } 

Dies sind die beiden Funktionen, die zeitlich gesteuert werden. Jede 'Kreatur' hat ihr eigenes Netzwerk (die erste für die Schleife), jedes Netzwerk hat versteckte Knoten (die zweite für die Schleife) und ich muss die Summe der Gewichte für jede Eingabe finden (die dritte Schleife). In meinem Test habe ich es entfernt, so dass es nicht wirklich ist, was ich in meinem tatsächlichen Code mache, aber die gleiche Menge an Schleifen passiert (Die Datenvariable hätte ihr eigenes 2D-Array, aber ich wollte die Ergebnisse möglicherweise nicht verfälschen) . Daraus habe ich versucht ein Gefühl dafür zu bekommen, welches schneller ist und zu meiner Überraschung war das Array von Arrays.

-Code, um die Tests zu starten:

 // Array of Array test 
     Stopwatch timer = Stopwatch.StartNew(); 

     RunArrayOfArrayTest(arrayOfArrays, dataArrays); 

     timer.Stop(); 
     Console.WriteLine("Array of Arrays finished in: " + timer.ElapsedTicks); 

     // 2D Array test 
     timer = Stopwatch.StartNew(); 

     Run2DArrayTest(array2D, dataArrays, NumberOfNetworks, NumberOfInputNeurons); 

     timer.Stop(); 
     Console.WriteLine("2D Array finished in: " + timer.ElapsedTicks); 

nur zeigen wollte, wie ich es testete. Die Ergebnisse davon im Freigabemodus geben mir Werte wie:

Array of Arrays finished in: 8972 
2D Array finished in: 16376 

Kann mir jemand erklären, was ich falsch mache? Warum ist ein Array von Arrays in dieser Situation um so viel schneller? Ist kein 2D-Array alle zusammen gespeichert, was bedeutet, dass es mehr Cache-freundlich wäre?

Hinweis ich brauche wirklich, um schnell zu sein, da es Hunderttausende - Millionen von Zahlen pro Rahmen zusammenzufassen braucht, und wie ich sagte, ich will nicht, dass dies ein Problem sein wird. Ich weiß, dass dies in der Zukunft ziemlich einfach multi-threading sein kann, da jedes Netzwerk vollständig getrennt ist und sogar jeder Knoten vollständig getrennt ist.

Letzte Frage ich nehme an, wäre so etwas möglich auf der GPU statt laufen? Ich denke, eine GPU würde nicht darum kämpfen, viel größere Mengen von Netzwerken mit einer viel größeren Anzahl von Eingangs-/versteckten Neuronen zu haben.

Answer 1

in der CLR, gibt es zwei verschiedene Arten von Array:

• Vektoren, die die Basis null, eindimensionaler Arrays
• Arrays, die
Nicht-Null-Basen und mehr Dimensionen aufweisen kann

Ihr "Array von Arrays" ist ein "Vektor von Vektoren" in CLR-Termini.

Vektoren sind grundsätzlich wesentlich schneller als Arrays. Es ist möglich, dass Arrays in späteren CLR-Versionen weiter optimiert werden könnten, aber ich bezweifle, dass es die gleiche Menge Liebe wie Vektoren erhalten wird, da sie relativ selten verwendet werden. Es gibt nicht viel, was Sie tun können, um CLR-Arrays schneller zu machen. Wie du sagst, werden sie mehr Cachefreundlich sein, aber sie haben diese CLR-Strafe.

Sie können Ihre Array-of-Arrays Code bereits, jedoch verbessern, indem sie nur einmal die erste Indizierungsoperation pro Zeile:

private void RunArrayOfArrayTest(float[][] testArray, Data[] data) 
{ 
    for (int i = 0; i < testArray.Length; i++) { 

     // These don't change in the loop below, so extract them 
     var row = testArray[i];    
     var inputTotal = data[i].bias; 
     var weightLength = data[i].weights.Length; 
     for (int j = 0; j < row.Length; j++) { 
      for (int k = 0; k < weightLength; k++) { 
       inputTotal += row[k]; 
      } 
     } 
    } 
} 

Wenn Sie den Cache Freundlichkeit erhalten möchten und noch einen Vektor verwenden, Sie könnten ein einzelnesfloat[] haben und die Indizierung selbst durchführen ... aber ich würde wahrscheinlich mit dem array-of-arrays Ansatz beginnen.