Entiendo lo que es un puntero de pila, pero ¿para qué se utiliza?

El puntero de la pila apunta a la parte superior de la pila, que almacena datos en lo que llamamos una base "LIFO". Para robar la analogía de otra persona, es como una pila de platos en los que pones y tomas platos en la parte superior. El puntero de la pila, OTOH, apunta al "plato" superior de la pila. Al menos, eso es cierto para x86.

Pero, ¿por qué la computadora / programa "importa" lo que señala el puntero de la pila? En otras palabras, ¿para qué sirve tener el puntero de la pila y saber dónde apunta a servir?

Se agradecería una explicación comprensible para los programadores de C.

¿Para qué sirve realmente esta pila, en lugar de explicar su estructura?

Usted tiene muchas respuestas que describen con precisión la estructura de los datos almacenados en la pila, lo que noto es lo opuesto a la pregunta que hizo.

El propósito al que sirve la pila es: la pila es parte de la reificación de la continuación en un lenguaje sin rutinas .

Vamos a desempaquetar eso.

La continuación es simplemente la respuesta a la pregunta "¿qué va a suceder después en mi programa?" En cada punto de cada programa, algo va a suceder después. Se van a calcular dos operandos, luego el programa continúa calculando su suma, y ​​luego el programa continúa asignando la suma a una variable, y luego ... y así sucesivamente.

Reificación es solo una palabra muy falsa para hacer una implementación concreta de un concepto abstracto. "¿Qué pasa después?" es un concepto abstracto; La forma en que se presenta la pila es parte de cómo ese concepto abstracto se convierte en una máquina real que realmente computa las cosas.

Las corutinas son funciones que pueden recordar dónde estaban, ceder el control a otra corutina por un tiempo y luego reanudar donde se quedaron más tarde, pero no necesariamente inmediatamente después de los rendimientos de corutina llamados. Piense en "retorno de rendimiento" o "espera" en C #, que debe recordar dónde estaban cuando se solicita el siguiente elemento o se completa la operación asincrónica. Los idiomas con corutinas o características de lenguaje similares requieren estructuras de datos más avanzadas que una pila para implementar la continuación.

¿Cómo implementa una pila la continuación? Otras respuestas dicen cómo. La pila almacena (1) valores de variables y temporales cuyas vidas se sabe que no son mayores que la activación del método actual, y (2) la dirección del código de continuación asociado con la activación del método más reciente. En idiomas con manejo de excepciones, la pila también puede almacenar información sobre la "continuación de error", es decir, lo que el programa hará a continuación cuando ocurra una situación excepcional.

Permítanme aprovechar esta oportunidad para señalar que la pila no les dice "¿de dónde vine?" - aunque a menudo se usa tanto en la depuración. La pila le indica a dónde irá a continuación y cuáles serán los valores de las variables de activación cuando llegue allí . El hecho de que, en un idioma sin rutinas, el lugar al que va a continuación es casi siempre de donde viene hace que este tipo de depuración sea más fácil. Pero no es necesario que un compilador almacene información sobre el origen del control si puede escapar sin hacerlo. Las optimizaciones de llamadas de cola, por ejemplo, destruyen información sobre el origen del control del programa.

¿Por qué usamos la pila para implementar la continuación en lenguajes sin rutinas? Debido a que la característica de la activación síncrona de los métodos es que el patrón de "suspender el método actual, activar otro método, reanudar el método actual conociendo el resultado del método activado" cuando está compuesto lógicamente forma una pila de activaciones. Hacer una estructura de datos que implemente este comportamiento de pila es muy barato y fácil. ¿Por qué es tan barato y fácil? Debido a que los conjuntos de chips han sido diseñados por muchas décadas específicamente para facilitar este tipo de programación para los escritores de compiladores.

El uso más básico de stack es almacenar la dirección de retorno de las funciones:

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

y desde el punto de vista C esto es todo. Desde el punto de vista del compilador:

• todos los argumentos de la función son pasados ​​por los registros de la CPU: si no hay suficientes registros, los argumentos se colocarán en la pila
• después de que la función finaliza (la mayoría) los registros deben tener los mismos valores que antes de ingresarla, por lo que los registros usados ​​se respaldan en la pila

Y desde el punto de vista del sistema operativo: el programa se puede interrumpir en cualquier momento, por lo que, una vez que hayamos terminado con la tarea del sistema, tenemos que restaurar el estado de la CPU, así que vamos a almacenar todo en la pila

Todo esto funciona ya que no nos importa cuántos elementos ya están en la pila o cuántos elementos agregará alguien más en el futuro, solo necesitamos saber cuánto movimos el puntero de la pila y restaurarlo después de que hayamos terminado.

