¿Cuál es el propósito de una pila? ¿Por qué lo necesitamos?

Así que estoy aprendiendo MSIL ahora mismo para aprender a depurar mis aplicaciones C # .NET.

Siempre me he preguntado: ¿cuál es el propósito de la pila?

Solo para poner mi pregunta en contexto:
¿Por qué hay una transferencia de memoria a pila o "cargando"? Por otro lado, ¿por qué hay una transferencia de la pila a la memoria o "almacenamiento"? ¿Por qué no simplemente tenerlos todos en la memoria?

• ¿Es porque es más rápido?
• ¿Es porque está basado en RAM?
• Por eficiencia?

Estoy tratando de comprender esto para ayudarme a comprender los códigos CIL mucho más profundamente.

ACTUALIZACIÓN: Me gustó tanto esta pregunta que la convertí en el tema de mi blog el 18 de noviembre de 2011 . Gracias por la gran pregunta!

Siempre me he preguntado: ¿cuál es el propósito de la pila?

Supongo que te refieres a la pila de evaluación del lenguaje MSIL, y no a la pila real por subproceso en tiempo de ejecución.

¿Por qué hay una transferencia de memoria a pila o "cargando"? Por otro lado, ¿por qué hay una transferencia de la pila a la memoria o "almacenamiento"? ¿Por qué no simplemente tenerlos todos en la memoria?

MSIL es un lenguaje de "máquina virtual". Los compiladores como el compilador de C # generan CIL , y luego, en tiempo de ejecución, otro compilador llamado compilador JIT (Just In Time) convierte el IL en código de máquina real que puede ejecutarse.

Entonces, primero respondamos la pregunta "¿por qué tener MSIL?" ¿Por qué no simplemente hacer que el compilador de C # escriba el código de la máquina?

Porque es más barato hacerlo de esta manera. Supongamos que no lo hicimos de esa manera; supongamos que cada idioma debe tener su propio generador de código de máquina. Tiene veinte lenguajes diferentes: C #, JScript .NET , Visual Basic, IronPython , F # ... Y suponga que tiene diez procesadores diferentes. ¿Cuántos generadores de código tienes que escribir? 20 x 10 = 200 generadores de código. Eso es mucho trabajo. Ahora suponga que desea agregar un nuevo procesador. Tienes que escribir el generador de código veinte veces, uno para cada idioma.

Además, es un trabajo difícil y peligroso. ¡Escribir generadores de códigos eficientes para chips en los que no eres un experto es un trabajo difícil! Los diseñadores de compiladores son expertos en el análisis semántico de su lenguaje, no en la asignación eficiente de registros de nuevos conjuntos de chips.

Ahora supongamos que lo hacemos a la manera CIL. ¿Cuántos generadores CIL tienes que escribir? Uno por idioma. ¿Cuántos compiladores JIT tienes que escribir? Uno por procesador. Total: 20 + 10 = 30 generadores de código. Además, el generador de lenguaje a CIL es fácil de escribir porque CIL es un lenguaje simple, y el generador de código de CIL a máquina también es fácil de escribir porque CIL es un lenguaje simple. Nos deshacemos de todas las complejidades de C # y VB y otras cosas y "reducimos" todo a un lenguaje simple para el cual es fácil escribir un jitter.

Tener un idioma intermedio reduce drásticamente el costo de producir un nuevo compilador de idiomas . También reduce drásticamente el costo de soportar un nuevo chip. Desea admitir un nuevo chip, encuentra algunos expertos en ese chip y hace que escriban una inquietud CIL y listo; entonces soportas todos esos idiomas en tu chip.

Bien, entonces hemos establecido por qué tenemos MSIL; porque tener un idioma intermedio reduce los costos. ¿Por qué entonces el lenguaje es una "máquina de pila"?

Porque las máquinas de pila son conceptualmente muy simples para los escritores de compiladores de idiomas. Las pilas son un mecanismo simple y fácil de entender para describir los cálculos. Las máquinas apiladoras también son conceptualmente muy fáciles de manejar para los escritores de compiladores JIT. El uso de una pila es una abstracción simplificada y, por lo tanto, una vez más, reduce nuestros costos .

Usted pregunta "¿por qué tener una pila?" ¿Por qué no simplemente hacer todo directamente de memoria? Bueno, pensemos en eso. Suponga que desea generar código CIL para:

int x = A() + B() + C() + 10;

Supongamos que tenemos la convención de que "agregar", "llamar", "almacenar", etc., siempre quitan sus argumentos de la pila y colocan su resultado (si hay uno) en la pila. Para generar código CIL para este C #, simplemente decimos algo como:

load the address of x // The stack now contains address of x
call A()              // The stack contains address of x and result of A()
call B()              // Address of x, result of A(), result of B()
add                   // Address of x, result of A() + B()
call C()              // Address of x, result of A() + B(), result of C()
add                   // Address of x, result of A() + B() + C()
load 10               // Address of x, result of A() + B() + C(), 10
add                   // Address of x, result of A() + B() + C() + 10
store in address      // The result is now stored in x, and the stack is empty.

