*(p + i) vs p[i]

Archivado
Yo siempre he accedido a arrays en C usando *(p + i) en lugar de p[i]. Supongo que leí hace un montón de años algo sobre el tema y se me quedó grabado en la cabeza. Hace poco un colega me preguntó que por qué lo hacía al ver mi código lleno de paréntesis y asteriscos XD y no supe qué responderle.
Me puse a buscar por internet acerca de optimización en C y sólo encontré una referencia, que dice que hay que hacer justo lo contrario a lo que yo hago: usar p[i] en lugar de *(p + i), para facilitar la tarea de optimización al compilador (los punteros están menos restringidos). Así que modifiqué el código que ya tenía (bendito replace regexp) e hice algunas pruebas... y obtengo que mi código original, usando *(p + i), es un 10% más rápido que usando p[i] (ambos con CXXFLAGS="-O3 -ffast-math -funroll-loops").

Así que... ¿cuál es la respuesta correcta? ¿O es uno de esos casos en los que depende del código y no hay respuesta clara?

Saludos :).
"Creo", que el precompilador lo que hace es p[i] -> *(p+i), asique teoricamente no deberia haber diferencias o_O
A ver si algun guru de la programación en C nos aclara... x)
Salu2!
e-Minguez escribió:"Creo", que el precompilador lo que hace es p[i] -> *(p+i), asique teoricamente no deberia haber diferencias o_O

Yo por lo que he leído, esa la idea que tenía, pero tampoco soy un experto ni mucho menos.

Un saludo.
e-Minguez escribió:"Creo", que el precompilador lo que hace es p[i] -> *(p+i), asique teoricamente no deberia haber diferencias o_O
A ver si algun guru de la programación en C nos aclara... x)
Salu2!


Nop, no lo hace. Estas son las diferencias entre los dos códigos:

$ diff detectSphere.cc detectSphere2.cc
49,51c49,51
<   for (int i=0;i<uMLE.numel();i++) *(uMLEC + i)=uMLE(i);
<   for (int i=0;i<u.numel();i++) *(uC + i)=u(i);
<   for (int i=0;i<constell.numel();i++) *(constellC + i)=constell(i);
---
>   for (int i=0;i<uMLE.numel();i++) uMLEC[i]=uMLE(i);
>   for (int i=0;i<u.numel();i++) uC[i]=u(i);
>   for (int i=0;i<constell.numel();i++) constellC[i]=constell(i);
64,65c64,65
<   for (int i=0;i<distances.numel();i++) distances(i)=*(distancesD + i);
<   for (int i=0;i<symbols.numel();i++) symbols(i)=*(symbolsD + i);
---
>   for (int i=0;i<distances.numel();i++) distances(i)=distancesD[i];
>   for (int i=0;i<symbols.numel();i++) symbols(i)=symbolsD[i];
98c98
<             *(distancesD + distancesInd + j) = INFINITY;
---
>             distancesD[distancesInd + j] = INFINITY;
122c122
<       sumatC += *(uC + uInd + j) * *(diffCandC + j);
---
>       sumatC += uC[uInd + j] * diffCandC[j];
127,129c127,129
<       *(diffCandC + antenna) = *(constellC + i) - *(uMLEC + uMLEInd + antenna);
<       double uii = (*(uC + uInd + antenna)).real();
<       Complex resultC = *(diffCandC + antenna) + sumatC / uii;
---
>       diffCandC[antenna] = constellC[i] - uMLEC[uMLEInd + antenna];
>       double uii = (uC[uInd + antenna]).real();
>       Complex resultC = diffCandC[antenna] + sumatC / uii;
133c133
<         *(candidateVector + antenna) = i;
---
>         candidateVector[antenna] = i;
141c141
<             double worstDistance = *(distancesD + distancesInd);
---
>             double worstDistance = distancesD[distancesInd];
145c145
<                 if (*(distancesD + distancesInd + j) > worstDistance)
---
>                 if (distancesD[distancesInd + j] > worstDistance)
147c147
<                     worstDistance = *(distancesD + distancesInd + j);
---
>                     worstDistance = distancesD[distancesInd + j];
154c154
<                 *(distancesD + distancesInd + worstCand) = distance;
---
>                 distancesD[distancesInd + worstCand] = distance;
157c157
<                     *(symbolsD + symbolsInd + j) = *(candidateVector + j);
---
>                     symbolsD[symbolsInd + j] = candidateVector[j];


Es decir, sólo punteros por arrays. Y en cambio:

franjva@tay64 ~/octave/detection $ rm *.o
franjva@tay64 ~/octave/detection $ rm *.oct
franjva@tay64 ~/octave/detection $ CXXFLAGS="-O0" mkoctfile detectSphere.cc
franjva@tay64 ~/octave/detection $ CXXFLAGS="-O0" mkoctfile detectSphere2.cc
franjva@tay64 ~/octave/detection $ cmp detectSphere.o detectSphere2.o
detectSphere.o detectSphere2.o differ: byte 41, line 1


Es decir, ni siquiera desactivando las optimizaciones resulta el mismo código. El resultado sí es el mismo, pero con los punteros es más rápido.
Yo también creía que a[i] -> *(a+i). De hecho en compiladores antiguos, esto es 'válido':

int 5["array"];


Ya que la conversión era 'ciega'. Ahora GCC llora si lo intentas :)

Mis pruebas dicen que es lo mismo; veamos:

[ $ ~/prueba-punteros ] cat arrays.c
#include <stdio.h>

int main (int argc, char **argv)
{
   int arr[10];
   int i;

   for ( i = 0 ; i < 10 ; i++ )
      arr[i] = i;

   for ( i = 0 ; i < 10 ; i++ )
      printf("%d\n",arr[i]);

   return 0;
}
[ $ ~/prueba-punteros ] cat punteros.c
#include <stdio.h>

