Comment se fait-il que mon index de tableau soit plus rapide que le pointeur

Pourquoi l’index de tableau est plus rapide que le pointeur? Le pointeur n’est-il pas supposé être plus rapide qu’un index de tableau?

** J’ai utilisé time.h clock_t pour tester deux fonctions, chaque boucle 2 millions de fois.

Pointer time : 0.018995 Index time : 0.017864 void myPointer(int a[], int size) { int *p; for(p = a; p < &a[size]; p++) { *p = 0; } } void myIndex(int a[], int size) { int i; for(i = 0; i < size; i++) { a[i] = 0; } } 

Non, jamais les pointeurs ne sont supposés être plus rapides que l’index de tableau. Si l’un des codes est plus rapide que l’autre, c’est principalement parce que certains calculs d’adresse peuvent être différents. La question devrait également fournir des informations sur le compilateur et les indicateurs d’optimisation, car cela peut grandement affecter les performances.

L’index de tableau dans votre contexte (le lien de tableau n’est pas connu) est exactement identique à l’opération de pointeur. Du sharepoint vue des compilateurs, il s’agit simplement d’une expression différente de l’arithmétique de pointeur. Voici un exemple de code x86 optimisé dans Visual Studio 2010 avec optimisation complète et aucun inline .

  3: void myPointer(int a[], int size) 4: { 013E1800 push edi 013E1801 mov edi,ecx 5: int *p; 6: for(p = a; p < &a[size]; p++) 013E1803 lea ecx,[edi+eax*4] 013E1806 cmp edi,ecx 013E1808 jae myPointer+15h (13E1815h) 013E180A sub ecx,edi 013E180C dec ecx 013E180D shr ecx,2 013E1810 inc ecx 013E1811 xor eax,eax 013E1813 rep stos dword ptr es:[edi] 013E1815 pop edi 7: { 8: *p = 0; 9: } 10: } 013E1816 ret 13: void myIndex(int a[], int size) 14: { 15: int i; 16: for(i = 0; i < size; i++) 013E17F0 test ecx,ecx 013E17F2 jle myIndex+0Ch (13E17FCh) 013E17F4 push edi 013E17F5 xor eax,eax 013E17F7 mov edi,edx 013E17F9 rep stos dword ptr es:[edi] 013E17FB pop edi 17: { 18: a[i] = 0; 19: } 20: } 013E17FC ret 

