¿Por qué el orden de los bucles afecta el rendimiento cuando se itera sobre una matriz 2D?

9 minutos de lectura

avatar de usuario
Marca

A continuación hay dos programas que son casi idénticos excepto que cambié el i y j variables alrededor. Ambos se ejecutan en diferentes cantidades de tiempo. ¿Alguien podría explicar por qué sucede esto?

Versión 1

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (i = 0; i < 4000; i++) {
    for (j = 0; j < 4000; j++) {
      x[j][i] = i + j; }
  }
}

Versión 2

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (j = 0; j < 4000; j++) {
     for (i = 0; i < 4000; i++) {
       x[j][i] = i + j; }
   }
}

  • es.wikipedia.org/wiki/…

    – Brendan largo

    30 de marzo de 2012 a las 2:21

  • ¿Puede agregar algunos resultados de referencia?

    – nada101

    30 de marzo de 2012 a las 3:25

  • Relacionado: stackoverflow.com/questions/9888154/…

    – Thomas Padrón-McCarthy

    30 de marzo de 2012 a las 3:37


  • @ naught101 Los puntos de referencia mostrarán una diferencia de rendimiento de entre 3 y 10 veces. Esto es C/C++ básico, estoy completamente perplejo en cuanto a cómo obtuvo tantos votos…

    – TC1

    30 de marzo de 2012 a las 9:12

  • @TC1: No creo que sea tan básico; tal vez intermedio. Pero no debería sorprender que las cosas “básicas” tiendan a ser útiles para más personas, de ahí los muchos votos a favor. Además, esta es una pregunta difícil de buscar en Google, incluso si es “básica”.

    – LarsH

    30 de marzo de 2012 a las 18:50

avatar de usuario
Roberto Martín

Como han dicho otros, el problema es el almacenamiento en la ubicación de la memoria en la matriz: x[i][j]. Aquí hay una pequeña idea de por qué:

Tiene una matriz bidimensional, pero la memoria en la computadora es inherentemente unidimensional. Entonces, mientras imagina su matriz así:

0,0 | 0,1 | 0,2 | 0,3
----+-----+-----+----
1,0 | 1,1 | 1,2 | 1,3
----+-----+-----+----
2,0 | 2,1 | 2,2 | 2,3

Su computadora lo almacena en la memoria como una sola línea:

0,0 | 0,1 | 0,2 | 0,3 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,1 | 2,2 | 2,3

En el segundo ejemplo, accede a la matriz pasando primero por el segundo número, es decir:

x[0][0] 
        x[0][1]
                x[0][2]
                        x[0][3]
                                x[1][0] etc...

Lo que significa que los estás golpeando a todos en orden. Ahora mira la primera versión. Estás haciendo:

x[0][0]
                                x[1][0]
                                                                x[2][0]
        x[0][1]
                                        x[1][1] etc...

Debido a la forma en que C dispuso la matriz bidimensional en la memoria, le estás pidiendo que salte por todos lados. Pero ahora el truco: ¿Por qué importa esto? Todos los accesos a la memoria son iguales, ¿verdad?

No: por los cachés. Los datos de su memoria se transfieren a la CPU en pequeños fragmentos (llamados “líneas de caché”), generalmente de 64 bytes. Si tiene enteros de 4 bytes, eso significa que está obteniendo 16 enteros consecutivos en un paquete pequeño y ordenado. En realidad, es bastante lento recuperar estos fragmentos de memoria; su CPU puede hacer mucho trabajo en el tiempo que tarda en cargarse una sola línea de caché.

Ahora mire hacia atrás en el orden de los accesos: El segundo ejemplo es (1) tomar un trozo de 16 entradas, (2) modificarlas todas, (3) repetir 4000*4000/16 veces. Eso es bueno y rápido, y la CPU siempre tiene algo en lo que trabajar.