int main (int argc, char **argv)
{
   int arr[10];
   int i;

   for ( i = 0 ; i < 10 ; i++ )
      *(arr+i) = i;

   for ( i = 0 ; i < 10 ; i++ )
      printf("%d\n",*(arr+i));

   return 0;
}
[ $ ~/prueba-punteros ] for i in *.c ; do gcc -S -o ${i/.c/.s} ${i} ; done
[ $ ~/prueba-punteros ] diff -u arrays.s punteros.s
--- arrays.s   2005-10-09 00:14:23.000000000 +0200
+++ punteros.s   2005-10-09 00:14:23.000000000 +0200
@@ -1,4 +1,4 @@
-   .file   "arrays.c"
+   .file   "punteros.c"
   .section   .rodata
.LC0:
   .string   "%d\n"


Veamos con alguna optimización:

[ $ ~/prueba-punteros ] for i in *.c ; do gcc -O3 -S -o ${i/.c/.s} ${i} ; done
[ $ ~/prueba-punteros ] diff -u arrays.s punteros.s
--- arrays.s   2005-10-09 00:19:24.000000000 +0200
+++ punteros.s   2005-10-09 00:19:24.000000000 +0200
@@ -1,4 +1,4 @@
-   .file   "arrays.c"
+   .file   "punteros.c"
   .section   .rodata.str1.1,"aMS",@progbits,1
.LC0:
   .string   "%d\n"


mmmm parece generar lo mismo.

Todo apunta a que puede ser algo de los tipos que usas para los arrays, o del propio C++, o específico de tu código. O que se te haya pasado algo en las pruebas...

Un Saludo.Ferdy
Jum, se me pasó el -S [tomaaa]

franjva@tay64 ~/octave/detection $ CXXFLAGS="-S -O0" mkoctfile -c detectSphere.cc
franjva@tay64 ~/octave/detection $ CXXFLAGS="-S -O0" mkoctfile -c detectSphere2.cc
franjva@tay64 ~/octave/detection $ diff detectSphere.o detectSphere2.o
1c1
<       .file   "detectSphere.cc"
---
>       .file   "detectSphere2.cc"
2335,2337c2335
<       movq    distancesInd@GOTPCREL(%rip), %rax
<       movl    (%rax), %eax
<       movslq  %eax,%rdx
---
>       movq    distancesInd@GOTPCREL(%rip), %rdx
2338a2337
>       addl    (%rdx), %eax
2340d2338
<       leaq    (%rdx,%rax), %rax
2435,2436d2432
<       movl    -32(%rbp), %eax
<       movslq  %eax,%rdx
2437a2434
>       addl    -32(%rbp), %eax
2439d2435
<       leaq    (%rdx,%rax), %rax
2471,2473c2467
<       movq    uMLEInd@GOTPCREL(%rip), %rax
<       movl    (%rax), %eax
<       movslq  %eax,%rdx
---
>       movq    uMLEInd@GOTPCREL(%rip), %rdx
2474a2469
>       addl    (%rdx), %eax
2476d2470
<       leaq    (%rdx,%rax), %rax
2500,2501d2493
<       movl    -32(%rbp), %eax
<       movslq  %eax,%rdx
2502a2495
>       addl    -32(%rbp), %eax
2504d2496
<       leaq    (%rdx,%rax), %rax
2562a2555
>       movq    candidateVector@GOTPCREL(%rip), %rcx
2564,2566c2557
<       cltq
<       leaq    0(,%rax,4), %rcx
<       movq    candidateVector@GOTPCREL(%rip), %rdx
---
>       movslq  %eax,%rdx
2568c2559
<       movl    %eax, (%rcx,%rdx)
---
>       movl    %eax, (%rcx,%rdx,4)
2603,2605c2594
<       movq    distancesInd@GOTPCREL(%rip), %rax
<       movl    (%rax), %eax
<       movslq  %eax,%rdx
---
>       movq    distancesInd@GOTPCREL(%rip), %rdx
2606a2596
>       addl    (%rdx), %eax
2608d2597
<       leaq    (%rdx,%rax), %rax
2618,2620c2607
<       movq    distancesInd@GOTPCREL(%rip), %rax
<       movl    (%rax), %eax
<       movslq  %eax,%rdx
---
>       movq    distancesInd@GOTPCREL(%rip), %rdx
2621a2609
>       addl    (%rdx), %eax
2623d2610
<       leaq    (%rdx,%rax), %rax
2642,2644c2629
<       movq    distancesInd@GOTPCREL(%rip), %rax
<       movl    (%rax), %eax
<       movslq  %eax,%rdx
---
>       movq    distancesInd@GOTPCREL(%rip), %rdx
2645a2631
>       addl    (%rdx), %eax
2647d2632
<       leaq    (%rdx,%rax), %rax
2667,2668d2651
<       movl    -180(%rbp), %eax
<       movslq  %eax,%rdx
2669a2653
>       addl    -180(%rbp), %eax
2671,2672c2655
<       leaq    (%rdx,%rax), %rax
<       leaq    0(,%rax,8), %rcx
---
>       leaq    0(,%rax,8), %rsi
2674c2657,2658
<       movq    (%rax), %rsi
---
>       movq    (%rax), %rcx
>       movq    candidateVector@GOTPCREL(%rip), %rdx
2677,2680c2661,2662
<       leaq    0(,%rax,4), %rdx
<       movq    candidateVector@GOTPCREL(%rip), %rax
<       cvtsi2sd        (%rdx,%rax), %xmm2
<       movsd   %xmm2, (%rcx,%rsi)
---
>       cvtsi2sd        (%rdx,%rax,4), %xmm2
>       movsd   %xmm2, (%rsi,%rcx)


