Como a coleta de lixo funciona em idiomas nativamente compilados?

79

Após procurar várias respostas em um estouro de pilha, fica claro que alguns idiomas compilados nativamente têm coleta de lixo . Mas não está claro para mim como exatamente isso funcionaria.

Entendo como a coleta de lixo pode funcionar com uma linguagem interpretada. O coletor de lixo simplesmente rodaria ao lado do intérprete e excluiria objetos não utilizados e inacessíveis da memória do programa. Ambos estão correndo juntos.

Como isso funcionaria com as linguagens compiladas? Meu entendimento é que, uma vez que o compilador tenha compilado o código-fonte para o código de destino - especificamente o código da máquina nativa - isso é feito. Seu trabalho está terminado. Então, como o programa compilado também pode ser coletado de lixo?

O compilador funciona com a CPU de alguma forma, enquanto o programa é executado para excluir objetos "lixo"? Ou o compilador inclui algum coletor de lixo mínimo no executável do programa compilado.

Acredito que minha última declaração teria mais validade do que a anterior devido a esse trecho desta resposta no Stack Overflow :

Uma dessas linguagens de programação é Eiffel. A maioria dos compiladores Eiffel gera código C por motivos de portabilidade. Este código C é usado para produzir código de máquina por um compilador C padrão. As implementações do Eiffel fornecem GC (e às vezes até GC preciso) para esse código compilado, e não há necessidade de VM. Em particular, o compilador VisualEiffel gerou código de máquina x86 nativo diretamente com suporte total ao GC .

A última declaração parece implicar que o compilador inclui algum programa no executável final que atua como um coletor de lixo enquanto o programa está sendo executado.

A página no site da linguagem D sobre coleta de lixo - que é compilada nativamente e possui um coletor de lixo opcional - também parece sugerir que algum programa em segundo plano seja executado ao lado do programa executável original para implementar a coleta de lixo.

D é uma linguagem de programação de sistemas com suporte para coleta de lixo. Geralmente, não é necessário liberar memória explicitamente. Apenas aloque conforme necessário, e o coletor de lixo retornará periodicamente toda a memória não utilizada para o conjunto de memória disponível.

Se o método mencionado acima for usado, como exatamente funcionaria? O compilador armazena uma cópia de algum programa de coleta de lixo e a cola em cada executável gerado?

Ou eu sou falha no meu pensamento? Em caso afirmativo, quais métodos são usados ​​para implementar a coleta de lixo para linguagens compiladas e como exatamente eles funcionariam?

language-agnostic compiler garbage-collection Christian Dean
fonte
1
Eu apreciaria se o eleitor próximo desta pergunta pudesse declarar exatamente o que está errado para que eu pudesse corrigi-lo?
Christian Dean
6
Se você aceitar o fato de que o GC é basicamente parte de uma biblioteca exigida por uma implementação de linguagem de programação específica, a essência da sua pergunta não tem nada a ver com o GC em si e tudo a ver com vinculação estática versus dinâmica .
Theodoros Chatzigiannakis
7
Você pode considerar o coletor de lixo como parte da biblioteca de tempo de execução que implementa o equivalente ao idioma malloc().
Barmar
9
A operação de um coletor de lixo depende das características do alocador , não do modelo de compilação . O alocador conhece todos os objetos que foram alocados; alocou-os. Agora, tudo o que você precisa é de uma maneira de saber quais objetos ainda estão vivos , e o coletor pode desalocar todos os objetos, exceto eles. Nada nessa descrição tem algo a ver com o modelo de compilação.
precisa
1
O GC é um recurso da memória dinâmica, não um recurso do intérprete.
Dmitry Grigoryev

Respostas:

52

A coleta de lixo em um idioma compilado funciona da mesma maneira que em um idioma interpretado. Idiomas como Go usam o rastreamento de coletores de lixo, mesmo que seu código geralmente seja compilado no código da máquina com antecedência.

A coleta de lixo (rastreamento) geralmente começa caminhando pelas pilhas de chamadas de todos os threads que estão em execução no momento. Os objetos nessas pilhas estão sempre ativos. Depois disso, o coletor de lixo percorre todos os objetos apontados por objetos ativos, até que todo o gráfico de objetos ativos seja descoberto.

