Qual é o propósito de uma pilha? Por que precisamos disso?

Então, agora estou aprendendo o MSIL a aprender a depurar meus aplicativos C # .NET.

Eu sempre me perguntei: qual é o propósito da pilha?

Apenas para colocar minha pergunta em contexto:
Por que há uma transferência da memória para a pilha ou "carregamento"? Por outro lado, por que há uma transferência da pilha para a memória ou "armazenamento"? Por que não colocá-los todos na memória?

• É porque é mais rápido?
• É porque é baseado em RAM?
• Para eficiência?

Estou tentando entender isso para me ajudar a entender os códigos CIL muito mais profundamente.

ATUALIZAÇÃO: gostei tanto desta pergunta que a tornei o assunto do meu blog em 18 de novembro de 2011 . Obrigado pela ótima pergunta!

Eu sempre me perguntei: qual é o propósito da pilha?

Suponho que você queira dizer a pilha de avaliação da linguagem MSIL, e não a pilha por thread real em tempo de execução.

Por que há uma transferência da memória para a pilha ou "carregando"? Por outro lado, por que há uma transferência da pilha para a memória ou "armazenamento"? Por que não colocá-los todos na memória?

MSIL é uma linguagem de "máquina virtual". Compiladores como o compilador C # geram CIL e, em tempo de execução, outro compilador chamado JIT (Just In Time) transforma o IL em código de máquina real que pode ser executado.

Então, primeiro, vamos responder à pergunta "por que o MSIL é mesmo?" Por que não apenas fazer o compilador C # escrever o código da máquina?

Porque é mais barato fazê-lo desta maneira. Suponha que não fizemos dessa maneira; suponha que cada idioma tenha que ter seu próprio gerador de código de máquina. Você tem vinte idiomas diferentes: C #, JScript .NET , Visual Basic, IronPython , F # ... E suponha que você tenha dez processadores diferentes. Quantos geradores de código você precisa escrever? 20 x 10 = 200 geradores de código. Isso dá muito trabalho. Agora, suponha que você queira adicionar um novo processador. Você precisa escrever o gerador de código para ele vinte vezes, um para cada idioma.

Além disso, é um trabalho difícil e perigoso. Escrever geradores de código eficientes para chips nos quais você não é especialista é um trabalho árduo! Os projetistas de compiladores são especialistas na análise semântica de seu idioma, e não na alocação eficiente de registros de novos conjuntos de chips.

Agora, suponha que façamos da maneira CIL. Quantos geradores CIL você precisa escrever? Um por idioma. Quantos compiladores JIT você precisa escrever? Um por processador. Total: 20 + 10 = 30 geradores de código. Além disso, o gerador de linguagem para CIL é fácil de escrever porque o CIL é uma linguagem simples, e o gerador de CIL para código de máquina também é fácil de escrever porque o CIL é uma linguagem simples. Nós nos livramos de todos os meandros do C # e do VB e outros enfeites e "abaixamos" tudo para uma linguagem simples e fácil de escrever.

Ter um idioma intermediário reduz drasticamente o custo de produção de um novo compilador de idiomas . Também reduz drasticamente o custo de suporte de um novo chip. Você deseja oferecer suporte a um novo chip, encontra alguns especialistas nesse chip e solicita que eles escrevam uma instabilidade CIL e pronto; então você suporta todos esses idiomas no seu chip.

OK, então estabelecemos por que temos o MSIL; porque ter um idioma intermediário reduz os custos. Por que então o idioma é uma "máquina de empilhar"?

Como as máquinas de pilha são conceitualmente muito simples para os escritores de compiladores de idiomas lidarem. As pilhas são um mecanismo simples e de fácil compreensão para descrever cálculos. Máquinas de empilhar também são conceitualmente muito fáceis para os escritores de compiladores JIT. Usar uma pilha é uma abstração simplificadora e, portanto, novamente, reduz nossos custos .

Você pergunta "por que ter uma pilha?" Por que não fazer tudo diretamente sem memória? Bem, vamos pensar sobre isso. Suponha que você queira gerar código CIL para:

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

Suponha que tenhamos a convenção de que "add", "call", "store" e assim por diante sempre retiram seus argumentos da pilha e colocam seu resultado (se houver) na pilha. Para gerar código CIL para este C #, apenas dizemos 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.

Agora, suponha que fizemos isso sem uma pilha. Vamos fazer do seu jeito, onde todo código de operação leva os endereços de seus operandos e o endereço no qual armazena seu 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
...