Pese a que el único ensamblador que conozco es el del MIPS, parece claro que con punteros utiliza unos registros diferentes que al usar arrays. Si es preferible usar rax o rdx ya tendrá que decirlo alguien que controle de x86 (o x86-64, para ser exactos) XD.

Las pruebas están requeterepetidas, no hay fallo. El código generado por detectSphere es más rápido que el de detectSphere2.

(edit) Por cierto, no pongo las diferencias con -O3 -funroll-loops -ffast-math porque no caben en la página XD.
¿ Has comprobado que te pasa lo mismo con código C ? Yo no se apenas C++ como para hacer una prueba simple. Como ves en mi caso ha generado lo mismo con -O3 que sin optimizaciones.

Mañana lo pruebo en un alpha... ahora me voy al sobre.

Saludos.Ferdy
Ferdy escribió:¿ Has comprobado que te pasa lo mismo con código C ? Yo no se apenas C++ como para hacer una prueba simple. Como ves en mi caso ha generado lo mismo con -O3 que sin optimizaciones.

Mañana lo pruebo en un alpha... ahora me voy al sobre.

Saludos.Ferdy

Sí, lo primero que probé, antes de hacer el cambio *()->[], fue un ejemplo sencillo en C, similar al que has puesto. Los objetos generados eran idénticos. Por eso me puse a cambiar (a mí me da igual, llevo años usando punteros y estoy más que acostumbrado, pero si comparto el código es más sencillo de ver la notación de arrays).

Por cierto, bajo x86 (antes era x86-64) las diferencias son bastante menores:
franjva@tay64 ~/octave/detection $ CXXFLAGS="-S -O0" mkoctfile -c detectSphere.cc
franjva@tay64 ~/octave/detection $ CXXFLAGS="-S -O0" mkoctfile -c detectSphere2.cc
franjva@tay64 ~/octave/detection $ diff detectSphere.o detectSphere2.o
1c1
<       .file   "detectSphere.cc"
---
>       .file   "detectSphere2.cc"
2888,2890c2888,2889
<       movl    16(%ebp), %eax
<       leal    0(,%eax,4), %ecx
<       movl    candidateVector@GOT(%ebx), %edx
---
>       movl    candidateVector@GOT(%ebx), %ecx
>       movl    16(%ebp), %edx
2892c2891
<       movl    %eax, (%ecx,%edx)
---
>       movl    %eax, (%ecx,%edx,4)
2990c2989
<       leal    0(,%eax,8), %ecx
---
>       leal    0(,%eax,8), %esi
2992c2991,2992
<       movl    (%eax), %esi
---
>       movl    (%eax), %ecx
>       movl    candidateVector@GOT(%ebx), %edx
2994,2997c2994,2995
<       leal    0(,%eax,4), %edx
<       movl    candidateVector@GOT(%ebx), %eax
<       fildl   (%edx,%eax)
<       fstpl   (%ecx,%esi)
---
>       fildl   (%edx,%eax,4)
>       fstpl   (%esi,%ecx)

Aunque siga habiendo diferencias en el código, la diferencia de tiempo en este caso es nula.
Tiempos en x86 (CXXFLAGS="-O3 -ffast-math -funroll-loops")
detectSphere:  ans = 10.024
detectSphere2: ans = 10.022

Tiempos en x86-64, mismos CXXFLAGS (esos registros extra no le han venido mal al x86-64, ganancia de >30% en el mismo ordenador :)):
detectSphere:  ans = 6.7558
detectSphere2: ans = 7.5135

Espero tus resultados en alpha :). Tengo curiosidad por saber si definitivamente es mejor usar punteros, como parece, o arrays.

Aun así tengo que probarlo en C, pero antes tendré que limpiar algunas clases de octave del código para que compile.
Pues la misma 'chorrada' de ejemplo en alpha genera dos objetos iguales y el mismo código ensamblador (ningún -mcpu hace que sean distintos)

[ $ ~/prueba-punteros ] for i in *.c ; do alpha-unknown-linux-gnu-gcc -O2 -mieee -S -o ${i/.c/.s} ${i} ; done
[ $ ~/prueba-punteros ] for i in *.c ; do alpha-unknown-linux-gnu-gcc -O2 -mieee -c -o ${i/.c/.o} ${i} ; done
[ $ ~/prueba-punteros ] sha1sum *.o *.s
e5ee7b263db3826451abd6eb0f239319bb683232  arrays.o
e5ee7b263db3826451abd6eb0f239319bb683232  punteros.o
c0da51261acf27fed18790236cd0c14d6307c562  arrays.s
c0da51261acf27fed18790236cd0c14d6307c562  punteros.s


No tengo muchas más ideas... si luego pillo a algún 'gcc-ninja' le preguntaré.

De todas formas habría que ver qué líneas de código C generan cambios en el asm; eso quizá nos ayudaría a ver por qué el compilador hace cosas distintas.

Saludos.Ferdy
Hola, a ver, desempolvando mis apuntes de estructura de datos, y segun mi profesor que es muy friki para esto, es practicamente equivalente, lo que hace el compilador es pasar p[i] a *(p + i), nada mas, luego el compilador lo que hace es esta operacion, valor de p + i x numero de bits del dato que contienes p, para poder acceder a esa posicion de memoria, solo eso. Creo que es asi, en un programa corto no creo que importe mucho ese cambio de notacion, supongo que en un programa algo mas sobrecargado ganará algo de velocidad.

Salu2
Creo que eso no es así. Es así: (nota a las negritas)

Sea p un puntero cualquiera no genérico. Y sea T el tamaño del tipo de dato al que p apunta. Entonces *(p + i) se convierte a p+Ti.

Que para entendernos eso significa que al dereferenciar un puntero no genérico p el compilador hace automáticamente el ajuste con el tamaño del tipo de datos. Así que las diferencias que pueda haber entre *(p+i) y p[i] no son por eso que comentas si no por otro comportamiento del compilador.

