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.