En un coup d'œil, myIndex semble plus rapide, car le nombre d'instructions est inférieur. Cependant, les deux parties du code sont essentiellement les mêmes. Les deux utilisent finalement rep stos , qui est une instruction de répétition (boucle) x86. La seule différence est due au calcul de la boucle liée. La boucle for dans myIndex a la size nombre de déplacements telle quelle (aucun calcul n'est nécessaire). Mais myPointer besoin de quelques calculs pour obtenir le nombre de myPointer de la boucle for . C'est la seule différence. Les opérations de boucle importantes sont exactement les mêmes. Ainsi, la différence est négligeable.

En résumé, les performances de myPointer et de myIndex dans un code optimisé doivent être identiques.


Pour votre information, si la limite du tableau est connue au moment de la compilation, par exemple, int A[constant_expression] , les access sur ce tableau peuvent être beaucoup plus rapides que ceux du pointeur. Cela est principalement dû au fait que les access au tableau sont libres du problème d' parsing du pointeur . Les compilateurs peuvent parfaitement calculer les informations de dépendance sur les calculs et accéder à un tableau de taille fixe, ce qui lui permet d'effectuer des optimisations avancées, notamment la parallélisation automatique.

Toutefois, si les calculs sont basés sur un pointeur, les compilateurs doivent effectuer une parsing du pointeur pour une optimisation plus poussée, ce qui est assez limité en C / C ++. Il aboutit généralement à des résultats conservateurs sur l'parsing de pointeur et donne lieu à quelques opportunités d'optimisation.

C’est peut-être la comparaison dans la boucle for qui fait la différence. La condition de terminaison est testée à chaque itération et votre exemple de “pointeur” présente une condition de terminaison légèrement plus compliquée (prenant l’adresse de & a [taille]). Etant donné que & a [taille] ne change pas, vous pouvez essayer de le définir comme une variable pour éviter de le recalculer à chaque itération de la boucle.

La déréférence du tableau p[i] est *(p + i) . Les compilateurs utilisent des instructions qui calculent math + dereference en 1 ou 2 cycles (par exemple une instruction x86 LEA) pour optimiser la vitesse.

Avec la boucle de pointeur, il divise l’access et le décalage en parties séparées et le compilateur ne peut pas l’optimiser.

Oups, sur mon système 64 bits, les résultats sont assez différents. J’ai ça

  int i; for(i = 0; i < size; i++) { *(a+i) = 0; } 

est environ 100 fois !! plus lent que cela

  int i; int * p = a; for(i = 0; i < size; i++) { *(p++) = 0; } 

lors de la compilation avec -O3 . Cela laisse à penser qu'il est beaucoup plus facile de passer à l'adresse suivante pour un processeur 64 bits que de calculer l'adresse de destination à partir d'un décalage. Mais je ne suis pas sur.

MODIFIER:
Cela a vraiment quelque chose à voir avec l'architecture 64 bits, car un même code avec les mêmes drapeaux de compilation ne montre pas de réelle différence de performances sur les systèmes 32 bits.

Les temps sont si rapprochés que si vous les avez répétés, vous ne verrez peut-être pas beaucoup de différence. Les deux segments de code sont compilés dans le même assemblage. Par définition, il n’y a pas de différence.

Je suggérerais d’exécuter chaque boucle 200 millions de fois, puis d’exécuter chaque boucle 10 fois et de prendre la mesure la plus rapide. Cela tiendra compte des effets de la planification du système d’exploitation, etc.

Je vous suggérerais alors de désassembler le code pour chaque boucle.

Il semble que la solution d’index puisse enregistrer quelques instructions avec la comparaison dans la boucle for.

Accéder aux données via un index de tableau ou un pointeur est exactement équivalent. Passez par le programme ci-dessous avec moi …

Il existe une boucle qui continue 100 fois, mais lorsque nous voyons du code désassembler, certaines données auxquelles nous accédons ont une comparabilité d’instruction inférieure à celle d’un tableau. Index

Mais cela ne signifie pas que l’access aux données via un pointeur est rapide, cela dépend en réalité de l’instruction exécutée par le compilateur.

 int a[100]; fun1(a,100); fun2(&a[0],5); } void fun1(int a[],int n) { int i; for(i=0;i<=99;i++) { a[i]=0; printf("%d\n",a[i]); } } void fun2(int *p,int n) { int i; for(i=0;i<=99;i++) { *p=0; printf("%d\n",*(p+i)); } } disass fun1 Dump of assembler code for function fun1: 0x0804841a <+0>: push %ebp 0x0804841b <+1>: mov %esp,%ebp 0x0804841d <+3>: sub $0x28,%esp`enter code here` 0x08048420 <+6>: movl $0x0,-0xc(%ebp) 0x08048427 <+13>: jmp 0x8048458  0x08048429 <+15>: mov -0xc(%ebp),%eax 0x0804842c <+18>: shl $0x2,%eax 0x0804842f <+21>: add 0x8(%ebp),%eax 0x08048432 <+24>: movl $0x0,(%eax) 0x08048438 <+30>: mov -0xc(%ebp),%eax 0x0804843b <+33>: shl $0x2,%eax 0x0804843e <+36>: add 0x8(%ebp),%eax 0x08048441 <+39>: mov (%eax),%edx 0x08048443 <+41>: mov $0x8048570,%eax 0x08048448 <+46>: mov %edx,0x4(%esp) 0x0804844c <+50>: mov %eax,(%esp) 0x0804844f <+53>: call 0x8048300  0x08048454 <+58>: addl $0x1,-0xc(%ebp) 0x08048458 <+62>: cmpl $0x63,-0xc(%ebp) 0x0804845c <+66>: jle 0x8048429  0x0804845e <+68>: leave 0x0804845f <+69>: ret End of assembler dump. (gdb) disass fun2 Dump of assembler code for function fun2: 0x08048460 <+0>: push %ebp 0x08048461 <+1>: mov %esp,%ebp 0x08048463 <+3>: sub $0x28,%esp 0x08048466 <+6>: movl $0x0,-0xc(%ebp) 0x0804846d <+13>: jmp 0x8048498  0x0804846f <+15>: mov 0x8(%ebp),%eax 0x08048472 <+18>: movl $0x0,(%eax) 0x08048478 <+24>: mov -0xc(%ebp),%eax 0x0804847b <+27>: shl $0x2,%eax 0x0804847e <+30>: add 0x8(%ebp),%eax 0x08048481 <+33>: mov (%eax),%edx 0x08048483 <+35>: mov $0x8048570,%eax 0x08048488 <+40>: mov %edx,0x4(%esp) 0x0804848c <+44>: mov %eax,(%esp) 0x0804848f <+47>: call 0x8048300  0x08048494 <+52>: addl $0x1,-0xc(%ebp) 0x08048498 <+56>: cmpl $0x63,-0xc(%ebp) 0x0804849c <+60>: jle 0x804846f  0x0804849e <+62>: leave 0x0804849f <+63>: ret End of assembler dump. (gdb) 

