¿Por qué esto mejora el rendimiento?

Question

Tengo dos bucles for que básicamente miran en dos matrices diferentes (cada una tiene un tamaño de alrededor de 2-4k en el pico) y establecen un valor en una tercera matriz en función de estos valores. Por algún extraño motivo, hay una diferencia de dos factores entre el rendimiento de esta pieza de código, según en qué orden puse los dos lazos.

Esta es la primera configuración. Se ejecuta en ~ 150 milisegundos en mi PC:

public static int[] SchoolMultiplication(int[] a, int[] b, int numberBase) 
{ 
    List<double> times = new List<double>(); 
    TimeTest timeTest = new TimeTest(); 

    int aLen = a.Length; 
    int bLen = b.Length; 

    int[,] resultMatrix = new int[a.Length + b.Length, aLen]; 
    int[] result = new int[a.Length + b.Length]; 

    timeTest.Start(); 

    for (int horizontalIndex = 0; horizontalIndex < b.Length; horizontalIndex++) 
    { 
     for (int verticalIndex = 0; verticalIndex < a.Length; verticalIndex++) 

     { 
      resultMatrix[a.Length + b.Length - 1 - verticalIndex - horizontalIndex, verticalIndex] = a[a.Length - verticalIndex - 1] * b[b.Length - horizontalIndex - 1]; 
     } 
    } 

Ahora si cambio de nada más que el orden de los bucles como esto

for (int verticalIndex = 0; verticalIndex < a.Length; verticalIndex++) 
{ 
    for (int horizontalIndex = 0; horizontalIndex < b.Length; horizontalIndex++) 
{ 
     resultMatrix[a.Length + b.Length - 1 - verticalIndex - horizontalIndex, verticalIndex] = a[a.Length - verticalIndex - 1] * b[b.Length - horizontalIndex - 1]; 
    } 
} 

El tiempo total de ejecución del método se reduce a unos ~ 400 milisegundos . ¿Cómo un simple intercambio de orden de bucles mejora el rendimiento en casi un 300%? Supongo que se trata de algún tipo de funcionamiento de almacenamiento en caché o puntero?

Answer 1

Es una cosa de arreglo de datos. Piense en la memoria como una matriz de una sola dimensión. Así es como las cosas están realmente organizadas en el disco (en lo que respecta a la computadora). Por lo tanto, cuando se crean matrices multidimensionales, cuando se cambia el orden de los bucles se cambia la forma en que se recorre la matriz. En lugar de leer en orden, estás saltando de posición en posición.

---

Una matriz multidimensional parece a esto:

Y como éste al ordenador. La forma óptima de desplazamiento tiene los índices siguientes en la flecha abajo:

modo que cuando cambie usted matriz bucle la matriz es atravesada así:

De este modo se obtiene más errores de caché y un algoritmo más pobre desempeño .

Answer 2

Es muy probable que esté relacionado con los aciertos/errores de la caché. La diferencia radica en el acceso secuencial frente al disperso que se encuentra en un tamaño superior al tamaño de una línea de caché.

Para bucles C++ simples, también ayudaría a hacer los bucles hacia atrás para obtener un poco de rendimiento en el bucle. No estoy seguro de cómo se ajusta para .NET.

Answer 3

Localidad, localidad, localidad de datos. De Wikipedia (que lo dice mejor que yo):

Estructuras de datos lineales: La localización a menudo ocurre porque el código contiene bucles que tienden a hacer referencia a matrices u otras estructuras de datos por índices. Localidad secuencial, un caso especial de localidad espacial, se produce cuando los elementos de datos relevantes se organizan y se accede linealmente. Por ejemplo, la simple travesía de elementos en una matriz unidimensional, desde la dirección base hasta el elemento más alto, explotaría la localidad secuencial de la matriz en la memoria. [2] La localidad equidistante más general ocurre cuando el recorrido lineal se realiza sobre un área más larga de estructuras de datos adyacentes que tienen estructura y tamaño idénticos, y además de esto, no todas las estructuras están en acceso, sino solo los mismos elementos mutuamente correspondientes de las estructuras. Este es el caso cuando una matriz se representa como una matriz secuencial de filas y el requisito es acceder a una sola columna de la matriz.

Answer 4

Recuerdo haber leído sobre esto en Code Complete.En la mayoría de los lenguajes, los arreglos se configuran con el último índice configurado secuencialmente, por lo que está accediendo a los bytes directamente en una fila cuando itera sobre el último índice, en lugar de omitir al iterar sobre el primero.

Answer 5

Su intuición es correcta, es un problema de almacenamiento en caché. La publicación de @Mike Daniels a la pregunta siguiente básicamente describe exactamente el mismo problema. El segundo bit de código obtendrá muchos más éxitos de caché.

Fastest way to loop through a 2d array?

Pero, shhhh No se supone que se preocupan por la derecha del rendimiento? :)

Answer 6

También creo que los tamaños relativos de las matrices a y b marcarían la diferencia.

Si a.length es grande y b.length es pequeño, la segunda opción debe ser más rápida. Por el contrario, si a.length es pequeño y b.length es grande, la primera opción sería más rápida. El problema es evitar el costo de configuración/desmontaje del ciclo interno.

Por cierto, ¿por qué tienes

int alen = a.length;

¿Pero luego también llama a.Length directamente? Parece que deberías elegir uno u otro.