Puedo estar equivocado... pero si se cumpliera lo que tu dices para punteros no genéricos cualquier código que hiciera asignaciones a *(p+i) no funcionaría en arquitecturas de 64bits.

Saludos.Ferdy
Es lo que he dicho yo, aunque si vuelves a leer, mi post no he dicho que ese sea el motivo, sino que el compilador ejecuta la orden de direccionamiento del puntero de esa manera. Yo creo que el compilador hace el cambio de p[i] a *(p+i), unicamente, no mas, no lo se con seguridad, pero no le encuentro mas logica, ademas no se a nivel de asm, el tiempo que perdera en cambiar de p[i] a *(p+i).

Salu2
No es exactamente lo que has dicho. Si relees mis negritas eso solo se cumple para punteros no genéricos. Ademas de hacerse en tiempo de compilación y no de ejecución. Por otro lado, parece que en el código que está manejando Narf el compilador no se está comportando de esa forma.

Y un 10% en el rendimiento no es moco de pavo...

Saludos.Ferdy
No tenia razon, en lo que he dicho de que el compilador hace p[i] -> *(p+i), lo he estado compribando pasando a asm y no hace nada por el estilo, una pequeña cagada mia....Pos si no es eso, no se que puede ser, habrá que seguir mirando.

Salu2
Pregunta de novato... ¿por qué si, como decís, el compilador hace el cambio, es más rápido de una froma que de otra? ¿No debería ser igual de rápido? Igual me he perdido algo del hilo ó no he entendido varias cosas... :-S. Es que si realmente se gana ese 10%, como dice Ferdy, es algo a tener muy en cuenta.

Es raro que esto no aparezca de forma más explicada por Internet ó los libros, ¿no?

Salu2!
Si es más rápido en la forma *(p+i) que en la forma p[i] entonces es porque el compilador no está haciendo tal cambio :). Por eso me gustaría saber en qué líneas produce el mismo código y en cuales no; para tener algo más de idea.

Saludos.Ferdy
Ahhhh! Ok... ya entiendo de qué va el tema, jeje!

A ver si conseguimos averiguar algo, que estas cosas son interesantes.

Gracias! Un saludo!
Estuve probando a "desobjetizar" el código, y los objetos generados eran idénticos, pero sólo en x86. En x86-64 seguía habiendo diferencia. Así que me puse a hacer cambios en el código y esto es lo que provoca la diferencia:

p1.c:
main()
{
  int i, j, k, *p;
  i = *(p + j + k);
}


p2.c
main()
{
  int i, j, k, *p;
  i = p[j + k];
}


franjva@tay64 ~/prueba2 $ gcc -S p1.c
franjva@tay64 ~/prueba2 $ gcc -S p2.c
franjva@tay64 ~/prueba2 $ diff p1.s p2.s
1c1
<       .file   "p1.c"
---
>       .file   "p2.c"
11,12d10
<       movl    -8(%rbp), %eax
<       movslq  %eax,%rdx
13a12
>       addl    -8(%rbp), %eax
15d13
<       leaq    (%rdx,%rax), %rax


Esto sólo ocurre si, como en este caso, la dirección del array no es una variable, sino la suma de dos o más variables. Si sólo es *(p + i) y p[i], sí es idéntico (fue el primer caso que probé ayer).

En x86, en cambio, no ocurre esto. El código generado es el mismo:
franjva@tay64 ~/prueba2 $ gcc -m32 -S p1.c
franjva@tay64 ~/prueba2 $ gcc -m32 -S p2.c
franjva@tay64 ~/prueba2 $ diff p1.s p2.s
1c1
<       .file   "p1.c"
---
>       .file   "p2.c"


Estos son los fragmentos de código generados (sólo main)

p1.s:
main:
.LFB2:
        pushq   %rbp
.LCFI0:
        movq    %rsp, %rbp
.LCFI1:
        movl    -8(%rbp), %eax
        movslq  %eax,%rdx
        movl    -12(%rbp), %eax
        cltq
        leaq    (%rdx,%rax), %rax
        leaq    0(,%rax,4), %rdx
        movq    -24(%rbp), %rax
        movl    (%rdx,%rax), %eax
        movl    %eax, -4(%rbp)
        leave
        ret


p2.s:
main:
.LFB2:
        pushq   %rbp
.LCFI0:
        movq    %rsp, %rbp
.LCFI1:
        movl    -12(%rbp), %eax
        addl    -8(%rbp), %eax
        cltq
        leaq    0(,%rax,4), %rdx
        movq    -24(%rbp), %rax
        movl    (%rdx,%rax), %eax
        movl    %eax, -4(%rbp)
        leave
        ret


Lo curioso es que con punteros genera un código más largo, y aparentemente más lento: un simple addl con arrays (suma 32 bits, si no me equivoco, que supongo será un ciclo), por un movl, un movslq y un leaq con punteros (la q indica operaciones de 64 bits).

Después de ver esto cambiaría todo mi código a [], pero mis simulaciones dicen justo lo contrario :?
Bueno, creo q esto pinta bien, mirar lo que he econtrado en el Kernighan-Ritchie, (el libro de los creadores de C), es una cita sobre p[i] y *(p+i).

" Al evaluar p[i],C la convierte inmediatamente a *(p+i); las dos formas son equivalentes......En resumen, cualquier expresión de array en índice es equivalente a una expresión escrita como un puntero y desplazamiento."

Supongo que esto no saca de todas las dudas, pero si que aclara un poco el tema, supongo (que es mucho suponer) que el 10% de velocidad de diferencia se pierde en el cambio de uno a otro, aunque no creo, ya que el cambio lo haría en tiempo de compilacion....

