Como um coletor de lixo impede que toda a memória seja varrida em cada coleta?

16

Alguns coletores de lixo (pelo menos Mono e .NET) têm uma área de memória de curto prazo que eles varrem com freqüência e uma área de memória secundária que eles varrem com menos frequência. Mono chama isso de berçário.

Para descobrir quais objetos podem ser descartados, eles examinam todos os objetos a partir de raízes, a pilha e os registros e descartam todos os objetos que não estão mais sendo referenciados.

Minha pergunta é como eles impedem que toda a memória em uso seja varrida em cada coleta? Em princípio, a única maneira de descobrir quais objetos não estão mais em uso é verificar todos os objetos e todas as suas referências. No entanto, isso impediria que o sistema operacional trocasse memória, mesmo que não esteja sendo usado pelo aplicativo e pareça uma enorme quantidade de trabalho que precisa ser feito, também para "Coleção de berçário". Não parece que eles estão ganhando muito usando um berçário.

Estou faltando alguma coisa ou o coletor de lixo está realmente varrendo todos os objetos e todas as referências toda vez que faz uma coleta?

algorithms garbage-collection Pieter van Ginkel
fonte
1
Uma boa visão geral está em um artigo A arte do ajuste da coleta de lixo, escrita por Angelika Langer. Formalmente, é sobre a maneira como é feito em Java, mas conceitos apresentados são praticamente agnóstico linguagem
mosquito

Respostas:

14

As observações fundamentais que permitem que a coleta de lixo geracional evite a verificação de todos os objetos da geração mais antiga são:

  1. Após uma coleção, todos os objetos que ainda existem serão de alguma geração mínima (por exemplo, em .net, após uma coleção Gen0, todos os objetos são Gen1 ou Gen2; após uma coleção Gen1 ou Gen2, todos os objetos são Gen2).
  2. Um objeto, ou parte dele, que não foi gravado desde que uma coleção que promoveu tudo para a geração N ou superior não pode conter referências a objetos de gerações inferiores.
  3. Se um objeto atingiu uma determinada geração, ele não precisa ser identificado como acessível para garantir sua retenção ao coletar gerações inferiores.

Em muitas estruturas de GC, é possível para o coletor de lixo sinalizar objetos ou partes dele de tal maneira que a primeira tentativa de gravar neles acionará um código especial para registrar o fato de que eles foram modificados. Um objeto ou parte dele modificado, independentemente de sua geração, deve ser verificado na próxima coleção, pois pode conter referências a objetos mais recentes. Por outro lado, é muito comum haver muitos objetos antigos que não são modificados entre as coleções. O fato de as verificações de geração mais baixa poderem ignorar esses objetos pode permitir que essas verificações sejam concluídas muito mais rapidamente do que seriam.

Observe que, mesmo que não seja possível detectar quando os objetos são modificados e tiver que varrer tudo em cada passagem do GC, a coleta de lixo geracional ainda pode melhorar o desempenho do estágio de "varredura" de um coletor de compactação. Em alguns ambientes incorporados (especialmente aqueles em que há pouca ou nenhuma diferença de velocidade entre acessos de memória seqüenciais e aleatórios), mover blocos de memória é relativamente caro comparado às referências de marcação. Consequentemente, mesmo que a fase de "marcação" não possa ser acelerada usando um coletor de gerações, acelerar a fase de "varredura" pode valer a pena.

