¿En C, el acceso a mi índice de matriz es más rápido o el acceso por puntero es más rápido?

¿En C, el acceso a un índice de matriz es más rápido o el acceso por puntero es más rápido? Por más rápido quiero decir, cuál tomaría menos ciclo de reloj. La matriz no es una matriz constante.

templatetypedef lo ha resumido. Para añadir algún apoyo a su respuesta. Toma estas funciones de ejemplo:

 unsigned int fun1 (unsigned int * x)
 {
     unsigned int ra, rb;

     rb = 0;
     para (ra = 0; ra <1000; ra ++) rb + = * x ++;
     retorno (rb);
 }

 unsigned int fun2 (unsigned int * x)
 {
     unsigned int ra, rb;
     rb = 0;
     para (ra = 0; ra <1000; ra ++) rb + = x [ra];
     retorno (rb);
 }

Ahora gcc produjo esto:

 00000000 fun1:
    0: e52d4004 push {r4};  (str r4, [sp, # -4]!)
    4: e1a03000 mov r3, r0
    8: e2804efa agrega r4, r0, # 4000;  0xfa0
    c: e3a00000 mov r0, # 0
   10: e1a02003 mov r2, r3
   14: e492c004 ldr ip, [r2], # 4
   18: e5931004 ldr r1, [r3, # 4]
   1c: e2823004 agregue r3, r2, # 4
   20: e080000c agrega r0, r0, ip
   24: e1530004 cmp r3, r4
   28: e0800001 agrega r0, r0, r1
   2c: 1fffff7 bne 10 
   30: e49d4004 pop {r4};  (ldr r4, [sp], # 4)
   34: e12fff1e bx lr

 00000038 fun2:
   38: e3a03000 mov r3, # 0
   3c: e1a02003 mov r2, r3
   40: e790c003 ldr ip, [r0, r3]
   44: e2833004 agregar r3, r3, # 4
   48: e7901003 ldr r1, [r0, r3]
   4c: e2833004 agrega r3, r3, # 4
   50: e082200c agrega r2, r2, ip
   54: e3530efa cmp r3, # 4000;  0xfa0
   58: e0822001 agrega r2, r2, r1
   5c: 1fffff7 bne 40 
   60: e1a00002 mov r0, r2
   64: e12fff1e bx lr

El código es diferente, pero estoy sorprendido por las oportunidades perdidas de optimización.

Clang / llvm produjo esto:


 00000000 fun1:
    0: e3a01000 mov r1, # 0
    4: e3a02ffa mov r2, # 1000;  0x3e8
    8: e1a03001 mov r3, r1
    c: e2522001 subs r2, r2, # 1
   10: e490c004 ldr ip, [r0], # 4
   14: e08c3003 agrega r3, ip, r3
   18: e2c11000 sbc r1, r1, # 0
   1c: e182c001 orr ip, r2, r1
   20: e35c0000 cmp ip, # 0
   24: 1fffff8 bne c 
   28: e1a00003 mov r0, r3
   2c: e12fff1e bx lr

 00000030 fun2:
   30: e3a01000 mov r1, # 0
   34: e3a02ffa mov r2, # 1000;  0x3e8
   38: e1a03001 mov r3, r1
   3c: e2522001 subs r2, r2, # 1
   40: e490c004 ldr ip, [r0], # 4
   44: e08c3003 agrega r3, ip, r3
   48: e2c11000 sbc r1, r1, # 0
   4c: e182c001 orr ip, r2, r1
   50: e35c0000 cmp ip, # 0
   54: 1fffff8 bne 3c
   58: e1a00003 mov r0, r3
   5c: e12fff1e bx lr

Puede notar que el comstackdor produjo exactamente el mismo código, puntero o desplazamiento. Y al cambiar los comstackdores estaba mejor que cambiando la indexación de puntero contra matriz. Creo que llvm podría haberlo hecho un poco mejor, necesitaré estudiar esto un poco más para entender lo que hizo mi código para causar esto.

EDITAR:

Esperaba que el comstackdor usara como mínimo la instrucción ldr rd, [rs], # 4 que favorece los punteros, y esperaba que el comstackdor viera que podría destruir la dirección de la matriz, tratándola como un puntero en lugar de un desplazamiento en una matriz (y use la instrucción anterior, que es básicamente lo que hizo clang / llvm). O si hizo la matriz, usaría la instrucción ldr rd, [rm, rn]. Básicamente esperaba que uno de los comstackdores generara una de estas soluciones:


 funa:
     mov r1, # 0
     mov r2, # 1000
 funa_loop:
     ldr r3, [r0], # 4
     agrega r1, r1, r3
     subs r2, r2, # 1
     bne funa_loop
     mov r0, r1
     bx lr

 funb:
     mov r1, # 0
     mov r2, # 0
 funb_loop:
     ldr r3, [r0, r2]
     agrega r1, r1, r3
     agrega r2, r2, # 4
     cmp r2, # 0x4000
     bne funb_loop
     mov r0, r1
     bx lr

 func:
     mov r1, # 0
     mov r2, # 4000
     subs r2, r2, # 4
 func_loop:
     beq func_done
     ldr r3, [r0, r2]
     agrega r1, r1, r3
     subs r2, r2, # 4
     b func_loop
 func_done:
     mov r0, r1
     bx lr

No llegué, pero se me acercó bastante. Este fue un ejercicio divertido. Tenga en cuenta que lo anterior es todo el ensamblador ARM.

En general, (no es mi ejemplo de código C específico y no necesariamente un ARM), una serie de architectures populares que tendrá una carga de una dirección basada en registro (ldr r0, [r1]) y una carga con un índice / desplazamiento de registro (ldr r0, [r1, r2]) donde la dirección es la sum de los dos registros. idealmente, un registro es la dirección base de la matriz y el segundo el índice / desplazamiento. La primera carga del registro se presta a los punteros, la última a los arreglos. Si su progtwig C no va a cambiar o mover el puntero o el índice, en ambos casos eso significa una dirección estática que se calcula y luego se usa una carga normal, tanto la matriz como el puntero deben producir las mismas instrucciones. Para el caso más interesante de cambiar el puntero / índice.

 Puntero ldr r0, [r1] ... agregue r1, r1, algún número Índice de matriz ldr r0, [r1, r2] ... agregue r2, r2, algún número 

(Reemplace la carga con una tienda y agregue con un sub como sea necesario)

Algunas architectures no tienen una instrucción de índice de registro de tres registros, por lo que hay que hacer algo como:

 índice de matriz:
 mov r2, r1
 ...
 ldr r0, [r2]
 ...
 agrega r2, r2, algún número

O, dependiendo del comstackdor, puede volverse realmente malo, especialmente si comstack para depurar o sin optimizaciones, y suponiendo que no tiene un agregado de tres registros

 índice de matriz:
 mov r2, # 0
 ...
 mov r3, r1
 agrega r3, r2
 ldr r4, [r3]
 ...
 agrega r2, algún número

Entonces es bastante posible que los dos enfoques sean iguales. Como se ve en el ARM, puede combinar las dos instrucciones de puntero (dentro de los límites para el inmediato) en una, lo que hace que sea un poco más rápido. La solución de índice de matriz quema más registros y, dependiendo de la cantidad de registros disponibles para la architecture que lo empuja a tener que intercambiar registros en la stack antes y más a menudo (de lo que lo haría con los punteros), ralentizando aún más. Si no le importa destruir la dirección base, la conclusión es que la solución de puntero podría darle una ventaja desde una perspectiva de rendimiento. Tiene mucho que ver con tu código y el comstackdor. Para mí, la legibilidad entra en juego y siento que las matrices son más fáciles de leer y seguir, y segundo, necesito preservar ese puntero para liberar un malloc o pasar por esa memoria nuevamente, etc. Si es así, probablemente usaré una matriz con un índice, si es un pase de una sola vez y no me importa destruir la dirección base, usaré un puntero. Como se vio anteriormente con el código generado por el comstackdor, si el rendimiento es crítico, codifique manualmente la solución en el ensamblador de todos modos (según los enfoques sugeridos dejando que los comstackdores lo intenten primero).

Depende completamente del sistema, uno es más rápido, pero los dos son funcionalmente equivalentes entre sí y me sorprendería mucho si uno fuera más rápido. Es decir, el código.

myArr[index] 

Es completamente equivalente a

 *(&myArr[0] + index) 

Del mismo modo, escribiendo

 *ptr 

Es equivalente a escribir

 ptr[0] 

La mayoría de los comstackdores son lo suficientemente inteligentes como para resolver esto, así que me sorprendería si uno fuera más rápido que otro.

Sin embargo, lo más importante es que probablemente no debas preocuparte demasiado por esto. Preocúpate de las optimizaciones después de tener todo lo demás funcionando. Si encuentra que los accesos a la matriz realmente lo están matando, entonces considere encontrar una alternativa más rápida. De lo contrario, no te preocupes por eso; es infinitamente más valioso tener un código limpio, legible y mantenible que tener un código optimizado a menos que tenga una necesidad urgente de optimización.

Las operaciones de índice simples se comstackn con el mismo código de máquina en cada comstackdor que he tocado. Por índice se suele recomendar por legibilidad.

Los casos más complejos que involucran una lógica diferente para el acceso de puntero frente a la indexación de matrices deben examinarse caso por caso. Si tiene dudas, haga un perfil de su código, como siempre.

No hay una respuesta significativa a tu pregunta. Las operaciones de nivel de idioma no tienen una “velocidad” específica asociada a ellas. Por sí mismos, no pueden ser “más rápidos” o “más lentos”.

Solo las instrucciones de la CPU pueden ser más rápidas o más lentas y solo las instrucciones de la CPU pueden consumir ciclos de CPU. Para poder trasladar de alguna manera este concepto de “velocidad” de las instrucciones de la CPU a las operaciones a nivel de idioma [en general, estas instrucciones de la CPU se generaron] en caso de que necesite conocer el contexto. Esto es así porque la misma operación de nivel de idioma puede generar instrucciones de CPU totalmente diferentes en contextos diferentes (sin mencionar que también podría depender de la configuración del comstackdor, etc.)

En otras palabras, publicar el código real. Como una pregunta abstracta sin contexto, simplemente no tiene sentido.

En el nivel más bajo, estas operaciones tienden a comstackrse en la misma cosa. Si está realmente interesado, debería hacer que su comstackdor de C genere resultados de ensamblaje (como con gcc -S ) para que pueda verificar, especialmente porque depende, como mínimo, de:

  • su plataforma de destino.
  • tu comstackdor
  • Su nivel de optimización.

Descubrirá que, incluso si existiera una diferencia (lo cual es dudoso), el nivel de microoptimización no vale la pena el esfuerzo que le pone. Es mejor hacer macro-optimizaciones, como algoritmos mejorados, ya que es el tipo de cosa que ofrece más retorno de la inversión.

En este tipo de situaciones, donde es probable que el efecto sea mínimo, siempre optimizo para facilitar la lectura.

Eliminar explícitamente las subexpresiones comunes podría funcionar para usted. Puede haber una diferencia si está utilizando la architecture x86 o RISC y la calidad del optimizador.

Cuando escribo una rutina que tiene que correr a través de una matriz o estructura indexada, calculo un puntero a la base del miembro de la matriz / estructura y lo uso para direccionar. El caso basico

 struct SOMETHING list[100]; int find_something (...) { int i; i=0; while (i<(sizeof(list)/sizeof(struct SOMETHING))) { if (list[i].active && list[i].last_access+60 

se puede refinar a (es decir, ayudar al comstackdor a producir un mejor código):

 int find_something (...) { int i; struct SOMETHING *pList; i=0; while (i<(sizeof(list)/sizeof(struct SOMETHING))) { pList=&list[i]; if (pList->active && pList->last_access+60 

Esto es solo para ilustrar y la simplicidad del código probablemente generará el puntero de manera implícita, pero si la rutina es más compleja, podría no ser así. Utilizando "list [i]". como en el primer ejemplo, ejecutaría (en el x86) el riesgo (RISC haha) de que el comstackdor no tenga suficientes registros para generar y almacenar la dirección una vez, en lugar de generarla para cada referencia. Para el caso x86, se necesita una variable local para almacenar el puntero y pocos comstackdores crearán variables de stack a menos que se indique explícitamente. En RISC, el comstackdor tiene muchos registros a su disposición y, por lo general, decidirá que vale la pena crear (y mantener) el puntero una vez por cada iteración.

El bucle se puede refinar aún más:

  pList=list; i=0; while (i<(sizeof(list)/sizeof(struct SOMETHING))) { if (pList->active && pList->last_access+60 

Esta construcción carece de gastos generales de cálculo de dirección. "pList + = 1" (otros pueden preferir "++ pList") hace que se agregue un valor constante (igual al tamaño de una fila / miembro individual) a pList.

Y además:

  pList=list; pEndList=&list[sizeof(list)/sizeof(struct SOMETHING)]; while (pList!=pEndList) { if (pList->active && pList->last_access+60 

Lo que elimina el incremento del índice y lo reemplaza con una multiplicación fuera y una división dentro del bucle (ejecutada solo una vez, en la construcción de retorno).

Ahora, antes de que todos los optimizadores que hay por ahí comiencen a gritar un asesinato sangriento, mi punto es que las construcciones que son aceptables están determinadas por el tamaño y la complejidad de la función en la que residen. Probablemente no consideraría esta construcción en una función de 300 líneas que sea lo suficientemente compleja para comenzar, pero en una situación como la anterior. ¿Si las búsquedas son una parte importante del procesamiento general? Si las aceleraciones son lo suficientemente grandes?

¿Entonces por qué no? Pros y contras. Siempre es pros y contras. Haciendo lo mejor de ellos. Absolutos? Rara vez (si alguna vez).

Mismo. Es todo O (1), y la hora del reloj es despreciable. Básicamente estás accediendo a la dirección de memoria.

Al acceder a una matriz a través de un índice, en realidad está realizando dos operaciones: una adición (agregando el índice a la dirección de la matriz base), luego un acceso a la memoria (en realidad leyendo o escribiendo lo que está en la dirección resultante). Supongo que cuando se habla de “acceso por puntero” significa que ya tiene el puntero al elemento de destino. Entonces, lógicamente, el uso del puntero guarda la parte de “adición”, y por lo tanto debería ser más rápido, o al menos no más lento.

Sin embargo…

Como una aproximación aproximada, en una computadora moderna, el acceso a la memoria es mucho más costoso que una adición (especialmente si se cae de las caches), por lo que la diferencia, si la hay, será leve. En algunas architectures (por ejemplo, x86 o PowerPC), la adición y el acceso a la memoria se pueden combinar en un solo código de operación. Las cosas también serán diferentes, dependiendo de si la dirección de la matriz es una constante de tiempo de comstackción (es decir, la matriz no es de datos constantes, sino que se declara como una variable global, en comparación con un bloque obtenido con malloc() ). El uso de una matriz puede ayudar al comstackdor a encontrar un mejor código, con respecto a un puntero genérico (en particular cuando se usa la palabra clave restrict ). El contexto tiene una gran influencia (por ejemplo, ¿cuántos registros libres hay en ese momento?).

Asi que:

  • No hay una respuesta absoluta a tu pregunta. Tienes que intentar y tomar medidas.
  • Si hay una diferencia detectable (es probable que no haya ninguna), es difícil predecir en qué dirección, y depende de un gran conjunto de factores externos, incluidos la versión específica del comstackdor y los indicadores de optimización, la architecture del procesador y el modelo. diseño de memoria y así sucesivamente.
  • No podrá obtener una ganancia de optimización confiable sin tener un conocimiento más profundo del ensamblaje y un poco de teoría de la comstackción.
  • Primero debe concentrarse en hacer un código correcto , y luego solo preocuparse por la optimización; y no hay problema de rendimiento hasta que se haya medido debidamente en condiciones realistas.