Por que a coleta de lixo varre apenas a pilha?

28

Basicamente, aprendi até agora que a coleta de lixo apaga para sempre qualquer estrutura de dados que não está sendo apontada no momento. Mas isso apenas verifica a pilha para tais condições.

Por que também não verifica a seção de dados (globais, constantes, etc etc) ou a pilha também? O que há na pilha que é a única coisa que queremos que seja coletada no lixo?

Templário das Trevas
fonte
21
"varrer a pilha" é mais seguro do que "bater a pilha" ... :-)
Brian Knoblauch

Respostas:

62

O coletor de lixo faz a varredura da pilha - para ver o que as coisas na pilha estão sendo usados atualmente (apontado) por coisas na pilha.

Não faz sentido que o coletor de lixo considere coletar memória da pilha porque a pilha não é gerenciada dessa maneira: tudo na pilha é considerado "em uso". E a memória usada pela pilha é recuperada automaticamente quando você retorna de chamadas de método. O gerenciamento de memória do espaço da pilha é tão simples, barato e fácil que você não gostaria que a coleta de lixo estivesse envolvida.

(Existem sistemas, como smalltalk, em que os quadros de pilha são objetos de primeira classe armazenados na pilha e no lixo coletados como todos os outros objetos. Mas essa não é a abordagem popular atualmente. A JVM do Java e o CLR da Microsoft usam a pilha de hardware e a memória contígua .)

Jeff Grigg
fonte
7
+1 a pilha está sempre totalmente acessível de modo nenhum sentido para varrê-la
aberração catraca
2
+1 obrigado, levou 4 postagens para encontrar a resposta certa. Não sei por que você tinha que dizer que tudo na pilha é "considerado" como sendo usado, é pelo menos tão forte quanto os objetos de pilha ainda em uso estão em uso - mas isso é realmente um uma resposta muito boa
Psr
@psr ele quer dizer que tudo na pilha é fortemente acessível e não tem necessidade de ser recolhidos até que o método retorna, mas que (RAII) já é gerido de forma explícita
catraca aberração
@ratchetfreak - eu sei. E eu apenas quis dizer que a palavra "considerado" provavelmente não é necessária, não há problema em fazer uma afirmação mais forte sem ela.
Psr
5
@ psr: eu discordo. " considerado em uso" é mais correto tanto para pilha quanto para heap, por razões muito importantes. O que você quer é descartar o que não será usado novamente; o que você faz é descartar o que não é alcançável . Você pode ter dados acessíveis que você nunca precisará; Quando esses dados crescem, há um vazamento de memória (sim, eles são possíveis mesmo em idiomas do GC, ao contrário de muitas pessoas pensam). E pode-se argumentar que vazamentos de pilha também acontecem, o exemplo mais comum são os quadros de pilha desnecessários em programas recursivos de cauda executados sem eliminação de chamada de cauda (por exemplo, na JVM).
Blaisorblade
19

Vire sua pergunta. A verdadeira questão motivadora está em que circunstâncias podemos evitar os custos da coleta de lixo?

Bem, primeiro, quais são os custos da coleta de lixo? Existem dois custos principais. Primeiro, você precisa determinar o que está vivo ; isso requer potencialmente muito trabalho. Segundo, você precisa compactar os furos formados quando liberar algo que foi alocado entre duas coisas que ainda estão vivas. Esses buracos são um desperdício. Mas compactá-los também é caro.

Como podemos evitar esses custos?

Claramente, se você puder encontrar um padrão de uso de armazenamento no qual nunca aloque algo de longa duração, aloque algo de curta duração e aloque algo de longa duração, poderá eliminar o custo dos furos. Se você pode garantir que, para algum subconjunto de seu armazenamento, cada alocação subsequente tenha uma vida útil mais curta que a anterior nesse armazenamento, nunca haverá buracos nesse armazenamento.

Mas se resolvemos o problema do furo , também resolvemos o problema da coleta de lixo . Você tem algo nesse armazenamento que ainda está vivo? Sim. Tudo foi alocado antes de durar mais? Sim - essa suposição é como eliminamos a possibilidade de buracos. Portanto, tudo o que você precisa fazer é dizer "a alocação mais recente está viva?" e você sabe que tudo está vivo nesse armazenamento.