Salu2
jyck escribió:" Al evaluar p[i],C la convierte inmediatamente a *(p+i); las dos formas son equivalentes......En resumen, cualquier expresión de array en índice es equivalente a una expresión escrita como un puntero y desplazamiento."

Eso díselo a los encargados de gcc/x86-64. XD

jyck escribió:Supongo que esto no saca de todas las dudas, pero si que aclara un poco el tema, supongo (que es mucho suponer) que el 10% de velocidad de diferencia se pierde en el cambio de uno a otro, aunque no creo, ya que el cambio lo haría en tiempo de compilacion....

Obviamente se hace en tiempo de compilación. ;)
Parece un "bug" en la implementacion del direccionamiento de memoria de gcc para amd64 más bien, pero me temo que pocos EOLianos nos podran ayudar, porque hay poca gente que sepa ensamblador de maquinas "modernas".
¿ Y este código en amd64 qué genera ?

main()
{
  int i, j, k, *p;
  i = *(p + (j + k));
}


Puede que esté haciendo internamente una conversión int->pointer. Hacerla en x86 no da problemas; pero al hacerla en amd64 necesita 'algo más' (que no se muy bien lo que es); de ahí podría venir que haya más código.

Es una simple especulación ya que no conozco asm de x86.

Saludos.Ferdy
Ferdy escribió:¿ Y este código en amd64 qué genera ?

main()
{
  int i, j, k, *p;
  i = *(p + (j + k));
}


Puede que esté haciendo internamente una conversión int->pointer. Hacerla en x86 no da problemas; pero al hacerla en amd64 necesita 'algo más' (que no se muy bien lo que es); de ahí podría venir que haya más código.

Es una simple especulación ya que no conozco asm de x86.

Genera lo mismo que p2.c (array), es decir: p[j + k] == *(p + (j + k)) != *(p + j + k).
Mmmm me lo temía... ¿ en x86_64 no segfaultea ?

Parece un "bug" en la implementacion del direccionamiento de memoria de gcc para amd64 más bien


Yo me decanto por eso.

Saludos.Ferdy
Ferdy escribió:Mmmm me lo temía... ¿ en x86_64 no segfaultea ?

No, todo perfecto. No he tenido ningun problema con código C ni C++, propio o ajeno. El gentoo ~amd64 que tengo instalado es sólido como una roca, y las simulaciones de octave con bastantes funciones propias en C++ aguantan las horas que les eche.

En cuanto al gcc, el 3.4 lleva bastante tiempo desenmascarado en x86-64... me parecería extraño que un bug relativamente evidente se hubiese escapado durante tanto tiempo. Parece más bien algo propio de la arquitectura, que no considera asociativa la suma de enteros y punteros por alguna razón... sea cual sea XD.

Ah, probé a pasar otra de mis funciones C++ de punteros a arrays y de nuevo obtengo una pérdida, mucho más pequeña (1-2%), pero pérdida al fin y al cabo.

Supongo que me quedaré con mis punteros...
Mmmm en alpha *(p + j + k) también es distinto de *(p + (j+k)). De hecho hace algo raro ya que entra el juego el registro $31. Voy a ver si consigo echarle un vistazo y actualizo con más detalles si encuentro algo.

Saludos.Fedy

-----------------

Esto me parece rarísimo... en alpha el diff es:

(asociativa-2.s contiene el código generado por un acceso a *(p + (j+k)) y asociativa.s contiene lo mismo con *(p + j + k))

--- asociativa.s   2005-10-09 20:37:36.000000000 +0200
+++ asociativa-2.s   2005-10-09 20:38:03.000000000 +0200
@@ -21,7 +21,8 @@
   stl $1,16($15)
   ldl $2,36($15)
   ldl $1,40($15)
-   addq $2,$1,$1
+   addl $2,$1,$1
+   addl $31,$1,$1
   s4addq $1,0,$2
   ldq $1,48($15)
   addq $2,$1,$1


Explicación guarra, rápida y simple:

En alpha hay varios tipos de datos, entre ellos quadwords y longwords (las primeras son más grandes que las segundas; 8 y 4 bytes respectivamente). Los alpha tienen 32 registros de enteros ($0 .. $31) y 32 registros de coma flotante ($f0 .. $f31). Todos de 64bit. Con la peculiaridad de que $31 y $f31 deben SIEMPRE ser 0. (y son raramente utilizados).

Así que:

addq $2,$1,$1


Viene a ser: suma $2 y $1 y lo guardas en $1. (tipo de datos quadword).

En el otro caso se genera lo siguiente:

addl $2,$1,$1
addl $31,$1,$1


Que viene a ser: suma $2 y $1 y lo guardas en $1 (tipo de datos longword). Además suma $31 y $1 y lo guardas en $1 (tipo longword). Pero eso realmente significa, suma 0 a $1. Y siempre será 0 ya que $31 siempre va a tener 0.

No me lo explico... ¿alguien que sepa asm del amd64 que pueda ilustrarnos si es el mismo comportamiento?

Personalmente creo que en alpha es una estupidez... aunque no se cuanto 'cuesta' sumar 0. En una operación iterativa no creo que le venga muy bien al micro hacer un 'addl $31,$1,$1' ya que es completamente innecesario...

En fin... que ni puñetera idea :)

Saludos.Ferdy
Entonces... me adapto a utilizarlo como punteros ó sigo con el clásico p[i]? Es que me extraña que una cosa así no esté más debatida si realmente se gana rendimiento. Quizá sólo por ser de arquitecturas no x86 no haya demasiado sobre esto.
También, cambiar todo a *(p + i), aparte de engorroso, es un poco lío para la gente con la que se comparte el código. Porque, si no he entendido mal, la inmensísima mayoría utiliza p[i] y no *(p + i), ¿no es así?

De todas formas está muy interesante todo esto. Gracias Narf por darnos este tema :).

