Como os coletores de lixo evitam o estouro de pilha?

23

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?

Jake
fonte
1
O GC atravessa todas as estruturas mais ou menos da mesma maneira, mas apenas em um sentido muito abstrato (ver resposta). O modo como eles controlam as coisas concretamente é muito mais sofisticado do que o indicado pelas apresentações elementares que você pode encontrar nos livros didáticos. E eles não usam recursão. Além disso, com memória virtual, implementações ruins são exibidas como desaceleração do GC, raramente como excesso de memória.
babou
Você se preocupa com o espaço necessário para o rastreamento. Mas e o espaço ou as estruturas necessárias para distinguir a memória que foi rastreada e é conhecida por estar em uso, da memória que é potencialmente recuperável. Isso pode ter um custo de memória significativo, possivelmente proporcional ao tamanho da pilha.
babou
Imaginei que isso seria feito com um vetor de bits em um tamanho de objeto maior que 16 bytes ou mais, para que a sobrecarga fosse 1000 vezes menos no mínimo.
Jake
Existem várias maneiras de fazer isso (consulte a resposta) e elas também podem ser usadas para rastreamento, o que responderia à sua pergunta (vetores ou bitmaps podem ser usados ​​para rastreamento, em vez da pilha ou fila que você sugere). Você não pode assumir que todos os objetos são grandes, a menos que pretenda desperdiçar espaço em objetos pequenos, dos quais podem haver muitos, e não se preocupe com o espaço. Se você estiver na memória virtual, o espaço geralmente é muito menos um problema e os problemas são muito diferentes.
babou

Respostas:

13

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.

Gilles 'SO- parar de ser mau'
fonte
2
A técnica descrita no último parágrafo é freqüentemente chamada de " reversão de ponteiro ".
Wandering Logic
@WanderingLogic Sim, a reversão do ponteiro é como eu o chamei na minha própria resposta. É devido a Deutsch, Schorr e Waite (1967). No entanto, é incorrecto afirmar que ele funciona na memória constante: ele exige extra de bits para cada célula com p ponteiros, embora este pode ser reduzido pelo uso de pilhas bits. A resposta aceita que você faz referência não é totalmente correta ou completa pelo mesmo motivo. registro2pp
babou
Eu tenho usado reversão ponteiro em uma GC personalizado sem precisar esses bits extras; o truque era usar uma representação especial na memória de objetos na memória. Ou seja, o objeto "cabeçalho" estava no meio, com campos de ponteiro antes do cabeçalho e campos sem ponteiro depois; além disso, todos os ponteiros estavam alinhados e o cabeçalho incluía um campo com o bit menos significativo sempre definido. Assim, durante a reversão da reversão do ponteiro, alcançar o próximo ponteiro e perceber que havíamos terminado com um objeto poderia ser feito sem ambiguidade, sem os bits extras. Esse layout também suportava herança de OOP.
22615 Thomas Barin
@ThomasPornin Acho que a informação do bit precisa estar em algum lugar. A questão é onde? Podemos discutir isso no chat? Eu tenho que sair agora, mas gostaria de chegar ao fundo disso. Ou existe uma descrição acessível na web?
babou
1
@babou e Thomas please
Gilles 'SO- stop
11

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

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 ;VVV=UT

  • 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

VvocêUT

UV

UcVUcUT

UUV=TVHVV

VUUT

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.

  • log2pp

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

  • VTTU

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

babou
fonte
4

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.

DW
fonte
Quando o GC é chamado, o heap geralmente está cheio. Outro ponto é que acontece que a pilha ea crescer montão de ambas as extremidades do mesmo espaço de memória ..
babou
4

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 é:

Exemplo de algoritmo de Cheyney

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

Lógica Errante
fonte
Na verdade, conforme explicado na minha resposta, as coleções Mark + Sweep e Copy são o mesmo algoritmo gráfico abstrato. A coleção MS e Copy diferem apenas na maneira como os conjuntos usados ​​pelo algoritmo abstrato são implementados, e as duas famílias são incluídas, com muitas variantes, em alguma combinação das técnicas de implementação de conjuntos descritas na minha resposta. Algumas variantes de GC realmente misturam MS e Copiar no mesmo GC. A separação entre MS e Copy é vista por alguns como uma maneira conveniente de estruturar livros, mas é uma visão arbitrária, e acredito desatualizada.
babou
@babou: Se alguém estiver usando um algoritmo de cópia no qual tudo o que for visitado será copiado (lento, mas pode ser útil em pequenas plataformas onde o conjunto de trabalho nunca é tão grande), alguns algoritmos podem ser um pouco simplificados, pois é possível usar a memória anteriormente ocupada por um objeto realocado como um bloco de rascunho. Também é possível obter uma capacidade limitada de outros threads executarem acessos somente leitura aos objetos durante a coleção, desde que se verifique a validade do objeto antes e depois de cada leitura e siga o ponteiro de encaminhamento se um objeto foi movido.
supercat
@ supercat Não tenho certeza do que você está tentando dizer, qual é a sua intenção. Algumas de suas declarações parecem corretas. Mas não entendo como você pode usar do espaço antes que o ciclo do GC termine (ele contém ponteiros de encaminhamento). E seria um bloco de anotações para quê? Simplifique o algoritmo como? Em relação a vários segmentos de mutadores executados enquanto o GC está ocorrendo, esse é um problema ortogonal, embora possa afetar severamente a implementação. Eu não tentaria abordar isso nos comentários. Isso deve gerar menos problemas no acesso somente leitura, mas o diabo está nos detalhes.
babou