El primer ejemplo es (1) tomar un trozo de 16 entradas, (2) modificar solo una de ellas, (3) repetir 4000*4000 veces. Eso requerirá 16 veces el número de “obtenciones” de la memoria. Su CPU realmente tendrá que pasar tiempo sentado esperando que aparezca esa memoria, y mientras está sentado, está perdiendo un tiempo valioso.

Nota IMPORTANTE:

Ahora que tiene la respuesta, aquí hay una nota interesante: no hay una razón inherente por la que su segundo ejemplo tenga que ser el rápido. Por ejemplo, en Fortran, el primer ejemplo sería rápido y el segundo lento. Eso es porque en lugar de expandir las cosas en “filas” conceptuales como lo hace C, Fortran se expande en “columnas”, es decir:

0,0 | 1,0 | 2,0 | 0,1 | 1,1 | 2,1 | 0,2 | 1,2 | 2,2 | 0,3 | 1,3 | 2,3

El diseño de C se llama ‘fila principal’ y el de Fortran se llama ‘columna principal’. Como puede ver, es muy importante saber si su lenguaje de programación es de fila principal o de columna principal. Aquí hay un enlace para más información: http://en.wikipedia.org/wiki/Row-major_order

  • Tienes las versiones “primera” y “segunda” de forma incorrecta; el primer ejemplo varía el primero index en el bucle interno, y será el ejemplo de ejecución más lenta.

    – café

    30 de marzo de 2012 a las 5:39

  • Gran respuesta. Si Mark quiere leer más sobre estos detalles, le recomendaría un libro como Write Great Code.

    – 逆さま

    30 de marzo de 2012 a las 13:59

  • Puntos de bonificación por señalar que C cambió el orden de las filas de Fortran. Para la computación científica, el tamaño de la memoria caché L2 lo es todo porque si todas sus matrices caben en L2, entonces el cálculo se puede completar sin tener que ir a la memoria principal.

    –Michael Shopsin

    30 de marzo de 2012 a las 15:26

  • @birryree: El disponible gratuitamente Lo que todo programador debe saber sobre la memoria también es una buena lectura.

    – café

    30 de marzo de 2012 a las 22:38

  • Gran respuesta, pero en realidad imagino una matriz como 0,0 1,0 2,0 … ¿Por qué dirías 0,0 1,0 2,0?

    – Koray Tugay

    14/10/2013 a las 19:07

Nada que ver con el montaje. Esto es debido a fallas de caché.

Las matrices multidimensionales de C se almacenan con la última dimensión como la más rápida. Entonces, la primera versión perderá el caché en cada iteración, mientras que la segunda versión no. Entonces, la segunda versión debería ser sustancialmente más rápida.

Ver también: http://en.wikipedia.org/wiki/Loop_interchange.

La versión 2 se ejecutará mucho más rápido porque usa mejor el caché de su computadora que la versión 1. Si lo piensa bien, las matrices son solo áreas contiguas de memoria. Cuando solicita un elemento en una matriz, su sistema operativo probablemente traerá una página de memoria en el caché que contiene ese elemento. Sin embargo, dado que los siguientes elementos también están en esa página (porque son contiguos), ¡el próximo acceso ya estará en caché! Esto es lo que está haciendo la versión 2 para acelerar.

La versión 1, por otro lado, accede a los elementos en forma de columna y no en forma de fila. Este tipo de acceso no es contiguo a nivel de memoria, por lo que el programa no puede aprovechar tanto el almacenamiento en caché del sistema operativo.

  • Con estos tamaños de matriz, probablemente el administrador de caché en la CPU en lugar del sistema operativo sea el responsable aquí.

    – krlmlr

    30 de marzo de 2012 a las 8:59

El motivo es el acceso a datos locales de caché. En el segundo programa, está escaneando linealmente a través de la memoria, lo que se beneficia del almacenamiento en caché y la captación previa. El patrón de uso de memoria de su primer programa está mucho más disperso y, por lo tanto, tiene un peor comportamiento de caché.

avatar de usuario
pescador