Por cierto, Ferdy, sólo si te sobra tiempo... sabes ó puedes averiguar algo de lo que pasa en PowerPC? Es que yo Mac no tengo, si no copiaba y posteaba resultados.

Salu2!
Como dijo alguien en este foro: Mira que sois frikis.

No en serio, me gusta leer posts tan técnicos.

Saludos.
En mi OSX [G4 (32bit) / darwin-7.9.0 / gcc-3.3]. No hay diferencia en los asm.

Voy a ver si consigo que alguien me haga una prueba en un sparc64 o en un MIPS n64. Pero mucho me temo que el resultado en máquinas de 32 bits va a ser el mismo y va a diferir en máquinas de 64bit. (quizá por la conversion int->puntero).

Saludos.Ferdy
Josemilla escribió:Como dijo alguien en este foro: Mira que sois frikis.

No en serio, me gusta leer posts tan técnicos.

Saludos.

La cita exacta es esta:

http://www.elotrolado.net/showthread.php?s=&postid=1702559060#post1702559060
Lo de alpha me deja descolocado del todo XD. Lo de amd64 empiezo a entenderlo con un pdf que explica el juego de instrucciones de x86-64.

Veamos: los registros en amd64 son los 8 registros generales de x86 de 32 bits de siempre (eax, ecx, etc)... pero se han extendido a 64 bits (rax, rcx, etc) además de contar con 8 registros extra de 64 bits. eax es la mitad menos significativa de rax, ecx de rcx, etc.

*(p + j + k):
        movl    -8(%rbp), %eax               -> mueve lo apuntado por rbp-8 a eax (32 bit). Seguramente sea j (ó k).
        movslq  %eax,%rdx                    -> mueve eax a rdx, extendiéndolo (con signo) a 64 bits
        movl    -12(%rbp), %eax              -> mueve lo apuntado por rbp-12 a eax (32 bit). Seguramente k (ó j).
        cltq                                 -> extiende eax a rax, pasando a ser de 64 bits.
        leaq    (%rdx,%rax), %rax            -> suma rdx y rax (j + k, ambos 64bit) y lo deja en rax


*(p + (j + k)) ó p[j + k]:
        movl    -12(%rbp), %eax                   -> mete en eax j
        addl    -8(%rbp), %eax                    -> le suma k y lo deja en eax (en 32 bits)
        cltq                                      -> pasa eax a 64 bits (rax)

Al final en ambos casos tenemos en rax j+k, 64 bit. Pero por un lado ( *(p + (j + k)) ) hemos hecho una operación de 32 bits y transformado el entero en uno de 64 para sumar más tarde al puntero, también de 64, y por otro ( *(p + j + k) ) hemos hecho la suma en 64 bits, para lo que hemos tenido que dar un rodeo algo absurdo.

Y sigo preguntándome cómo es más rápido lo segundo que lo primero. Maravillas de la arquitectura de ordenadores XD. Bueno, ya que estoy en Departamento de Electrónica y Sistemas, podría preguntarle a los del área de arquitectura, que son la otra mitad del departamento :-|.
Ehm... yo tampoco soy capaz de encontrarle explicación. Si descubres algo nos cuentas :)

Saludos.Ferdy
Estaria bien saber los ciclos de reloj que tarda el micro en ejecutar cada instruccion en amd64 porque esta claro que alguna de ellas se ve penalizada en 64 bits. Me interesa este problema porque también tengo un AMD64 y además tengo una asignatura este cuatrimestre llamada precisamente "Arquitectura de Ordenadores".

Rebuscando un poco en San Google me he encontrado un articulo interesante que puede ayudarnos:
"x86-64 Machine-Level Programming" Randal E. Bryant
el_Salmon escribió:Rebuscando un poco en San Google me he encontrado un articulo interesante que puede ayudarnos:
"x86-64 Machine-Level Programming" Randal E. Bryant

Precisamente ése es el pdf que menciono arriba y que me ayudó a comprender el asm x86-64 ;).

Los ciclos, sean los que sean por instrucción, tienen que ser menos en el caso de p[j + k]. No puede ser que un addl sea más lento que movl, movsql y leaq. Pero en un código tan largo como el C++ de la simulación y con un procesador tan complejo como el amd64, predecir cuál será más rápido es algo bastante más complicado. Lo verás en esa asignatura :P.
Veamos ;)
Si en teoria lo que hace el precompilador es pasar p[i] a *(p+i)... no hay alguna manera de "parar" al compilador para ver el codigo antes de compilar (justo despues de que pase el precompilador)?
La verdad es que esta interesante el tema este... x)
Salu2!
Si os hacen falta benchs en ppc/osx ppc/linux avisar! :D
Narf escribió:Y sigo preguntándome cómo es más rápido lo segundo que lo primero. Maravillas de la arquitectura de ordenadores XD.


Como dice el_Salmon seria interesante ver los ciclos de reloj de cada
operación pero observa:




1 movl -12(%rbp), %eax -> mete en eax j
2 addl -8(%rbp), %eax -> le suma k y lo deja en eax (en 32 bits)
3 cltq -> pasa eax a 64 bits (rax)


Estas 3 instrucciones depende la una de la otra y no se pueden
ejecutar a la vez en el pipe...


1movl -8(%rbp), %eax -> mueve lo apuntado por rbp-8 a eax (32 bit). Seguramente sea j (ó k).
2movslq %eax,%rdx -> mueve eax a rdx, extendiéndolo (con signo) a 64 bits
3movl -12(%rbp), %eax -> mueve lo apuntado por rbp-12 a eax (32 bit). Seguramente k (ó j).
4 cltq -> extiende eax a rax, pasando a ser de 64 bits.
5leaq (%rdx,%rax), %rax -> suma rdx y rax (j + k, ambos 64bit) y lo deja en rax