Temos um conjunto de alocações de armazenamento em que sabemos que todas as alocações subseqüentes têm vida útil mais curta que a alocação anterior? Sim! Os quadros de ativação dos métodos são sempre destruídos na ordem oposta à qual foram criados, porque eles sempre têm vida mais curta do que a ativação que os criou.

Portanto, podemos armazenar quadros de ativação na pilha e saber que eles nunca precisam ser coletados. Se houver algum quadro na pilha, o conjunto inteiro de quadros abaixo terá vida mais longa, portanto, eles não precisam ser coletados. E eles serão destruídos na ordem oposta em que foram criados. O custo da coleta de lixo é eliminado para os quadros de ativação.

É por isso que temos o pool temporário na pilha em primeiro lugar: porque é uma maneira fácil de implementar a ativação do método sem incorrer em uma penalidade no gerenciamento de memória.

(É claro que o custo da coleta de lixo da memória referida pelas referências nos quadros de ativação ainda existe.)

Agora considere um sistema de fluxo de controle no qual os quadros de ativação não sejam destruídos em uma ordem previsível. O que acontece se uma ativação de curta duração pode dar origem a uma ativação de longa duração? Como você pode imaginar, neste mundo você não pode mais usar a pilha para otimizar a necessidade de coletar ativações. O conjunto de ativações pode conter furos novamente.

O C # 2.0 possui esse recurso na forma de yield return. Um método que produz um retorno de rendimento será reativado posteriormente - na próxima vez que MoveNext for chamado - e quando isso acontecer não será previsível. Portanto, as informações que normalmente estariam na pilha para o quadro de ativação do bloco iterador são armazenadas na pilha, onde são coletadas como lixo quando o enumerador é coletado.

Da mesma forma, o recurso "async / waitit", que vem nas próximas versões do C # e do VB, permitirá criar métodos cujas ativações "produzem" e "resumem" em pontos bem definidos durante a ação do método. Como os quadros de ativação não são mais criados e destruídos de maneira previsível, todas as informações que costumavam ser armazenadas na pilha precisam ser armazenadas no heap.

Foi apenas um acidente da história que decidimos por algumas décadas que os idiomas com quadros de ativação criados e destruídos de maneira estritamente ordenada estavam na moda. Como os idiomas modernos carecem cada vez mais dessa propriedade, espere ver mais e mais idiomas que refificam as continuações no heap de coleta de lixo, em vez da pilha.

Eric Lippert
fonte
13

A resposta mais óbvia, e talvez não a mais completa, é que o heap é o local dos dados da instância. Por dados de instância, entendemos os dados que representam as instâncias de classes, também conhecidas como objetos, criadas em tempo de execução. Esses dados são inerentemente dinâmicos e o número desses objetos e, portanto, a quantidade de memória que eles ocupam, são conhecidos apenas em tempo de execução. É necessário que haja alguma recuperação da memória ou programas de longa duração consumiriam toda a memória ao longo do tempo.

A memória consumida por definições de classe, constantes e outras estruturas de dados estáticas é inerentemente improvável que aumente desmarcada. Como há apenas uma definição de classe na memória por um número desconhecido de instâncias de tempo de execução dessa classe, faz sentido que esse tipo de estrutura não seja uma ameaça ao uso da memória.

Chade
fonte
5
Mas o heap não é o local dos "dados da instância". Eles também podem estar na pilha.
Sv16
@svick Depende do idioma, é claro. Java suporta apenas objetos alocados em heap, e Vala distingue explicitamente entre alocado em heap (classe) e alocado em pilha (struct).
macia
11
@ fofo: esses são idiomas muito limitados, você não pode assumir que isso se aplica em geral, pois nenhum idioma foi precisado.
Matthieu M.
@MatthieuM. Esse foi o meu ponto de vista.
macia
@fluffy: então, por que as classes são alocadas na pilha, enquanto as estruturas são alocadas na pilha?
Escuro Templar
10