É claro que isso exige informações extras que idiomas como C não fornecem. Em particular, requer um mapa do quadro de pilha de cada função que contenha as compensações de todos os ponteiros (e provavelmente seus tipos de dados), bem como mapas de todos os layouts de objetos que contêm as mesmas informações.

No entanto, é fácil ver que idiomas que possuem garantias de tipo fortes (por exemplo, se o ponteiro lança para tipos de dados diferentes não são permitidos) podem realmente computar esses mapas em tempo de compilação. Eles simplesmente armazenam uma associação entre endereços de instruções e mapas de quadros de pilha e uma associação entre tipos de dados e mapas de layout de objetos dentro do binário. Essas informações permitem que eles percorram o gráfico do objeto.

O coletor de lixo em si nada mais é do que uma biblioteca vinculada ao programa, semelhante à biblioteca padrão C. Por exemplo, essa biblioteca poderia fornecer uma função semelhante à malloc()que executa o algoritmo de coleta se a pressão da memória for alta.

avdgrinten
fonte
9
Entre as bibliotecas de utilitários e a compilação JIT, as linhas entre "compilado para nativo" e "executado em um ambiente de tempo de execução" estão ficando cada vez mais embaçadas.
corsiKa
6
Apenas para adicionar um pouco sobre os idiomas que não são compatíveis com o GC: é verdade que C e outros idiomas não fornecem informações sobre pilhas de chamadas, mas se você concorda com algum código específico da plataforma (geralmente inclui um pouco do código de montagem) ainda é possível implementar a "coleta conservadora de lixo". O Boehm GC é um exemplo disso usado em programas da vida real.
Matti Virkkunen
2
@corsiKa Ou melhor, a linha é muito mais distinta. Agora vemos que esses são conceitos diferentes e não relacionados, e não antônimos um do outro.
Kroltan
4
Uma complexidade adicional que você precisa conhecer nos tempos de execução compilados versus interpretados está relacionada a esta frase na sua resposta: "(Rastreando) a coleta de lixo geralmente começa caminhando pelas pilhas de chamadas de todos os threads que estão em execução no momento". Minha experiência na implementação do GC em um ambiente compilado é que rastrear as pilhas não é suficiente. O ponto de partida geralmente suspende os encadeamentos por tempo suficiente para rastrear seus registros , porque eles podem ter referências nos registros que ainda não foram armazenados na pilha. Para um intérprete, isso geralmente não é ...
Jules
... um problema, porque o ambiente pode providenciar para que o GC ocorra em "pontos seguros", onde o intérprete sabe que todos os dados são armazenados com segurança nas pilhas interpretadas.
Jules
123

O compilador armazena uma cópia de algum programa de coleta de lixo e a cola em cada executável gerado?

Parece deselegante e estranho, mas sim. O compilador tem uma biblioteca de utilidades inteira, contendo muito mais do que apenas código de coleta de lixo, e as chamadas para essa biblioteca serão inseridas em cada executável que criar. Isso é chamado de biblioteca de tempo de execução e você ficaria surpreso com quantas tarefas diferentes ela normalmente serve.