Las instrucciones 1 2 depende la una de la otra pero
las intrucciones 3 y 4son independientes de estas
(pero dependientes entre ellas)

En cualquier caso se pueden ejecutar simulataneamente y
aunque sean más intrucciones, perederan menos ciclos
(cosa de los chips superescalares)
Y no tiene por que afectar que las dos usen rax para eso esta
el renombrado de registros :Ð

PD:
los athlon64 tienen otros 8 registros de proposito general
(16 en total)
e-Minguez escribió:Veamos ;)
Si en teoria lo que hace el precompilador es pasar p[i] a *(p+i)... no hay alguna manera de "parar" al compilador para ver el codigo antes de compilar (justo despues de que pase el precompilador)?

No es necesario; por los resultados, lo que hace es p[i] -> *(p + (i)), que no es lo mismo. Si i, en vez de ser una variable, es una expresión aritmética, la cosa cambia.

Harl escribió:En cualquier caso se pueden ejecutar simulataneamente y
aunque sean más intrucciones, perederan menos ciclos
(cosa de los chips superescalares)
Y no tiene por que afectar que las dos usen rax para eso esta
el renombrado de registros

Sí, podría ser posible ejecutar en paralelo los 2 grupos de instrucciones que dices. Pero difícilmente podría ser más rápido que el caso anterior. Igual de rápido, posible; más rápido, bastante difícil. En el mejor de los casos sigues teniendo 3 instrucciones dependientes, y además ocupas más la cpu (el programa no es sólo ese fragmento).

Harl escribió:PD:
los athlon64 tienen otros 8 registros de proposito general
(16 en total)

Sip, es lo que dije :P:
los registros en amd64 son los 8 registros generales de x86 de 32 bits de siempre (eax, ecx, etc)... pero se han extendido a 64 bits (rax, rcx, etc) además de contar con 8 registros extra de 64 bits
Narf escribió:Sí, podría ser posible ejecutar en paralelo los 2 grupos de instrucciones que dices. Pero difícilmente podría ser más rápido que el caso anterior. Igual de rápido, posible; más rápido, bastante difícil


Puede que sean instrucciones más rápidas.
Ten en cuenta que eso se pasa a microcodigo dentro de la CPU
y puede que ela add se implmente por instrucciones más complejas
que el leaq
Sin saber como esl pipe o el microcodigo del Athlon
es dificl saberlo

Tambien observa que el add que usa el primer codigo
lee de memoria (eso es muy complejo)
y que en el segundo ejemplo se suman dos registros
direactamente.
Las lecturas de memoria es lo que más ciclos pierde
y en el segundo ejemplo esos ciclos perdidos
se enmascaran con las otras instrucciones
¿pero se esta ejecutando más rápido?¿no?


Recuerdo un ejemplo que nos pusieron en Arquitecturas especializadas bastante curioso
donde usaban una instrucción de las SSE que hacia divisiones
en precisión de 11 bits en 2 ciclos (en lugar de 20 ciclos por
los 23 bits de precisión)

Lo gracioso es que implmentenado una interpolacion
por newton-rapson (creo que algoritmo era ese)
se tardaba en total menos de 20 ciclos
eso con unas 8 intrucciones y finalmente obtenias
el mismo resultado que la instrucción de división normal
¬_¬
Logicamente Intel recomendaba no usar div a secas por que
no tiene sentido

Lo de los temas de optimización era muy gracioso
ya que principalmente se hacia desenrollado de bucles,
y reordenar el codigo para que las intricciones fuesen de distintos
unidades de decodificación y meter instrucciones nop
para que quedaran alineads y no partidas entre dos páginas
de cache
Todo para que el pipe estuviera lleno el mayor tiempo
posible ya que donde se pierde rendimiento son en
las burbujas por dependencias o por usar la misma unidad [reves]
Harl escribió:Puede que sean instrucciones más rápidas.
Ten en cuenta que eso se pasa a microcodigo dentro de la CPU
y puede que ela add se implmente por instrucciones más complejas
que el leaq
Sin saber como esl pipe o el microcodigo del Athlon
es dificl saberlo

Tambien observa que el add que usa el primer codigo
lee de memoria (eso es muy complejo)
y que en el segundo ejemplo se suman dos registros
direactamente.
Las lecturas de memoria es lo que más ciclos pierde
y en el segundo ejemplo esos ciclos perdidos
se enmascaran con las otras instrucciones
¿pero se esta ejecutando más rápido?¿no?

Ese ejemplo en concreto no, no lo he probado. Es la simulación de sphere detection la que se ejecuta más rápido, algo bastante más complejo (una búsqueda en árbol recursiva, en profundidad, de los vectores de símbolos de una modulación digital más probablemente transmitidos). Tengo que probar a ver cuál es más rápido en ese ejemplo simple. Ya contaré :).

(edit) Esperable :)

franjva@tay64 ~/prueba2 $ diff -U 10 p1.c p2.c
--- p1.c        2005-10-10 20:14:12.000000000 +0200
+++ p2.c        2005-10-10 20:14:01.000000000 +0200
@@ -1,6 +1,6 @@
main()
{
   int i, j=2, k=5, p[10];
   long int ind;
-  for (ind=10e8; ind--; ) i = *(p + j + k);
+  for (ind=10e8; ind--; ) i = p[j + k];
}


franjva@tay64 ~/prueba2 $ gcc -S p1.c
franjva@tay64 ~/prueba2 $ gcc -S p2.c
franjva@tay64 ~/prueba2 $ diff p1.s p2.s
1c1
<       .file   "p1.c"
---
>       .file   "p2.c"
19,20d18
<       movl    -8(%rbp), %eax
<       movslq  %eax,%rdx
21a20
>       addl    -8(%rbp), %eax
23d21
<       leaq    (%rdx,%rax), %rax


