Je comprends ce qu'est un pointeur de pile - mais à quoi sert-il?

Le pointeur de pile pointe vers le haut de la pile, qui stocke les données sur ce que nous appelons une base "LIFO". Pour voler l'analogie de quelqu'un d'autre, c'est comme une pile de plats dans laquelle vous mettez et prenez des plats au sommet. Le pointeur de pile, OTOH, pointe vers le "plat" supérieur de la pile. Du moins, c'est vrai pour x86.

Mais pourquoi l'ordinateur / programme "se soucie" de ce que pointe le pointeur de pile? En d'autres termes, à quoi sert le pointeur de pile et savoir où il pointe pour servir?

Une explication compréhensible par les programmeurs C serait appréciée.

À quoi sert cette pile, au lieu d'expliquer sa structure?

Vous avez de nombreuses réponses qui décrivent avec précision la structure des données stockées sur la pile, ce qui, je le note, est à l'opposé de la question que vous avez posée.

Le but de la pile est: la pile fait partie de la réification de la continuation dans une langue sans coroutines .

Déballons cela.

La suite est simplement posée, la réponse à la question "que va-t-il se passer ensuite dans mon programme?" À chaque étape de chaque programme, quelque chose va se passer ensuite. Deux opérandes vont être calculés, puis le programme continue en calculant leur somme, puis le programme continue en affectant la somme à une variable, puis ... et ainsi de suite.

La réification est juste un mot de haute valeur pour faire une mise en œuvre concrète d'un concept abstrait. "Que se passe-t-il ensuite?" est un concept abstrait; la façon dont la pile est disposée fait partie de la façon dont ce concept abstrait est transformé en une véritable machine qui calcule vraiment les choses.

Les coroutines sont des fonctions qui peuvent se rappeler où elles se trouvaient, céder le contrôle à une autre coroutine pendant un certain temps, puis reprendre là où elles se sont arrêtées plus tard, mais pas nécessairement immédiatement après les rendements de la coroutine. Pensez à "return return" ou "wait" en C #, qui doivent se rappeler où ils étaient lorsque l'élément suivant est demandé ou que l'opération asynchrone se termine. Les langages avec coroutines ou fonctionnalités de langage similaires nécessitent des structures de données plus avancées qu'une pile afin de mettre en œuvre la continuation.

Comment une pile met-elle en œuvre la continuation? D'autres réponses disent comment. La pile stocke (1) les valeurs des variables et des temporelles dont la durée de vie n'est pas supérieure à l'activation de la méthode actuelle, et (2) l'adresse du code de continuation associé à l'activation la plus récente de la méthode. Dans les langues avec gestion des exceptions, la pile peut également stocker des informations sur la "continuation d'erreur" - c'est-à-dire ce que le programme fera ensuite en cas de situation exceptionnelle.

Permettez-moi de saisir cette occasion pour noter que la pile ne vous dit pas "d'où je viens?" - bien qu'il soit souvent utilisé dans le débogage. La pile vous indique où vous allez ensuite et quelles seront les valeurs des variables d'activation lorsque vous y arriverez . Le fait que dans une langue sans coroutines, où vous allez ensuite est presque toujours d'où vous venez, ce genre de débogage est plus facile. Mais il n'est pas nécessaire qu'un compilateur stocke des informations sur la provenance du contrôle s'il peut s'échapper sans le faire. Les optimisations des appels de queue, par exemple, détruisent les informations sur la provenance du contrôle du programme.

Pourquoi utilisons-nous la pile pour implémenter la continuation dans des langues sans coroutines? Parce que la caractéristique de l'activation synchrone des méthodes est que le modèle de "suspendre la méthode actuelle, activer une autre méthode, reprendre la méthode actuelle en connaissant le résultat de la méthode activée" lorsqu'elle est composée avec elle-même forme logiquement une pile d'activations. Créer une structure de données qui implémente ce comportement de type pile est très bon marché et facile. Pourquoi est-ce si bon marché et si facile? Parce que les jeux de puces ont été spécialement conçus pendant de nombreuses décennies pour faciliter ce type de programmation aux rédacteurs de compilateurs.

L'utilisation la plus élémentaire de la pile consiste à stocker l'adresse de retour des fonctions:

void a(){
    sub();
}
void b(){
    sub();
}
void sub() {
    //should i got back to a() or to b()?
}

et du point de vue C c'est tout. Du point de vue du compilateur:

