Array index vs pointer I

Como muchos de vosotros yo suelo utilizar un puntero para iterar los datos de un array. Pero hace poco un amigo me dijo: "¿Por qué lo haces así y no utilizas un índice?". A lo que yo respondí, "Pues porque es más optimo".Mi amigo mostró su disconformidad y nos enzarzamos en una discusión que, como casi todas hoy en día, hemos tratado de resolver buscando la respuesta en internet. Y he de confesar que ésta la tengo medio perdida. Cuando buscas en Google la frase “array index vs pointer”, se encuentran documentos donde se plantea que no hay muchas diferencias; pruebas realizadas demuestran que se emplea el mismo tiempo tanto si se itera con índice como con punteros. El por qué de este resultado depende de muchos factores, entre ellos (el compilador utilizado, las optimizaciones, el tipo de procesador y el código fuente que se utiliza entre otros). En este artículo voy explicar como afectan los diferentes factores a la iteración de datos en un array. Tomemos como base el siguiente código en C.

char *texto = "1234567890";
int len = strlen(texto);
for (int j =0;j < len;j++)
    if (texto[j] == '6') break;
for (char* cptr=texto;*cptr != 0;cptr++)
    if (*cptr == '6') break;

Utilizando el compilador de Microsoft para x86 32Bits y sin aplicar optimizaciones se obtiene el siguiente código en ensamblador.

int len = strlen(texto);
mov eax,dword ptr [texto] push eax call strlen (00416d70) add esp,4 mov dword ptr [len],eax
for (int j=0;j< len;j++)		for (char* cptr=texto;*cptr != 0;cptr++)
mov dword ptr [j],0 jmp 1 2: mov edx,dword ptr [j] add edx,1 mov dword ptr [j],edx 1: mov eax,dword ptr [j] cmp eax,dword ptr [len] jge 4	j = 0 (j < len) edx=j edx++ j=edx eax=j eax < len break	mov eax,dword ptr [texto] mov dword ptr [cptr],eax jmp 1 2: mov ecx,dword ptr [cptr] add ecx,1 mov dword ptr [cptr],ecx 1: mov edx,dword ptr [cptr] movsx eax,byte ptr [edx] test eax,eax je 4	ax = &texto cptr = aex (*cptr != 0) ecx = cptr ecx ++ cptr = ecx edx = cptr eax = *cptr eax == 0 break
if (texto[j] =='6') break;		if (*cptr == '6') break;
mov ecx,dword ptr [texto] add ecx,dword ptr [j] movsx edx,byte ptr [ecx] cmp edx,36h jne 3 jmp 4 3: jmp 2 4:	cx =&texto ecx= texto+j edx = texto[j] edx == 6 else break ( j++ )	mov ecx,dword ptr [cptr] movsx edx,byte ptr [ecx] cmp edx,36h jne 3 jmp 4 3: jmp 2 4:	ecx = cptr edx = *cptr edx == '6' else break; ( cptr++ )

	Indice	Puntero
Inicialización	7	3
Condición ciclo	3	4
Incremento	3	3
Instrucciones	7	6
Total ciclo	13	13

Analizando el final del código podemos apreciar como el compilador ha pasado por alto una optimización muy sencilla; las instrucciones (jne 3 , jmp4, jmp 2) son equivalente a (je 4, jmp 2). La cantidad de instrucciones que se utilizan para la Inicialización, condición, incremento y realización del ciclo se resumen en la tabla. Lo cual permite concluir que los dos ciclos son igual de rápidos; pero hemos olvidado algo importante; el ciclo con indice no es exactamente igual al ciclo con punteros, el código correcto se muestra a continuación.

for (int j=0;texto[j]!=0;j++)
mov dword ptr [j],0 jmp 1 2: mov edx,dword ptr [j] add edx,1 mov dword ptr [j],edx 1: mov edx,dword ptr [texto] add edx,dword ptr [j] movsx eax,byte ptr [edx] test eax,eax jge 4	j = 0 ( texto[j]!=0 ) edx=j edx++ j=edx edx=texto edx=&texto[j] eax=texto[j] texto[j] == 0 break
if (texto[j] == '6') break;
mov ecx,dword ptr [texto] add ecx,dword ptr [j] movsx edx,byte ptr [ecx] cmp edx,36h jne 3 jmp 4 3: jmp 2 4:	ecx = &texto ecx= texto+j edx = texto[j] edx == 6 else break ( j++ )

Con este nuevo desarrollo hemos eliminado la llamada a la función strlen, la inicialización del ciclo es más rápida por una instrucción, pero la condición de ciclo es mas lenta; de momento la ventaja es para el puntero, pero por muy poco margen. Vamos a introducir una complejidad extra al ciclo, en lugar de iterar un sencillo array de char vamos a iterar una estructura.

struct S {
int a;
char c;
BYTE b;
};
struct S aS[] = {
  {1,'a',1},
  {2,'b',2},
  {3,'b',4},
  {0,0,0} };