Kilian Foth
fonte
51
@ChristianDean Observe que mesmo C possui uma biblioteca de tempo de execução. Embora não tenha GC, ele ainda executa o gerenciamento de memória por meio dessa biblioteca de tempo de execução: malloc()e free()não está embutido no idioma, não faz parte do sistema operacional, mas é função nesta biblioteca. Às vezes, o C ++ também é compilado com uma biblioteca de coleta de lixo, mesmo que o idioma não tenha sido projetado com o GC em mente.
amon
18
O C ++ também contém uma biblioteca de tempo de execução que faz coisas como fazer dynamic_caste exceções funcionarem, mesmo se você não adicionar um GC.
Sebastian Redl
23
A biblioteca de tempo de execução não é necessariamente copiada em cada executável (que é chamado de vinculação estática), apenas pode ser referenciada (um caminho para o binário que contém a biblioteca) e acessada no tempo de execução: trata-se de vinculação dinâmica.
Mouviciel 14/06
16
O compilador também não precisa pular diretamente para o ponto de entrada do seu programa sem que nada aconteça. Estou achando que todo compilador realmente insere um monte de código de inicialização específico da plataforma antes de chamar main(), e é perfeitamente legal, digamos, acionar um encadeamento de GC nesse código. (Supondo que o GC não seja feito dentro de chamadas de alocação de memória.) Em tempo de execução, o GC realmente precisa apenas saber quais partes de um objeto são ponteiros ou referências a objetos, e o compilador precisa emitir o código para converter uma referência de objeto em um ponteiro. se o GC realocar objetos.
millimoose
15
@millimoose: Sim. Por exemplo, em GCC, este pedaço de código é crt0.o(que significa " C R un T ime, o básico do básico"), que fica ligado com cada programa (ou pelo menos a cada programa que não é free-standing ).
Jörg W Mittag
58

Ou o compilador inclui algum coletor de lixo mínimo no código do programa compilado.

Essa é uma maneira estranha de dizer "o compilador vincula o programa a uma biblioteca que executa a coleta de lixo". Mas sim, é isso que está acontecendo.

Isso não é nada de especial: os compiladores geralmente vinculam toneladas de bibliotecas nos programas que compilam; caso contrário, os programas compilados não poderiam fazer muito sem reimplementar muitas coisas do zero: até escrever texto na tela / um arquivo / ... requer uma biblioteca.

Mas talvez o GC seja diferente dessas outras bibliotecas, que fornecem APIs explícitas que o usuário chama?

Não: na maioria dos idiomas, as bibliotecas de tempo de execução fazem muito trabalho nos bastidores sem a API voltada ao público, além do GC. Considere estes três exemplos:

  1. Propagação de exceção e chamada de desenrolamento / destruição de pilha.
  2. Alocação dinâmica de memória (que geralmente não está apenas chamando uma função, como em C, mesmo quando não há coleta de lixo).
  3. Rastreamento de informações dinâmicas do tipo (para elencos etc).

Portanto, uma biblioteca de coleta de lixo não é nada especial e, a priori , nada tem a ver com a compilação antecipada de um programa.

Konrad Rudolph
fonte
este não parece oferecer nada substancial sobre pontos feitos e explicado em resposta topo postado 3 horas antes
mosquito
11
@gnat Eu senti que era útil / necessário porque a resposta principal não é suficientemente forte: menciona fatos semelhantes, mas falha ao apontar que destacar a coleta de lixo é uma distinção completamente artificial. Fundamentalmente, a suposição do OP é falha e a resposta principal não menciona isso. A minha (embora evite o termo bastante brusco "defeituoso").
Konrad Rudolph
Não é tão especial, mas eu diria que é algo especial, já que geralmente as pessoas pensam nas bibliotecas como algo que explicitamente chamam de seu código; em vez de uma implementação da semântica da linguagem fundamental. Acho que a suposição errada do OP aqui é que um compilador é apenas para traduzir código de maneira mais ou menos direta, em vez de instrumentá-lo com chamadas de biblioteca que o autor não especificou.
millimoose
7
As bibliotecas do @millimoose Runtime operam nos bastidores de várias maneiras, sem interação explícita do usuário. Considere a propagação de exceção e empurre o desenrolamento / chamada de destruidor. Considere a alocação dinâmica de memória (que geralmente não está apenas chamando uma função, como em C, mesmo quando não há coleta de lixo). Considere o manuseio de informações de tipo dinâmico (para projeções etc.). Portanto, o GC não é realmente único.
Konrad Rudolph
3
Sim, eu admito que tinha dito isso de maneira estranha. Isso foi simplesmente porque eu era cético em relação ao compilador real fazendo algo assim. Mas agora que penso sobre isso, faz muito mais sentido. O compilador poderia simplesmente vincular um coletor de lixo como qualquer outra parte da biblioteca padrão. Acredito que parte da minha confusão decorreu de pensar em um coletor de lixo como apenas parte de uma implementação de intérprete e não um programa separado por si só.
Christian Dean
23