Ahora supongamos que lo hicimos sin una pila. Lo haremos a su manera, donde cada código de operación toma las direcciones de sus operandos y la dirección en la que almacena su resultado :

Allocate temporary store T1 for result of A()
Call A() with the address of T1
Allocate temporary store T2 for result of B()
Call B() with the address of T2
Allocate temporary store T3 for the result of the first addition
Add contents of T1 to T2, then store the result into the address of T3
Allocate temporary store T4 for the result of C()
Call C() with the address of T4
Allocate temporary store T5 for result of the second addition
...

¿Ves cómo va esto? Nuestro código se está volviendo enorme porque tenemos que asignar explícitamente todo el almacenamiento temporal que normalmente, por convención, simplemente iría a la pila . Peor aún, nuestros códigos de operación se están volviendo enormes porque ahora todos tienen que tomar como argumento la dirección en la que van a escribir su resultado y la dirección de cada operando. Una instrucción de "agregar" que sepa que va a quitar dos cosas de la pila y colocar una puede ser un solo byte. Una instrucción de agregar que toma dos direcciones de operando y una dirección de resultado será enorme.

Utilizamos códigos de operación basados ​​en pila porque las pilas resuelven el problema común . A saber: quiero asignar algo de almacenamiento temporal, usarlo muy pronto y luego deshacerme de él rápidamente cuando haya terminado . Al suponer que tenemos una pila a nuestra disposición, podemos hacer que los códigos de operación sean muy pequeños y el código muy breve.

ACTUALIZACIÓN: algunos pensamientos adicionales

Por cierto, esta idea de reducir drásticamente los costos al (1) especificar una máquina virtual, (2) escribir compiladores que apuntan al lenguaje VM, y (3) escribir implementaciones de la VM en una variedad de hardware, no es una idea nueva en absoluto . No se originó con MSIL, LLVM, código de bytes Java ni ninguna otra infraestructura moderna. La primera implementación de esta estrategia que conozco es la máquina pcode de 1966.

Lo primero que escuché personalmente sobre este concepto fue cuando supe cómo los implementadores de Infocom lograron que Zork funcionara en tantas máquinas tan bien. Especificaron una máquina virtual llamada máquina Z y luego crearon emuladores de máquina Z para todo el hardware en el que querían ejecutar sus juegos. Esto tenía el enorme beneficio adicional de que podían implementar la administración de memoria virtual en sistemas primitivos de 8 bits; un juego podría ser más grande de lo que cabría en la memoria porque podrían simplemente paginar el código desde el disco cuando lo necesitaran y descartarlo cuando necesitaran cargar un nuevo código.

Tenga en cuenta que cuando habla de MSIL, habla de instrucciones para una máquina virtual . La VM utilizada en .NET es una máquina virtual basada en pila. A diferencia de una VM basada en registros, la VM Dalvik utilizada en los sistemas operativos Android es un ejemplo de eso.

La pila en la VM es virtual, depende del intérprete o del compilador justo a tiempo traducir las instrucciones de la VM al código real que se ejecuta en el procesador. Que en el caso de .NET es casi siempre una inquietud, el conjunto de instrucciones de MSIL fue diseñado para ser sacudido desde el principio. A diferencia del código de bytes de Java, por ejemplo, tiene instrucciones distintas para operaciones en tipos de datos específicos. Lo que lo hace optimizado para ser interpretado. Sin embargo, en realidad existe un intérprete de MSIL, se utiliza en .NET Micro Framework. Que se ejecuta en procesadores con recursos muy limitados, no puede permitirse la RAM necesaria para almacenar el código de la máquina.

El modelo de código de máquina real es mixto, tiene tanto una pila como registros. Uno de los grandes trabajos del optimizador de código JIT es encontrar formas de almacenar variables que se mantienen en la pila en registros, mejorando así en gran medida la velocidad de ejecución. Una inquietud de Dalvik tiene el problema opuesto.

La pila de máquinas es una instalación de almacenamiento muy básica que ha existido en los diseños de procesadores durante mucho tiempo. Tiene una muy buena localidad de referencia, una característica muy importante en las CPU modernas que analizan los datos mucho más rápido de lo que la RAM puede suministrar y admite la recursividad. El diseño del lenguaje está fuertemente influenciado por tener una pila, visible en soporte para variables locales y alcance limitado al cuerpo del método. Un problema importante con la pila es el nombre de este sitio.

Hay un artículo de Wikipedia muy interesante / detallado sobre esto, Ventajas de los conjuntos de instrucciones de la máquina de pila . Tendría que citarlo por completo, por lo que es más fácil simplemente poner un enlace. Simplemente citaré los subtítulos

• Código de objeto muy compacto
• Compiladores simples / intérpretes simples
• Estado mínimo de procesador

