Quando um coletor de lixo compacta objetos na pilha, ele altera as referências na pilha?

18

Parece uma pergunta simples, mas depois de muita leitura sobre o assunto, ainda não encontrei uma resposta definitiva (talvez por ser tão simples).

Minha pergunta é a seguinte: quando um coletor de lixo compacta objetos na pilha, como as referências a esses objetos na pilha são atualizadas? Eu posso pensar em duas soluções possíveis:

  1. Percorra a pilha (e as referências na pilha) e atualize a referência para apontar para o novo local do objeto. Em uma analogia à mudança, seria como enviar uma carta para qualquer pessoa que possua seu endereço e pedir que atualizem o catálogo de endereços com o seu novo endereço.
  2. Forneça algum tipo de tabela de consulta. Seria como deixar um endereço de encaminhamento na estação de correios local.

Os coletores de lixo usam predominantemente um desses dois métodos? Algum outro método? Ambos?

garbage-collection todorojo
fonte
Consulte stackoverflow.com/questions/3799203/… e en.wikipedia.org/wiki/…
Gort the Robot
@StevenBurnap me corrija se estiver errado, mas acredito que o tópico ao qual você vinculou não teve respostas definitivas. Eles pareciam estar especulando sobre essa pergunta exata também. Eu posso ter lido errado. Se eles fizeram fornecer uma resposta para a pergunta, se você não se importa, eu acho que seria útil resumir a resposta aqui para futuros usuários SE (e eu!)
todorojo
O termo para o que você está falando é um "coletor de lixo em movimento". Francamente, não sei como eles são usados ​​com frequência.
Gort the Robot

Respostas:

9

Não tenho conhecimentos específicos sobre isso, mas meu entendimento é que o primeiro método é geralmente usado.

O coletor de lixo precisa analisar a pilha de qualquer maneira para descobrir a que coisas na pilha são referidas na pilha. Depois que decide mover algo, ele precisa corrigir as referências a ele de qualquer maneira, e não há motivo para diferenciar entre heap e stack nesse ponto.

A abordagem da tabela de pesquisa em princípio poderia funcionar. No entanto, isso faria com que todos os acessos a ponteiros precisassem executar 2 etapas. Isso seria um enorme impacto no desempenho em tempos de execução normais. Especialmente para o caso de uso de muitos objetos pequenos. (Esse é um caso em que os programas de GC de última geração geralmente superam a contagem de referência.)

btilly
fonte
3
Eu acrescentaria que acho que os GCs provavelmente tentam não mover as coisas na pilha, a menos que precisem. No mundo atual de multiprocessadores, deve ser um pesadelo de sincronização quando eles precisam atualizar todas as referências para algo na pilha enquanto um programa que usa essas referências está em execução. A tabela de pesquisa simplificaria isso, mas acho que essa é a exceção e não a norma; portanto, a maioria dos GC provavelmente precisa bloquear algumas referências, mover a memória e atualizar as referências. +1 pergunta interessante, +1 boa resposta.
GlenPeterson
3
@GlenPeterson Muitos GCs, de fato, não movem as coisas na pilha e não enfrentam esse problema. Mas um GC compacto, por definição, move objetos ativos para desfragmentar a memória.
btilly
@GlenPeterson, é uma boa observação que mover coisas no heap é uma enorme dor de sincronização, isso é muitas vezes esquecido, embora a compactação GC tenha enormes efeitos de ondulação em um processo em execução devido a isso. É o maior motivo pelo qual as pessoas são instruídas a fazer tudo o que podem para manter os objetos com a menor duração possível, para evitar grandes atualizações de heap, fazendo com que a compactação retenha um mutex longo. A ignorância da maneira como essas coisas se comportam pode levar ao que é chamado com carinho de Modo Freakout do GC.
Jimmy Hoffa
2
O Macintosh e o Palm OS originais usavam uma abordagem de tabela de pesquisa para o gerenciamento de memória. Ponteiros para a tabela foram referidos como alças. Um GC realocado deve saber o paradeiro de absolutamente absolutamente todas as referências a qualquer objeto que ele esteja movendo; o uso de uma única tabela para tais fins simplifica bastante as coisas.
Supercat 24/12