supercat
fonte
movimentar blocos de memória é caro em qualquer sistema; portanto, melhorar a varredura é um ganho, mesmo no seu sistema de CPU quad Ghz.
Gbjbaanb
@gbjbaanb: Em muitos casos, o custo de digitalizar tudo para encontrar objetos ao vivo seria significativo e censurável, mesmo que o movimento dos objetos fosse totalmente gratuito. Consequentemente, deve-se, quando praticável, evitar a digitalização de objetos antigos. Por outro lado, abster-se de compactar objetos antigos é uma otimização simples que pode ser realizada mesmo em estruturas simples. BTW, se alguém estivesse projetando uma estrutura de GC para um pequeno sistema incorporado, o suporte declarativo a objetos imutáveis ​​poderia ser útil. Controlar se um objeto mutável foi alterado é difícil, mas pode-se fazer bem em ... #
23712
... simplesmente assuma que objetos mutáveis ​​precisam ser varridos a cada passagem do GC, mas objetos imutáveis ​​não. Mesmo que a única maneira de construir um objeto imutável fosse construir um "protótipo" no espaço mutável e copiá-lo, a operação de cópia extra única poderia evitar a necessidade de varrer o objeto em futuras operações do GC.
Supercat
Aliás, o desempenho da coleta de lixo nas implementações do BASIC da década de 1980 para os microprocessadores 6502 (e talvez outros também) poderia ser bastante aprimorado em alguns casos, se um programa que gerasse muitas seqüências de caracteres que nunca mudariam, copiasse o "próximo alocação de cadeia "ponteiro para o ponteiro" topo do espaço de cadeia ". Essa mudança impediria o coletor de lixo de examinar qualquer uma das cadeias antigas para ver se elas ainda eram necessárias. O Commodore 64 não era de alta tecnologia, mas esse GC "geracional" ajudaria mesmo lá.
Supercat
7

Os GCs aos quais você está se referindo são coletores de lixo geracionais . Eles são projetados para tirar o máximo proveito de uma observação conhecida como "mortalidade infantil" ou "hipótese geracional", o que significa que a maioria dos objetos se torna inacessível muito rapidamente. Eles realmente digitalizam a partir das raízes, mas ignoram todos os objetos antigos . Portanto, eles não precisam varrer a maioria dos objetos na memória, eles examinam apenas objetos jovens (à custa de não detectar objetos antigos inacessíveis, pelo menos não nesse ponto).

"Mas isso está errado", ouvi você gritar, "objetos antigos podem e se referem a objetos jovens". Você está certo, e existem várias soluções para isso, que giram em torno do ganho de conhecimento, rápida e eficientemente, quais objetos antigos devem ser verificados e quais são seguros para ignorar. Eles se resumem a objetos de gravação ou pequenos intervalos de memória (maiores que os objetos, mas muito menores que a pilha inteira) que contêm indicadores para as gerações mais jovens. Outros os descreveram muito melhor do que eu, portanto, darei algumas palavras-chave: Marcação de cartões, conjuntos lembrados, barreiras de gravação. Existem outras técnicas também (incluindo híbridos), mas elas abrangem as abordagens comuns que eu conheço.


fonte
3

Para descobrir quais objetos do viveiro ainda estão ativos, o coletor só precisa varrer o conjunto raiz e qualquer objeto antigo que tenha sido alterado desde a última coleção , pois um objeto antigo que não tenha sido alterado recentemente não poderá apontar para um objeto jovem . Existem algoritmos diferentes para manter essas informações em diferentes níveis de precisão (de um conjunto exato de campos alterados a um conjunto de páginas em que a mutação pode ter ocorrido), mas todos geralmente envolvem algum tipo de barreira de gravação : código executado em todas as referências mutação de tipo de campo que atualiza a contabilidade do GC.

Ryan Culpepper
fonte
1

A geração mais antiga e mais simples de coletores de lixo, na verdade, examinou toda a memória e teve que interromper todo o outro processamento enquanto o fazia. Algoritmos posteriores melhoraram isso de várias maneiras - tornando a cópia / digitalização incremental ou executada em paralelo. A maioria dos coletores de lixo modernos segregam objetos em gerações e gerenciam cuidadosamente ponteiros entre gerações, para que as gerações mais novas possam ser coletadas sem perturbar as mais antigas.

O ponto principal é que os coletores de lixo trabalham em estreita colaboração com o compilador e com o restante do tempo de execução para manter a ilusão de que ele está assistindo toda a memória.

