Como os coletores de lixo evitam o estouro de pilha?

Então, eu estava pensando em como os coletores de lixo funcionam e pensei em uma questão interessante. Presumivelmente, os coletores de lixo precisam atravessar todas as estruturas da mesma maneira. Eles não sabem o tempo que estão percorrendo uma lista vinculada, uma árvore equilibrada ou o que quer. Eles também não podem usar muita memória em suas pesquisas. Uma maneira possível, e a única maneira de pensar em atravessar TODAS as estruturas, pode ser apenas atravessá-las todas recursivamente, da mesma maneira que faria com uma árvore binária. No entanto, isso causaria um estouro de pilha em uma lista vinculada ou até mesmo em uma árvore binária mal equilibrada. Mas todos os idiomas de coleta de lixo que eu já usei parecem não ter problemas em lidar com esses casos.

No livro do dragão, ele usa uma fila de tipos "Não digitalizados". Basicamente, em vez de percorrer a estrutura recursivamente, apenas adiciona coisas que precisam ser marcadas como uma fila e, em seguida, para cada coisa não marcada no final, ela é excluída. Mas essa fila não ficaria muito grande?

Então, como os coletores de lixo atravessam estruturas arbitrárias? Como essa técnica de travessia evita o transbordamento?

Observe que eu não sou especialista em coleta de lixo. Esta resposta fornece apenas exemplos de técnicas. Não afirmo que seja uma visão geral representativa das técnicas de coleta de lixo.

Uma fila não digitalizada é uma escolha comum. A fila pode ficar grande - potencialmente tão grande quanto a estrutura de dados mais profunda. A fila geralmente é armazenada explicitamente, não na pilha do encadeamento de coleta de lixo.

Depois que todos, exceto um dos filhos de um nó, forem verificados, o nó poderá ser removido da fila não verificada. Isso é basicamente uma otimização de chamada de cauda. Os coletores de lixo podem incluir heurísticas para tentar varrer o filho mais profundo de um nó por último; por exemplo, um GC para Lisp deve verificar o carde a consantes de cdr.

Uma maneira de evitar manter uma fila não digitalizada é modificar os ponteiros no lugar, fazendo o filho apontar temporariamente para o pai. Essa é uma técnica de passagem em árvore com memória constante usada em contextos diferentes dos coletores de lixo. A desvantagem dessa técnica é que, enquanto o GC está percorrendo uma estrutura de dados, a estrutura de dados é inválida; portanto, o GC precisa parar o mundo. Isso não é um problema: muitos coletores de lixo incluem uma fase que para o mundo, além de fases que não perdem o lixo como resultado.

Em poucas palavras : coletores de lixo não usam recursão. Eles apenas controlam o rastreio acompanhando essencialmente dois conjuntos (que podem ser combinados). A ordem de rastreamento e processamento de células é irrelevante, o que oferece considerável liberdade de implementação para representar os conjuntos. Portanto, existem muitas soluções que são realmente muito baratas no uso de memória. Isso é essencial, pois o GC é chamado precisamente quando o heap fica sem memória. As coisas são um pouco diferentes com grandes memórias virtuais, pois novas páginas podem ser facilmente alocadas e o inimigo não é falta de espaço, mas falta de localidade dos dados .

Suponho que você esteja pensando em rastrear coletores de lixo, e não na contagem de referências à qual sua pergunta não parece se aplicar.

A questão está focada no custo da memória de rastreamento para acompanhar um conjunto: o conjunto (para não rastreado) de células de memória acessíveis que ainda contêm ponteiros que ainda não foram rastreados. Isso é apenas metade do problema de memória para coleta de lixo. O GC também deve acompanhar outro conjunto: o conjunto V (para visitado) de todas as células que foram consideradas acessíveis, de modo a recuperar todas as outras células no final do processo. Discutir um e não o outro faz sentido limitado, pois eles podem ter um custo semelhante, usar soluções semelhantes e até mesmo serem combinados.$U$$V$

A primeira coisa a observar é que todos os GC de rastreamento seguem o mesmo modelo abstrato, com base na exploração sistemática do gráfico direcionado de células na memória acessível a partir do programa, onde as células de memória são vértices e ponteiros são as arestas direcionadas. Utiliza para isso os seguintes conjuntos:

• o conjunto (visitado) de células já consideradas acessíveis pelo mutador , ou seja, o programa ou algoritmo para o qual o GC é realizado. O conjunto V é particionado em dois subconjuntos separados: V = U ∪ T ;$V$$V$$V=U\cup T$

• o conjunto (não rastreado) de células visitadas com ponteiros que ainda não foram seguidos;$U$

• o conjunto (rastreado) das células visitadas que tiveram todos os seus ponteiros rastreados.$T$

• $H$

$V$$U$$U$$T$

$U$$V$

$U$$c$$V$$U$$c$$U$$T$

$U$$U$$V=T$$V$$H-V$$V$

$V$$U$$U$$T$

