5

Quisiera saber cual de los dos es mas eficiente en cuanto a tiempo de ejecución (no importa si consume mas recursos que otros). Dicha comparación es en base a lo siguiente:

Acceder de forma matriz[fila][columna];
Acceder de forma vector[totalcolumnas * fila + columna];

O si existe otro mejor método.

1 respuesta 1

6

Caso 1: acceso aleatorio

Vamos a comprobar qué sucede con un caso práctico sencillo:

int matrizPila[10][10];
int **matrizDinamica;
int vectorPila[100];
int* vectorDinamico;

int funcMatrizPila(int fila, int columna)
{
  return matrizPila[fila][columna];
}

int funcMatrizDinamica(int fila, int columna)
{
  return matrizDinamica[fila][columna];
}

int funcVectorPila(int fila, int columna)
{
  return vectorPila[fila*10+columna];
}

int funcVectorDinamico(int fila, int columna, int numColumnas)
{
  return vectorDinamico[fila*numColumnas+columna];
}

Las variables las he etiquetado como extern para evitar warnings al compilar.

Compilándo el código anterior con gcc 6.3 (es una compilación C++ aunque no creo que diste mucho de una compilación en C) el resultado es el siguiente:

funcMatrizPila(int, int):
    movsx   rdi, edi
    movsx   rsi, esi
    lea     rax, [rdi+rdi*4]
    lea     rax, [rsi+rax*2]
    mov     eax, DWORD PTR matrizPila[0+rax*4]
    ret
funcMatrizDinamica(int, int):
    mov     rax, QWORD PTR matrizDinamica[rip]
    movsx   rdi, edi
    movsx   rsi, esi
    mov     rax, QWORD PTR [rax+rdi*8]
    mov     eax, DWORD PTR [rax+rsi*4]
    ret
funcVectorPila(int, int):
    lea     eax, [rdi+rdi*4]
    lea     eax, [rsi+rax*2]
    cdqe
    mov     eax, DWORD PTR vectorPila[0+rax*4]
    ret
funcVectorDinamico(int, int, int):
    imul    edi, edx
    mov     rax, QWORD PTR vectorDinamico[rip]
    lea     edx, [rdi+rsi]
    movsx   rdx, edx
    mov     eax, DWORD PTR [rax+rdx*4]
    ret

Si analizamos el código resultante podemos sacar algunas conclusiones:

  • En el caso de matrizPila y vectorPila el resultado es prácticamente el mismo. Esto es porque en ambos casos la memoria es contigua y está organizada de la misma forma, luego la operación que permite obtener el valor de una celda es la misma.
  • En el caso de matrizDinamica el compilador tiene que resolver dos indirecciones para obtener el valor (uno para saltar a la fila que corresponda y otro para saltar a la columna para la fila dada). Esto se traduce en un rendimiento más pobre respecto a los dos casos anteriores.
  • En el caso de vectorDinamico, el compilador se ve obligado a realizar una indirección más respecto a vectorPila. Esto se traduce, como en el caso anterior, en un rendimiento inferior. Además ahora tiene que realizar un producto de forma manual (fila*numColumnas -> imul edi,edx), lo que supone una penalización importante.

Un detalle que no se ve en el ensamblador pero que también afecta es la localidad de los datos. Los ordenadores tienden a cachear la memoria para permitir un acceso rápido a los datos. Esto tiende a acelerar muchísimo las operaciones si los datos tienden a estar todos juntos. En el caso de matrizDinamica este punto no se cumple ya que cada fila se encontrará en una posición aleatoria de la memoria y esto obligará al sistema a repaginar la caché constantemente y esto se puede traducir fácilmente en una pérdida de rendimiento bastante perceptible.

Caso 2: acceso a posiciones conocidas en tiempo de compilación

int matrizPila[10][10];
int **matrizDinamica;
int vectorPila[100];
int* vectorDinamico;

int funcMatrizPila()
{
  return matrizPila[3][4];
}

int funcMatrizDinamica()
{
  return matrizDinamica[3][4];
}

int funcVectorPila()
{
  return vectorPila[3*10+4];
}

int funcVectorDinamico(int numColumnas)
{
  return vectorDinamico[3*numColumnas+4];
}

Para este código el ensamblador resultante es:

funcMatrizPila():
    mov     eax, DWORD PTR matrizPila[rip+136]
    ret
funcMatrizDinamica():
    mov     rax, QWORD PTR matrizDinamica[rip]
    mov     rax, QWORD PTR [rax+24]
    mov     eax, DWORD PTR [rax+16]
    ret
funcVectorPila():
    mov     eax, DWORD PTR vectorPila[rip+136]
    ret
funcVectorDinamico(int):
    lea     eax, [rdi+rdi*2]
    mov     rdx, QWORD PTR vectorDinamico[rip]
    cdqe
    mov     eax, DWORD PTR [rdx+16+rax*4]
    ret

