Efficacité: tableaux vs pointeurs

Question

L'accès à la mémoire par le biais de pointeurs est dit pour être plus efficace que l'accès à la mémoire par le biais d'un tableau. Je suis en train d'apprendre le C et le ci-dessus est indiqué dans le K&R. Spécifiquement qu'ils disent

Toute opération qui peut être réalisée par des indices de tableaux peut également être fait avec des pointeurs. Le pointeur de la version sera en général plus rapide

J'ai démonté le code suivant à l'aide de visual C++.(Le mien est un 686 processeur. J'ai désactivé toutes les optimisations.)

int a[10], *p = a, temp;

void foo()
{
    temp = a[0];
    temp = *p;
}

À ma grande surprise je vois que l'accès à la mémoire par le biais d'un pointeur prend 3 instructions pour les deux prises par l'accès à la mémoire par le biais d'un tableau. Ci-dessous est le code correspondant.

; 5    : temp = a[0];

    mov eax, DWORD PTR _a
    mov DWORD PTR _temp, eax

; 6    : temp = *p;

    mov eax, DWORD PTR _p
    mov ecx, DWORD PTR [eax]
    mov DWORD PTR _temp, ecx

Merci de m'aider à comprendre. Ce qui me manque ici??

---

Comme l'ont souligné de nombreuses réponses et commentaires, j'ai utilisé un moment de la compilation constante que l'index de tableau rendant ainsi sans doute plus facile pour l'accès à travers un tableau. Ci-dessous est le code assembleur avec une variable que l'index. J'ai maintenant, en nombre égal, des instructions pour l'accès au travers de l'aiguille et de tableaux. Mes questions plus larges tient toujours bon. L'accès à la mémoire par le biais d'un pointeur n'est pas prêt de lui-même comme étant plus efficace.

; 7    :        temp = a[i];

    mov eax, DWORD PTR _i
    mov ecx, DWORD PTR _a[eax*4]
    mov DWORD PTR _temp, ecx

; 8    : 
; 9    :    
; 10   :        temp = *p;

    mov eax, DWORD PTR _p
    mov ecx, DWORD PTR [eax]
    mov DWORD PTR _temp, ecx

Answer 1

L'accès à la mémoire par le biais de pointeurs est dit pour être plus efficace que l'accès à la mémoire par le biais d'un tableau.

Cela a pu être vrai dans le passé, lorsque les compilateurs ont été relativement stupides bêtes. Vous avez seulement besoin de regarder le code de sortie par gcc en haute modes d'optimisation de savoir qu'il n'est plus vrai. Certaines de que le code est très dur à comprendre, mais, une fois que vous faites, son éclat est évident.

Un décent compilateur génère le même code pour pointeur accès et accès à des tableaux et vous devriez probablement pas se soucier de ce niveau de performance. Les gens qui écrivent des compilateurs savoir beaucoup plus au sujet de leurs architectures cibles que nous, simples mortels. Se concentrer davantage sur le niveau macro lors de l'optimisation de votre code (algorithme de sélection et ainsi de suite) et la confiance dans l'outil de les décideurs à faire leur travail.

---

En fait, je suis surprise de voir que le compilateur n'a pas d'optimiser l'ensemble de la

temp = a[0];

ligne hors de l'existence depuis temp est écrit dans le très à côté de la ligne avec une valeur différente et a n'est en aucune façon marquée volatile.

Je me souviens d'une légende urbaine, il y a longtemps sur un point de référence pour la dernière VAX compilateur Fortran (montrant mon âge ici) qui a surclassé ses concurrents par plusieurs ordres de grandeur.

S'avère le compilateur déduit que le résultat de l'indice de référence de calcul n'a pas été utilisé anyhwere donc optimisé l'ensemble de la boucle de calcul dans l'oubli. D'où une amélioration substantielle de la vitesse de course.

---

Mise à jour: La raison qui unoptimized code est plus efficace dans votre cas particulier est à cause de la façon dont vous trouverez la localisation. a sera à un endroit fixe a décidé, lors de lien/temps de charge, et la référence à il sera fixé à la même heure. Donc, a[0] ou, en fait, a[any constant] sera à un emplacement fixe.

Et p lui-même sera aussi à un emplacement fixe pour la même raison. Mais *p (le contenu de p) est variable et, par conséquent, aura un supplément de recherche concernées de trouver le bon emplacement de la mémoire.

Vous trouverez probablement que le fait d'avoir encore une autre variable x 0 (pas de const) et à l'aide de a[x] serait également introduire des calculs supplémentaires.

---

Dans un de vos commentaires, vous dites:

De faire comme vous l'avez suggéré, a entraîné 3 instructions pour l'accès à la mémoire par le biais de réseaux de trop (fetch index, récupère la valeur de l'élément de tableau, stocker dans le temp). Mais je suis toujours incapable de voir l'efficacité. :-(

Ma réponse à cela est que vous avez très probablement ne pas voir une efficacité dans l'utilisation de pointeurs. Les compilateurs modernes sont plus à la tâche de trouver que les opérations de matrice et les opérations de pointeur peut être tourné dans le même sous-jacent du code machine.

En fait, sans optimisation activée, le pointeur de code peut être moins efficace. Considérer les traductions suivantes:

int *pa, i, a[10];

for (i = 0; i < 10; i++)
    a[i] = 100;
/*
    movl    $0, -16(%ebp)              ; this is i, init to 0
L2:
    cmpl    $9, -16(%ebp)              ; from 0 to 9
    jg      L3
    movl    -16(%ebp), %eax            ; load i into register
    movl    $100, -72(%ebp,%eax,4)     ; store 100 based on array/i
    leal    -16(%ebp), %eax            ; get address of i
    incl    (%eax)                     ; increment
    jmp     L2                         ; and loop
L3:
*/

for (pa = a; pa < a + 10; pa++)
    *pa = 100;
/*
    leal    -72(%ebp), %eax
    movl    %eax, -12(%ebp)            ; this is pa, init to &a[0]
L5:
    leal    -72(%ebp), %eax
    addl    $40, %eax
    cmpl    -12(%ebp), %eax            ; is pa at &(a[10])
    jbe     L6                         ; yes, stop
    movl    -12(%ebp), %eax            ; get pa
    movl    $100, (%eax)               ; store 100
    leal    -12(%ebp), %eax            ; get pa
    addl    $4, (%eax)                 ; add 4 (sizeof int)
    jmp     L5                         ; loop around
L6:
*/

À partir de cet exemple, vous pouvez voir que le pointeur exemple est plus long, et donc inutilement. Il charge pa en %eax plusieurs fois sans en changeant et en effet suppléants %eax entre pa et &(a[10]). La valeur par défaut de l'optimisation ici est en fait pas du tout.

Lorsque vous passez à l'optimisation de niveau 2, le code que vous obtenez est:

    xorl    %eax, %eax
L5:
    movl    $100, %edx
    movl    %edx, -56(%ebp,%eax,4)
    incl    %eax
    cmpl    $9, %eax
    jle     L5

pour le choix de la version, et:

    leal    -56(%ebp), %eax
    leal    -16(%ebp), %edx
    jmp     L14
L16:
    movl    $100, (%eax)
    addl    $4, %eax
L14:
    cmpl    %eax, %edx
    ja      L16

pour le pointeur de la version.

Je ne vais pas vous faire une analyse sur les cycles d'horloge ici (car c'est trop de travail et je suis fondamentalement paresseux), mais je ferai remarquer une chose. Il n'y a pas une énorme différence dans le code pour les deux versions en termes d'instructions en assembleur et, étant donné les vitesses des Processeurs modernes fonctionnent en réalité, vous ne remarquerez pas la différence, sauf si vous êtes en train de faire des milliards de ces opérations. J'ai toujours tendance à préférer l'écriture de code pour plus de lisibilité et seulement à vous soucier de la performance, si cela devient un problème.

En aparté, que la déclaration de référence:

5.3 les Pointeurs et les Tableaux: Le pointeur de la version sera en général plus rapide, mais, au moins pour les non-initiés, un peu plus difficiles à saisir immédiatement.

remonte aux premières versions de K&R, y compris mon ancienne 1978 l'un où les fonctions sont encore écrit:

getint(pn)
int *pn;
{
    ...
}

Les compilateurs sont venus un bien long chemin depuis l'époque.

Answer 2

Si vous êtes à la programmation des plateformes embarquées, vous apprendrez rapidement que le pointeur de méthode est beaucoup plus rapide que d'utiliser un index.

struct bar a[10], *p;

void foo()
{
    int i;

    // slow loop
    for (i = 0; i < 10; ++i)
        printf( a[i].value);

    // faster loop
    for (p = a; p < &a[10]; ++p)
        printf( p->value);
}

La lenteur de la boucle pour calculer un + i * sizeof(struct bar) à chaque fois à travers, tandis que le second vient d'ajouter sizeof(struct bar) pour p chaque fois. La multiplication des utilisations plus de cycles d'horloge que le complément sur le nombre de processeurs.

Vous avez vraiment commencer à voir des améliorations, si vous faites référence à un[i] à plusieurs reprises à l'intérieur de la boucle. Certains compilateurs ne cache pas que de l'adresse, de sorte qu'il peut l'être de nouveau à plusieurs reprises à l'intérieur de la boucle.

Essayez de mettre à jour votre échantillon d'utiliser une structure de référence et de plusieurs éléments.

Answer 3

Les pointeurs qui s'exprime naturellement simple induction variables, tandis que les indices un peu intrinsèquement besoin de plus sophistiqué des optimisations du compilateur

Dans de nombreux cas, simplement à l'aide d'un indice expression exige qu'une couche supplémentaire sera ajouté au problème. Une boucle qui incrémente la valeur d'un indice, j'ai peut être bien comme une machine d'état, et l'expression a[i] techniquement nécessite, à chaque fois qu'il est utilisé, que j'ai multiplié fois la taille de chaque élément et ajouté à l'adresse de base.

Afin de les transformer en modèle de l'accès à l'utilisation des pointeurs, le compilateur doit analyser la totalité de la boucle et de déterminer que, par exemple, chaque élément est en cours d'accès. Ensuite, le compilateur peut remplacer les multiples instances de multipliant l'indice par la taille de l'élément avec une simple incrémentation de la boucle précédente valeur. Ce processus combine optimisations appelée commune de la sous-expression de l'élimination et de la variable d'induction de réduction de la résistance.

Lors de l'écriture avec des pointeurs, l'ensemble du processus d'optimisation n'est pas nécessaire parce que le programmeur va généralement à quelques pas seulement par le biais de la matrice de départ.

Parfois, le compilateur peut faire l'optimisation et parfois il ne peut pas. Il est plus commun au cours des dernières années d'avoir un système sophistiqué de compilateur à la main, de sorte que le pointeur de code est pas toujours plus rapide.

Parce que arrrays doit généralement être contiguës, un autre avantage pour les pointeurs, c'est à créer progressivement alloué structures composites.

Answer 4

Dans le premier cas, le compilateur connaît directement l'adresse du tableau (qui est également l'adresse du premier élément) et y accède. Dans le second cas, il connaît l'adresse du pointeur et lit la valeur du pointeur qui pointe vers cet emplacement de la mémoire. C'est en fait une indirection supplémentaire, donc c'est probablement plus lent ici.

Answer 5

La vitesse est acquise dans les boucles, la plupart de tous. Lorsque vous utilisez un tableau, vous devez utiliser un compteur qui vous incrément. Pour calculer la position, le système multiplie ce compteur avec la taille de l'élément du tableau, puis ajoute l'adresse du premier élément pour obtenir l'adresse. Avec les pointeurs, tout ce que vous devez faire pour aller à l'élément suivant est d'augmenter le pointeur courant avec la taille de l'élément pour obtenir le suivant, en supposant que tous les éléments sont à côté les uns des autres en mémoire.

L'arithmétique des pointeurs, donc un peu moins de calculs quand vous faites des boucles. Aussi, pour avoir des pointeurs vers la droite de l'élément est plus rapide que l'utilisation d'un index dans un tableau.

Le développement moderne est lentement se débarrasser de nombreuses opérations de pointeur, si. Les processeurs sont de plus en plus vite et les tableaux sont plus faciles à gérer que des pointeurs. En outre, les matrices ont tendance à réduire la quantité de bogues dans le code. Tableau permettra à l'indice de vérifications et assurez-vous que vous n'êtes pas d'accéder à des données à l'extérieur de la matrice.