matriz - punteros y vectores en c
Eficiencia: matrices versus punteros (13)
Se dice que el acceso a la memoria a través de punteros es más eficiente que el acceso a memoria a través de una matriz.
Eso pudo haber sido cierto en el pasado cuando los compiladores eran bestias relativamente estúpidas. Solo necesita ver algunos de los códigos emitidos por gcc en modos de alta optimización para saber que ya no son verdaderos. Parte de ese código es muy difícil de entender pero, una vez que lo haces, su brillo es evidente.
Un compilador decente generará el mismo código para los accesos a los punteros y los accesos a la matriz y probablemente no deberías preocuparte por ese nivel de rendimiento. Las personas que escriben compiladores saben mucho más sobre sus arquitecturas de destino que nosotros, simples mortales. Concéntrate más en el nivel macro cuando optimices tu código (selección de algoritmos, etc.) y confía en tus fabricantes de herramientas para hacer su trabajo.
De hecho, estoy sorprendido de que el compilador no haya optimizado todo
temp = a[0];
línea fuera de existencia ya que la temp se temp en la siguiente línea con un valor diferente y a no se marca de ninguna manera como volatile .
Recuerdo un mito urbano de hace mucho tiempo sobre un punto de referencia para el último compilador VAX Fortran (mostrando mi edad aquí) que superó a sus competidores en varios órdenes de magnitud.
Resulta que el compilador descubrió que el resultado del cálculo del punto de referencia no se usó en ninguna parte, por lo que optimizó todo el ciclo de cálculo en el olvido. De ahí la mejora sustancial en la velocidad de ejecución.
Actualización: la razón por la cual el código optimizado es más eficiente en su caso particular se debe a la forma en que usted encuentra la ubicación. a estará en una ubicación fija decidida en el tiempo de enlace / carga y la referencia a ella se arreglará al mismo tiempo. Entonces, a[0] o incluso a[any constant] estarán en una ubicación fija.
Y p también estará en una ubicación fija por la misma razón. Pero *p (el contenido de p ) es variable y, por lo tanto, tendrá una búsqueda adicional para encontrar la ubicación correcta de la memoria.
Probablemente encontrará que tener otra variable x establecida en 0 (no const ) y usar a[x] también introduciría cálculos adicionales.
En uno de sus comentarios, usted declara:
Hacer lo que sugirió dio como resultado 3 instrucciones para el acceso a la memoria a través de las matrices también (índice de búsqueda, valor de búsqueda del elemento de la matriz, almacenar en la temperatura). Pero aún no puedo ver la eficiencia. :-(
Mi respuesta a eso es que muy probablemente no verá una eficiencia en el uso de punteros. Los compiladores modernos están más que listos para descifrar que las operaciones de matriz y las operaciones de puntero se pueden convertir en el mismo código de máquina subyacente.
De hecho, sin la optimización activada, el código del puntero puede ser menos eficiente. Considere las siguientes traducciones:
int *pa, i, a[10];
for (i = 0; i < 10; i++)
a[i] = 100;
/*
movl $0, -16(%ebp) ; this is i, init to 0
L2:
cmpl $9, -16(%ebp) ; from 0 to 9
jg L3
movl -16(%ebp), %eax ; load i into register
movl $100, -72(%ebp,%eax,4) ; store 100 based on array/i
leal -16(%ebp), %eax ; get address of i
incl (%eax) ; increment
jmp L2 ; and loop
L3:
*/
for (pa = a; pa < a + 10; pa++)
*pa = 100;
/*
leal -72(%ebp), %eax
movl %eax, -12(%ebp) ; this is pa, init to &a[0]
L5:
leal -72(%ebp), %eax
addl $40, %eax
cmpl -12(%ebp), %eax ; is pa at &(a[10])
jbe L6 ; yes, stop
movl -12(%ebp), %eax ; get pa
movl $100, (%eax) ; store 100
leal -12(%ebp), %eax ; get pa
addl $4, (%eax) ; add 4 (sizeof int)
jmp L5 ; loop around
L6:
*/
A partir de ese ejemplo, puede ver que el ejemplo del puntero es más largo e innecesariamente . Carga pa en %eax varias veces sin que cambie y de hecho alterna %eax entre pa y &(a[10]) . La optimización predeterminada aquí es básicamente ninguna.
Cuando cambia al nivel de optimización 2, el código que obtiene es:
xorl %eax, %eax
L5:
movl $100, %edx
movl %edx, -56(%ebp,%eax,4)
incl %eax
cmpl $9, %eax
jle L5
para la versión de matriz, y:
leal -56(%ebp), %eax
leal -16(%ebp), %edx
jmp L14
L16:
movl $100, (%eax)
addl $4, %eax
L14:
cmpl %eax, %edx
ja L16
para la versión del puntero.
No voy a hacer un análisis sobre los ciclos de reloj aquí (ya que es demasiado trabajo y soy básicamente vago) pero señalaré una cosa. No hay una gran diferencia en el código para ambas versiones en términos de instrucciones del ensamblador y, dadas las velocidades con las que funcionan las CPU modernas, no notará una diferencia a menos que esté haciendo miles de millones de estas operaciones. Siempre tiendo a preferir escribir código para la legibilidad y solo preocuparme por el rendimiento si se convierte en un problema.
Como un aparte, esa declaración que hace referencia:
5.3 Punteros y matrices: la versión del puntero será, en general, más rápida, pero, al menos para los no iniciados, algo más difícil de comprender de inmediato.
se remonta a las primeras versiones de K & R, incluido el antiguo 1978 en el que todavía se escriben funciones:
getint(pn)
int *pn;
{
...
}
Los compiladores han recorrido un largo camino desde entonces.
Se dice que el acceso a la memoria a través de punteros es más eficiente que el acceso a memoria a través de una matriz. Estoy aprendiendo C y lo anterior se establece en K & R. Específicamente dicen
Cualquier operación que se puede lograr mediante la suscripción de matriz también se puede hacer con punteros. La versión del puntero será, en general, más rápida
Desensamblé el siguiente código usando C ++ visual. (Mine es un procesador 686. He desactivado todas las optimizaciones).
int a[10], *p = a, temp;
void foo()
{
temp = a[0];
temp = *p;
}
Para mi sorpresa, veo que el acceso a la memoria a través de un puntero lleva 3 instrucciones a las dos tomadas por el acceso a la memoria a través de una matriz. A continuación está el código correspondiente.
; 5 : temp = a[0];
mov eax, DWORD PTR _a
mov DWORD PTR _temp, eax
; 6 : temp = *p;
mov eax, DWORD PTR _p
mov ecx, DWORD PTR [eax]
mov DWORD PTR _temp, ecx
Por favor, ayúdame a entender. ¿¿Que me estoy perdiendo aqui??
Como lo señalaron muchas respuestas y comentarios, utilicé una constante de tiempo de compilación como índice de matriz, lo que hace que sea más fácil acceder a través de una matriz. A continuación se muestra el código de ensamblaje con una variable como índice. Ahora tengo el mismo número de instrucciones para acceder a través de punteros y matrices. Mis preguntas más amplias siguen siendo válidas. El acceso a la memoria a través de un puntero no se presta a sí mismo como más eficiente.
; 7 : temp = a[i];
mov eax, DWORD PTR _i
mov ecx, DWORD PTR _a[eax*4]
mov DWORD PTR _temp, ecx
; 8 :
; 9 :
; 10 : temp = *p;
mov eax, DWORD PTR _p
mov ecx, DWORD PTR [eax]
mov DWORD PTR _temp, ecx
Los punteros expresan naturalmente variables de inducción simples, mientras que los subíndices requieren intrínsecamente optimizaciones de compilador más sofisticadas
En muchos casos, el uso de una expresión con subíndice requiere que se agregue una capa adicional al problema. Un bucle que incrementa un subíndice se puede considerar como una máquina de estados, y la expresión a [i] técnicamente requiere, cada vez que se usa, multiplicarla por el tamaño de cada elemento y agregarla a la dirección base.
Para transformar ese patrón de acceso para usar punteros, el compilador debe analizar todo el ciclo y determinar, por ejemplo, a qué elemento se accede. Entonces el compilador puede reemplazar las múltiples instancias de multiplicar el subíndice por el tamaño del elemento con un simple incremento del valor del ciclo anterior. Este proceso combina optimizaciones llamadas eliminación de subexpresiones comunes y reducción de la fuerza de inducción .
Cuando se escriben con punteros, no es necesario todo el proceso de optimización porque el programador simplemente pasará por la matriz para comenzar.
Algunas veces el compilador puede hacer la optimización y otras no. Es más común en los últimos años tener a mano un compilador sofisticado, por lo que el código basado en punteros no siempre es más rápido .
Debido a que los arrrays generalmente deben ser contiguos, otra ventaja para los punteros es crear estructuras compuestas incrementalmente asignadas.
"La versión del puntero será, en general, más rápida" significa que en la mayoría de los casos es más fácil para el compilador generar un código más eficiente con un puntero (que solo necesita ser desreferenciado) que tener una matriz y un subíndice (lo que significa que el compilador necesita cambiar la dirección desde el inicio de la matriz). Sin embargo, con los procesadores modernos y los compiladores de optimización, el acceso a la matriz en el caso típico no es más lento que el acceso al puntero.
Específicamente en su caso, deberá activar la optimización para obtener el mismo resultado.
Como 0 se define como una constante, a [0] también es una constante, y el compilador sabe dónde está en tiempo de compilación. En el caso "normal", el compilador tendría que calcular la dirección del elemento a partir de una base + desplazamiento (con el desplazamiento siendo escalado de acuerdo con el tamaño del elemento).
OTOH, p es una variable, y la indirección requiere un movimiento adicional.
En general, el índice de matriz se maneja internamente como aritmética de puntero de todos modos, por lo que no estoy seguro de ver el punto que el K & R estaba tratando de hacer.
Como dijo paxdiablo, cualquier compilador nuevo los hará muy similares.
Aún más, vi situaciones en las que la matriz era más rápida que los punteros. Esto fue en un procesador DSP que usa operaciones vectoriales.
En este caso, el uso de matrices fue similar al uso de punteros restrictivos . Porque al usar dos matrices, el compilador -implicitamente- sabe que no apuntan a la misma ubicación. Pero si maneja el puntero 2, el compilador puede pensar que apuntan a la misma ubicación y saltará el revestimiento de la tubería.
por ejemplo:
int a[10],b[10],c[10];
int *pa=a, *pb=b, *pc=c;
int i;
// fill a and b.
fill_arrays(a,b);
// set c[i] = a[i]+b[i];
for (i = 0; i<10; i++)
{
c[i] = a[i] + b[i];
}
// set *pc++ = *pa++ + *pb++;
for (i = 0; i<10; i++)
{
*pc++ = *pa++ + *pb++;
}
En el caso 1, el compilador hará fácilmente un revestimiento de tuberías para agregar ayb y almacenar el valor en c.
En el caso 2, el compilador no tenderá una línea, porque podría estar sobrescribiendo aob mientras guarda en C.
Dado que la mayoría de la gente ya ha dado respuestas detalladas, daré un ejemplo intuitivo. Si usa una matriz y un puntero en una escala mayor, la eficiencia del uso del puntero será más significativa. Por ejemplo, si desea ordenar un conjunto de datos largos largos int clasificándolo en varios subconjuntos y luego combínalos.
long int * testData = calloc(N, sizeof(long int));
Para las máquinas de ram 8G diarias en 2017, podemos establecer N en 400000000, lo que significa que usará aproximadamente 1.5G de memoria para este conjunto de datos original. Y si está utilizando MPI , puede separar sus datos rápidamente mediante el uso de
MPI_Scatterv(testData, partitionLength, partitionIndex, MPI_LONG, MPI_IN_PLACE, N/number_of_thread, MPI_LONG, 0, MPI_COMM_WORLD);
Simplemente puede tratar paritionLength como un puntero que almacena N/number_of_thread como longitud para cada parte idéntica, y tratar partitionIndex como un puntero que almacena N / number_of_threads staring index de forma increamental. Supongamos que tiene una CPU de 4 núcleos y solo separa su trabajo en 4 subprocesos. MPI definitivamente hará el trabajo en un sentido rápido por las referencias. Pero si usa una matriz, esta rutina debe ejecutar una aritmética de puntero en la matriz para buscar primero el punto de partición. Que no es tan directo como el puntero. Además, cuando fusiona el conjunto de datos particionados, es posible que desee utilizar la K-way merge para acelerar. Necesita un espacio temporal para almacenar los cuatro conjuntos de datos clasificados. Aquí, si usa el puntero, solo necesita almacenar 4 direcciones. Sin embargo, si usa una matriz, almacenará 4 matrices secundarias completas, lo que no es eficiente. A veces, si no está utilizando MPI_Barrier para asegurarse de que su programa es seguro para subprocesos, MPI incluso podría quejarse de que su implementación de memoria es mala. Obtuve una máquina 32G para ordenar 400000000 valores largos en 8 hilos por método de matriz y puntero, obtuve 11.054980s y 13.182739s correspondientemente. Y si aumento el tamaño a 1000000000, mi programa de clasificación no se ejecutará con éxito si estoy usando una matriz. Es por eso que muchas personas usan punteros para todas las estructuras de datos excepto los escalares en C.
En el primer caso, el compilador conoce directamente la dirección de la matriz (que también es la dirección del primer elemento) y accede a ella. En el segundo caso, conoce la dirección del puntero y lee el valor del puntero, que apunta a esa ubicación de memoria. Eso es en realidad una indirección adicional, por lo que es presumiblemente más lento aquí.
Está obteniendo buenas respuestas a su pregunta aquí, pero como está aprendiendo, vale la pena señalar que las eficiencias a ese nivel rara vez se notan.
Cuando esté ajustando un programa para obtener el máximo rendimiento, debe prestar al menos la misma atención a la hora de encontrar y solucionar problemas más grandes en la estructura del programa. Después de que se hayan solucionado, las optimizaciones de bajo nivel pueden marcar una mayor diferencia.
Esta es una pregunta muy antigua y ha sido respondida, ¡como tal no necesito responder! Sin embargo, no noté una respuesta simple, así que estoy proporcionando una.
RESPUESTA: Un acceso indirecto (puntero / matriz) "podría" agregar una instrucción adicional para cargar la dirección (base), pero todos los accesos posteriores (elementos en el caso de matriz / miembros en caso de puntero a estructura) deberían ser solo una instrucción porque es una mera adición de un desplazamiento a la dirección (base) que ya está cargada. Por lo tanto, de alguna manera va a ser tan bueno como el acceso directo. Como tal, en la mayoría de los casos, el acceso a través de matriz / puntero es equivalente y los accesos a elementos también son tan buenos como el acceso directo a una variable.
Ex. si tengo una matriz (o puntero) con 10 elementos o una estructura con 10 miembros (a la que se accede mediante un puntero a la estructura), y estoy accediendo a un elemento / miembro, la única instrucción adicional posible solo se requiere una vez al comienzo. Todos los accesos al elemento / miembro deben ser solo una instrucción después de eso.
La velocidad se gana en bucles, sobre todo. Cuando use una matriz, usaría un contador que incrementará. Para calcular la posición, el sistema multiplica este contador por el tamaño del elemento de la matriz, luego agrega la dirección del primer elemento para obtener la dirección. Con los punteros, todo lo que necesita hacer para ir al siguiente elemento es aumentar el puntero actual con el tamaño del elemento para obtener el siguiente, suponiendo que todos los elementos están uno al lado del otro en la memoria.
La aritmética del puntero requiere cálculos un poco menores cuando se realizan bucles. Además, tener punteros al elemento correcto es más rápido que usar un índice dentro de una matriz.
Sin embargo, el desarrollo moderno se está deshaciendo lentamente de muchas operaciones de punteros. Los procesadores son cada vez más rápidos y las matrices son más fáciles de administrar que los punteros. Además, las matrices tienden a reducir la cantidad de errores en el código. Array permitirá verificaciones de índices, asegurándose de que no está accediendo a los datos fuera de la matriz.
Los punteros solían ser más rápidos que las matrices. Ciertamente, cuando se diseñó el lenguaje C, los punteros eran bastante más rápidos. Pero en la actualidad, los optimizadores generalmente pueden hacer un mejor trabajo optimizando las matrices que con los punteros porque las matrices son más restringidas.
Los conjuntos de instrucciones de los procesadores modernos también se han diseñado para ayudar a optimizar el acceso a la matriz.
Entonces, la conclusión es que las matrices suelen ser más rápidas estos días, especialmente cuando se usan en bucles con variables de índice.
Por supuesto, usted todavía querría usar punteros para cosas como listas vinculadas, pero la optimización anterior de caminar un puntero a través de una matriz en lugar de usar una variable de índice ahora es probable que sea una des-optimización.
Si está programando plataformas integradas, rápidamente aprenderá que el método del puntero es mucho más rápido que usar un índice.
struct bar a[10], *p;
void foo()
{
int i;
// slow loop
for (i = 0; i < 10; ++i)
printf( a[i].value);
// faster loop
for (p = a; p < &a[10]; ++p)
printf( p->value);
}
El ciclo lento tiene que calcular a + (i * sizeof (struct bar)) cada vez que pasa, mientras que el segundo solo tiene que agregar sizeof (struct bar) a p cada vez que pasa. La operación de multiplicar usa más ciclos de reloj que el agregado en muchos procesadores.
Realmente comienzas a ver mejoras si haces referencia a [i] varias veces dentro del ciclo. Algunos compiladores no almacenan en caché esa dirección, por lo que puede volver a calcularse varias veces dentro del ciclo.
Intente actualizar su muestra para usar una estructura y hacer referencia a múltiples elementos.
estoy un poco sorprendido acerca de la ptr más rápido que la discusión en matriz, donde la evidencia de que este no es el caso viene dada inicialmente por el código asm de Abhijith.
mov eax, dord ptr _a; // cargar directamente el valor de la dirección _a
vs
mov eax, dword ptr _p; // carga dirección / valor de p en eax
y
mov ecx, dword ptr [eax]; // use la dirección cargada para acceder al valor y ponerlo en ecx
Una matriz representa una dirección fija para que la CPU pueda acceder directamente a ella, ¡no así con la que necesita ser desreferenciada para que la CPU acceda al valor!
El segundo lote de código no es comareable, ya que la compensación de la matriz debe ser calificada, para hacer eso para el ptr también necesitaría al menos 1/2 instrucción más.
Cualquier cosa que un compilador pueda inferir durante el tiempo de compilación (direcciones fijas, desplazamientos, etc.) es clave para el código de rendimiento. Comparando código iterativo y asignando a vars:
Formación:
; 2791: tmp = buf_ai [l];
mov eax, DWORD PTR _l$[ebp]
mov ecx, DWORD PTR _buf_ai$[ebp+eax*4]
mov DWORD PTR _tmp$[ebp], ecx
vs
PTR
; 2796: tmp2 = * p;
mov eax, DWORD PTR _p$[ebp]
mov ecx, DWORD PTR [eax]
mov DWORD PTR _tmp2$[ebp], ecx
más
; 2801: ++ p;
mov eax, DWORD PTR _p$[ebp]
add eax, 4
mov DWORD PTR _p$[ebp], eax
¡Es simplemente para la dirección de carga de ptr primero que usarlo en comparación con la dirección de uso de Array y obtener valor simultáneamente!
atentamente