ddyer
fonte
Não tenho certeza de quais abordagens de coleta de lixo foram usadas em minicomputadores e mainframes antes do final da década de 1970, mas o coletor de lixo do Microsoft BASIC, pelo menos em máquinas 6502, definiria o ponteiro da "próxima seqüência" para o topo da memória e pesquisaria todas as referências de string para encontrar o endereço mais alto que estava abaixo do "próximo ponteiro de string". Essa string seria copiada logo abaixo do "próximo ponteiro da string", e esse ponteiro seria estacionado logo abaixo dela. O algoritmo seria repetido. Era possível que o código fizesse o ponteiro dos ponteiros para fornecer ... #
22612
... algo como coleção geracional. Às vezes, me perguntei como seria difícil corrigir o BASIC para implementar a coleção "geracional", simplesmente mantendo os endereços da parte superior de cada geração e adicionando algumas operações de troca de ponteiro antes e depois de cada ciclo do GC. O desempenho do GC ainda seria muito ruim, mas em muitos casos poderia ser cortado de dezenas de segundos a décimos de segundos.
Supercat
-2

Basicamente ... O GC usa "buckets" para separar o que está em uso e o que não está. Depois de fazer a verificação, elimina as coisas que não estão em uso e move todo o resto para a 2ª geração (que é verificada com menos frequência que a 1ª geração) e depois move as coisas que ainda estão em uso na 2ª den para a 3ª geração.

Portanto, as coisas da 3ª geração geralmente são objetos que ficam presos por algum motivo e o GC não verifica lá com muita frequência.

aserwin
fonte
1
Mas como ele sabe quais objetos estão em uso?
Pieter van Ginkel
Ele monitora quais objetos podem ser alcançados a partir de um código acessível. Depois que um objeto não está mais acessível a partir de qualquer código que pode executar (por exemplo, código para um método que retornou), então o GC sabe que é seguro para coletar
johnl
Vocês estão descrevendo como os GCs estão corretos, não como eles são eficientes. A julgar pela pergunta, o OP sabe muito bem disso.
@ delnan sim, eu estava respondendo à pergunta de como ele sabe quais objetos estão em uso, qual é o que estava no comentário de Pieter.
precisa saber é
-5

O algoritmo normalmente usado por este GC é o Naïve mark-and-sweep

você também deve estar ciente do fato de que isso não é gerenciado pelo próprio C #, mas pelo chamado CLR .

user827992
fonte
Essa é a sensação que tive ao ler sobre o coletor de lixo de Mono. No entanto, o que eu não entendo é por que, se eles estão examinando o conjunto completo de trabalho em uma coleção, eles têm um coletor geracional com o qual o GEN-0 coleta muito rapidamente. Como isso pode ser rápido com um conjunto de digamos 2 GB?
Pieter van Ginkel
bem, o verdadeiro GC para mono é Sgen, você deve ler este mono-project.com/Generational_GC ou alguns artigos online schani.wordpress.com/tag/mono infoq.com/news/2011/01/SGen , o ponto é que Como essas novas tecnologias, como CLR e CLI, têm um design realmente modular, a linguagem se torna apenas uma maneira de expressar algo para o CLR e não uma maneira de produzir código binário. Sua pergunta é sobre detalhes da implementação e não sobre algoritmos, porque um algoritmo ainda não tem uma implementação, você deve ler artigos e artigos técnicos da Mono, mais ninguém.
user827992
Estou confuso. A estratégia que um coletor de lixo usa não é um algoritmo?
Pieter van Ginkel
2
-1 Pare de confundir OP. O fato de o GC fazer parte do CLR e não ser específico do idioma não é relevante. Um GC é principalmente caracterizada pelo caminho que define a pilha e determina a acessibilidade, e o último é tudo sobre o algoritmo (s) usado para isso. Embora possa haver muitas implementações de um algoritmo, e você não deve se envolver nos detalhes da implementação, o algoritmo sozinho determina quantos objetos são verificados. Um GC geracional é simplesmente um algoritmo + layout de pilha que tenta utilizar a "hipótese geracional" (que a maioria dos objetos morre jovem). Estes não são ingênuos.
4
Algoritmo! = Implementação de fato, mas uma implementação só pode se desviar tão longe antes de se tornar uma implementação de um algoritmo diferente. Uma descrição de algoritmo, no mundo da GC, é muito específica e inclui coisas como não varrer toda a pilha na coleção do berçário e como os ponteiros entre gerações são encontrados e armazenados. É verdade que um algoritmo não informa quanto tempo levará uma etapa específica do algoritmo, mas isso não é relevante para essa questão.