C’est une chose très difficile à chronométrer, car les compilateurs sont très bons pour optimiser ces choses. Néanmoins, il vaut mieux donner au compilateur autant d’informations que possible, c’est pourquoi dans ce cas, je vous conseillerais d’utiliser std :: fill et de laisser le compilateur choisir.

Mais … si vous voulez entrer dans les détails

a) Les CPU donnent normalement le pointeur + la valeur gratuitement, comme par exemple: mov r1, r2 (r3).
b) Cela signifie qu’une opération d’index nécessite seulement: mul r3, r1, taille
Ceci est juste un cycle supplémentaire, par boucle.
c) Les CPU fournissent souvent des emplacements de décrochage / délai, ce qui signifie que vous pouvez souvent masquer les opérations à cycle unique.

Dans l’ensemble, même si vos boucles sont très volumineuses, le coût de l’access n’est rien comparé au coût de quelques cache-miss. Il est préférable d’optimiser vos structures avant de vous préoccuper des coûts de boucle. Essayez par exemple d’ emballer vos structures pour réduire d’abord l’empreinte mémoire.

Les optimisations du compilateur correspondent à un modèle.

Lorsque votre compilateur optimise, il recherche les modèles de code connus, puis le transforme en fonction de certaines règles. Vos deux extraits de code semblent déclencher des transformations différentes et produire ainsi un code légèrement différent.

C’est l’une des raisons pour lesquelles nous insistons toujours pour réellement mesurer les performances obtenues en matière d’optimisation: vous ne pouvez jamais être sûr de ce en quoi votre compilateur transforme votre code, à moins de le tester.


Si vous êtes vraiment curieux, essayez de comstackr votre code avec gcc -S -Os , cela produira le code assembleur le plus lisible, mais optimisé. Sur vos deux fonctions, je reçois l’assembleur suivant avec cela:

 pointer code: .L2: cmpq %rax, %rdi jnb .L5 movl $0, (%rdi) addq $4, %rdi jmp .L2 .L5: index code: .L7: cmpl %eax, %esi jle .L9 movl $0, (%rdi,%rax,4) incq %rax jmp .L7 .L9: 

Les différences sont légères, mais peuvent en effet déclencher une différence de performance. Plus important encore, la différence entre addq et incq pourrait être significative.