Também pulo detalhes sobre o que é uma célula, se eles vêm em um tamanho ou em muitos, como encontramos indicadores neles, como podem ser compactados e uma série de outras questões técnicas que você pode encontrar em livros e pesquisas sobre coleta de lixo .

$U$

Onde as implementações conhecidas diferem está na maneira como esses conjuntos são realmente representados. Muitas técnicas foram realmente usadas:

• mapa de bits: algum espaço de memória é preservado para um mapa que possui um bit para cada célula de memória, que pode ser encontrado usando o endereço da célula. O bit está ativado quando a célula correspondente está no conjunto definido pelo mapa. Se apenas mapas de bits forem usados, você precisará de apenas 2 bits por célula.

• Como alternativa, você pode ter espaço para um bit de tag especial (ou 2) em cada célula para marcá-lo.

• $\log_2 p$$p$

• você pode testar um predicado no conteúdo da célula e em seus ponteiros.

• você pode realocar a célula em uma parte livre da memória destinada a todas as células pertencentes ao conjunto representado.

• $V$$T$$T$$U$

• você pode realmente combinar essas técnicas, mesmo para um único conjunto.

Como dito, todos os itens acima foram usados ​​por alguns coletores de lixo implementados, por mais estranhos que alguns possam parecer. Tudo depende das várias restrições da implementação. E eles podem ser bastante baratos no uso da memória, possivelmente ajudados pelo processamento de políticas de pedidos que podem ser livremente escolhidas para esse fim, pois não importam para o resultado final.

O que pode parecer o mais estranho, transferir células para uma nova área, é realmente muito comum: é chamado de coleção de cópias. É usado principalmente com memória virtual.

Claramente, não há recursão, e a pilha do algoritmo do mutador não precisa ser usada.

Outro ponto importante é que muitos GC modernos são implementados para grandes memórias virtuais . Então, conseguir espaço para implementar e lista ou pilha extra não é um problema, pois novas páginas podem ser facilmente alocadas. No entanto, em grandes memórias virtuais, o inimigo não é falta de espaço, mas falta de localidade . Em seguida, a estrutura que representa os conjuntos e seu uso deve ser voltada para preservar a localidade da estrutura de dados e da execução do GC. O problema não é o espaço, mas o tempo. Implementações inadequadas têm mais probabilidade de mostrar uma desaceleração inaceitável do que o estouro de memória.

Não dei referências a muitos algoritmos específicos, resultantes de várias combinações dessas técnicas, pois isso parece longo o suficiente.

A maneira padrão de evitar um estouro de pilha é usar uma pilha explícita (armazenada como uma estrutura de dados no heap). Isso funciona para esses propósitos também. Os coletores de lixo geralmente têm uma lista de itens que precisam ser examinados / percorridos, o que serve para essa função. Por exemplo, sua fila "Não digitalizada" é um exemplo exatamente desse tipo de padrão. A fila pode potencialmente ficar grande, mas não causa um estouro de pilha, porque não é armazenada no segmento de pilha. De qualquer forma, nunca será maior que o número de objetos ativos na pilha.

Nas descrições "clássicas" da coleta de lixo (por exemplo, Mark Wilson, " Uniprocessor Garbage Collection Techniques ", Workshop Internacional sobre Gerenciamento de Memória , 1992, ( link alternativo ) ou a descrição na Modern Compiler Implementation de Andrew Appel (Cambridge University Press, 1998)), os colecionadores são classificados como "Marcar e varrer" ou "Copiar".

Os coletores de marcas e varreduras evitam a necessidade de espaço extra usando a reversão do ponteiro, conforme descrito na resposta de @ Gilles. Appel diz que Knuth atribui o algoritmo de reversão de ponteiro a Peter Deutsch e Herbert Schorr e WM Waite.

Os coletores de lixo de cópia usam o que é chamado de algoritmo de Cheyney para executar uma passagem de fila sem precisar de espaço extra. Este algoritmo foi introduzido no CJ Cheyney, "Um algoritmo de compactação de lista não-recursiva", Comm. ACM , 13 (11): 677-678, 1970.

Em um coletor de lixo de cópia, você tem um pedaço de memória que está tentando coletar, chamado from-space , e um pedaço de memória que você está usando para as cópias chamadas to-space . O espaço para o espaço é organizado como uma fila com um scanponteiro apontando para o registro mais antigo copiado, mas não verificado, e um freeponteiro para a próxima posição livre no espaço. A imagem disso no artigo de Wilson é:

À medida que você digitaliza cada item no espaço, você copia seus filhos do espaço para o freeponteiro no espaço e altera o ponteiro para o filho do espaço para a nova cópia do filho no espaço. Há um truque extra que você precisa usar quando suas estruturas de dados não são árvores (quando um filho pode ter mais de um pai). Nesse caso, quando você copia um filho de um espaço para outro, é necessário substituir a versão antiga do filho com um ponteiro de encaminhamento para a nova cópia do filho. Então, se você digitalizar outro ponteiro para a versão antiga da criança, perceberá que ela já foi copiada e não copie novamente.