Para agregar un poco más a la pregunta de la pila. El concepto de pila se deriva del diseño de la CPU donde el código de máquina en la unidad de lógica aritmética (ALU) opera en operandos que se encuentran en la pila. Por ejemplo, una operación de multiplicación puede tomar los dos operandos superiores de la pila, multiplicarlos y volver a colocar el resultado en la pila. El lenguaje de máquina generalmente tiene dos funciones básicas para agregar y eliminar operandos de la pila; EMPUJE y POP. En muchos dsp (procesador de señal digital) y controladores de máquina (como el que controla una lavadora), la pila se encuentra en el chip. Esto proporciona un acceso más rápido a la ALU y consolida la funcionalidad requerida en un solo chip.

Si no se sigue el concepto de pila / montón y los datos se cargan en una ubicación de memoria aleatoria O los datos se almacenan desde ubicaciones de memoria aleatorias ... será muy desestructurado y no administrado.

Estos conceptos se utilizan para almacenar datos en una estructura predefinida para mejorar el rendimiento, el uso de la memoria ... y, por lo tanto, se denominan estructuras de datos.

Se puede tener un sistema que funcione sin pilas, utilizando un estilo de codificación de paso continuo . Luego, los marcos de llamada se convierten en continuaciones asignadas en el montón de basura recolectada (el recolector de basura necesitaría algo de pila).

Vea los escritos antiguos de Andrew Appel: Compilar con Continuaciones y Recolección de Basura puede ser más rápido que la Asignación de Pila

(Podría estar un poco equivocado hoy debido a problemas de caché)

Busqué "interrupción" y nadie lo incluyó como una ventaja. Para cada dispositivo que interrumpe un microcontrolador u otro procesador, generalmente hay registros que se insertan en una pila, se llama una rutina de servicio de interrupción y, cuando se hace, los registros se vuelven a sacar de la pila y se vuelven a colocar donde están. fueron. Luego se restablece el puntero de instrucciones y la actividad normal continúa donde lo dejó, casi como si la interrupción nunca hubiera sucedido. Con la pila, puede hacer que varios dispositivos (teóricamente) se interrumpan entre sí, y todo simplemente funciona, debido a la pila.

También hay una familia de lenguajes basados ​​en pila llamados lenguajes concatenativos . Todos ellos son (creo) lenguajes funcionales, porque la pila es un parámetro implícito pasado, y también la pila modificada es un retorno implícito de cada función. Tanto Forth como Factor (que es excelente) son ejemplos, junto con otros. Factor se ha utilizado de manera similar a Lua para los juegos de secuencias de comandos y fue escrito por Slava Pestov, un genio que actualmente trabaja en Apple. Su Google TechTalk en youtube lo he visto algunas veces. Él habla sobre los constructores de Boa, pero no estoy seguro de lo que quiere decir ;-).

Realmente creo que algunas de las máquinas virtuales actuales, como la JVM, el CIL de Microsoft e incluso la que vi que estaba escrita para Lua, deberían estar escritas en algunos de estos lenguajes basados ​​en pila, para que sean portátiles en aún más plataformas. Creo que estos lenguajes concatenativos están perdiendo de alguna manera sus llamamientos como kits de creación de VM y plataformas de portabilidad. Incluso hay pForth, un Forth "portátil" escrito en ANSI C, que podría usarse para una portabilidad aún más universal. ¿Alguien intentó compilarlo usando Emscripten o WebAssembly?

Con los lenguajes basados ​​en la pila, hay un estilo de código llamado punto cero, porque puede enumerar las funciones que se invocarán sin pasar ningún parámetro (a veces). Si las funciones encajan perfectamente, no tendría más que una lista de todas las funciones de punto cero, y esa sería su aplicación (teóricamente). Si profundizas en Forth o Factor, verás de lo que estoy hablando.

En Easy Forth , un buen tutorial en línea escrito en JavaScript, aquí hay una pequeña muestra (tenga en cuenta el "sq sq sq sq" como un ejemplo de estilo de llamada de punto cero):

: sq dup * ;  ok
2 sq . 4  ok
: ^4 sq sq ;  ok
2 ^4 . 16  ok
: ^8 sq sq sq sq ;  ok
2 ^8 . 65536  ok

Además, si mira la fuente de la página web de Easy Forth, verá en la parte inferior que es muy modular, escrita en aproximadamente 8 archivos JavaScript.

He gastado mucho dinero en casi todos los libros de Forth que pude conseguir en un intento de asimilar a Forth, pero ahora estoy empezando a asimilarlo mejor. Quiero avisar a los que vienen después, si realmente quieres obtenerlo (descubrí esto demasiado tarde), obtén el libro en FigForth e impleméntalo. Los Forth comerciales son demasiado complicados, y lo mejor de Forth es que es posible comprender todo el sistema, de arriba a abajo. De alguna manera, Forth implementa un entorno de desarrollo completo en un nuevo procesador, y aunque el necesidadporque parece haber pasado con C en todo, todavía es útil como un rito de pasaje para escribir un Forth desde cero. Entonces, si elige hacer esto, pruebe el libro FigForth: son varios Forths implementados simultáneamente en una variedad de procesadores. Una especie de Rosetta Stone of Forths.

¿Por qué necesitamos una pila? Eficiencia, optimización, punto cero, guardar registros en caso de interrupción, y para algoritmos recursivos es "la forma correcta".