Como isso funcionaria com as linguagens compiladas?

Sua redação está errada. Uma linguagem de programação é uma especificação escrita em algum relatório técnico (para um bom exemplo, consulte R5RS ). Na verdade, você está se referindo a alguma implementação de linguagem específica (que é um software).

(algumas linguagens de programação têm especificações ruins, ou mesmo os ausentes, ou apenas como em conformidade com alguma implementação amostra; ainda assim, uma linguagem de programação define um comportamento - por exemplo, tem uma sintaxe e semântica -, é não um produto de software, mas poderia ser implementado por algum produto de software; muitas linguagens de programação têm várias implementações; em particular, "compilado" é um adjetivo aplicado a implementações - mesmo que algumas linguagens de programação sejam mais facilmente implementadas por intérpretes do que por compiladores.)

Meu entendimento é que, uma vez que o compilador tenha compilado o código-fonte para o código de destino - especificamente o código da máquina nativa - isso é feito. Seu trabalho está terminado.

Observe que intérpretes e compiladores têm um significado pouco amplo, e algumas implementações de linguagem podem ser consideradas como sendo ambas. Em outras palavras, há um continuum no meio. Leia o Dragon Book mais recente e pense sobre bytecode , compilação JIT , emitindo código C dinamicamente compilado em algum "plugin" e depois dlopen (3) -ed pelo mesmo processo (e nas máquinas atuais, isso é rápido o suficiente para ser compatível com um REPL interativo , veja isso )

Eu recomendo fortemente a leitura do manual do GC . É necessário um livro inteiro para responder . Antes disso, leia a wiki da Garbage Collection (que eu assumo que você leu antes de ler abaixo).

O sistema de tempo de execução da implementação da linguagem compilada contém o coletor de lixo, e o compilador está gerando um código adequado ao sistema de tempo de execução específico. Em particular, as primitivas de alocação (são compiladas no código da máquina que) chamarão (ou poderão) o sistema de tempo de execução.

Então, como o programa compilado também pode ser coletado de lixo?

Apenas emitindo código de máquina que usa (e é "amigável" e "compatível com") o sistema de tempo de execução.

Observe que você pode encontrar várias bibliotecas de coleta de lixo, em particular o Boehm GC , o MPS de Ravenbrook ou mesmo o meu (não mantido) Qish . E codificação de um simples GC não é muito difícil (no entanto, a depuração é mais difícil, e codificação de um competidor GC é difícil ).

Em alguns casos, o compilador usaria um GC conservador (como o Boehm GC ). Então, não há muito para codificar. O GC conservador (quando o compilador chama sua rotina de alocação ou toda a rotina do GC) às vezes varre toda a pilha de chamadas e assume que qualquer zona de memória (indiretamente) acessível a partir da pilha de chamadas está ativa. Isso é chamado de GC conservador porque as informações de digitação são perdidas: se um número inteiro na pilha de chamadas parecer algum endereço, ele será seguido etc.

Em outros casos (mais difíceis), o tempo de execução fornece uma coleta de lixo de cópia geracional (um exemplo típico é o compilador Ocaml, que compila o código Ocaml para o código da máquina usando esse GC). A questão é encontrar com precisão nas pilhas de chamadas todos os indicadores, e alguns deles são movidos pelo GC. Em seguida, o compilador gera metadados que descrevem os quadros da pilha de chamadas, que o tempo de execução usa. Portanto, as convenções de chamada e a ABI estão se tornando específicas para essa implementação (ou seja, compilador) e sistema de tempo de execução.

Em alguns casos, o código de máquina gerado pelo compilador (na verdade, até os fechamentos apontando para ele) é o próprio lixo coletado . Esse é o caso da SBCL (uma boa implementação do Common Lisp), que gera código de máquina para cada interação REPL . Isso também requer alguns metadados que descrevem o código e os quadros de chamada usados ​​dentro dele.

O compilador armazena uma cópia de algum programa de coleta de lixo e a cola em cada executável gerado?