Você vê como isso vai? Nosso código está ficando enorme porque temos que alocar explicitamente todo o armazenamento temporário que normalmente por convenção iria para a pilha . Pior, nossos próprios opcodes estão ficando enormes, porque agora eles têm que usar como argumento o endereço no qual escreverão o resultado e o endereço de cada operando. Uma instrução "add" que sabe que vai tirar duas coisas da pilha e colocar uma coisa pode ser um único byte. Uma instrução add que usa dois endereços de operando e um endereço de resultado será enorme.

Usamos opcodes baseados em pilha porque as pilhas resolvem o problema comum . A saber: quero alocar algum armazenamento temporário, usá-lo muito em breve e depois me livrar dele rapidamente quando terminar . Ao supor que temos uma pilha à nossa disposição, podemos tornar os códigos de operação muito pequenos e o código muito concisos.

ATUALIZAÇÃO: Algumas reflexões adicionais

Aliás, essa idéia de reduzir drasticamente os custos (1) especificando uma máquina virtual, (2) escrevendo compiladores direcionados à linguagem da VM e (3) escrevendo implementações da VM em uma variedade de hardware, não é uma idéia totalmente nova. . Não se originou com MSIL, LLVM, Java bytecode ou qualquer outra infra-estrutura moderna. A primeira implementação dessa estratégia que conheço é a máquina pcode de 1966.

A primeira vez que ouvi falar desse conceito foi quando aprendi como os implementadores da Infocom conseguiram fazer com que o Zork funcionasse tão bem em tantas máquinas diferentes. Eles especificaram uma máquina virtual chamada Z-machine e, em seguida, criaram emuladores de Z-machine para todo o hardware em que queriam rodar seus jogos. Isso teve o enorme benefício adicional de poder implementar o gerenciamento de memória virtual em sistemas primitivos de 8 bits; um jogo poderia ser maior do que caberia na memória, porque eles poderiam apenas paginar o código do disco quando precisassem e descartá-lo quando precisassem carregar um novo código.

Lembre-se de que, quando você está falando sobre o MSIL, está falando sobre instruções para uma máquina virtual . A VM usada no .NET é uma máquina virtual baseada em pilha. Ao contrário de uma VM baseada em registro, a VM Dalvik usada nos sistemas operacionais Android é um exemplo disso.

A pilha na VM é virtual, cabe ao intérprete ou ao compilador just-in-time traduzir as instruções da VM em código real que é executado no processador. Que, no caso do .NET, quase sempre é instável, o conjunto de instruções MSIL foi projetado para ser acionado desde o início. Ao contrário do bytecode Java, por exemplo, ele possui instruções distintas para operações em tipos de dados específicos. O que o torna otimizado para ser interpretado. No entanto, existe um intérprete MSIL, ele é usado no .NET Micro Framework. Que roda em processadores com recursos muito limitados, não pode permitir a RAM necessária para armazenar o código da máquina.

O modelo de código de máquina real é misto, tendo uma pilha e registradores. Um dos grandes trabalhos do otimizador de código JIT é apresentar maneiras de armazenar variáveis ​​que são mantidas na pilha nos registradores, melhorando muito a velocidade de execução. Um tremor de Dalvik tem o problema oposto.

Caso contrário, a pilha da máquina é uma instalação de armazenamento muito básica que existe nos designs de processadores há muito tempo. Possui uma localidade de referência muito boa, um recurso muito importante nas CPUs modernas que analisam os dados muito mais rapidamente do que a RAM pode fornecer e suporta recursão. O design do idioma é fortemente influenciado por ter uma pilha, visível no suporte a variáveis ​​locais e escopo limitado ao corpo do método. Um problema significativo com a pilha é o nome desse site.

Há um artigo muito interessante / detalhado da Wikipedia sobre isso, Vantagens dos conjuntos de instruções para máquinas de empilhar . Eu precisaria citá-lo inteiramente, para que seja mais fácil simplesmente colocar um link. Vou simplesmente citar os subtítulos

• Código de objeto muito compacto
• Compiladores simples / intérpretes simples
• Estado mínimo do processador

Para adicionar um pouco mais à questão da pilha. O conceito de pilha deriva do design da CPU, onde o código de máquina na unidade lógica aritmética (ALU) opera em operandos localizados na pilha. Por exemplo, uma operação de multiplicação pode pegar os dois operandos principais da pilha, multiplicá-los e colocar o resultado de volta na pilha. A linguagem de máquina geralmente possui duas funções básicas para adicionar e remover operandos da pilha; PUSH e POP. Em muitos dsp (processadores de sinais digitais) e controladores de máquinas (como os que controlam uma máquina de lavar), a pilha está localizada no próprio chip. Isso permite acesso mais rápido à ULA e consolida a funcionalidade necessária em um único chip.