Además de las otras excelentes respuestas sobre aciertos de caché, también existe una posible diferencia de optimización. Es probable que el compilador optimice su segundo ciclo en algo equivalente a:

for (j=0; j<4000; j++) {
  int *p = x[j];
  for (i=0; i<4000; i++) {
    *p++ = i+j;
  }
}

Esto es menos probable para el primer ciclo, porque necesitaría incrementar el puntero “p” con 4000 cada vez.

EDITAR: p++ e incluso *p++ = .. se puede compilar en una sola instrucción de CPU en la mayoría de las CPU. *p = ..; p += 4000 no puede, por lo que hay menos beneficio en optimizarlo. También es más difícil, porque el compilador necesita saber y usar el tamaño de la matriz interna. Y no ocurre tan a menudo en el ciclo interno en el código normal (ocurre solo para matrices multidimensionales, donde el último índice se mantiene constante en el ciclo y el penúltimo se escalona), por lo que la optimización es una prioridad menor. .

  • No entiendo qué significa ‘porque necesitaría saltar el puntero “p” con 4000 cada vez’.

    – Veedrac

    06/03/2016 a las 20:57


  • @Veedrac El puntero debería incrementarse con 4000 dentro del ciclo interno: p += 4000 Yo asi p++

    – pescador

    7 de marzo de 2016 a las 8:46


  • ¿Por qué el compilador encontraría eso como un problema? i ya está incrementado por un valor no unitario, dado que es un incremento de puntero.

    – Veedrac

    7 de marzo de 2016 a las 11:16

  • He agregado más explicación

    – pescador

    07/03/2016 a las 14:55

  • Intenta escribir int *f(int *p) { *p++ = 10; return p; } int *g(int *p) { *p = 10; p += 4000; return p; } en gcc.godbolt.org. Los dos parecen compilar básicamente lo mismo.

    – Veedrac

    7 de marzo de 2016 a las 17:13

avatar de usuario
Nicolás Modrzyk

Esta línea el culpable:

x[j][i]=i+j;

La segunda versión usa memoria continua, por lo que será sustancialmente más rápida.

probé con

x[50000][50000];

y el tiempo de ejecución es de 13 s para la versión 1 frente a 0,6 s para la versión 2.

  • No entiendo qué significa ‘porque necesitaría saltar el puntero “p” con 4000 cada vez’.

    – Veedrac

    06/03/2016 a las 20:57


  • @Veedrac El puntero debería incrementarse con 4000 dentro del ciclo interno: p += 4000 Yo asi p++

    – pescador

    7 de marzo de 2016 a las 8:46


  • ¿Por qué el compilador encontraría eso como un problema? i ya está incrementado por un valor no unitario, dado que es un incremento de puntero.

    – Veedrac

    7 de marzo de 2016 a las 11:16

  • He agregado más explicación

    – pescador

    07/03/2016 a las 14:55

  • Intenta escribir int *f(int *p) { *p++ = 10; return p; } int *g(int *p) { *p = 10; p += 4000; return p; } en gcc.godbolt.org. Los dos parecen compilar básicamente lo mismo.

    – Veedrac

    7 de marzo de 2016 a las 17:13

avatar de usuario
Sebastián Mach

Intento dar una respuesta genérica.

Porque i[y][x] es una abreviatura de *(i + y*array_width + x) en C (pruebe el elegante int P[3]; 0[P] = 0xBEEF;).

A medida que itera sobre yiteras sobre trozos de tamaño array_width * sizeof(array_element). Si tienes eso en tu bucle interno, entonces tendrás array_width * array_height iteraciones sobre esos fragmentos.

Al voltear el pedido, solo tendrá array_height iteraciones de fragmentos, y entre cualquier iteración de fragmentos, tendrá array_width iteraciones de solo sizeof(array_element).

Mientras que en las CPU x86 realmente antiguas esto no importaba mucho, los x86 de hoy en día realizan una gran cantidad de búsqueda previa y almacenamiento en caché de datos. Probablemente produzca muchos fallas de caché en su orden de iteración más lento.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad