En C, accéder à mon index de tableau est plus rapide ou accéder par un pointeur est plus rapide?

En C, accéder à un index de tableau est plus rapide ou accéder par un pointeur est plus rapide? Par plus rapide, je veux dire lequel prendrait moins de cycle d’horloge. Le tableau n’est pas un tableau constant.

templatetypedef l’a résumé. Pour append un peu de soutien à sa réponse. Prenons ces exemples de fonctions:

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

     rb = 0;
     pour (ra = 0; ra <1000; ra ++) rb + = * x ++;
     return (rb);
 }

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

Maintenant gcc a produit ceci:

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

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

Le code est différent, mais je suis surpris des opportunités d’optimisation manquées.

Clang / llvm a produit ceci:


 00000000 fun1:
    0: e3a01000 mov r1, # 0
    4: e3a02ffa mov r2, # 1000;  0x3e8
    8: e1a03001 mov r3, r1
    c: e2522001 subs r2, r2, n ° 1
   10: e490c004 ldr ip, [r0], n ° 4
   14: e08c3003 add r3, ip, r3
   18: e2c11000 sbc r1, r1, # 0
   1c: e182c001 orr ip, r2, r1
   20: e35c0000 cmp ip, # 0
   24: 1afffff8 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, n ° 1
   40: e490c004 ldr ip, [r0], n ° 4
   44: e08c3003 add r3, ip, r3
   48: e2c11000 sbc r1, r1, # 0
   4c: e182c001 orr ip, r2, r1
   50: e35c0000 cmp ip, # 0
   54: 1afffff8 bne 3c
   58: e1a00003 mov r0, r3
   5c: e12fff1e bx lr

Vous remarquerez peut-être que le compilateur a produit exactement le même code, le même pointeur ou le même offset. Et en changeant de compilateur, j'étais mieux loti que de changer l'indexation pointeur / tableau. Je pense que llvm aurait pu faire un peu mieux, il va falloir que je l'étudie un peu plus pour comprendre ce que mon code a provoqué.

MODIFIER:

