¿Por qué las matrices multidimensionales en .NET son más lentas que las matrices normales?

Editar: Pido disculpas a todos. Usé el término “array irregular” cuando en realidad quería decir “matriz multidimensional” (como se puede ver en mi ejemplo a continuación). Me disculpo por usar el nombre incorrecto. De hecho, ¡descubrí que las matrices irregulares son más rápidas que las multidimensionales! He agregado mis medidas para arreglos irregulares.

Estaba intentando usar un dentado matriz multidimensional hoy en día, cuando noté que su rendimiento no es el que esperaba. Usar una matriz unidimensional e índices de cálculo manual fue mucho más rápido (casi dos veces) que usar una matriz 2D. Escribí una prueba usando matrices 1024*1024 (inicializadas a valores aleatorios), para 1000 iteraciones, y obtuve los siguientes resultados en mi máquina:

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

Este es mi código de prueba:

 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); } 

La investigación adicional mostró que el IL para el segundo método es 23% más grande que el del primer método. (Código de tamaño 68 frente a 52.) Esto se debe principalmente a las llamadas a System.Array::GetLength(int) . El comstackdor también emite llamadas a Array::Get for the dentado matriz multidimensional, mientras que simplemente llama a ldelem para la matriz simple.

Entonces me pregunto, ¿por qué el acceso a través de matrices multidimensionales es más lento que las matrices normales? Hubiera supuesto que el comstackdor (o JIT) haría algo similar a lo que hice en mi primer método, pero este no fue el caso.

¿Podrías ayudarme a entender por qué está sucediendo de esta manera?


Actualización: siguiendo la sugerencia de Henk Holterman, aquí está la implementación de 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); } 

Las matrices unidimensionales con un límite inferior de 0 son un tipo diferente a las matrices de límite inferior multidimensional o no 0 dentro de IL ( vector frente a array IIRC). es más fácil trabajar con el vector : para llegar al elemento x, simplemente haz pointer + size * x . Para una array , debe hacer pointer + size * (x-lower bound) para una matriz dimensional única y aún más aritmética para cada dimensión que agregue.

Básicamente, el CLR está optimizado para el caso más común.

Array límites de comprobación?

La matriz de dimensión única tiene un miembro de longitud al que se accede directamente: cuando se comstack, esta es solo una lectura de memoria.

La matriz multidimensional requiere una llamada de método GetLength (dimensión int) que procesa el argumento para obtener la longitud relevante para esa dimensión. Eso no se comstack hasta una lectura de memoria, por lo que recibe una llamada de método, etc.

Además, GetLength (dimensión int) hará una verificación de límites en el parámetro.

Interesantemente, ejecuté el siguiente código desde arriba usando VS2008 NET3.5SP1 Win32 en una caja de Vista, y en la versión / optimizar la diferencia era apenas mensurable, mientras que la depuración / noopt las matrices multi-tenues eran mucho más lentas. (Ejecuté las tres pruebas dos veces para reducir los efectos de JIT en el segundo conjunto).

  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 

Mira el segundo conjunto de tres números. La diferencia no es suficiente para que yo codifique todo en matrices de una sola dimensión.

Aunque no los publiqué, en Debug / unoptimized la multidimensión frente a single / irregular hace una gran diferencia.

Progtwig 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); } } } 

Debido a que una matriz multidimensional es solo un azúcar sintáctico, ya que en realidad es solo una matriz plana con algo de magia de cálculo de índice. Por otro lado, una matriz dentada es como una matriz de matrices. Con una matriz bidimensional, acceder a un elemento requiere leer la memoria solo una vez, mientras que con una matriz dentada de dos niveles, debe leer la memoria dos veces.

EDITAR: Aparentemente, el cartel original mezcló “arreglos dentados” con “arreglos multidimensionales” por lo que mi razonamiento no se sostiene exactamente. Por la verdadera razón, consulte la respuesta de artillería pesada de Jon Skeet más arriba.

Las matrices dentadas son matrices de referencias de clase (otras matrices) hasta la matriz de hojas, que puede ser una matriz de tipo primitivo. Por lo tanto, la memoria asignada para cada una de las otras matrices puede estar por todas partes.

Mientras que una matriz multidimensional tiene su memoria asignada en una masa contigua.

Creo que tiene algo que ver con el hecho de que las matrices irregulares son en realidad matrices de matrices, por lo tanto, hay dos niveles de indirección para llegar a los datos reales.

Estoy con todos los demás aquí

Tenía un progtwig con matriz de tres dimensiones, déjenme decirles que cuando moví la matriz en dos dimensiones, vi un gran impulso y luego me moví a una matriz de una dimensión.

Al final, creo que vi un aumento de rendimiento de más del 500% en el tiempo de ejecución.

El único inconveniente fue la complejidad añadida para descubrir dónde estaba qué en el conjunto de una dimensión, frente a los tres.

Creo que multidimensional es más lento, el tiempo de ejecución tiene que comprobar dos o más (tres dimensiones y arriba) verificación de límites.

Límites de comprobación. Su variable “j” podría exceder 12 siempre que “i” fuera menor que l1. Esto no sería legal en el segundo ejemplo