• tous les arguments de fonction sont passés par les registres CPU - s'il n'y a pas assez de registres les arguments seront mis sur la pile
• après la fin de la fonction (la plupart), les registres doivent avoir les mêmes valeurs qu'avant de les saisir - les registres utilisés sont donc sauvegardés sur la pile

Et du point de vue du système d'exploitation: le programme peut être interrompu à tout moment, donc après avoir terminé la tâche système, nous devons restaurer l'état du processeur, permet donc de tout stocker sur la pile

Tout cela fonctionne, car peu importe combien d'éléments sont déjà sur la pile ou combien d'éléments quelqu'un d'autre ajoutera à l'avenir, nous avons juste besoin de savoir combien nous avons déplacé le pointeur de pile et de le restaurer après avoir terminé.

LIFO vs FIFO

LIFO signifie Last In, First Out. Comme dans, le dernier élément placé dans la pile est le premier élément retiré de la pile.

Ce que vous avez décrit avec votre analogie avec les plats (dans la première révision ), c'est une file d'attente ou FIFO, First In, First Out.

La principale différence entre les deux, c'est que le LIFO / pile pousse (insère) et saute (supprime) de la même extrémité, et une FIFO / file d'attente le fait des extrémités opposées.

// Both:

Push(a)
-> [a]
Push(b)
-> [a, b]
Push(c)
-> [a, b, c]

// Stack            // Queue
Pop()               Pop()
-> [a, b]           -> [b, c]

Le pointeur de pile

Jetons un coup d'œil à ce qui se passe sous le capot de la pile. Voici un peu de mémoire, chaque case est une adresse:

...[ ][ ][ ][ ]...                       char* sp;
    ^- Stack Pointer (SP)

Et il y a un pointeur de pile pointant au bas de la pile actuellement vide (que la pile grandisse ou ne soit pas particulièrement pertinente ici, donc nous l'ignorerons, mais bien sûr dans le monde réel, cela détermine quelle opération ajoute , et qui soustrait du SP).

Alors poussons a, b, and cencore. Graphique à gauche, opération "haut niveau" au milieu, pseudo-code C-ish à droite:

...[a][ ][ ][ ]...        Push('a')      *sp = 'a';
    ^- SP
...[a][ ][ ][ ]...                       ++sp;
       ^- SP

...[a][b][ ][ ]...        Push('b')      *sp = 'b';
       ^- SP
...[a][b][ ][ ]...                       ++sp;
          ^- SP

...[a][b][c][ ]...        Push('c')      *sp = 'c';
          ^- SP
...[a][b][c][ ]...                       ++sp;
             ^- SP

Comme vous pouvez le voir, chaque fois que nous le faisons push, il insère l'argument à l'emplacement vers lequel pointe le pointeur de pile et ajuste le pointeur de pile pour pointer à l'emplacement suivant.

Voyons maintenant:

...[a][b][c][ ]...        Pop()          --sp;
          ^- SP
...[a][b][c][ ]...                       return *sp; // returns 'c'
          ^- SP
...[a][b][c][ ]...        Pop()          --sp;
       ^- SP
...[a][b][c][ ]...                       return *sp; // returns 'b'
       ^- SP

Popest l'opposé de push, il ajuste le pointeur de pile pour pointer vers l'emplacement précédent et supprime l'élément qui était là (généralement pour le renvoyer à celui qui a appelé pop).

Vous l'avez probablement remarqué bet vous cêtes toujours en mémoire. Je veux juste vous assurer que ce ne sont pas des fautes de frappe. Nous y reviendrons sous peu.

La vie sans pointeur de pile

Voyons ce qui se passe si nous n'avons pas de pointeur de pile. En commençant par pousser à nouveau:

...[ ][ ][ ][ ]...
...[ ][ ][ ][ ]...        Push(a)        ? = 'a';

Euh, hmm ... si nous n'avons pas de pointeur de pile, nous ne pouvons pas déplacer quelque chose à l'adresse vers laquelle il pointe. Peut-être pouvons-nous utiliser un pointeur qui pointe vers la base au lieu du haut.

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);

...[a][ ][ ][ ]...        Push(a)        *bp = 'a';
    ^- bp
// No stack pointer, so no need to update it.
...[b][ ][ ][ ]...        Push(b)        *bp = 'b';
    ^- bp

Euh oh. Comme nous ne pouvons pas changer la valeur fixe de la base de la pile, nous avons simplement écrasé le aen poussant bau même emplacement.

Eh bien, pourquoi ne suivons-nous pas le nombre de fois où nous avons poussé. Et nous devrons également garder une trace des moments où nous sommes apparus.

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);
                                         int count = 0;