J'espérais que le compilateur utilise au minimum l'instruction ldr rd, [rs], n ° 4 qui favorise les pointeurs, et espérais que le compilateur verrait qu'il pourrait détruire l'adresse du tableau et le traiter ainsi comme un pointeur plutôt que comme un offset dans un tableau (et utilisez l'instruction ci-dessus, qui est fondamentalement ce que clang / llvm a fait). Ou si elle utilisait le tableau, elle utiliserait l'instruction ldr rd, [rm, rn]. Fondamentalement, nous espérions qu'un des compilateurs générerait l'une de ces solutions:


 funa:
     mov r1, # 0
     mov r2, # 1000
 funa_loop:
     ldr r3, [r0], n ° 4
     append r1, r1, r3
     sous-marins r2, r2, n ° 1
     bne funa_loop
     mov r0, r1
     bx lr

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

 func:
     mov r1, # 0
     mov r2, # 4000
     sous-marins r2, r2, n ° 4
 func_loop:
     beq func_done
     ldr r3, [r0, r2]
     append r1, r1, r3
     sous-marins r2, r2, n ° 4
     b func_loop
 func_done:
     mov r0, r1
     bx lr

Je ne suis pas tout à fait arrivé mais je me suis approché C'était un exercice amusant. Notez ce qui précède est tout assembleur ARM.

En général, (pas mon exemple de code C spécifique et pas nécessairement un ARM), un certain nombre d'architectures populaires auront une charge à partir d'une adresse basée sur un registre (ldr r0, [r1]) et une charge avec un registre index / offset (ldr r0, [r1, r2]) où l'adresse est la sum des deux registres. un registre correspond idéalement à l'adresse de base du tableau et le second à l'index / offset. La première charge du registre se prête aux pointeurs, la dernière aux tableaux. si votre programme C ne va PAS changer ou déplacer le pointeur ou l'index, dans les deux cas, cela signifie une adresse statique calculée, puis un chargement normal est utilisé, le tableau et le pointeur doivent produire les mêmes instructions. Pour le cas le plus intéressant de changer le pointeur / index.

 Aiguille

 ldr r0, [r1]
 ...
 append r1, r1, un certain nombre

 Indice de tableau

 ldr r0, [r1, r2]
 ...
 append r2, r2, un certain nombre

(remplacez la charge par un magasin et l'addition par un sous si nécessaire)

Certaines architectures n’ont pas d’instruction d’indexation de registre à trois registres, vous devez donc faire quelque chose comme:

 index de tableau:
 mov r2, r1
 ...
 ldr r0, [r2]
 ...
 append r2, r2, un certain nombre

Ou selon le compilateur, cela peut devenir très mauvais, surtout si vous comstackz pour le débogage ou sans optimisations, et en supposant que vous n'avez pas de registre à trois registres

 index de tableau:
 mov r2, # 0
 ...
 mov r3, r1
 append r3, r2
 ldr r4, [r3]
 ...
 append r2, un nombre

Il est donc fort possible que les deux approches soient égales. Comme on le voit sur l’ARM, il peut combiner les deux instructions de pointeur (dans les limites de l’immédiat) en un seul élément, ce qui le rend un peu plus rapide. La solution d'indexage de tableau brûle plus de registres et, en fonction du nombre de registres disponibles pour l'architecture qui vous oblige à échanger des registres vers la stack plus tôt et plus souvent (qu'avec des pointeurs), vous ralentissant encore plus. Si vous ne craignez pas de détruire l'adresse de base, la solution au pointeur pourrait vous donner un avantage en termes de performances. Cela a beaucoup à voir avec votre code et le compilateur. Pour moi, la lisibilité entre en jeu et je pense que les tableaux sont plus faciles à lire et à suivre. Deuxièmement, dois-je conserver ce pointeur pour libérer un malloc ou pour repasser par cette mémoire, etc. Si tel est le cas, j'utiliserai probablement un tableau avec un index, si c'est un passage unique et que je ne me soucie pas de détruire l'adresse de base, j'utiliserai un pointeur. Comme vous l'avez vu plus haut avec le code généré par le compilateur, si les performances sont critiques, codez quand même manuellement la solution dans l'assembleur (sur la base des approches suggérées en laissant les compilateurs l'essayer en premier).

Le modèle le plus rapide dépend totalement du système, mais les deux sont fonctionnellement équivalents et je serais vraiment surpris si l’un d’entre eux était réellement plus rapide. C’est le code

myArr[index] 

Est complètement équivalent à

 *(&myArr[0] + index) 

De même, l’écriture

 *ptr 

Est équivalent à l’écriture

 ptr[0] 

La plupart des compilateurs sont assez intelligents pour comprendre cela, alors je serais surpris si l’un était plus rapide qu’un autre.

Plus important encore, vous ne devriez probablement pas être trop inquiet à ce sujet. Inquiétez-vous des optimisations une fois que vous avez tout fait fonctionner. Si vous constatez que les access aux tableaux vous tuent vraiment, envisagez de trouver une alternative plus rapide. Sinon, ne vous inquiétez pas pour ça. Il est infiniment plus précieux d’avoir un code propre, lisible et maintenable que d’avoir un code optimisé, sauf si vous avez un besoin pressant d’optimisation.

Des opérations d’index simples sont compilées dans le même code machine sur chaque compilateur que j’ai jamais touché. Par index est généralement recommandé pour la lisibilité.

Les cas plus complexes impliquant une logique différente d’access par pointeur et d’indexation de tableau doivent être examinés au cas par cas. Si vous avez des doutes, profilez votre code – comme toujours.

Il n’y a pas de réponse significative à votre question. Les opérations au niveau de la langue n’ont pas de “vitesse” spécifique qui leur est associée. À eux seuls, ils ne peuvent pas être “plus rapides” ou “plus lents”.

Seules les instructions du processeur peuvent être plus rapides ou plus lentes et seules les instructions du processeur peuvent consumr des cycles du processeur. Afin de reprendre en quelque sorte ce concept de “vitesse” des instructions de la CPU aux opérations au niveau de la langue [ces instructions de la CPU ont été générées à partir de], vous devez en général connaître le contexte. En effet, une même opération au niveau de la langue peut générer des instructions totalement différentes de la CPU dans des contextes différents (sans même mentionner que cela pourrait également dépendre des parameters du compilateur, etc.).

En d’autres termes, postez le code actuel. En tant que question abstraite sans contexte, cela n’a tout simplement aucun sens.

Au niveau le plus bas, ces opérations ont généralement tendance à se comstackr de la même manière. Si vous êtes vraiment intéressé, vous devriez demander à votre compilateur C de générer une sortie d’assemblage (comme avec gcc -S ) afin de pouvoir vérifier, d’autant plus que cela dépend, à tout le moins, de:

  • votre plate-forme cible.
  • votre compilateur.
  • votre niveau d’optimisation.

Vous constaterez que, même s’il existe une différence (ce qui est douteux), ce niveau de micro-optimisation ne vaut généralement pas la peine que vous y consacriez. Vous feriez mieux de faire des macro-optimisations telles que des algorithmes améliorés car c’est le genre de chose qui offre plus de retour sur investissement.

Dans ce genre de situation, où l’effet est susceptible d’être minime, j’optimise toujours pour la lisibilité.

Éliminer explicitement les sous-expressions courantes pourrait fonctionner pour vous. Il peut y avoir une différence si vous utilisez l’architecture x86 ou RISC et la qualité de l’optimiseur.

Lorsque j’écris une routine devant parcourir un tableau ou une structure indexée, je calcule un pointeur sur la base du membre tableau / structure et l’utilise pour l’adresse. Le cas de base

 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 

peut être affiné pour (c’est-à-dire aider le compilateur à produire un meilleur code):

 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 

Ceci est juste pour illustrer et la simplicité du code générerait probablement le pointeur implicitement, mais si la routine est plus complexe, cela pourrait ne pas être le cas. Utiliser "list [i]". comme dans le premier exemple, vous exécuteriez (sur le x86) le risque (RISC haha) du compilateur ne disposant pas de suffisamment de registres pour générer et stocker l'adresse une fois, au lieu de la générer pour chaque référence. Pour le cas x86, une variable locale est nécessaire pour stocker le pointeur et peu de compilateurs créeront des variables de stack, sauf indication contraire explicite. Sur RISC, le compilateur dispose de nombreux registres et décide généralement qu'il vaut la peine de créer (et de conserver) le pointeur une fois pour chaque itération.

La boucle peut être affinée davantage:

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

Cette construction est dépourvue de frais généraux de calcul d'adresse. "pList + = 1" (d'autres pourraient préférer "++ pList") provoquent l'ajout d'une valeur constante (égale à la taille d'une ligne / d'un membre individuel) à pList.

Et plus loin:

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

Ce qui élimine l'incrément d'index et le remplace par une multiplication à l'extérieur et une division à l'intérieur de la boucle (exécutée une seule fois, dans la construction de retour).

Maintenant, avant que tous les optimiseurs ne commencent à crier au meurtre, mon idée est que ce qui est acceptable construit est déterminé par la taille et la complexité de la fonction dans laquelle ils résident. Je ne considérerais probablement pas cette construction dans une fonction de 300 lignes assez complexe au départ, mais dans une situation telle que celle décrite ci-dessus? Si les recherches représentent une partie importante du traitement global? Si les accélérations sont assez grandes?

Alors pourquoi pas? Avantages et inconvénients C'est toujours pour et contre. Faire le meilleur d'eux. Absolus? Rarement (si jamais).

Même. C’est tout O (1), et le temps d’horloge est négligeable. Vous accédez essentiellement à l’adresse mémoire.

Lors de l’access à un tableau via un index, vous effectuez en réalité deux opérations: une addition (en ajoutant l’index à l’adresse du tableau de base), puis un access à la mémoire (en train de lire ou d’écrire ce qui se trouve à l’adresse résultante). Je suppose que lorsque vous parlez d’access par pointeur, vous voulez dire que vous avez déjà le pointeur sur l’élément cible. Ainsi, logiquement, l’utilisation du pointeur enregistre la partie “addition” et devrait donc être plus rapide, ou du moins pas plus lente.

Toutefois…

En gros, dans un ordinateur moderne, l’access à la mémoire est beaucoup plus coûteux qu’un ajout (surtout s’il sort des caches), de sorte que la différence, le cas échéant, sera faible. Sur certaines architectures (x86 ou PowerPC, par exemple), l’addition et l’access à la mémoire peuvent être combinés en un seul code opération. Les choses seront également différentes, selon que l’adresse du tableau est une constante de compilation (c’est-à-dire que le tableau n’est pas une donnée constante, mais est déclaré en tant que variable globale, par opposition à un bloc obtenu avec malloc() ). L’utilisation d’un tableau peut aider le compilateur à trouver un meilleur code, en ce qui concerne un pointeur générique (en particulier lorsque le mot-clé ressortingct est utilisé). Le contexte a une influence énorme (par exemple combien de registres libres il y a à ce moment là?).

Alors:

  • Il n’y a pas de réponse absolue à votre question. Vous devez essayer de prendre des mesures.
  • S’il existe une différence détectable (il est probable qu’il n’y en aura pas), il est difficile de prédire dans quelle direction, et cela dépend d’un grand nombre de facteurs externes, notamment la version spécifique du compilateur et les indicateurs d’optimisation, l’architecture et le modèle de processeur, mise en page de la mémoire et ainsi de suite.
  • Vous ne pourrez pas obtenir un gain d’optimisation fiable sans une connaissance assez approfondie de l’assemblage et un peu de théorie de la compilation.
  • Vous devez d’abord vous concentrer sur la création d’un code correct , puis vous préoccuper uniquement de l’optimisation. et il n’y a pas de problème de performance tant qu’il n’a pas été dûment mesuré dans des conditions réalistes.