Usar uma tabela de hash na coleta de lixo resolveria o problema mundial de marcar e varrer?

No algoritmo de coleta de lixo mark-sweep-compact, é necessário parar o mundo ao realocar objetos, porque o gráfico de referência se torna inconsistente e é necessário substituir os valores de todas as referências que apontam para o objeto.

Mas e se você tivesse uma tabela de hash com o ID do objeto como chave e ponteiro como valor, e as referências apontassem para o referido ID em vez do endereço do objeto ... a correção de referências exigiria apenas a alteração de um valor e a pausa seria necessária apenas se o objeto é tentado a ser gravado durante a cópia ...

Existe algum erro na minha linha de pensamento?

Atualizar referências não é a única coisa que requer uma pausa. Os algoritmos padrão geralmente agrupados em "varredura de marca" assumem que todo o gráfico de objetos permanece inalterado enquanto está sendo marcado. O manuseio correto de modificações (novos objetos criados, referências alteradas) requer algoritmos alternativos bastante complicados, como o algoritmo tricolor. O termo geral é "coleta de lixo simultânea".

Mas sim, a atualização de referências após a compactação também precisa de uma pausa. E sim, o uso da indireção (por exemplo, através de um ID de objeto persistente e uma tabela de hash para ponteiros reais) pode reduzir bastante a pausa. Pode até ser possível tornar essa peça livre de bloqueios, se assim o desejar. Ainda seria tão complicado acertar quanto qualquer concorrência de memória compartilhada de baixo nível, mas não há razão fundamental para que isso não funcione.

No entanto , isso teria sérias desvantagens. Além de ocupar espaço extra ( pelo menos duas palavras extras para todos os objetos), torna cada desreferência muito mais cara. Mesmo algo tão simples como obter um atributo agora envolve uma pesquisa completa da tabela de hash. Eu estimaria o desempenho atingido como muito pior do que para rastreamento incremental.

Todos os problemas em ciência da computação podem ser resolvidos por outro nível de indireção ... exceto pelo problema de muitas camadas de indireção

Sua abordagem não resolve imediatamente o problema da coleta de lixo, mas apenas a eleva um nível. E a que custo! Agora, todo acesso à memória passa por outra desreferência de ponteiro. Não podemos armazenar em cache o local do resultado, pois, embora possa ter sido realocado, sempre devemos passar pelo ID do objeto. Na maioria dos sistemas, esse indireto não é aceitável e presume-se que parar o mundo tenha um custo total de tempo de execução mais baixo.

Eu disse que sua proposta apenas move o problema, não o resolve. O problema está relacionado à reutilização de IDs de objetos. Os IDs de objetos agora são equivalentes a ponteiros e há apenas uma quantidade finita de endereços. É concebível (especialmente em um sistema de 32 bits) que durante a vida útil do seu programa, mais de objetos INT_MAX tenham sido criados, por exemplo, em um loop como

while (true) {
    Object garbage = new Object();
}

Se apenas incrementarmos o ID do objeto para cada objeto, ficaremos sem IDs em algum momento. Portanto, temos que descobrir quais IDs ainda estão em uso e quais são gratuitos para que possam ser recuperados. Soa familiar? Agora estamos de volta à estaca zero.

Não há nenhum erro na sua linha de pensamento, você acabou de descrever algo muito próximo de como o coletor de lixo Java original funcionava

A Java virtual machine original [6] e algumas máquinas virtuais Smalltalk usam ponteiros indiretos, chamados de identificadores em [6], para se referir a objetos. As alças permitem a fácil realocação de objetos durante a coleta de lixo, pois, com as alças, existe apenas um ponteiro direto para cada objeto: aquele em sua alça. Todas as outras referências ao objeto indiretas através do manuseio. Em tais sistemas de memória baseados em identificadores, enquanto os endereços de objetos mudam durante a vida útil dos objetos e, portanto, não podem ser usados ​​para hash, os endereços de identificadores permanecem constantes.

Hashing com economia de espaço e tempo de objetos coletados pelo lixo

Na implementação atual da Sun da Java Virtual Machine, uma referência a uma instância de classe é um ponteiro para um identificador que é um par de ponteiros: um para uma tabela que contém os métodos do objeto e um ponteiro para o objeto Class que representa o tipo do objeto e o outro na memória alocada do heap Java para os dados do objeto.

A especificação da máquina virtual Java (1997)

Portanto, ele funciona, foi tentado e sua ineficiência levou ao desenvolvimento de sistemas geradores de marca e varredura.