franjva@tay64 ~/prueba2 $ gcc -o p1 p1.c
franjva@tay64 ~/prueba2 $ gcc -o p2 p2.c
franjva@tay64 ~/prueba2 $ time ./p1

real    0m3.710s
user    0m3.640s
sys     0m0.064s
franjva@tay64 ~/prueba2 $ time ./p1

real    0m3.711s
user    0m3.656s
sys     0m0.040s
franjva@tay64 ~/prueba2 $ time ./p1

real    0m3.710s
user    0m3.652s
sys     0m0.048s
franjva@tay64 ~/prueba2 $ time ./p2

real    0m3.248s
user    0m3.196s
sys     0m0.040s
franjva@tay64 ~/prueba2 $ time ./p2

real    0m3.248s
user    0m3.196s
sys     0m0.044s
franjva@tay64 ~/prueba2 $ time ./p2

real    0m3.250s
user    0m3.196s
sys     0m0.044s


ES más rápido el programa con notación de array que con notación de puntero. Esas 2 instrucciones más se notan bastante (15% de pérdida). Pero lo dicho, al pasar a un programa mucho más complejo, predecir algo es casi imposible. De hecho, sucede lo contrario.

En fin ;)
En el caso de un alpha la notación con punteros es más rápida que con arrays:

--- punteros.s   2005-10-10 15:32:37 -0400
+++ arrays.s   2005-10-10 15:32:37 -0400
@@ -32,7 +32,8 @@
$L5:
   ldl $2,20($15)
   ldl $1,24($15)
-   addq $2,$1,$1
+   addl $2,$1,$1
+   addl $31,$1,$1
   s4addq $1,0,$1
   lda $2,16($15)
   addq $1,$2,$1


El código es el mismo que el que ha posteado Narf:

ferdy@gendcc02 ~ $ time ./punteros

real   0m28.346s
user   0m28.336s
sys   0m0.007s
ferdy@gendcc02 ~ $ time ./punteros

real   0m28.348s
user   0m28.327s
sys   0m0.021s
ferdy@gendcc02 ~ $ time ./punteros

real   0m28.348s
user   0m28.329s
sys   0m0.018s
ferdy@gendcc02 ~ $ time ./arrays 

real   0m32.119s
user   0m32.104s
sys   0m0.014s
ferdy@gendcc02 ~ $ time ./arrays

real   0m32.116s
user   0m32.102s
sys   0m0.014s
ferdy@gendcc02 ~ $ time ./arrays

real   0m32.120s
user   0m32.102s
sys   0m0.017s


En este caso los arrays son más lentos...

Sin embargo si quito el addl $31,$1,$1 y recompilo 'arrays.s', la cosa cambia:

ferdy@gendcc02 ~/punteros-test $ vim arrays.s   
ferdy@gendcc02 ~/punteros-test $ gcc -o arrays-noaddl-31-1-1 arrays.s
ferdy@gendcc02 ~/punteros-test $ time ./arrays-noaddl-31-1-1

real   0m28.348s
user   0m28.333s
sys   0m0.013s
ferdy@gendcc02 ~/punteros-test $ time ./arrays-noaddl-31-1-1

real   0m28.348s
user   0m28.331s
sys   0m0.016s
ferdy@gendcc02 ~/punteros-test $ time ./arrays-noaddl-31-1-1

real   0m28.347s
user   0m28.331s
sys   0m0.014s


Un tiempo 'igual' al de punteros. En el caso del alpha, 'addq' y 'addl' tardan prácticamente lo mismo de ahí que la diferencia (si es que la hay) es inapreciable.

Un Saludo.Ferdy

-----------------

En #gentoo-alpha, kloeri me ha solucionado la duda. Espero que os ayude a los demas jeje

22:17 <@ferdy> do you have any idea on why p[i+j] is different from *(p+i+j) ?
22:17 <@ferdy> I thought the compiler did the p[i] -> *(p+i) change...
22:19 <@kloeri> that would probably depend of locality of p, i and j, number of free registers,
                whether gcc thinks it's worth pushing all those registers when calling functions
                etc.
22:19 <@ferdy> rather unpredictably then...
22:19 <@kloeri> there's a lot more to optimizers than (usually) meets the eye
22:20 <@ferdy> it generates the same code on x86 (with easy and complex code)... but seems to
               generate different code on 64bit platforms...
22:21 <@ferdy> thanks anyway :)
22:21 <@kloeri> depends a lot on number of registers, various penalties etc.
22:22 <@ferdy> I see...
22:22 <@kloeri> so it makes a lot of sense that it doesn't behave equally on different archs
22:23 <@ferdy> mind If I paste this to someone that was also trying to find out why ?
22:23 <@kloeri> not at all
22:23 <@ferdy> thanks million


Saludos.Ferdy
Ok, gracias :).

En fin, duda resuelta, lo que hay que hacer es... probar las dos opciones y ver cuál funciona más rápido XD.

Saludos ;).
Gracias Ferdy por las molestias que te has tomado en preguntar y tal.

A ver si al final me he enterado bien. Según mis conclusiones si lo hacemos de la forma "tradicional" siempre será igual ó más lento que la forma de punteros, ¿me equivoco?
Si es así convendría acostumbrarse más a hacerlo con punteros puesto que dependiendo de la arquitectura puede haber ganancia ó, como mínimo, ejecutarse igual de rápido que la otra forma.

Me he perdido algo, mucho, ó realmente ésta es la conclusión base que hemos sacado con todo esto?

Gracias! Salu2!
No; la conclusión es: hazlo como más rabia te dé, que al final el compilador hará lo que le salga de las narices. En el código complejo gano con punteros; en el simple con arrays. Y en estas cosas NADA es extrapolable. Así que lo dicho ;).
42 respuestas
Archivado
Volver a Software libre