Vale lembrar que temos a coleta de lixo: porque às vezes é difícil saber quando desalocar a memória. Você realmente só tem esse problema com a pilha. Os dados alocados na pilha serão desalocados eventualmente, portanto, não há realmente nenhuma necessidade de fazer coleta de lixo lá. Presume-se que as coisas na seção de dados estejam alocadas durante a vida útil do programa.

Jason Baker
fonte
11
Não apenas será desalocado 'eventualmente', mas será desalocado no momento certo.
Boris Yankov
3
  1. O tamanho desses é previsível (constante, exceto para a pilha, e a pilha geralmente é limitada a alguns MB) e geralmente muito pequena (pelo menos em comparação com as centenas de MB que aplicativos grandes podem alocar).

  2. Objetos alocados dinamicamente geralmente têm um pequeno período de tempo em que são alcançáveis. Depois disso, não há como eles serem referenciados novamente. Compare isso com as entradas na seção de dados, variáveis ​​globais e outras coisas: freqüentemente, há um pedaço de código que as referencia diretamente (pense const char *foo() { return "foo"; }). Normalmente, o código não muda, portanto, a referência existe para permanecer e outra referência será criada sempre que a função for chamada (que pode ser a qualquer momento, tanto quanto o computador sabe - a menos que você resolva o problema de interrupção, ou seja, ) Portanto, você não poderia liberar a maior parte dessa memória, pois ela sempre seria acessível.

  3. Em muitas linguagens de coleta de lixo, tudo o que pertence ao programa sendo executado é alocado para heap. No Python, simplesmente não há nenhuma seção de dados nem valores alocados à pilha (existem as referências de variáveis ​​locais e a pilha de chamadas, mas também não há um valor no mesmo sentido que intem C). Todo objeto está na pilha.


fonte
"No Python, simplesmente não há nenhuma seção de dados". Isso não é rigorosamente verdade. Nenhum, True e False são alocados na seção de dados como eu o entendo: stackoverflow.com/questions/7681786/how-is-hashnone-calculated
Jason Baker
@ JasonBaker: Interessante encontrar! Mas não tem nenhum efeito. É um detalhe de implementação e restrito a objetos internos. Isso não é de mencionar que esses objetos não são esperados para ser desalocada na vigência do programa de qualquer maneira, não são, e também são minúsculos em tamanho (menos de 32 bytes cada, eu acho).
@delnan Como Eric Lippert gostava de ressaltar, para a maioria dos idiomas, a existência de regiões de memória separadas para a pilha e a pilha é um detalhe de implementação. Você pode implementar a maioria das linguagens sem usar uma pilha em tudo (embora o desempenho pode sofrer quando você faz) e ainda estar em conformidade com as suas especificações
Jules
2

Como vários outros respondentes disseram, a pilha faz parte do conjunto raiz, portanto é varrida por referências, mas não "coletada", por si só.

Eu só quero responder a alguns dos comentários que implicam que o lixo na pilha não importa; isso ocorre, pois pode fazer com que mais lixo no heap seja considerado acessível. Gravadores conscientes de VM e compilador anulam ou excluem partes mortas da pilha da varredura. No IIRC, algumas VMs têm tabelas de mapeamento de intervalos de PCs para bitmaps de pilha dinâmica e outras apenas anulam os slots. Não sei qual técnica é atualmente preferida.

Um termo usado para descrever essa consideração em particular é seguro para o espaço .

Ryan Culpepper
fonte
Seria interessante saber. O primeiro pensamento é que anular os espaços é o mais realista. Atravessar uma árvore de áreas excluídas pode levar mais tempo do que apenas verificar nulos. Obviamente, qualquer tentativa de compactar a pilha está repleta de perigos! Fazer esse trabalho parecer um processo alucinante / propenso a erros.
Brian Knoblauch
@Brian, na verdade, pensando um pouco mais, para uma VM digitada, você precisa de algo assim de qualquer maneira, para poder determinar quais slots são referências, em vez de números inteiros, flutuantes, etc. Além disso, para compactar a pilha, consulte "CONS Não CONS Seus Argumentos ", de Henry Baker.
Ryan Culpepper
Determinar os tipos de slots e verificar se eles são usados ​​adequadamente pode e geralmente é feito estaticamente, no tempo de compilação (para VMs usando bytecode confiável) ou no tempo de carregamento (onde o bytecode vem de uma fonte não confiável, por exemplo, Java).
Jules
1

