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

320

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.

Jan Carlo Viray
fonte
28
A pilha é uma parte da memória, assim como o heap é outra parte da memória.
CodesInChaos
@CodeInChaos você está falando sobre tipos de valor versus tipos de referência? ou é o mesmo em termos de códigos IL? ... Eu sei que a pilha é apenas mais rápido e mais eficiente do que a pilha (mas que é no mundo do valor / tipos ref .. que eu não sei se é o mesmo aqui?)
Jan Carlo Viray
15
@CodeInChaos - Eu acho que a pilha que a referência de Jan é a máquina de pilha contra a qual a IL é escrita, em oposição à região da memória que aceita quadros de pilha durante as chamadas de função. São duas pilhas diferentes e, após o JIT, a pilha IL não existe (no x86, de qualquer maneira) #
Damien_The_Unbeliever
4
Como o conhecimento do MSIL o ajudará a depurar aplicativos .NET?
Piotr Perak
1
Nas máquinas modernas, o comportamento do código em cache é um fator decisivo para o desempenho. A memória está em todo lugar. Stack é, geralmente, apenas aqui. Supondo que a pilha é uma coisa real, e não apenas um conceito usado para expressar a operação de algum código. Na implementação de uma plataforma que executa o MSIL, não há exigência de que o conceito de pilha chegue ao hardware que está realmente avançando.
Reintegrar Monica

Respostas:

441

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.

Eric Lippert
fonte
63
UAU. Isso é exatamente o que eu estava procurando. A melhor maneira de obter uma resposta é obter uma do próprio desenvolvedor principal. Obrigado pelo tempo, e tenho certeza que isso ajudará a todos que se perguntam os meandros do compilador e do MSIL. Obrigado Eric.
Jan Carlo Viray
18
Essa foi uma ótima resposta. Me lembra por que li seu blog, mesmo sendo um cara de Java. ;-)
jprete 24/10/11
34
@JanCarloViray: De nada! Observo que sou um desenvolvedor principal, não o desenvolvedor principal. Há várias pessoas nessa equipe com esse cargo e eu nem sou a mais velha delas.
Eric Lippert
17
@ Eric: Se / quando você parar de amar a codificação, considere ensinar os programadores. Além da diversão, você poderia estar matando sem a pressão dos negócios. Um talento incrível é o que você tem nessa área (e uma paciência maravilhosa, devo acrescentar). Eu digo isso como ex-professor universitário.
Alan
19
Cerca de quatro parágrafos em que eu estava dizendo para mim mesmo "Isso soa como Eric", no dia 5 ou 6 eu me formei em "Sim, definitivamente Eric" :) Outra resposta verdadeiramente e épica e abrangente.
Preocupante binário 25/10
86

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.

Hans Passant
fonte
2
+1 para uma explicação muito detalhada, e +100 (se pudesse) para comparação detalhada extra para outros sistemas e linguagem :)
Jan Carlo Viray
4
Por que o Dalvik é uma máquina de registro? A Sicne é direcionada principalmente aos processadores ARM. Agora, o x86 tem a mesma quantidade de registros, mas sendo um CISC, apenas 4 deles são realmente úteis para armazenar locais, porque o restante é implicitamente usado em instruções comuns. As arquiteturas ARM, por outro lado, têm muito mais registros que podem ser usados ​​para armazenar locais, portanto, eles facilitam um modelo de execução baseado em registro.
Johannes Rudolph
1
@JohannesRudolph Isso não é verdade há quase duas décadas. Só porque a maioria dos compiladores C ++ ainda tem como alvo o conjunto de instruções x86 dos anos 90 não significa que o próprio x86 seja insuficiente. Haswell possui 168 registros inteiros de uso geral e 168 GP AVX, por exemplo - muito mais do que qualquer CPU ARM que eu conheça. Você pode usar todos os da montagem x86 (moderna) da maneira que desejar. Culpe os escritores do compilador, não a arquitetura / CPU. De fato, é uma das razões pelas quais a compilação intermediária é tão atraente - um melhor código binário para uma determinada CPU; sem mexer na arquitetura dos anos 90.
Luaan
2
@JohannesRudolph O compilador .NET JIT realmente usa muito os registros; a pilha é principalmente uma abstração da máquina virtual IL, o código que realmente é executado na sua CPU é muito diferente. As chamadas de método podem ser registradoras de passagem, os locais podem ser elevados para os registradores ... O principal benefício da pilha no código de máquina é o isolamento que ela dá às chamadas de sub-rotina - se você colocar um local em um registrador, uma chamada de função pode ser você perde esse valor e não pode realmente dizer.
Luaan
1
@RahulAgarwal O código de máquina gerado pode ou não usar a pilha para qualquer valor local ou intermediário. Em IL, todos os argumentos e locais estão na pilha - mas no código da máquina, isso não é verdade (é permitido, mas não obrigatório). Algumas coisas são úteis na pilha e são colocadas na pilha. Algumas coisas são úteis na pilha e são colocadas na pilha. Algumas coisas não são necessárias, ou precisam apenas de alguns momentos em um registro. As chamadas podem ser totalmente eliminadas (inline) ou seus argumentos podem ser passados ​​em registros. O JIT tem muita liberdade.
Luaan 07/04
20

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
Peter Mortensen
fonte
-1 @xanatos Você poderia tentar resumir os títulos que tirou?
Tim Lloyd
@chibacity Se eu quisesse resumir, eu teria feito uma resposta. Eu estava tentando recuperar um link muito bom.
Xanatos
@xanatos Entendo seus objetivos, mas compartilhar um link para um artigo tão grande da Wikipedia não é uma ótima resposta. Não é difícil encontrar apenas pesquisando no Google. Por outro lado, Hans tem uma boa resposta.
Tim Lloyd
@chibacity O OP provavelmente estava com preguiça de não procurar primeiro. O atendedor aqui deu um bom link (sem descrevê-lo). Dois males fazem um bem :-) E eu votarei em Hans.
Xanatos
para responder e @xanatos +1 para obter um ótimo link. Eu estava esperando alguém resumir completamente e ter uma resposta do pacote de conhecimento. Se Hans não desse uma resposta, eu teria feito a sua como a resposta aceita. É apenas um link, então não era. justo para Hans que colocou um bom esforço pela sua resposta .. :)
Jan Carlo Viray
8

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.

skyman
fonte
5

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.

Azodious
fonte
4

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)

Basile Starynkevitch
fonte
0

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

MicroservicesOnDDD
fonte