...[a][ ][ ][ ]...        Push(a)        bp[count] = 'a';
    ^- bp
...[a][ ][ ][ ]...                       ++count;
    ^- bp
...[a][b][ ][ ]...        Push(a)        bp[count] = 'b';
    ^- bp
...[a][b][ ][ ]...                       ++count;
    ^- bp
...[a][b][ ][ ]...        Pop()          --count;
    ^- bp
...[a][b][ ][ ]...                       return bp[count]; //returns b
    ^- bp

Eh bien, cela fonctionne, mais c'est en fait assez similaire à avant, sauf qu'il *pointerest moins cher que pointer[offset](pas d'arithmétique supplémentaire), sans parler du fait qu'il est moins à taper. Cela me semble une perte.

Essayons encore. Au lieu d'utiliser le style de chaîne Pascal pour trouver la fin d'une collection basée sur un tableau (suivi du nombre d'éléments dans la collection), essayons le style de chaîne C (analyse du début à la fin):

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);

...[ ][ ][ ][ ]...        Push(a)        char* top = bp;
    ^- bp, top
                                         while(*top != 0) { ++top; }
...[ ][ ][ ][a]...                       *top = 'a';
    ^- bp    ^- top

...[ ][ ][ ][ ]...        Pop()          char* top = bp;
    ^- bp, top
                                         while(*top != 0) { ++top; }
...[ ][ ][ ][a]...                       --top;
    ^- bp       ^- top                   return *top; // returns '('

Vous avez peut-être déjà deviné le problème ici. La mémoire non initialisée n'est pas garantie d'être 0. Ainsi, lorsque nous recherchons le haut à placer a, nous finissons par ignorer un tas d'emplacements de mémoire inutilisés contenant des déchets aléatoires. De même, lorsque nous numérisons vers le haut, nous finissons par sauter bien au-delà de ce que anous venons de pousser jusqu'à ce que nous trouvions enfin un autre emplacement de mémoire qui se trouve être 0, et reculons et renvoyons les déchets aléatoires juste avant cela.

C'est assez facile à corriger, il nous suffit d'ajouter des opérations Pushet Popde nous assurer que le haut de la pile est toujours mis à jour pour être marqué d'un 0, et nous devons initialiser la pile avec un tel terminateur. Bien sûr, cela signifie également que nous ne pouvons pas avoir 0(ou la valeur que nous choisissons comme terminateur) comme valeur réelle dans la pile.

En plus de cela, nous avons également changé les opérations O (1) en opérations O (n).

TL; DR

Le pointeur de pile garde une trace du haut de la pile, où se déroule toute l'action. Il existe des moyens de s'en débarrasser ( bp[count]et topsont essentiellement toujours le pointeur de pile), mais ils finissent tous les deux par être plus compliqués et plus lents que d'avoir simplement le pointeur de pile. Et ne pas savoir où se trouve le haut de la pile signifie que vous ne pouvez pas utiliser la pile.

Remarque: Le pointeur de pile pointant vers le "bas" de la pile d'exécution dans x86 peut être une idée fausse liée au fait que la pile d'exécution entière est à l'envers. En d'autres termes, la base de la pile est placée à une adresse mémoire élevée, et la pointe de la pile se développe en adresses mémoire inférieures. Le pointeur de pile ne pointe à l'extrémité de la pile où l'action se produit, il suffit que la pointe se trouve à une adresse mémoire inférieure à la base de la pile.

Le pointeur de pile est utilisé (avec le pointeur de trame) pour la pile d'appel (suivez le lien vers wikipedia, où il y a une bonne image).

La pile d'appels contient des trames d'appel, qui contiennent l'adresse de retour, des variables locales et d'autres données locales (en particulier, le contenu renversé des registres; les formels).

Lisez également les appels de queue (certains appels récursifs de queue n'ont pas besoin de trame d'appel), la gestion des exceptions (comme setjmp et longjmp , ils peuvent impliquer de faire apparaître plusieurs trames de pile à la fois), les signaux et les interruptions et les continuations . Voir aussi les conventions d'appel et les interfaces binaires d'application (ABI), en particulier l' ABI x86-64 (qui définit que certains arguments formels sont passés par les registres).

Aussi, codez des fonctions simples en C, puis utilisez-les gcc -Wall -O -S -fverbose-asm pour les compiler et examinez le .s fichier assembleur généré .

Appel a écrit un vieux document de 1986 affirmant que la récupération de place peut être plus rapide que l'allocation de pile (en utilisant le style de passage en continu dans le compilateur), mais cela est probablement faux sur les processeurs x86 d'aujourd'hui (notamment en raison des effets de cache).

Notez que les conventions d'appel, les ABI et la disposition de la pile sont différentes sur i686 32 bits et sur x86-64 64 bits. De plus, les conventions d'appel (et qui est responsable de l'allocation ou du saut de la trame d'appel) peuvent être différentes selon les langages (par exemple, C, Pascal, Ocaml, SBCL Common Lisp ont des conventions d'appel différentes ....)

BTW, les extensions x86 récentes comme AVX imposent des contraintes d'alignement de plus en plus importantes au pointeur de pile (IIRC, une trame d'appel sur x86-64 veut être alignée sur 16 octets, soit deux mots ou pointeurs).

En termes simples, le programme se soucie car il utilise ces données et doit savoir où les trouver.

Si vous déclarez des variables locales dans une fonction, la pile est l'endroit où elles sont stockées. De plus, si vous appelez une autre fonction, la pile est l'endroit où elle stocke l'adresse de retour afin qu'elle puisse revenir à la fonction dans laquelle vous étiez lorsque celle que vous avez appelée est terminée et reprendre là où elle s'était arrêtée.

Sans le SP, une programmation structurée telle que nous la connaissons serait pratiquement impossible. (Vous pouvez contourner le fait de ne pas l'avoir, mais cela nécessiterait à peu près l'implémentation de votre propre version, donc ce n'est pas vraiment une différence.)

Pour la pile de processeur dans un processeur x86, l'analogie d'une pile de plats est vraiment inexacte.
Pour diverses raisons (principalement historiques), la pile du processeur se développe du haut de la mémoire vers le bas de la mémoire, donc une meilleure analogie serait une chaîne de maillons suspendus au plafond. Lorsque vous poussez quelque chose sur la pile, un maillon de chaîne est ajouté au maillon le plus bas.

Le pointeur de pile fait référence au maillon le plus bas de la chaîne et est utilisé par le processeur pour "voir" où se trouve ce maillon le plus bas, de sorte que les maillons peuvent être ajoutés ou supprimés sans avoir à parcourir la chaîne entière du plafond vers le bas.

Dans un sens, à l'intérieur d'un processeur x86, la pile est à l'envers mais le seuil de terminologie de pile normal est utilisé, de sorte que le lien le plus bas est appelé le haut de la pile.

Les maillons de chaîne dont j'ai parlé ci-dessus sont en fait des cellules de mémoire dans un ordinateur et ils sont utilisés pour stocker des variables locales et des résultats intermédiaires de calculs. Les programmes informatiques se soucient de l'endroit où se trouve le haut de la pile (c'est-à-dire où se trouve le lien le plus bas), car la grande majorité des variables auxquelles une fonction doit accéder existent près de l'endroit où le pointeur de la pile fait référence et un accès rapide à ces dernières est souhaitable.

Cette réponse se réfère spécifiquement à la pointeur de pile du fil de courant (d'exécution) .

Dans les langages de programmation procédurale, un thread a généralement accès à une pile ¹ aux fins suivantes:

• Flux de contrôle, à savoir "pile d'appels".
  • Lorsqu'une fonction appelle une autre fonction, la pile d'appels se souvient où retourner.
  • Une pile d'appels est nécessaire parce que c'est ainsi que nous voulons qu'un «appel de fonction» se comporte - «pour reprendre là où nous nous sommes arrêtés» .
  • Il existe d'autres styles de programmation qui n'ont pas d'appels de fonction en cours d'exécution (par exemple, uniquement autorisés à spécifier la fonction suivante lorsque la fin de la fonction actuelle est atteinte), ou n'ont aucun appel de fonction (uniquement en utilisant goto et des sauts conditionnels ). Ces styles de programmation peuvent ne pas avoir besoin d'une pile d'appels.
• Paramètres d'appel de fonction.
  • Lorsqu'une fonction appelle une autre fonction, les paramètres peuvent être poussés sur la pile.
  • Il est nécessaire que l'appelant et l'appelé suivent la même convention quant à qui est responsable de la suppression des paramètres de la pile, lorsque l'appel se termine.
• Variables locales qui vivent dans un appel de fonction.
  • Notez qu'une variable locale appartenant à un appelant peut être rendue accessible à un appelé en passant un pointeur vers cette variable locale à l'appelé.

Note ¹ : dédié à l'utilisation du fil, bien que son contenu soit entièrement lisible - et smashable - par d'autres fils.

Dans la programmation d'assemblage, C et C ++, les trois objectifs peuvent être remplis par la même pile. Dans certaines autres langues, certains objectifs peuvent être remplis par des piles distinctes ou une mémoire allouée dynamiquement.

Voici une version délibérément simplifiée de l'utilisation de la pile.

Imaginez la pile comme une pile de fiches. Le pointeur de pile pointe vers la carte du dessus.

Lorsque vous appelez une fonction:

• Vous écrivez l'adresse du code immédiatement après la ligne qui a appelé la fonction sur une carte et la mettez sur la pile. (C'est-à-dire que vous incrémentez le pointeur de pile d'une unité et écrivez l'adresse à laquelle il pointe)
• Ensuite, vous écrivez les valeurs contenues dans les registres sur certaines cartes et les mettez sur la pile. (c'est-à-dire que vous incrémentez le pointeur de pile du nombre de registres et copiez le contenu du registre à l'endroit vers lequel il pointe)
• Ensuite, vous mettez une carte marqueur sur la pile. (c'est-à-dire que vous enregistrez le pointeur de pile actuel.)
• Ensuite, vous écrivez la valeur de chaque paramètre avec lequel la fonction est appelée, un sur une carte, et la mettez sur la pile. (c'est-à-dire que vous augmentez le pointeur de pile du nombre de paramètres et écrivez les paramètres à l'endroit vers lequel pointe le pointeur de pile.)
• Ensuite, vous ajoutez une carte pour chaque variable locale, en y écrivant potentiellement la valeur initiale. (c'est-à-dire que vous incrémentez le pointeur de pile du nombre de variables locales.)

À ce stade, le code de la fonction s'exécute. Le code est compilé pour savoir où chaque carte est par rapport au sommet. Il sait donc que la variable xest la troisième carte du haut (c'est-à-dire le pointeur de pile - 3) et que le paramètre yest la sixième carte du haut (c'est-à-dire le pointeur de pile - 6.)

Cette méthode signifie que l'adresse de chaque variable ou paramètre local n'a pas besoin d'être intégrée dans le code. Au lieu de cela, tous ces éléments de données sont adressés par rapport au pointeur de pile.

Lorsque la fonction revient, l'opération inverse est simplement:

• Recherchez la carte marqueur et jetez toutes les cartes au-dessus. (c.-à-d. réglez le pointeur de pile sur l'adresse enregistrée.)
• Restaurez les registres des cartes enregistrées précédemment et jetez-les. (c'est-à-dire soustraire une valeur fixe du pointeur de pile)
• Commencez à exécuter le code à partir de l'adresse sur la carte en haut, puis jetez-la. (c'est-à-dire soustraire 1 du pointeur de pile.)

La pile est maintenant de retour dans l'état où elle était avant l'appel de la fonction.

Lorsque vous considérez cela, notez deux choses: l'allocation et la désallocation des sections locales est une opération extrêmement rapide car elle ne fait qu'ajouter ou soustraire un nombre au pointeur de pile. Notez également comment cela fonctionne naturellement avec la récursivité.

Ceci est simplifié à des fins explicatives. Dans la pratique, les paramètres et les sections locales peuvent être placés dans des registres comme optimisation, et le pointeur de pile sera généralement incrémenté et décrémenté par la taille de mot de la machine, pas une. (Pour nommer deux ou trois choses.)

Les langages de programmation modernes, comme vous le savez bien, prennent en charge le concept des appels de sous-programme (le plus souvent appelés "appels de fonction"). Cela signifie que:

1. Au milieu d'un code, vous pouvez appeler une autre fonction de votre programme;
2. Cette fonction ne sait pas explicitement d'où elle a été appelée;
3. Néanmoins, lorsque son travail est terminé et qu'il est terminé return, le contrôle revient au point exact où l'appel a été initié, avec toutes les valeurs des variables locales en vigueur comme lorsque l'appel a été initié.

Comment l'ordinateur garde-t-il cela? Il conserve un enregistrement continu des fonctions en attente des appels à retourner. Cet enregistrement est une pile — et comme il est si important, nous l'appelons normalement la pile.

Et puisque ce modèle d'appel / retour est si important, les processeurs ont longtemps été conçus pour lui fournir un support matériel spécial. Le pointeur de pile est une fonctionnalité matérielle des CPU - un registre exclusivement dédié à garder une trace du haut de la pile et utilisé par les instructions du CPU pour se ramifier dans un sous-programme et en revenir.