Deixe-me apontar alguns conceitos errôneos fundamentais que você e muitos outros erraram:

"Por que a coleta de lixo apenas varre a pilha?" É o contrário. Somente os coletores de lixo mais simples, mais conservadores e mais lentos varrem a pilha. É por isso que eles são tão lentos.

Os coletores de lixo rápidos varrem apenas a pilha (e, opcionalmente, algumas outras raízes, como algumas globais para ponteiros FFI e os registros para ponteiros ativos), e apenas copiam os ponteiros alcançáveis ​​pelos objetos da pilha. O restante é jogado fora (ou seja, ignorado), sem varrer a pilha.

Como o heap é cerca de 1000x maior que a (s) pilha (s), esse GC de varredura de pilha geralmente é muito mais rápido. ~ 15ms vs 250ms em montões de tamanho normal. Como está copiando (movendo) os objetos de um espaço para outro, é chamado principalmente de coletor de cópias semi-espaciais, ele precisa de 2 vezes de memória e, portanto, geralmente não é utilizável em dispositivos muito pequenos, como telefones com pouca memória. É compacto e, portanto, muito mais amigável para o cache, ao contrário dos simples scanners de pilha e varredura.

Como está movendo ponteiros, FFI, identidade e referências são complicadas. A identidade geralmente é resolvida com IDs aleatórios, referências através de ponteiros de encaminhamento. A FFI é complicada, pois objetos estranhos não podem conter ponteiros para o espaço antigo. Os ponteiros de FFI são geralmente mantidos em uma arena separada, por exemplo, com um coletor estático de marcações e varreduras lentas. Ou malloc trivial com recontagem. Observe que o malloc tem uma enorme sobrecarga e conta ainda mais.

Marcar e varrer é trivial de implementar, mas não deve ser usado em programas reais e, principalmente, não deve ser ensinado como o coletor padrão. O mais famoso desses coletores de cópias de escaneamento rápido é chamado coletor de dois dedos Cheney .

suburbano
fonte
A questão parece ser mais sobre quais partes da memória são coletadas como lixo, em vez de algoritmos específicos de coleta de lixo. A última frase implica especialmente que o OP está usando "varredura" como sinônimo genérico para "coleta de lixo", em vez de um mecanismo específico para implementar a coleta de lixo. Considerando isso, sua resposta é dizer que apenas os coletores de lixo mais simples coletam a pilha, e os coletores de lixo rápidos coletam a pilha e a memória estática, deixando a pilha crescer e crescer até ficar sem memória.
8bittree
Não, a pergunta era muito específica e inteligente. As respostas não são assim. Os GCs de marcação lenta e varredura têm duas fases, a etapa de marcação varrendo as raízes na pilha e a fase de varredura varrendo a pilha. Os GCs de cópia rápida têm apenas uma fase, digitalizando a pilha. Fácil assim. Como, aparentemente, ninguém sabe aqui sobre coletores de lixo adequados, a pergunta precisa ser respondida. Sua interpretação é descontroladamente.
rurbano
0

O que é alocado na pilha? Variáveis ​​locais e endereços de retorno (em C). Quando uma função retorna, suas variáveis ​​locais são descartadas. Não é necessário nem prejudicial varrer a pilha.

Muitas linguagens dinâmicas, e também Java ou C # são implementadas em uma linguagem de programação de sistema, geralmente em C. Você poderia dizer que Java é implementado com funções C e usa variáveis ​​locais C e, portanto, o coletor de lixo de Java não precisa varrer a pilha.

Há uma exceção interessante: o coletor de lixo do Chicken Scheme varre a pilha (de certa forma), porque sua implementação usa a pilha como um espaço de primeira geração da coleta de lixo: consulte Wikipedia .

nalply
fonte