Se o conceito de pilha / pilha não for seguido e os dados forem carregados no local de memória aleatória OU os dados forem armazenados de locais de memória aleatória ... será muito desestruturado e não gerenciado.

Esses conceitos são usados ​​para armazenar dados em uma estrutura predefinida para melhorar o desempenho, o uso da memória ... e, portanto, chamados estruturas de dados.

Pode-se ter um sistema funcionando sem pilhas, usando o estilo de codificação de passagem contínua . Em seguida, os quadros de chamada se tornam continuações alocadas no heap de coleta de lixo (o coletor de lixo precisaria de alguma pilha).

Veja os escritos antigos de Andrew Appel: Compilar com continuações e coleta de lixo pode ser mais rápido que a alocação de pilha

(Ele pode estar um pouco errado hoje devido a problemas de cache)

Eu procurei por "interrupção" e ninguém incluiu isso como uma vantagem. Para cada dispositivo que interrompe um microcontrolador ou outro processador, geralmente existem registros que são empurrados para uma pilha, uma rotina de serviço de interrupção é chamada e, quando isso é feito, os registros são retirados da pilha e recolocados onde eles estavam. Em seguida, o ponteiro de instruções é restaurado e a atividade normal começa de onde parou, quase como se a interrupção nunca tivesse acontecido. Com a pilha, é possível que vários dispositivos (teoricamente) se interrompam, e tudo funciona - por causa da pilha.

Há também uma família de idiomas baseados em pilha chamados idiomas concatenativos . São todas (acredito) linguagens funcionais, porque a pilha é um parâmetro implícito passado e também a pilha alterada é um retorno implícito de cada função. Ambos adiante e o Factor (que é excelente) são exemplos, juntamente com os outros. O fator foi usado de forma semelhante a Lua, para jogos de script, e foi escrito por Slava Pestov, um gênio atualmente trabalhando na Apple. Seu Google TechTalk no youtube eu assisti algumas vezes. Ele fala sobre os construtores de Boa, mas não tenho certeza do que ele quer dizer ;-).

Realmente acho que algumas das VMs atuais, como a JVM, CIL da Microsoft e até a que vi escrita para Lua, devem ser escritas em algumas dessas linguagens baseadas em pilha, para torná-las portáteis para ainda mais plataformas. Eu acho que essas linguagens concatenativas estão, de alguma forma, perdendo suas chamadas como kits de criação de VM e plataformas de portabilidade. Existe ainda o pForth, um Forth "portátil" escrito em ANSI C, que pode ser usado para uma portabilidade ainda mais universal. Alguém tentou compilá-lo usando o Emscripten ou o WebAssembly?

Com as linguagens baseadas em pilha, existe um estilo de código chamado ponto zero, porque você pode apenas listar as funções a serem chamadas sem passar nenhum parâmetro (às vezes). Se as funções se encaixassem perfeitamente, você teria apenas uma lista de todas as funções de ponto zero, e essa seria sua aplicação (teoricamente). Se você se aprofundar em Forth ou Factor, verá o que estou falando.

No Easy Forth , um bom tutorial on-line escrito em JavaScript, aqui está uma pequena amostra (observe o "sq sq sq sq" como um exemplo de estilo de chamada com ponto zero):

: 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

Além disso, se você olhar para a fonte da página da Web Easy Forth, verá na parte inferior que ela é muito modular, escrita em cerca de 8 arquivos JavaScript.

Gastei muito dinheiro em quase todos os livros da Forth em que pude pôr as mãos na tentativa de assimilar a Forth, mas agora estou começando a entender melhor. Quero dar uma indicação àqueles que vierem depois, se você realmente quiser entender (descobri isso tarde demais), pegue o livro no FigForth e implemente isso. Os comerciais da Forths são muito complicados, e o melhor de Forth é que é possível compreender todo o sistema, de cima para baixo. De alguma forma, a Forth implementa todo um ambiente de desenvolvimento em um novo processador, e embora o necessidadepois isso pareceu passar com C em tudo, ainda é útil como rito de passagem escrever um quarto adiante do zero. Portanto, se você optar por fazer isso, experimente o livro do FigForth - vários Forths são implementados simultaneamente em uma variedade de processadores. Uma espécie de Rosetta Stone of Forths.

Por que precisamos de uma pilha - eficiência, otimização, ponto zero, salvando registros em caso de interrupção e, para algoritmos recursivos, é "a forma correta".