LIFO vs FIFO

LIFO significa Last In, First Out. Como en, el último elemento puesto en la pila es el primer elemento sacado de la pila.

Lo que describiste con tu analogía de platos (en la primera revisión ), es una cola o FIFO, Primero en entrar, Primero en salir.

La principal diferencia entre los dos es que el LIFO / stack empuja (inserta) y hace estallar (elimina) desde el mismo extremo, y un FIFO / cola lo hace desde extremos opuestos.

// Both:

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

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

El puntero de la pila

Echemos un vistazo a lo que sucede debajo del capó de la pila. Aquí hay un poco de memoria, cada cuadro es una dirección:

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

Y hay un puntero de pila que apunta al final de la pila actualmente vacía (si la pila crece o disminuye no es particularmente relevante aquí, por lo que ignoraremos eso, pero, por supuesto, en el mundo real, eso determina qué operación agrega , y que resta del SP).

Así que empujemos de a, b, and cnuevo. Gráficos a la izquierda, operación de "alto nivel" en el medio, pseudocódigo C-ish a la derecha:

...[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

Como puede ver, cada vez pushque insertamos el argumento en la ubicación a la que apunta actualmente el puntero de la pila, y ajusta el puntero de la pila para que apunte a la siguiente ubicación.

Ahora hagamos estallar:

...[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

Popes lo contrario de push, ajusta el puntero de la pila para apuntar a la ubicación anterior y elimina el elemento que estaba allí (generalmente para devolverlo a quien llamó pop).

Probablemente lo hayas notado by ctodavía estás en la memoria. Solo quiero asegurarte que esos no son errores tipográficos. Volveremos a eso en breve.

La vida sin un puntero de pila

Veamos qué sucede si no tenemos un puntero de pila. Comenzando con empujar nuevamente:

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

Er, hmm ... si no tenemos un puntero de pila, entonces no podemos mover algo a la dirección a la que apunta. Quizás podamos usar un puntero que apunte a la base en lugar de a la parte superior.

...[ ][ ][ ][ ]...                       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

UH oh. Como no podemos cambiar el valor fijo de la base de la pila, simplemente sobrescribimos apresionando ba la misma ubicación.

Bueno, ¿por qué no hacemos un seguimiento de cuántas veces hemos presionado? Y también necesitaremos hacer un seguimiento de los tiempos que hemos aparecido.

...[ ][ ][ ][ ]...                       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

Bueno, funciona, pero en realidad es bastante similar a antes, excepto que *pointeres más barato que pointer[offset](sin aritmética adicional), sin mencionar que es menos para escribir. Esto me parece una pérdida.

Intentemoslo de nuevo. En lugar de usar el estilo de cadena Pascal para encontrar el final de una colección basada en una matriz (seguimiento de cuántos elementos hay en la colección), intentemos con el estilo de cadena C (escaneo desde el principio hasta el final):

...[ ][ ][ ][ ]...                       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 '('

Puede que ya hayas adivinado el problema aquí. No se garantiza que la memoria no inicializada sea 0. Entonces, cuando buscamos la parte superior para colocar a, terminamos saltando sobre un montón de ubicaciones de memoria no utilizadas que tienen basura aleatoria en ellas. De manera similar, cuando escaneamos hacia la parte superior, terminamos saltando mucho más allá de lo aque acabamos de empujar hasta que finalmente encontramos otra ubicación de memoria que resulta ser 0, y retrocedemos y devolvemos la basura aleatoria justo antes de eso.

Eso es bastante fácil de solucionar, solo tenemos que agregar operaciones Pushy Popasegurarnos de que la parte superior de la pila siempre se actualice para que se marque con un 0, y tenemos que inicializar la pila con dicho terminador. Por supuesto, eso también significa que no podemos tener un 0(o cualquier valor que elijamos como terminador) como un valor real en la pila.

Además de eso, también hemos cambiado lo que eran operaciones O (1) en operaciones O (n).

TL; DR

El puntero de la pila realiza un seguimiento de la parte superior de la pila, donde se produce toda la acción. Hay formas de deshacerse de él ( bp[count]y topsiguen siendo esencialmente el puntero de la pila), pero ambos terminan siendo más complicados y más lentos que simplemente tener el puntero de la pila. Y no saber dónde está la parte superior de la pila significa que no puedes usar la pila.

Nota: El puntero de la pila que apunta al "fondo" de la pila de tiempo de ejecución en x86 podría ser una idea errónea relacionada con que toda la pila de tiempo de ejecución está al revés. En otras palabras, la base de la pila se coloca en una dirección de memoria alta, y la punta de la pila crece en direcciones de memoria más bajas. El puntero de la pila hace punto a la punta de la pila donde se produce toda la acción, sólo que la punta se encuentra en una dirección de memoria más baja que la base de la pila.

El puntero de la pila se usa (con el puntero de marco) para la pila de llamadas (siga el enlace a wikipedia, donde hay una buena imagen).

La pila de llamadas contiene marcos de llamadas, que contienen la dirección de retorno, variables locales y otros datos locales (en particular, el contenido derramado de los registros; formales).

Lea también sobre las llamadas de cola (algunas llamadas recursivas de cola no necesitan ningún marco de llamada), manejo de excepciones (como setjmp y longjmp , pueden implicar estallar muchos marcos de pila a la vez), señales e interrupciones y continuaciones . Consulte también las convenciones de llamada y las interfaces binarias de aplicación ( ABI ), en particular la ABI x86-64 (que define que los registros pasan algunos argumentos formales).

Además, codifique algunas funciones simples en C, luego utilícelas gcc -Wall -O -S -fverbose-asm para compilarlas y mire el .s archivo ensamblador generado .

Appel escribió un artículo antiguo de 1986 afirmando que la recolección de basura puede ser más rápida que la asignación de la pila (usando el estilo de paso de continuación en el compilador), pero esto probablemente sea falso en los procesadores x86 de hoy (especialmente debido a los efectos de caché).

Tenga en cuenta que las convenciones de llamadas, las ABI y el diseño de la pila son diferentes en 32 bits i686 y en 64 bits x86-64. Además, las convenciones de llamadas (y quién es responsable de asignar o reventar el marco de la llamada) pueden ser diferentes con diferentes lenguajes (por ejemplo, C, Pascal, Ocaml, SBCL Common Lisp tienen diferentes convenciones de llamadas ...)

Por cierto, las extensiones x86 recientes como AVX están imponiendo restricciones de alineación cada vez más grandes en el puntero de la pila (IIRC, un marco de llamada en x86-64 quiere alinearse a 16 bytes, es decir, dos palabras o punteros).

En términos simples, el programa se preocupa porque está usando esos datos y necesita hacer un seguimiento de dónde encontrarlos.

Si declara variables locales en una función, la pila es donde se almacenan. Además, si llama a otra función, la pila es donde almacena la dirección de retorno para que pueda volver a la función en la que se encontraba cuando finaliza la que llamó y retomar donde la dejó.

Sin el SP, la programación estructurada como la conocemos sería esencialmente imposible. (Podría evitar no tenerlo, pero requeriría implementar su propia versión, por lo que no hay mucha diferencia).

Para la pila del procesador en un procesador x86, la analogía de una pila de platos es realmente inexacta.
Por varias razones (principalmente históricas), la pila del procesador crece desde la parte superior de la memoria hacia la parte inferior de la memoria, por lo que una mejor analogía sería la cadena de eslabones colgando del techo. Al empujar algo sobre la pila, se agrega un eslabón de cadena al eslabón más bajo.

El puntero de la pila se refiere al eslabón más bajo de la cadena y el procesador lo utiliza para "ver" dónde está ese eslabón más bajo, de modo que los eslabones se pueden agregar o quitar sin tener que desplazar toda la cadena desde el techo hacia abajo.

En cierto sentido, dentro de un procesador x86, la pila está al revés, pero se utiliza el umbral de terminología normal de la pila, de modo que el enlace más bajo se conoce como la parte superior de la pila.

Los eslabones de la cadena a los que me referí anteriormente son en realidad células de memoria en una computadora y se utilizan para almacenar variables locales y algunos resultados intermedios de los cálculos. A los programas de computadora les importa dónde está la parte superior de la pila (es decir, dónde se cuelga el enlace más bajo), porque la gran mayoría de las variables a las que una función necesita acceder existen cerca de donde se refiere el puntero de la pila y es deseable un acceso rápido a ellas.

Esta respuesta se refiere específicamente a la puntero de pila de la rosca actual (de la ejecución) .

En los lenguajes de programación de procedimientos, un subproceso generalmente tiene acceso a una pila ¹ para los siguientes propósitos:

• Control de flujo, a saber, "pila de llamadas".
  • Cuando una función llama a otra función, la pila de llamadas recuerda a dónde regresar.
  • Una pila de llamadas es necesaria porque así es como queremos que se comporte una "llamada de función": "retomar donde la dejamos" .
  • Hay otros estilos de programación que no tienen llamadas de función en la mitad de la ejecución (por ejemplo, solo se permite especificar la siguiente función cuando se alcanza el final de la función actual), o no tienen llamadas de función (solo usando goto y saltos condicionales ) Es posible que estos estilos de programación no necesiten una pila de llamadas.
• Parámetros de llamada a funciones.
  • Cuando una función llama a otra función, los parámetros se pueden insertar en la pila.
  • Es necesario que la persona que llama y la persona que llama sigan la misma convención en cuanto a quién es responsable de borrar los parámetros de la pila, cuando finaliza la llamada.
• Las variables locales que viven dentro de una llamada de función.
  • Tenga en cuenta que una variable local que pertenece a una persona que llama puede hacerse accesible a una persona que llama pasando un puntero a esa variable local a la persona que llama.

Nota ¹ : dedicada al uso del hilo, aunque su contenido es completamente legible, y rompible , por otros hilos.

En la programación de ensamblaje, C y C ++, la misma pila puede cumplir los tres propósitos. En algunos otros idiomas, algunos propósitos pueden cumplirse mediante pilas separadas o memoria asignada dinámicamente.

Aquí hay una versión deliberadamente simplificada de para qué se usa la pila.

Imagina la pila como una pila de fichas. El puntero de la pila apunta a la carta superior.

Cuando llamas a una función:

• Escribe la dirección del código inmediatamente después de la línea que llamó a la función en una tarjeta y la puso en la pila. (Es decir, incrementa el puntero de la pila en uno y escribe la dirección donde apunta)
• Luego, escribe los valores contenidos en los registros en algunas tarjetas y las coloca en la pila. (es decir, incrementa el puntero de la pila por el número de registros y copia el contenido del registro en el lugar al que apunta)
• Luego pones una tarjeta de marcador en la pila. (es decir, guarda el puntero de la pila actual).
• Luego, escribe el valor de cada parámetro con el que se llama la función, uno en una tarjeta, y lo coloca en la pila. (es decir, incrementa el puntero de la pila por el número de parámetros y escribe los parámetros en el lugar al que apunta el puntero de la pila).
• Luego agrega una tarjeta para cada variable local, potencialmente escribiendo el valor inicial en ella. (es decir, incrementa el puntero de la pila por el número de variables locales).

En este punto, se ejecuta el código en la función. El código se compila para saber dónde está cada tarjeta en relación con la parte superior. Entonces sabe que la variable xes la tercera carta desde la parte superior (es decir, el puntero de la pila - 3) y que el parámetro yes la sexta carta desde la parte superior (es decir, el puntero de la pila - 6.)

Este método significa que la dirección de cada variable o parámetro local no necesita ser incorporada en el código. En cambio, todos estos elementos de datos se direccionan en relación con el puntero de la pila.

Cuando la función regresa, la operación inversa es simplemente:

• Busca la tarjeta de marcador y tira todas las cartas sobre ella. (es decir, establezca el puntero de la pila en la dirección guardada).
• Restaure los registros de las tarjetas guardadas antes y deséchelas. (es decir, restar un valor fijo del puntero de la pila)
• Comience a ejecutar el código desde la dirección en la tarjeta en la parte superior y luego bótelo. (es decir, restar 1 del puntero de la pila).

La pila ahora está de vuelta en el estado que tenía antes de que se llamara a la función.

Cuando considere esto, tenga en cuenta dos cosas: la asignación y la desasignación de locales es una operación extremadamente rápida, ya que solo está sumando o restando un número del puntero de la pila. También tenga en cuenta cómo funciona naturalmente con la recursividad

Esto se simplifica demasiado con fines explicativos. En la práctica, los parámetros y los locales se pueden colocar en registros como una optimización, y el puntero de la pila generalmente se incrementará y disminuirá en función del tamaño de la palabra de la máquina, no uno. (Por nombrar un par de cosas).

Los lenguajes de programación modernos, como bien saben, admiten el concepto de llamadas de subrutina (a menudo llamadas "llamadas de función"). Esto significa que:

1. En medio de algún código, puede llamar a alguna otra función en su programa;
2. Esa función no sabe explícitamente de dónde fue llamada;
3. Sin embargo, cuando se realiza su trabajo y está listo return, el control vuelve al punto exacto donde se inició la llamada, con todos los valores de las variables locales vigentes como cuando se inició la llamada.

¿Cómo hace un seguimiento de eso la computadora? Mantiene un registro continuo de las funciones que esperan qué llamadas volver. Este registro es una pila y ya que es uno tan importante, que normalmente llaman la pila.

Y dado que este patrón de llamada / retorno es tan importante, las CPU se han diseñado durante mucho tiempo para proporcionarle soporte de hardware especial. El puntero de la pila es una característica de hardware en las CPU: un registro dedicado exclusivamente a realizar un seguimiento de la parte superior de la pila y utilizado por las instrucciones de la CPU para bifurcarse en una subrutina y regresar de ella.