En este caso observamos lo siguiente:

  • El acceso a matrizPila y a vectorPila es exactamente el mismo y el tiempo de ejecución tiende a 0. El compilador es capaz de precalcular el offset del salto, reduciendo la obtención del resultado a resolver una simple suma.
  • El acceso a matrizDinamica y vectorDinamico es más sencillo, lo que debería implicar un menor tiempo de ejecución. Quizás el mayor efecto se consigue en el caso de vectorDinamico, pero lo más costoso que es resolver las dos indirecciones las tiene que seguir realizando.

Vistas así las cosas la clasificación, en este caso, será muy similar a la del caso 1 pero con tiempos de ejecución más bajos.

Caso práctico:

Vamos a probar ahora todos los casos que hemos visto para ver como se comportan. Para ello podemos usar un código como el siguiente:

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

int matrizPila[10][10];
int **matrizDinamica;
int vectorPila[100];
int* vectorDinamico;

int funcMatrizPila(int fila, int columna)
{
  return matrizPila[fila][columna];
}

int funcMatrizDinamica(int fila, int columna)
{
  return matrizDinamica[fila][columna];
}

int funcVectorPila(int fila, int columna)
{
  return vectorPila[fila*10+columna];
}

int funcVectorDinamico(int fila, int columna, int numColumnas)
{
  return vectorDinamico[fila*numColumnas+columna];
}

int funcMatrizPilaFijo()
{
  return matrizPila[3][4];
}

int funcMatrizDinamicaFijo()
{
  return matrizDinamica[3][4];
}

int funcVectorPilaFijo()
{
  return vectorPila[3*10+4];
}

int funcVectorDinamicoFijo(int numColumnas)
{
  return vectorDinamico[3*numColumnas+4];
}

int res = 0;

#define BEGIN_TEST \
clock_t begin = clock(); \
for( int i=0; i<10000000; i++) \
  for( int j=0; j<100; j++)

#define END_TEST(nombre) \
clock_t end = clock(); \
double time_spent = (double)(end - begin) / CLOCKS_PER_SEC; \
printf("%-22s: %f\n",nombre,time_spent);

void testFunc0( const char* funcName, int(*func)())
{
  BEGIN_TEST

  res += func();

  END_TEST(funcName)
}

void testFunc1( const char* funcName, int(*func)(int), int var1)
{
  BEGIN_TEST

  res += func(var1);

  END_TEST(funcName)
}

void testFunc2( const char* funcName, int(*func)(int, int), int var1, int var2)
{
  BEGIN_TEST

  res += func(var1,var2);

  END_TEST(funcName)
}

void testFunc3( const char* funcName, int(*func)(int, int, int), int var1, int var2, int var3)
{
  BEGIN_TEST

  res += func(var1,var2,var3);

  END_TEST(funcName)
}

int main()
{
  matrizDinamica = (int**)malloc(10*sizeof(int*));
  for(int i=0; i<10; i++)
    matrizDinamica[i] = (int*)malloc(10*sizeof(int));

  vectorDinamico = (int*)malloc(100*sizeof(int));

  testFunc0( "funcMatrizPilaFijo",    funcMatrizPilaFijo);
  testFunc0( "funcVectorPilaFijo",    funcVectorPilaFijo);
  testFunc0( "funcMatrizDinamicaFijo",funcMatrizDinamicaFijo);
  testFunc1( "funcVectorDinamicoFijo",funcVectorDinamicoFijo,10);
  testFunc2( "funcMatrizPila",        funcMatrizPila,3,4);
  testFunc2( "funcVectorPila",        funcVectorPila,3,4);
  testFunc2( "funcMatrizDinamica",    funcMatrizDinamica,3,4);
  testFunc3( "funcVectorDinamico",    funcVectorDinamico,3,4,10);
}

En mi caso los resultados obtenidos son los siguientes:

funcMatrizPilaFijo    : 1.810000
funcVectorPilaFijo    : 1.800000
funcMatrizDinamicaFijo: 1.800000
funcVectorDinamicoFijo: 2.092000
funcMatrizPila        : 2.161000
funcVectorPila        : 2.190000
funcMatrizDinamica    : 2.321000
funcVectorDinamico    : 2.940000

Ahí vemos como efectivamente acceder a posiciones conocidas en tiempo de compilación supone una mejora de tiempo (en torno a un 10%-20%).

Un resultado que parece contradecir lo que he comentado es que los tiempos de acceso de vectorDinamico son peores que los obtenidos para matrizDinamica. Esto es así porque en este ejemplo tan sencillo la memoria de la matriz no solo tiene muchas posibilidades de acabar en posiciones consecutivas sino que además debido a su poco tamaño (400 bytes), no debería presentar demasiados problemas para la paginación de la caché. En entornos más complejos el resultado de matrizDinamica debería ser bastante peor.

2
  • 1
    No tengo palabras. Impecable. Peaso de respuesta, que decimos en mi tierra.
    – Trauma
    Commented el 12 ene. 2017 a las 17:40
  • @Trauma gracias :). Yo creo que tu respuesta es compatible con la mía, deberías plantearte el restaurarla
    – eferion
    Commented el 14 ene. 2017 a las 23:04

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.