Uma *stack* (ou pilha), neste contexto, é uma forma otimizada para organizar dados na memória alocados em sequência e abandonados (sim, normalmente não há desalocação) em sequência invertida a da entrada. [![Pilha/Stack][1]][1] Um *heap* (ou monte, ok, ninguém traduz isso) é a organização de memória mais flexível que permite o uso de qualquer área lógica disponível. [![Monte?Heap][2]][2] # De que pilha estamos falando? Existem alguns conceitos de pilha muito difundidos em computação, para citar alguns: - Existe a **pilha de execução** de alguma arquitetura onde as instruções e dados vão sendo empilhados e após executar algo ali, ocorre o desempilhamento. - Existe a **pilha de chamadas de funções**, que se confunde com o gerenciamento de memória, onde as funções vão sendo chamadas e empilhadas e quando sua execução termina, ela sai da pilha. - Existe a [**estrutura de dados genérica**][3] que empilha dados diversos. [Exemplo em C#][3]. # Conceito abstrato Os dois conceitos da pergunta são abstratos. Não existe fisicamente uma área da memória específica para a *stack* (e muito menos sua área é fisicamente empilhada) e não existe uma área reservada para o *heap*, pelo contrário, ele costuma ser bastante fragmentado. Usamos o conceito para entender melhor o funcionamento e suas implicações, principalmente no caso da pilha. A maioria das arquiteturas de computadores modernos e populares não tem grandes facilidades para manipular essa *stack* de memória (costuma ter só o registrador de ponteiro de pilha), assim como o *heap*, apesar que neste caso, instruções que ajudam manipular memória virtual de uma certa forma ajudam a organizar o *heap*, mas isso vale pra toda memória, não só o *heap*. # Ficando um pouco mais concreto Já o sistema operacional está bem ciente destes conceitos e é fundamental que eles possuam alguma forma, mesmo que limitada, para manipular a memória das aplicações, principalmente nos sistemas modernos e de utilidade geral. Os sistemas modernos possuem um gerenciamento complexo através do que se convencionou chamar de memória virtual que também é um conceito abstrato, muitas vezes mal compreendido. # Onde mexemos diretamente Em Assembly ou C é muito comum ter contato com esse gerenciamento de memória. Em Assembly é comum manipular a *stack* quase diretamente e em ambas linguagens pelo menos a alocação e desalocação do *heap* devem ser feitas manualmente através da API do sistema operacional. Em C a *stack* é gerenciado pelo compilador, salvo alguma operação incomum que seja necessária. Nada impede que se use alguma biblioteca que abstraia essa manipulação, mas isso só é comum em linguagens de mais alto nível. De fato é muito comum que outras linguagens usem internamente a API do OS para fazer o gerenciamento pesado da memória mas o acesso da memória no "varejo" é feito por um gerenciador próprio, em geral chamado de *garbage collector* através de técnicas de contagem de referências para um objeto no *heap* (há quem considere que isto não é uma técnica de *garbage collector*) ou de verificação posterior se há referências para o objeto no *heap*. Mesmo usando uma biblioteca mais abstrata, os conceitos permanecem. Quanto mais alto nível, menos precisam gerenciar tudo isso, mas entender o funcionamento geral é importante em todas linguagens. Linguagens que não precisam de performance pode deixar tudo no *heap* e "facilitar" a compressão e acesso. # Pilha ### Alocação Em condições normais, **a *stack* é alocado no início da execução da aplicação**, mais precisamente no início da *thread*, mesmo que a aplicação só tenha a *thread* principal. A *stack* é uma porção contígua de memória reservada para empilhar os dados necessários durante a execução de blocos de código. Cada necessidade de alocação é um trecho da *stack* que vai sendo usado sempre em sequência determinado por um marcador, ou seja, um apontador, um **ponteiro**, se "movimenta" para indicar que uma nova parte na sequência desta porção reservada está comprometida. Quando algo reservado para um segmento não é mais necessário, este marcador se movimenta em direção contrária a sequência de dados indicando que alguns desses dados podem ser descartados (sobrepostos com novos dados). A alocação de cada trecho da memória não existe na *stack*, é apenas o movimento deste ponteiro indicando que aquela área será usada por algum dado. A grosso modo podemos dizer que a aplicação tem total controle sobre a *stack, exceto quando acaba o espaço disponível nele. Existem recursos para alterar manualmente o tamanho da *stack*, mas isso é incomum. # Funcionamento A pilha funciona usado uma forma LIFO (Last in First Out) ou UEPS (Último a entrar, primeiro a sair). O escopo de uma variável costuma definir o tempo de alocação na *stack*. Os dados usados como parâmetros e retorno de funções são alocados na *stack*. Por isso a pilha de chamadas de função se confunde com a pilha da memória. Podemos dizer que os parâmetros são as primeiras variáveis de uma função alocadas na *stack*. O acesso aos dados na *stack* costuma ser feito de forma direta, mas há [indireções][4] também. ![alocação stack][5] Deu para entender que cada *thread* tem sua própria *stack*, certo? E o tamanho da *stack* de cada *thread* criada pode ter seu tamanho definido antes da criação. Um valor *default* costuma ser usado. A *stack* é considerado uma forma **automática** de alocação (muitas vezes confundida com estática que é alocação que ocorre junto ao execução logo na sua carga. Tecnicamente existe outra área da memória que realmente seja estática, que seja alocada antes do início da execução. A área efetivamente estática não pode ser manipulada, não pode ser escrita (pelo menos não deveria poder). A *stack* em si é estático, apesar de que seus dados não sejam, afinal eles vão sendo colocados e abandonados conforme o seu uso, o seu gerenciamento é automático. # Decisão sobre onde alocar Assim como no *heap*, não é possível alocar dados na *stack* antes de saber seu tamanho (não precisa saber na hora de compilar, mas sim na hora de executar a alocação, mas na *stack* tem algumas restrições). Mas se o tamanho for indeterminado em tempo de compilação ou pode ser determinado como **possivelmente** grande (talvez poucas dezenas de *bytes*), provavelmente a alocação deva ocorrer no *heap*. Linguagens de alto nível predeterminam isto. Outras deixam o programador ter mais controle, podendo até mesmo abusar da *stack* se for útil e o programador souber o que está fazendo. ### Stack overflow O famoso *stack overflow* ocorre quando você tenta alocar algo na *stack* e não há espaço reservado disponível. Também pode, em alguns casos se a linguagem prover mecanismos que permitam, haver *overflow* de um dado em cima de outro que venha a seguir na pilha. Execuções recursivas descontroladas causam *stack overflow*. ### Outra pilha Também existe uma pilha de chamadas que é onde são armazenados os endereços para onde o ponteiro da pilha deve retornar quando termina a execução de uma função. # Heap ### Alocação O *heap*, ao contrário da *stack*, não impõe um modelo, um padrão de alocação de memória. Isso não é muito eficiente mas é bastante flexível. O *heap* é considerado **dinâmico**. Em geral você aloca ou desaloca pequenos trechos de memória, só para a necessidade do dado. Esta alocação pode ocorrer fisicamente em qualquer parte livre da memória disponível para seu processo. O gerenciamento de memória virtual do sistema operacional, auxiliado por instruções do processador, ajudam a organizar isto. De certa forma podemos dizer que a *stack* como um todo é o primeiro objeto alocado no *heap*. Efetivamente estas alocações reais costumam ocorrer em blocos de tamanho fixo chamados de páginas. Isso evita a aplicação fazer dezenas ou centenas de pequenas alocações que fragmentaria a memória de forma extrema e evita chamadas ao sistema operacional que troca contexto e costuma ser bem mais lento. Em geral todo sistema de alocação da memória aloca mais do que precisa e vai dando acesso à aplicação conforme ela precisa, em alguns casos, ele quase simula uma *stack*, por algum tempo, ou fazer reorganização da memória (através de um GC compactador). ### Desalocação A desalocação do *heap* costuma acontecer: - manualmente (correndo o risco de *bugs*), embora isto não esteja disponível para algumas linguagens; - através do tal [*garbage collector*][6] que identifica quando uma parte do *heap* não é mais necessária; - quando uma aplicação se encerra. ### Depende de implementação Até existem linguagens que possuem *heaps* especializados que podem ter um comportamento um pouco diferente, mas vamos simplificar para os casos comuns. # Conceito abstrato Fica claro que o *heap* não é uma área da memória, mesmo conceituando abstratamente, ele é um conjunto de pequenas áreas da memória. Fisicamente ele costuma ser fragmentado por toda a memória. Essas partes são muito flexíveis no tamanho e [tempo de vida][7]. Por razões de segurança é bom saber que desalocar é um conceito abstrato também. Costuma ser possível acessar dados de uma aplicação mesmo depois que ela tenha terminado. O conteúdo só é apagado por pedido manual ou quando uma área disponível seja escrita novamente. ### Custo do *heap* A **alocação no *heap* "custa" caro**. Muitas tarefas devem ser realizados pelo sistema operacional para garantir a perfeita alocação de uma área para um trecho dele, principalmente em ambientes concorrentes, muito comuns hoje em dia, e mesmo quando não precisa do SO ainda tem um algoritmo complexo para alocar. Desalocar, ou disponibilizar de volta uma área também tem seu custo, em alguns casos para a alocação custar mais barata a liberação custa bem cara (ironicamente pode ser controlada por várias pilhas). Até existem formas de evitar as chamadas ao sistema operacional para cada alocação necessária, mas ainda assim o "custo" de processamento disto é considerado alto. Manter listas (em alguns casos ligadas) de áreas ou páginas alocadas não é algo trivial para o processador, pelo menos comparando com o movimento do ponteiro que é necessário na *stack*. ### Funcionamento ![alocação heap][8] O *heap* é acessado através de ponteiros. Mesmo em linguagens que não exista o conceito de ponteiros disponíveis para o programador, isto é realizado internamente de forma transparente. ![exemplo de alocação geral][9] Note que no exemplo, um objeto do tipo `class1` é alocado no *heap*. Mas há uma referência para este objeto, que é alocada na *stack* (em alguns casos poderia não estar). Esta alocação é necessária porque o tamanho do objeto pode ser muito grande para caber na *stack* (ou pelo menos ocupar uma parte considerável), ou porque ele pode sobreviver por mais tempo do que a função que criou ele. Se estivesse na *stack* a "única" forma de mantê-lo "vivo" seria copiando para a função chamadora, e assim sucessivamente para todas as outras, onde ele seja necessário. Imagine como isso sai "caro". Da forma como é organizado, só a referência, que é curta, é que precisa ser copiada, e isto pode ser feito só usando registradores, super rápido. # Conclusão Então o *runtime* de uma linguagem de programação se comunica com o OS para gerenciar a memória. Se esse *runtime* é exposto para o programador depende do objetivo da linguagem. Em linguagens chamadas "gerenciadas", tudo isso ocorre, os dois conceitos existem e precisam ser entendidos, mas você não tem que manipular manualmente o *heap*. Ele passa ser tão transparente quanto a *stack* é em outras linguagens mais baixo nível (exceto Assembly). A alocação de ambos costumam ser realizados na RAM, mas nada impede que seja alocado em outro local. A memória virtual pode colocar todo ou parte da *stack* ou do *heap* em memória de massa, por exemplo. "Roubei" algumas imagens [desta resposta do SO][10] que são muito boas para ilustrar tudo isso. [Coloquei no **GitHub** para referência futura][11]. [1]: https://i.sstatic.net/lN2Fx.png [2]: https://i.sstatic.net/iwwjW.jpg [3]: https://pt.stackoverflow.com/a/15063/101 [4]: https://pt.stackoverflow.com/q/181032/101 [5]: https://i.sstatic.net/9UshP.png [6]: https://pt.stackoverflow.com/q/255769/101 [7]: https://pt.stackoverflow.com/q/135572/101 [8]: https://i.sstatic.net/0Obi0.png [9]: https://i.sstatic.net/NS0k7.jpg [10]: https://stackoverflow.com/q/79923/221800 [11]: https://github.com/maniero/SOpt/blob/master/Conceptual.md