Rastreando coleta de lixo - Tracing garbage collection
Em programação de computador , o rastreamento da coleta de lixo é uma forma de gerenciamento automático de memória que consiste em determinar quais objetos devem ser desalocados ("coleta de lixo") rastreando quais objetos são acessíveis por uma cadeia de referências de certos objetos "raiz", e considerando o descanse como “lixo” e os recolha. Rastrear a coleta de lixo é o tipo mais comum de coleta de lixo - tanto que "coleta de lixo" geralmente se refere ao rastreamento da coleta de lixo, em vez de outros métodos, como contagem de referência - e há um grande número de algoritmos usados na implementação.
Acessibilidade de um objeto
Informalmente, um objeto é alcançável se for referenciado por pelo menos uma variável no programa, diretamente ou por meio de referências de outros objetos alcançáveis. Mais precisamente, os objetos podem ser alcançados de apenas duas maneiras:
- Um conjunto distinto de raízes: objetos que são considerados alcançáveis. Normalmente, eles incluem todos os objetos referenciados de qualquer lugar na pilha de chamadas (ou seja, todas as variáveis locais e parâmetros nas funções que estão sendo chamadas) e quaisquer variáveis globais .
- Qualquer coisa referenciada a partir de um objeto alcançável é ela mesma alcançável; mais formalmente, alcançabilidade é um fechamento transitivo .
A definição de alcançabilidade de "lixo" não é ótima, visto que a última vez que um programa usa um objeto pode ser muito antes de esse objeto sair do escopo do ambiente. Às vezes, é feita uma distinção entre lixo sintático , aqueles objetos que o programa não pode alcançar, e lixo semântico , aqueles objetos que o programa de fato nunca mais usará. Por exemplo:
Object x = new Foo();
Object y = new Bar();
x = new Quux();
/* At this point, we know that the Foo object
* originally assigned to x will never be
* accessed: it is syntactic garbage.
*/
/* In the following block, y *could* be semantic garbage;
* but we won't know until x.check_something() returns
* some value -- if it returns at all.
*/
if (x.check_something()) {
x.do_something(y);
}
System.exit(0);
O problema de identificar precisamente o lixo semântico pode ser facilmente mostrado como parcialmente decidível : um programa que aloca um objeto X , executa um programa de entrada arbitrário P e usa X se e somente se P terminar exigiria um coletor de lixo semântico para resolver a parada problema . Embora os métodos heurísticos conservadores para detecção de lixo semântico permaneçam uma área de pesquisa ativa, essencialmente todos os coletores de lixo práticos enfocam o lixo sintático.
Outra complicação com essa abordagem é que, em linguagens com tipos de referência e tipos de valor não encaixotados , o coletor de lixo precisa ser capaz de, de alguma forma, distinguir quais variáveis na pilha ou campos em um objeto são valores regulares e quais são referências: na memória, um inteiro e uma referência podem ser semelhantes. O coletor de lixo então precisa saber se deve tratar o elemento como uma referência e segui-lo, ou se é um valor primitivo. Uma solução comum é o uso de ponteiros marcados .
Referências fortes e fracas
O coletor de lixo pode recuperar apenas objetos que não tenham referências apontando para eles direta ou indiretamente do conjunto raiz. No entanto, alguns programas requerem referências fracas , que devem ser utilizáveis enquanto o objeto existir, mas não devem prolongar sua vida útil. Em discussões sobre referências fracas, as referências comuns às vezes são chamadas de referências fortes . Um objeto é elegível para a coleta de lixo se não houver referências fortes (ou seja, comuns) a ele, embora ainda possa haver algumas referências fracas a ele.
Uma referência fraca não é simplesmente qualquer ponteiro para o objeto com o qual um coletor de lixo não se preocupa. O termo é normalmente reservado para uma categoria gerenciada adequadamente de objetos de referência especial que são seguros para uso mesmo depois que o objeto desaparece porque eles perdem para um valor seguro (geralmente null). Uma referência insegura que não é conhecida pelo coletor de lixo simplesmente permanecerá pendente, continuando a se referir ao endereço onde o objeto residia anteriormente. Esta não é uma referência fraca.
Em algumas implementações, as referências fracas são divididas em subcategorias. Por exemplo, a Java Virtual Machine fornece três formas de referências fracas, ou seja , referências suaves , referências fantasmas e referências fracas regulares. Um objeto referenciado suavemente só é elegível para recuperação, se o coletor de lixo decidir que o programa está com pouca memória. Ao contrário de uma referência suave ou uma referência fraca regular, uma referência fantasma não fornece acesso ao objeto ao qual faz referência. Em vez disso, uma referência fantasma é um mecanismo que permite ao coletor de lixo notificar o programa quando o objeto referenciado torna-se alcançável fantasma . Um objeto é alcançável por fantasma, se ainda residir na memória e for referenciado por uma referência fantasma, mas seu finalizador já foi executado. Da mesma forma, o Microsoft.NET fornece duas subcategorias de referências fracas, ou seja, referências fracas longas (rastreia a ressurreição) e referências fracas curtas.
Coleções fracas
Estruturas de dados também podem ser concebidas com recursos de rastreamento fracos. Por exemplo, tabelas de hash fracas são úteis. Como uma tabela de hash regular, uma tabela de hash fraca mantém uma associação entre pares de objetos, onde cada par é entendido como uma chave e um valor. No entanto, a tabela hash não mantém, na verdade, uma referência forte sobre esses objetos. Um comportamento especial ocorre quando a chave ou o valor ou ambos se tornam lixo: a entrada da tabela de hash é excluída espontaneamente. Existem outros refinamentos, como tabelas de hash que têm apenas chaves fracas (referências de valor são comuns, referências fortes) ou apenas valores fracos (referências de chave são fortes).
As tabelas de hash fracas são importantes para manter associações entre objetos, de modo que os objetos envolvidos na associação ainda podem se tornar lixo se nada no programa se referir a eles por mais tempo (exceto a tabela de hash associada).
O uso de uma tabela de hash regular para tal propósito pode levar a um "vazamento de memória lógica": o acúmulo de dados alcançáveis que o programa não precisa e não usará.
Algoritmo básico
Os coletores de rastreamento são assim chamados porque rastreiam o conjunto de trabalho da memória. Esses coletores de lixo realizam a coleta em ciclos. É comum que os ciclos sejam disparados quando não há memória livre suficiente para o gerenciador de memória atender a uma solicitação de alocação. Mas os ciclos muitas vezes podem ser solicitados pelo modificador diretamente ou executados em um cronograma. O método original envolve uma marca-e-varredura ingênua em que todo o conjunto de memória é tocado várias vezes.
Marca-e-varredura ingênua
No método ingênuo de marcar e varrer, cada objeto na memória tem um sinalizador (normalmente um único bit) reservado apenas para uso na coleta de lixo. Este sinalizador está sempre desmarcado , exceto durante o ciclo de coleta.
O primeiro estágio é o estágio de marcação, que faz uma travessia em árvore de todo o 'conjunto raiz' e marca cada objeto apontado por uma raiz como estando 'em uso'. Todos os objetos para os quais esses objetos apontam, e assim por diante, também são marcados, de forma que todos os objetos que podem ser acessados por meio do conjunto raiz sejam marcados.
No segundo estágio, o estágio de varredura , toda a memória é escaneada do início ao fim, examinando todos os blocos livres ou usados; aqueles não marcados como 'em uso' não são alcançáveis por nenhuma raiz e sua memória é liberada. Para objetos marcados em uso, o sinalizador em uso é apagado, preparando para o próximo ciclo.
Esse método tem várias desvantagens, sendo a mais notável que todo o sistema deve ser suspenso durante a coleta; nenhuma mutação do conjunto de trabalho pode ser permitida. Isso pode fazer com que os programas 'travem' periodicamente (e geralmente de forma imprevisível), tornando impossíveis alguns aplicativos de tempo real e críticos. Além disso, toda a memória de trabalho deve ser examinada, grande parte dela duas vezes, podendo causar problemas em sistemas de memória paginada .
Marcação tricolor
Por causa desses problemas de desempenho, a maioria dos coletores de lixo de rastreamento modernos implementam alguma variante da abstração de marcação de três cores , mas coletores simples (como o coletor de marcação e varredura ) geralmente não tornam essa abstração explícita. A marcação tricolor funciona conforme descrito abaixo.
Três conjuntos são criados - branco , preto e cinza :
- O conjunto branco, ou conjunto condenado , é o conjunto de objetos candidatos à reciclagem de memória.
- O conjunto preto é o conjunto de objetos que podem ser mostrados como não tendo referências de saída para objetos no conjunto branco e que podem ser alcançados a partir das raízes. Os objetos no conjunto preto não são candidatos à coleção.
- O conjunto cinza contém todos os objetos acessíveis a partir das raízes, mas ainda não verificados em busca de referências a objetos "brancos". Uma vez que são conhecidos por serem alcançáveis a partir das raízes, eles não podem ser coletados como lixo e acabarão no conjunto preto após serem digitalizados.
Em muitos algoritmos, inicialmente o conjunto preto começa vazio, o conjunto cinza é o conjunto de objetos que são diretamente referenciados a partir das raízes e o conjunto branco inclui todos os outros objetos. Cada objeto na memória está o tempo todo em exatamente um dos três conjuntos. O algoritmo procede da seguinte forma:
- Escolha um objeto do conjunto cinza e mova-o para o conjunto preto.
- Mova cada objeto branco que faz referência ao conjunto cinza. Isso garante que nem este objeto nem qualquer objeto a que ele faz referência possam ser coletados como lixo.
- Repita as duas últimas etapas até que o conjunto cinza esteja vazio.
Quando o conjunto cinza está vazio, a varredura é concluída; os objetos pretos são alcançáveis a partir das raízes, enquanto os objetos brancos não são e podem ser coletados no lixo.
Uma vez que todos os objetos não imediatamente acessíveis a partir das raízes são adicionados ao conjunto branco, e os objetos só podem se mover do branco para o cinza e do cinza para o preto, o algoritmo preserva uma invariante importante - nenhum objeto preto faz referência a objetos brancos. Isso garante que os objetos brancos possam ser liberados quando o conjunto cinza estiver vazio. Isso é chamado de invariante tricolor . Algumas variações no algoritmo não preservam essa invariante, mas usam uma forma modificada para a qual todas as propriedades importantes são válidas.
O método tricolor tem uma vantagem importante - pode ser executado "em tempo real", sem interromper o sistema por períodos significativos de tempo. Isso é feito marcando objetos à medida que são alocados e durante a mutação, mantendo os vários conjuntos. Ao monitorar o tamanho dos conjuntos, o sistema pode realizar a coleta de lixo periodicamente, em vez de conforme necessário. Além disso, evita-se a necessidade de tocar todo o conjunto de trabalho em cada ciclo.
Estratégias de implementação
Móvel vs. imóvel
Uma vez que o conjunto inacessível foi determinado, o coletor de lixo pode simplesmente liberar os objetos inacessíveis e deixar tudo como está, ou pode copiar alguns ou todos os objetos alcançáveis em uma nova área da memória, atualizando todas as referências a esses objetos como precisava. Eles são chamados de coletores de lixo "não móveis" e "móveis" (ou, alternativamente, "não compactadores" e "compactadores"), respectivamente.
A princípio, um algoritmo móvel pode parecer ineficiente em comparação a um não móvel, uma vez que parece ser necessário muito mais trabalho em cada ciclo. Mas o algoritmo móvel leva a várias vantagens de desempenho, tanto durante o ciclo de coleta de lixo em si quanto durante a execução do programa:
- Nenhum trabalho adicional é necessário para recuperar o espaço liberado por objetos mortos; toda a região da memória da qual os objetos alcançáveis foram movidos pode ser considerada espaço livre. Em contraste, um GC imóvel deve visitar cada objeto inacessível e registrar que a memória que ocupou está disponível.
- Da mesma forma, novos objetos podem ser alocados muito rapidamente. Uma vez que grandes regiões contíguas de memória geralmente são disponibilizadas por um GC em movimento, novos objetos podem ser alocados simplesmente incrementando um ponteiro de 'memória livre'. Uma estratégia imóvel pode, depois de algum tempo, levar a um heap altamente fragmentado , exigindo uma consulta cara de "listas livres" de pequenos blocos de memória disponíveis para alocar novos objetos.
- Se uma ordem de passagem apropriada for usada (como cdr-first para list conses ), os objetos podem ser movidos muito perto dos objetos aos quais eles se referem na memória, aumentando a chance de que eles estejam localizados na mesma linha de cache ou página de memória virtual . Isso pode acelerar significativamente o acesso a esses objetos por meio dessas referências.
Uma desvantagem de um coletor de lixo móvel é que ele só permite o acesso por meio de referências gerenciadas pelo ambiente de coleta de lixo e não permite aritmética de ponteiro . Isso ocorre porque quaisquer ponteiros para objetos serão invalidados se o coletor de lixo mover esses objetos (eles se tornam ponteiros pendentes ). Para interoperabilidade com o código nativo, o coletor de lixo deve copiar o conteúdo do objeto para um local fora da região de coleta de lixo da memória. Uma abordagem alternativa é fixar o objeto na memória, evitando que o coletor de lixo o mova e permitindo que a memória seja diretamente compartilhada com ponteiros nativos (e possivelmente permitindo aritmética de ponteiro).
Copiar vs. marcar e varrer vs. marcar e não varrer
Não só os colecionadores diferem em se eles estão se movendo ou não, eles também podem ser categorizados pela forma como tratam os conjuntos de objetos brancos, cinza e pretos durante um ciclo de coleta.
A abordagem mais direta é o coletor semiespacial , que data de 1969. Nesse coletor móvel, a memória é dividida em um "do espaço" e "para o espaço" de tamanho igual. Inicialmente, os objetos são alocados no "espaço" até que fique cheio e um ciclo de coleta seja disparado. No início do ciclo, o "para o espaço" passa a ser o "do espaço" e vice-versa. Os objetos alcançáveis do conjunto raiz são copiados do "do espaço" para o "para o espaço". Esses objetos são verificados por sua vez, e todos os objetos para os quais eles apontam são copiados para "para o espaço", até que todos os objetos alcançáveis tenham sido copiados para "para o espaço". Uma vez que o programa continua a execução, novos objetos são novamente alocados no "espaço" até que ele esteja novamente cheio e o processo seja repetido.
Essa abordagem é muito simples, mas como apenas um semiespaço é usado para alocar objetos, o uso de memória é duas vezes maior em comparação com outros algoritmos. A técnica também é conhecida como parar e copiar . O algoritmo de Cheney é um aprimoramento do coletor de semi-espaço.
Um coletor de lixo de marcação e varredura mantém um ou dois bits com cada objeto para registrar se é branco ou preto. O conjunto cinza é mantido como uma lista separada ou usando outro bit. Como a árvore de referência é percorrida durante um ciclo de coleta (a fase de "marca"), esses bits são manipulados pelo coletor. Uma "varredura" final das áreas de memória, então, libera objetos brancos. A estratégia de marcação e varredura tem a vantagem de que, uma vez que o conjunto condenado seja determinado, uma estratégia de coleta móvel ou imóvel pode ser seguida. Essa escolha de estratégia pode ser feita em tempo de execução, conforme a memória disponível permitir. Tem a desvantagem de "inchar" os objetos em uma pequena quantidade, como em, cada objeto tem um pequeno custo de memória oculto por causa da lista / bit extra. Isso pode ser um pouco atenuado se o coletor também lidar com a alocação, pois então ele poderia usar bits não utilizados nas estruturas de dados de alocação. Ou, essa "memória oculta" pode ser eliminada usando um ponteiro Tagged , trocando o custo da memória pelo tempo de CPU. No entanto, a marcação e varredura é a única estratégia que coopera prontamente com alocadores externos em primeiro lugar.
Um coletor de marcar e não varrer , como o marcar e varrer, mantém um bit com cada objeto para registrar se é branco ou preto; o conjunto cinza é mantido como uma lista separada ou usando outro bit. Existem duas diferenças principais aqui. Primeiro, preto e branco significam coisas diferentes do que no coletor de marca e varredura. Em um coletor "marque e não varra", todos os objetos alcançáveis são sempre pretos. Um objeto é marcado em preto no momento em que é alocado e permanecerá preto mesmo se se tornar inacessível. Um objeto branco é memória não utilizada e pode ser alocado. Em segundo lugar, a interpretação do bit preto / branco pode mudar. Inicialmente, o bit preto / branco pode ter o sentido de (0 = branco, 1 = preto). Se uma operação de alocação falhar em encontrar qualquer memória disponível (branca), isso significa que todos os objetos são marcados como usados (preto). O sentido do bit preto / branco é então invertido (por exemplo, 0 = preto, 1 = branco). Tudo fica branco. Isso interrompe momentaneamente a invariante de que os objetos alcançáveis são pretos, mas uma fase de marcação completa segue imediatamente, para marcá-los novamente em preto. Feito isso, toda a memória inacessível é branca. Nenhuma fase de "varredura" é necessária.
A estratégia marcar e não varrer requer cooperação entre o alocador e o coletor, mas é incrivelmente eficiente em termos de espaço, uma vez que requer apenas um bit por ponteiro alocado (o que a maioria dos algoritmos de alocação exige de qualquer maneira). No entanto, essa vantagem é um pouco atenuada, uma vez que na maioria das vezes grandes porções de memória são erroneamente marcadas em preto (usado), tornando difícil devolver recursos ao sistema (para uso por outros alocadores, threads ou processos) em tempos de baixo uso de memória.
A estratégia de marcar e não varrer pode, portanto, ser vista como um meio-termo entre os lados positivos e negativos da marca e varredura e as estratégias de parada e cópia .
GC geracional (GC efêmero)
Foi empiricamente observado que em muitos programas, os objetos criados mais recentemente também são aqueles com maior probabilidade de se tornarem inacessíveis rapidamente (conhecido como mortalidade infantil ou hipótese geracional ). Um GC geracional (também conhecido como GC efêmero) divide os objetos em gerações e, na maioria dos ciclos, colocará apenas os objetos de um subconjunto de gerações no conjunto inicial branco (condenado). Além disso, o sistema de tempo de execução mantém o conhecimento de quando as referências cruzam gerações, observando a criação e a substituição das referências. Quando o coletor de lixo é executado, ele pode ser capaz de usar esse conhecimento para provar que alguns objetos no conjunto branco inicial são inacessíveis sem ter que percorrer toda a árvore de referência. Se a hipótese geracional for mantida, isso resultará em ciclos de coleta muito mais rápidos enquanto ainda recupera a maioria dos objetos inacessíveis.
Para implementar esse conceito, muitos coletores de lixo de geração usam regiões de memória separadas para diferentes idades de objetos. Quando uma região fica cheia, os objetos nela contidos são rastreados, usando as referências da (s) geração (ões) mais antiga (s) como raízes. Isso geralmente resulta na maioria dos objetos na geração sendo coletados (pela hipótese), deixando-o para ser usado para alocar novos objetos. Quando uma coleção não coleta muitos objetos (a hipótese não se sustenta, por exemplo, porque o programa calculou uma grande coleção de novos objetos que deseja reter), alguns ou todos os objetos sobreviventes que são referenciados de uma memória mais antiga as regiões são promovidas para a próxima região mais alta e toda a região pode ser substituída por objetos novos. Essa técnica permite a coleta de lixo incremental muito rápida, uma vez que a coleta de lixo de apenas uma região por vez é tudo o que normalmente é necessário.
O clássico necrófago de geração de Ungar tem duas gerações. Ele divide a geração mais jovem, chamada de "novo espaço", em um grande "éden" no qual novos objetos são criados e dois "espaços de sobreviventes" menores, espaço de sobrevivente passado e espaço de sobrevivente futuro. Os objetos da geração anterior que podem fazer referência a objetos em um novo espaço são mantidos em um "conjunto lembrado". Em cada limpeza, os objetos no novo espaço são rastreados a partir das raízes no conjunto lembrado e copiados para o futuro espaço sobrevivente. Se o espaço do futuro sobrevivente se encher, os objetos que não cabem são promovidos para o espaço antigo, um processo denominado "posse". No final da varredura, alguns objetos residem no espaço do sobrevivente futuro, e o éden e o espaço do sobrevivente passado estão vazios. Então, o espaço do futuro sobrevivente e o espaço do passado sobrevivente são trocados e o programa continua, alocando objetos no Éden. No sistema original de Ungar, o eden é 5 vezes maior do que o espaço de cada sobrevivente.
A coleta de lixo geracional é uma abordagem heurística e alguns objetos inacessíveis podem não ser recuperados em cada ciclo. Portanto, ocasionalmente pode ser necessário executar uma marcação completa e varrer ou copiar a coleta de lixo para recuperar todo o espaço disponível. Na verdade, os sistemas de tempo de execução para linguagens de programação modernas (como Java e .NET Framework ) geralmente usam alguns híbridos das várias estratégias que foram descritas até agora; por exemplo, a maioria dos ciclos de coleção pode olhar apenas para algumas gerações, enquanto ocasionalmente uma marcação e varredura é executada e, ainda mais raramente, uma cópia completa é executada para combater a fragmentação. Os termos "ciclo menor" e "ciclo principal" às vezes são usados para descrever esses diferentes níveis de agressão do coletor.
Stop-the-world vs. incremental vs. simultâneo
Os coletores de lixo simples interrompem completamente a execução do programa para executar um ciclo de coleta, garantindo assim que novos objetos não sejam alocados e que os objetos não fiquem subitamente inacessíveis enquanto o coletor está em execução.
Isso tem a desvantagem de que o programa não pode realizar nenhum trabalho útil durante a execução de um ciclo de coleta (às vezes chamada de "pausa embaraçosa"). A coleta de lixo Stop-the-world é, portanto, adequada principalmente para programas não interativos. Sua vantagem é que é mais simples de implementar e mais rápido do que a coleta de lixo incremental.
Os coletores de lixo incrementais e simultâneos são projetados para reduzir essa interrupção intercalando seu trabalho com a atividade do programa principal. Os coletores de lixo incrementais realizam o ciclo de coleta de lixo em fases discretas, com a execução do programa permitida entre cada fase (e às vezes durante algumas fases). Os coletores de lixo simultâneos não param a execução do programa, exceto, talvez, brevemente, quando a pilha de execução do programa é verificada. No entanto, a soma das fases incrementais leva mais tempo para ser concluída do que uma passagem de coleta de lixo em lote, portanto, esses coletores de lixo podem render uma taxa de transferência total menor.
É necessário um projeto cuidadoso com essas técnicas para garantir que o programa principal não interfira com o coletor de lixo e vice-versa; por exemplo, quando o programa precisa alocar um novo objeto, o sistema de tempo de execução pode precisar suspendê-lo até que o ciclo de coleta seja concluído ou, de alguma forma, notificar o coletor de lixo de que existe um novo objeto acessível.
Indicadores precisos vs. conservadores e internos
Alguns coletores podem identificar corretamente todos os ponteiros (referências) em um objeto; estes são chamados de coletores precisos (também exatos ou precisos ), sendo o oposto um colecionador conservador ou parcialmente conservador . Os coletores conservadores presumem que qualquer padrão de bits na memória pode ser um ponteiro se, interpretado como um ponteiro, apontar para um objeto alocado. Coletores conservadores podem produzir falsos positivos, onde a memória não utilizada não é liberada devido à identificação incorreta do ponteiro. Isso nem sempre é um problema na prática, a menos que o programa lide com muitos dados que podem ser facilmente identificados incorretamente como um ponteiro. Falsos positivos geralmente são menos problemáticos em sistemas de 64 bits do que em sistemas de 32 bits , porque o intervalo de endereços de memória válidos tende a ser uma pequena fração do intervalo de valores de 64 bits. Portanto, é improvável que um padrão arbitrário de 64 bits imite um ponteiro válido. Um falso negativo também pode acontecer se os ponteiros estiverem "ocultos", por exemplo, usando uma lista vinculada XOR . Se um coletor preciso é prático geralmente depende das propriedades de segurança de tipo da linguagem de programação em questão. Um exemplo para o qual um coletor de lixo conservador seria necessário é a linguagem C , que permite que ponteiros digitados (não nulos) sejam convertidos em ponteiros não digitados (nulos) e vice-versa.
Um problema relacionado diz respeito a ponteiros internos ou ponteiros para campos dentro de um objeto. Se a semântica de uma linguagem permitir ponteiros internos, então pode haver muitos endereços diferentes que podem se referir a partes do mesmo objeto, o que dificulta determinar se um objeto é lixo ou não. Um exemplo disso é a linguagem C ++ , na qual a herança múltipla pode fazer com que os ponteiros para objetos base tenham endereços diferentes. Em um programa altamente otimizado, o ponteiro correspondente para o próprio objeto pode ter sido sobrescrito em seu registro, portanto, esses ponteiros internos precisam ser verificados.
atuação
O desempenho dos coletores de lixo de rastreamento - latência e taxa de transferência - depende significativamente da implementação, da carga de trabalho e do ambiente. Implementações ingênuas ou uso em ambientes com muita memória restrita, notadamente sistemas embarcados, podem resultar em desempenho muito ruim em comparação com outros métodos, enquanto implementações sofisticadas e uso em ambientes com ampla memória podem resultar em excelente desempenho.
Em termos de taxa de transferência, o rastreamento por sua natureza requer alguma sobrecarga implícita de tempo de execução , embora em alguns casos o custo amortizado possa ser extremamente baixo, em alguns casos até menor do que uma instrução por alocação ou coleção, superando a alocação de pilha. O gerenciamento de memória manual requer sobrecarga devido à liberação explícita de memória, e a contagem de referência tem sobrecarga de aumentar e diminuir as contagens de referência e verificar se a contagem estourou ou caiu para zero.
Em termos de latência, os coletores de lixo simples param o mundo pausam a execução do programa para a coleta de lixo, o que pode acontecer em momentos arbitrários e demorar arbitrariamente, tornando-os inutilizáveis para computação em tempo real , notadamente sistemas incorporados, e um ajuste inadequado para a coleta de lixo uso, ou qualquer outra situação onde a baixa latência é uma prioridade. No entanto, coletores de lixo incrementais podem fornecer garantias em tempo real e em sistemas com tempo ocioso frequente e memória livre suficiente, como computadores pessoais, a coleta de lixo pode ser agendada para tempos ociosos e tem impacto mínimo no desempenho interativo. O gerenciamento manual de memória (como em C ++) e a contagem de referência têm um problema semelhante de pausas arbitrariamente longas no caso de desalocação de uma grande estrutura de dados e todos os seus filhos, embora eles ocorram apenas em horários fixos, não dependendo da coleta de lixo.
- Alocação manual de heap
- procure o melhor bloco / primeiro ajuste de tamanho suficiente
- manutenção de lista grátis
- Coleta de lixo
- localizar objetos alcançáveis
- copiar objetos alcançáveis para mover os coletores
- barreiras de leitura / gravação para coletores incrementais
- procure o melhor / primeiro bloco de ajuste e manutenção de lista livre para coletores imóveis
É difícil comparar os dois casos diretamente, pois seu comportamento depende da situação. Por exemplo, no melhor caso para um sistema de coleta de lixo, a alocação apenas incrementa um ponteiro, mas no melhor caso para a alocação manual de heap, o alocador mantém freelists de tamanhos específicos e a alocação requer apenas o seguimento de um ponteiro. No entanto, essa segregação de tamanho geralmente causa um alto grau de fragmentação externa, o que pode ter um impacto adverso no comportamento do cache. A alocação de memória em uma linguagem com coleta de lixo pode ser implementada usando a alocação de heap nos bastidores (em vez de simplesmente incrementar um ponteiro), portanto, as vantagens de desempenho listadas acima não se aplicam necessariamente neste caso. Em algumas situações, principalmente em sistemas incorporados , é possível evitar a sobrecarga de coleta de lixo e gerenciamento de heap, pré-alocando pools de memória e usando um esquema leve e personalizado para alocação / desalocação.
A sobrecarga das barreiras de gravação é mais provável de ser notada em um programa de estilo imperativo que freqüentemente escreve ponteiros em estruturas de dados existentes do que em um programa de estilo funcional que constrói dados apenas uma vez e nunca os altera.
Alguns avanços na coleta de lixo podem ser entendidos como reações a problemas de desempenho. Os primeiros colecionadores eram colecionadores de parar o mundo, mas o desempenho dessa abordagem era perturbador em aplicativos interativos. A coleta incremental evitou essa interrupção, mas ao custo de diminuição da eficiência devido à necessidade de barreiras. As técnicas de coleta geracional são usadas com coletores stop-the-world e incrementais para aumentar o desempenho; a desvantagem é que algum lixo não é detectado como tal por mais tempo do que o normal.
Determinismo
- O rastreamento da coleta de lixo não é determinístico no tempo de finalização do objeto. Um objeto que se torna elegível para a coleta de lixo geralmente será limpo eventualmente, mas não há garantia de quando (ou mesmo se) isso acontecerá. Esse é um problema de correção do programa quando os objetos estão vinculados a recursos que não são da memória, cuja liberação é um comportamento de programa visível externamente, como fechar uma conexão de rede, liberar um dispositivo ou fechar um arquivo. Uma técnica de coleta de lixo que fornece determinismo a esse respeito é a contagem de referência .
- A coleta de lixo pode ter um impacto não determinístico no tempo de execução, potencialmente introduzindo pausas na execução de um programa que não estão correlacionadas com o algoritmo que está sendo processado. No rastreamento da coleta de lixo, a solicitação para alocar um novo objeto pode, às vezes, retornar rapidamente e, em outras ocasiões, acionar um ciclo de coleta de lixo demorado. Na contagem de referência, enquanto a alocação de objetos é geralmente rápida, decrementar uma referência não é determinístico, uma vez que uma referência pode chegar a zero, disparando a recursão para decrementar as contagens de referência de outros objetos que aquele objeto contém.
Coleta de lixo em tempo real
Embora a coleta de lixo seja geralmente não determinística, é possível usá-la em sistemas de tempo real hard . Um coletor de lixo em tempo real deve garantir que, mesmo no pior caso, ele dedicará um certo número de recursos computacionais a threads mutadores. As restrições impostas a um coletor de lixo em tempo real geralmente são baseadas no trabalho ou no tempo. Uma restrição baseada no tempo seria semelhante a: dentro de cada janela de tempo de duração T , os threads mutadores devem ser executados pelo menos durante o tempo Tm . Para análise baseada em trabalho, MMU (utilização mínima de mutador) é geralmente usado como uma restrição em tempo real para o algoritmo de coleta de lixo.
Uma das primeiras implementações de coleta de lixo em tempo real difícil para a JVM foi baseada no algoritmo Metronome , cuja implementação comercial está disponível como parte do IBM WebSphere Real Time . Outro algoritmo de coleta de lixo em tempo real duro é Staccato, disponível na IBM 's J9 JVM , que também fornece escalabilidade para grandes arquiteturas de multiprocessadores, ao trazer várias vantagens sobre Metronome e outros algoritmos que, pelo contrário, requerem hardware especializado.