Perché gli array multidimensionali in .NET sono più lenti dei normali array?

Modifica: Chiedo scusa a tutti. Ho usato il termine “array frastagliato” quando in realtà intendevo dire “array multidimensionale” (come si può vedere nel mio esempio qui sotto). Mi scuso per aver usato il nome sbagliato. In realtà ho trovato matrici frastagliate per essere più veloci di quelle multidimensionali! Ho aggiunto le mie misurazioni per gli array frastagliati.

Stavo cercando di usare a frastagliato array multidimensionale oggi, quando ho notato che le sue prestazioni non sono come mi sarei aspettato. L’utilizzo di una matrice monodesmensionale e il calcolo manuale degli indici erano molto più veloci (quasi due volte) rispetto all’utilizzo di un array 2D. Ho scritto un test usando array 1024*1024 (inizializzati su valori casuali), per 1000 iterazioni, e ho ottenuto i seguenti risultati sulla mia macchina:

 sum(double[], int): 2738 ms (100%) sum(double[,]): 5019 ms (183%) sum(double[][]): 2540 ms ( 93%) 

Questo è il mio codice di prova:

 public static double sum(double[] d, int l1) { // assuming the array is rectangular double sum = 0; int l2 = d.Length / l1; for (int i = 0; i < l1; ++i) for (int j = 0; j < l2; ++j) sum += d[i * l2 + j]; return sum; } public static double sum(double[,] d) { double sum = 0; int l1 = d.GetLength(0); int l2 = d.GetLength(1); for (int i = 0; i < l1; ++i) for (int j = 0; j < l2; ++j) sum += d[i, j]; return sum; } public static double sum(double[][] d) { double sum = 0; for (int i = 0; i < d.Length; ++i) for (int j = 0; j < d[i].Length; ++j) sum += d[i][j]; return sum; } public static void Main() { Random random = new Random(); const int l1 = 1024, l2 = 1024; double[ ] d1 = new double[l1 * l2]; double[,] d2 = new double[l1 , l2]; double[][] d3 = new double[l1][]; for (int i = 0; i < l1; ++i) { d3[i] = new double[l2]; for (int j = 0; j < l2; ++j) d3[i][j] = d2[i, j] = d1[i * l2 + j] = random.NextDouble(); } // const int iterations = 1000; TestTime(sum, d1, l1, iterations); TestTime(sum, d2, iterations); TestTime(sum, d3, iterations); } 

Ulteriori indagini hanno dimostrato che l’IL per il secondo metodo è maggiore del 23% rispetto a quello del primo metodo. (Dimensione del codice 68 vs 52.) Ciò è dovuto principalmente alle chiamate a System.Array::GetLength(int) . Il compilatore emette anche chiamate a Array::Get for the frastagliato array multidimensionale, mentre semplicemente chiama ldelem per la matrice semplice.

Quindi mi chiedo, perché l’accesso attraverso gli array multidimensionali è più lento dei normali array? Avrei pensato che il compilatore (o JIT) avrebbe fatto qualcosa di simile a quello che ho fatto nel mio primo metodo, ma in realtà non era così.

Potresti aiutarmi a capire perché questo sta accadendo così com’è?


Aggiornamento: seguendo il suggerimento di Henk Holterman, ecco l’implementazione di TestTime :

 public static void TestTime(Func action, T obj, int iterations) { Stopwatch stopwatch = Stopwatch.StartNew(); for (int i = 0; i < iterations; ++i) action(obj); Console.WriteLine(action.Method.Name + " took " + stopwatch.Elapsed); } public static void TestTime(Func action, T1 obj1, T2 obj2, int iterations) { Stopwatch stopwatch = Stopwatch.StartNew(); for (int i = 0; i < iterations; ++i) action(obj1, obj2); Console.WriteLine(action.Method.Name + " took " + stopwatch.Elapsed); } 

Le matrici monodesmensionali con un limite inferiore di 0 sono di tipo diverso rispetto alle matrici con limite inferiore o multidimensionale all’interno di IL ( vector vs array IIRC). vector è più semplice con cui lavorare – per arrivare all’elemento x, basta fare pointer + size * x . Per un array , devi fare pointer + size * (x-lower bound) per un array monodesmensionale, e ancora più aritmetica per ogni dimensione che aggiungi.

Fondamentalmente il CLR è ottimizzato per il caso molto più comune.

Controllo dei limiti delle matrici?

L’array a dimensione singola ha un membro di lunghezza a cui si accede direttamente. Quando compilato, si tratta solo di una lettura di memoria.

L’array multidimensionale richiede una chiamata al metodo GetLength (int dimensione) che elabora l’argomento per ottenere la lunghezza rilevante per quella dimensione. Ciò non si riduce a una lettura di memoria, quindi ottieni una chiamata al metodo, ecc.

Inoltre, GetLength (dimensione int) eseguirà un controllo dei limiti sul parametro.

È interessante notare che ho eseguito il seguente codice dall’alto utilizzando VS2008 NET3.5SP1 Win32 su una confezione Vista, e in release / optimize la differenza era appena misurabile, mentre il debug / noopt degli array multi-dim erano molto più lenti. (Ho eseguito i tre test due volte per ridurre gli effetti JIT sul secondo set.)

  Here are my numbers: sum took 00:00:04.3356535 sum took 00:00:04.1957663 sum took 00:00:04.5523050 sum took 00:00:04.0183060 sum took 00:00:04.1785843 sum took 00:00:04.4933085 

Guarda il secondo gruppo di tre numeri. La differenza non è abbastanza per me per codificare tutto in matrici a dimensione singola.

Anche se non li ho pubblicati, in Debug / non ottimizzato la multidimensiona contro single / jagged fa un’enorme differenza.

Programma completo:

 using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; namespace single_dimension_vs_multidimension { class Program { public static double sum(double[] d, int l1) { // assuming the array is rectangular double sum = 0; int l2 = d.Length / l1; for (int i = 0; i < l1; ++i) for (int j = 0; j < l2; ++j) sum += d[i * l2 + j]; return sum; } public static double sum(double[,] d) { double sum = 0; int l1 = d.GetLength(0); int l2 = d.GetLength(1); for (int i = 0; i < l1; ++i) for (int j = 0; j < l2; ++j) sum += d[i, j]; return sum; } public static double sum(double[][] d) { double sum = 0; for (int i = 0; i < d.Length; ++i) for (int j = 0; j < d[i].Length; ++j) sum += d[i][j]; return sum; } public static void TestTime(Func action, T obj, int iterations) { Stopwatch stopwatch = Stopwatch.StartNew(); for (int i = 0; i < iterations; ++i) action(obj); Console.WriteLine(action.Method.Name + " took " + stopwatch.Elapsed); } public static void TestTime(Func action, T1 obj1, T2 obj2, int iterations) { Stopwatch stopwatch = Stopwatch.StartNew(); for (int i = 0; i < iterations; ++i) action(obj1, obj2); Console.WriteLine(action.Method.Name + " took " + stopwatch.Elapsed); } public static void Main() { Random random = new Random(); const int l1 = 1024, l2 = 1024; double[ ] d1 = new double[l1 * l2]; double[,] d2 = new double[l1 , l2]; double[][] d3 = new double[l1][]; for (int i = 0; i < l1; ++i) { d3[i] = new double[l2]; for (int j = 0; j < l2; ++j) d3[i][j] = d2[i, j] = d1[i * l2 + j] = random.NextDouble(); } const int iterations = 1000; TestTime(sum, d1, l1, iterations); TestTime(sum, d2, iterations); TestTime(sum, d3, iterations); TestTime(sum, d1, l1, iterations); TestTime(sum, d2, iterations); TestTime(sum, d3, iterations); } } } 

Perché un array multidimensionale è solo uno zucchero sintattico in quanto è in realtà solo un array piatto con qualche magia di calcolo dell’indice. D’altra parte, una matrice seghettata è come una schiera di array. Con un array bidimensionale, l’accesso a un elemento richiede la lettura della memoria solo una volta, mentre con un array frastagliato a due livelli, è necessario leggere la memoria due volte.

EDIT: Apparentemente il poster originale mescolava “array frastagliati” con “array multidimensionali”, quindi il mio ragionamento non sta esattamente in piedi. Per la vera ragione, controlla la risposta di artiglieria pesante di Jon Skeet qui sopra.

Gli array frastagliati sono matrici di riferimenti di class (altri array) fino all’array di foglie che può essere una matrice di un tipo primitivo. Quindi la memoria allocata per ciascuno degli altri array può essere ovunque.

Mentre una matrice multidimensionale ha la sua memoria allocata in un grumo contiguo.

Penso che abbia qualcosa da fare per il fatto che gli array frastagliati sono in realtà array di array, quindi ci sono due livelli di riferimento per raggiungere i dati reali.

Sono con tutti gli altri qui

Avevo un programma con un array a tre dimensioni, lascia che ti dica che quando ho spostato l’array in due dimensioni, ho visto una spinta enorme e poi mi sono spostato su un array ad una dimensione.

Alla fine, penso di aver visto oltre il 500% di aumento delle prestazioni nei tempi di esecuzione.

unico inconveniente era la complessità aggiunta per scoprire dov’era l’array monodesmensionale, contro il tre.

Penso che il multidimensionale sia più lento, il runtime deve controllare due o più controlli (tridimensionali e superiori).

Controlla i limiti. La tua variabile “j” potrebbe superare l2, a condizione che “i” fosse inferiore a l1. Questo non sarebbe legale nel secondo esempio