struct S *pS;
int j;
for (j=0;aS[j].a != 0;j++)
  if (aS[j].a == 3) break;
for (pS =aS;pS->a != 0;pS++)
  if (pS->a == 3) break;

for (j=0;aS[j].a != 0;j++)		for (pS = aS;pS->a != 0;pS++)
mov dword ptr [j],0 jmp 2 1: mov edx,dword ptr [j] add edx,1 mov dword ptr [j],edx 2: mov eax,dword ptr [j] imul eax,eax,1Ch cmp dword ptr aS[eax],0 je 4	j=0 (aS[j].a != 0) edx = j edx ++; j = edx eax = j eax=eax*0x1C aS[j].a != 0 break;	lea edx,[aS] mov dword ptr [pS],edx jmp 2 1: mov eax,dword ptr [pS] add eax,1Ch mov dword ptr [pS],eax 2: mov ecx,dword ptr [pS] cmp dword ptr [ecx],0 je 4	edx=aS pS=edx condición eax=pS eax+=0x1C pS=eax ecx=pS (pS-<a != 0) break
if (aS[j].a == 3) break;		if (pS->a == 3) break;
mov ecx,dword ptr [j] imul ecx,ecx,1Ch cmp dword ptr aS[ecx],3 jne 3 jmp 4 3: jmp 1 4:	ecx=j ecx*=0x1C aS[j].a == 3 else break; continue;	mov edx,dword ptr [pS] cmp dword ptr [edx],3 jne 3 jmp 4 3: jmp 1 4:	edx=pS pS-<a==3 else break; continue;

	Indice	Puntero
Inicialización	2	3
Condición ciclo	4	3
Incremento	3	3
Instrucciones	6	5
Total ciclo	13	11

Cuando iteramos una estructura el direccionamiento por indice requiere una istrucción de multiplicación que penaliza el rendimiento. Hay un aspecto mas a tener en cuenta; la variable "a" de la estructura es de tipo entero y está justo al incio, veamos la diferencia si es de tipo BYTE y se encuentra al final

struct S {
int b;
char c;
BYTE a;
};
struct S aS[] = {
  {1,'a',1},
  {2,'b',2},
  {3,'b',4},
  {0,0,0} };
struct S *pS;
int j;
for (j=0;aS[j].fin != 0;j++)
  if (aS[j].a == 3) break;
for (pS =aS;pS->fin != 0;pS++)
  if (pS->a == 3) break;

for (j=0;aS[j].a != 0;j++)		for (pS = aS;pS->a != 0;pS++)
mov dword ptr [j],0 jmp 2 1: mov edx,dword ptr [j] add edx,1 mov dword ptr [j],edx 2: mov eax,dword ptr [j] imul eax,eax,1Ch xor ecx,ecx mov cl,byte ptr [ebp+eax-0BF3h] test ecx,ecx je 4	j=0 ( aS[j].a != 0 ) edx = j edx++ j = edx eax = j eax *= 0x1C ecx = 0 cl = as[j].a cl == 0 break	lea ecx,[aS] mov dword ptr [pS],ecx jmp 2 1: mov edx,dword ptr [pS] add edx,1Ch mov dword ptr [pS],edx 2: mov eax,dword ptr [pS] xor ecx,ecx mov cl,byte ptr [eax+19h] test ecx,ecx je 4	ecx = aS cptr = ecx ( pS->a != 0 ) edx = pS edx += 0x1C pS = edx eax = pS ecx = 0 cl = pS->a ecx == 0 break
if (aS[j].a == 3) break;		if (pS->a == 3) break;
mov edx,dword ptr [j] imul edx,edx,1Ch xor eax,eax mov al,byte ptr [ebp+edx-0BF3h] cmp eax,3 jne 3 jmp 4 3: jmp 1 4:	edx = j edx *= 0x1C eax = 0 al = aS[j].a al == 3 else break ( j++ )	mov edx,dword ptr [pS] xor eax,eax mov al,byte ptr [edx+19h] cmp eax,3 jne 3 jmp 4 3: jmp 1 4:	edx = pS eax = 0 al = pS->a eax == 3 else break ( pS ++ )

	Indice	Puntero
Inicialización	2	3
Condición ciclo	6	5
Incremento	3	3
Instrucciones	8	7
Total ciclo	17	15

El código es mas complejo, pues un byte no se puede comparar directamente desde memoria, para ello hay que cargarlo en un registro (ecx) que previamente debe estar en cero, además hay que utilizar un desplazamiento de 0x19 para acceder a la variable "a". Este ejemplo a incrementado por igual el tamaño de los ciclos. A medida que el ciclo se hace complejo el factor que determina la diferencia es la velocidad para acceder a un elemento y sus datos. En la siguiente publicación abordare este tema

Como resumen podemos decir que: Acceder a la memoria con puntero es una instrucción más rápido que con indice y si mutliplicamos por la cantidad de iteraciones del ciclo y las veces que accedemos, la diferencia puede ser notable; además datos de tipo BYTE añade complejida al código ensamblador.