Tipo de. No entanto, o sistema de tempo de execução pode ser uma biblioteca compartilhada, etc. Às vezes (no Linux e em vários outros sistemas POSIX), pode até ser um interpretador de script, por exemplo, passado para execve (2) com um shebang . Ou um intérprete ELF , consulte elf (5) e PT_INTERPetc.

Hoje, a maioria dos compiladores de idiomas com coleta de lixo (e seu sistema de tempo de execução) são hoje software livre . Então faça o download do código fonte e estude-o.

Basile Starynkevitch
fonte
5
Você quer dizer que existem muitas implementações de linguagem de programação sem uma especificação explícita. Sim, eu concordo com isso. Mas o que quero dizer é que uma linguagem de programação não é um software (como um compilador ou um intérprete). É algo que tem uma sintaxe e uma semântica (talvez ambas estejam mal definidas).
Basile Starynkevitch
4
@KonradRudolph: Isso depende inteiramente da sua definição de "formal" e "especificação" :-D Existe a Especificação da Linguagem de Programação Ruby ISO / IEC 30170: 2012 , que especifica um pequeno subconjunto da interseção do Ruby 1.8 e 1.9. Existe o Ruby Spec Suite , um conjunto de exemplos de casos de fronteira que servem como um tipo de "especificação executável". Em seguida, a linguagem de programação Ruby, de David Flanagan e Yukihiro Matsumoto .
Jörg W Mittag
4
Além disso, a documentação do Ruby . Discussões de problemas no Ruby Issue Tracker . Discussões sobre as listas de discussão ruby-core (em inglês) e ruby-dev (em japonês). Expectativas do senso comum da comunidade (por exemplo, Array#[]é O (1) pior caso, Hash#[]é O (1) pior caso amortizado). E por último mas não menos importante: o cérebro de matz.
Jörg W Mittag
6
@KonradRudolph: O ponto é: mesmo uma linguagem sem especificação formal e apenas uma única implementação ainda pode ser separada na "linguagem" (as regras e restrições abstratas) e na "implementação" (os programas de processamento de código de acordo com essas regras e restrições). E a implementação ainda dá origem a uma especificação, ainda que trivial, a saber: "o que quer que o código faça é a especificação". Afinal, foi assim que as especificações ISO, RubySpec e RDocs foram escritas: brincando com a ressonância magnética e / ou a engenharia reversa.
Jörg W Mittag
1
Que bom que você trouxe o coletor de lixo de Bohem. Eu recomendaria o OP estudá-lo porque é um excelente exemplo de como a coleta de lixo pode ser simples, mesmo quando "aparafusada" a um compilador existente.
precisa
6

Já existem boas respostas, mas gostaria de esclarecer alguns mal-entendidos por trás dessa pergunta.

Não existe "linguagem compilada nativamente" em si. Por exemplo, o mesmo código Java foi interpretado (e depois compilado parcialmente em tempo de execução) no meu telefone antigo (Java Dalvik) e é (antecipado) compilado no meu novo telefone (ART).

A diferença entre executar código nativamente e interpretado é muito menos rigorosa do que parece ser. Ambos precisam de algumas bibliotecas de tempo de execução e de algum sistema operacional para funcionar (*). O código interpretado precisa de um intérprete, mas o intérprete é apenas uma parte do tempo de execução. Mas mesmo isso não é rigoroso, pois você pode substituir o intérprete por um compilador (just-in-time). Para obter o desempenho máximo, você pode querer ambos (o Java Runtime para desktop contém um intérprete e dois compiladores).

Não importa como executar o código, ele deve se comportar da mesma maneira. Alocar e liberar memória é uma tarefa para o tempo de execução (assim como abrir arquivos, iniciar threads etc.). No seu idioma, você apenas escreve new X()ou afins. A especificação da linguagem diz o que deve acontecer e o tempo de execução o faz.

Alguma memória livre é alocada, o construtor é chamado etc. Quando não há memória suficiente, o coletor de lixo é chamado. Como você já está no tempo de execução, que é um trecho de código nativo, a existência de um intérprete não importa.

Realmente não há conexão direta entre a interpretação de código e a coleta de lixo. É que linguagens de baixo nível como C são projetadas para velocidade e controle refinado de tudo, o que não se encaixa bem com a idéia de código não nativo ou um coletor de lixo. Portanto, há apenas uma correlação.

Isso era muito verdadeiro nos velhos tempos, onde, por exemplo, o interpretador Java era muito lento e o coletor de lixo, bastante ineficiente. Atualmente, as coisas são muito diferentes e falar sobre uma linguagem interpretada perdeu algum sentido.

(*) Pelo menos quando se fala de código de uso geral, deixando de lado os gerenciadores de inicialização e similares.

maaartinus
fonte
Ocaml e SBCL são compiladores nativos. Portanto, não são implementações "língua nativa compilada".
Basile Starynkevitch
@BasileStarynkevitch WAT? Como a nomeação de alguns compiladores menos conhecidos está relacionada à minha resposta? A SBCL como compilador de uma linguagem originalmente interpretada não é um argumento a favor da minha afirmação de que a distinção não faz sentido?
Maaartinus
O Lisp comum (ou qualquer outro idioma) não é interpretado ou compilado. É uma linguagem de programação (uma especificação). Sua implementação pode ser um compilador, intérprete ou algo intermediário (por exemplo, um intérprete de bytecode). SBCL é uma implementação compilada interativa do Common Lisp. O Ocaml também é uma linguagem de programação (com um interpretador de bytecode e um compilador nativo como implementações).
Basile Starynkevitch
@BasileStarynkevitch É o que estou reivindicando. 1. Não existe linguagem interpretada ou compilada (embora C raramente seja interpretado e o LISP costumava ser compilado raramente, mas isso realmente não importa). 2. Existem implementações interpretadas, compiladas e mistas para a maioria das linguagens conhecidas e nenhuma linguagem impede a compilação ou interpretação.
Maaartinus
6
Eu acho que seu argumento faz muito sentido. O ponto chave para grok é que você sempre executa um "programa nativo" ou "nunca", como quiser. Nenhum exe no Windows é, por si só, executável; ele precisa de um carregador e outros recursos do sistema operacional apenas para iniciar e, na verdade, é parcialmente "interpretado". Isso se torna mais óbvio com os executáveis ​​.net. java myprogé tão ou pouco nativo quanto grep myname /etc/passwdou ld.so myprog: é um executável (o que isso significa) que recebe um argumento e executa operações com os dados.
Peter - Restabelece Monica
3

Os detalhes variam entre as implementações, mas geralmente é uma combinação do seguinte:

  • Uma biblioteca de tempo de execução que inclui um GC. Isso manipulará a alocação de memória e terá outros pontos de entrada, incluindo a função "GC_now".
  • O compilador criará tabelas para o GC para que ele saiba quais campos em quais tipos de dados são referências. Isso também será feito para os quadros de pilha de cada função, para que o GC possa rastrear a partir da pilha.
  • Se o GC for incremental (a atividade do GC é intercalada com o programa) ou simultânea (executada em um encadeamento separado), o compilador também incluirá código de objeto especial para atualizar as estruturas de dados do GC quando as referências forem atualizadas. Os dois têm problemas semelhantes para a consistência dos dados.

No GC incremental e simultâneo, o código compilado e o GC precisam cooperar para manter alguns invariantes. Por exemplo, em um coletor de cópias, o GC trabalha copiando dados ativos do espaço A para o espaço B, deixando para trás o lixo. Para o próximo ciclo, vira A e B e repete. Portanto, uma regra pode ser garantir que, sempre que o programa do usuário tente se referir a um objeto no espaço A, isso seja detectado e o objeto seja copiado imediatamente no espaço B, onde o programa pode continuar acessando. Um endereço de encaminhamento fica no espaço A para indicar ao GC que isso aconteceu, para que outras referências ao objeto sejam atualizadas à medida que são rastreadas. Isso é conhecido como uma "barreira de leitura".

Os algoritmos de GC são estudados desde os anos 60, e há extensa literatura sobre o assunto. Google se você quiser mais informações.

Paul Johnson
fonte