Contagem de referência - Reference counting

Na ciência da computação , a contagem de referência é uma técnica de programação para armazenar o número de referências , ponteiros ou identificadores para um recurso, como um objeto, um bloco de memória, espaço em disco e outros.

Em algoritmos de coleta de lixo , as contagens de referência podem ser usadas para desalocar objetos que não são mais necessários.

Vantagens e desvantagens

A principal vantagem da contagem de referência sobre o rastreamento da coleta de lixo é que os objetos são recuperados assim que não podem mais ser referenciados, e de forma incremental, sem longas pausas para ciclos de coleta e com vida útil claramente definida de cada objeto. Em aplicativos ou sistemas em tempo real com memória limitada, isso é importante para manter a capacidade de resposta. A contagem de referência também está entre as formas mais simples de gerenciamento de memória para implementar. Também permite o gerenciamento eficaz de recursos que não são da memória, como objetos do sistema operacional, que geralmente são muito mais escassos do que a memória (sistemas de coleta de lixo de rastreamento usam finalizadores para isso, mas a recuperação atrasada pode causar problemas). Contagens de referência ponderadas são uma boa solução para a coleta de lixo em um sistema distribuído.

Exemplo de lista circular de uma dissertação de mestrado de 1985. Retângulos denotam pares Lisp , com contagens de referência. Mesmo se o ponteiro superior esquerdo de entrada for removido, todas as contagens permanecem> 0.

Ciclos de coleta de lixo de rastreamento são disparados com muita freqüência se o conjunto de objetos ativos preencher a maior parte da memória disponível; requer espaço extra para ser eficiente. O desempenho da contagem de referência não se deteriora à medida que a quantidade total de espaço livre diminui.

As contagens de referência também são informações úteis para usar como entrada para outras otimizações de tempo de execução. Por exemplo, sistemas que dependem fortemente de objetos imutáveis , como muitas linguagens de programação funcionais, podem sofrer uma penalidade de eficiência devido a cópias frequentes. No entanto, se o compilador (ou sistema de execução ) sabe que um determinado objeto tem apenas uma referência (como a maioria faz em muitos sistemas), e que a referência é perdida ao mesmo tempo que um novo objeto semelhante é criado (como na string append str ← str + "a"), ele pode substituir a operação por uma mutação no objeto original.

A contagem de referência na forma ingênua tem duas desvantagens principais sobre a coleta de lixo de rastreamento, ambas as quais requerem mecanismos adicionais para melhorar:

  • As atualizações frequentes que envolve são uma fonte de ineficiência. Embora o rastreamento de coletores de lixo possa afetar seriamente a eficiência por meio da troca de contexto e falhas de linha de cache, eles coletam com pouca frequência, enquanto o acesso a objetos é feito continuamente. Além disso, menos importante, a contagem de referência requer que cada objeto gerenciado pela memória reserve espaço para uma contagem de referência. No rastreamento de coletores de lixo, essas informações são armazenadas implicitamente nas referências que se referem a esse objeto, economizando espaço, embora o rastreamento de coletores de lixo, principalmente os incrementais, possa exigir espaço adicional para outros fins.
  • O algoritmo ingênuo descrito acima não consegue lidar ciclos de referência ,um objeto que se refere direta ou indiretamente a si mesmo. Um mecanismo que se baseia puramente em contagens de referência nunca considerará cadeias cíclicas de objetos para exclusão, uma vez que sua contagem de referência é garantida para permanecer diferente de zero (cf. figura). Existem métodos para lidar com esse problema, mas também podem aumentar a sobrecarga e a complexidade da contagem de referência - por outro lado, esses métodos precisam ser aplicados apenas a dados que podem formar ciclos, geralmente um pequeno subconjunto de todos os dados. Um desses métodos é o uso dereferências fracas, enquanto outro envolve o uso de umalgoritmo devarredura de marcaçãoque raramente é chamado para limpar.

Além disso, se a memória for alocada a partir de uma lista livre, a contagem de referência sofre de má localização. A contagem de referência sozinha não pode mover objetos para melhorar o desempenho do cache, portanto, os coletores de alto desempenho também implementam um coletor de lixo de rastreamento. A maioria das implementações (como as em PHP e Objective-C) sofrem de baixo desempenho do cache, pois não implementam a cópia de objetos.

Interpretação de gráfico

Ao lidar com esquemas de coleta de lixo, muitas vezes é útil pensar no gráfico de referência , que é um gráfico direcionado onde os vértices são objetos e há uma borda de um objeto A para um objeto B se A contém uma referência a B. Nós também têm um vértice ou vértices especiais que representam as variáveis ​​locais e referências mantidas pelo sistema de tempo de execução, e nenhuma aresta jamais vai para esses nós, embora as arestas possam ir deles para outros nós.

Nesse contexto, a contagem de referência simples de um objeto é o grau de seu vértice. Excluir um vértice é como coletar um objeto. Isso só pode ser feito quando o vértice não tem arestas de entrada, por isso não afeta o grau de saída de quaisquer outros vértices, mas pode afetar o grau de entrada de outros vértices, fazendo com que seus objetos correspondentes sejam coletados também se seus em grau também se torna 0 como resultado.

O componente conectado contendo o vértice especial contém os objetos que não podem ser coletados, enquanto outros componentes conectados do gráfico contêm apenas lixo. Se um algoritmo de coleta de lixo de contagem de referência for implementado, cada um desses componentes de lixo deve conter pelo menos um ciclo; caso contrário, eles teriam sido coletados assim que sua contagem de referência (ou seja, o número de arestas de entrada) caísse para zero.

Lidando com a ineficiência das atualizações

Incrementar e diminuir as contagens de referência sempre que uma referência é criada ou destruída pode prejudicar significativamente o desempenho. As operações não apenas demoram, mas também prejudicam o desempenho do cache e podem levar a bolhas de pipeline . Mesmo as operações somente leitura, como calcular o comprimento de uma lista, requerem um grande número de leituras e gravações para atualizações de referência com contagem de referência ingênua.

Uma técnica simples é o compilador combinar várias atualizações de referência próximas em uma. Isso é especialmente eficaz para referências que são criadas e rapidamente destruídas. Deve-se ter cuidado, entretanto, para colocar a atualização combinada na posição correta, de modo que uma liberação prematura possa ser evitada.

O método Deutsch-Bobrow de contagem de referência capitaliza o fato de que a maioria das atualizações de contagem de referência são de fato geradas por referências armazenadas em variáveis ​​locais. Ele ignora essas referências, apenas contando referências em estruturas de dados, mas antes que um objeto com contagem de referência zero possa ser excluído, o sistema deve verificar com uma varredura da pilha e registra que nenhuma outra referência a ele ainda existe.

Outra técnica desenvolvida por Henry Baker envolve incrementos adiados , nos quais as referências que são armazenadas em variáveis ​​locais não incrementam imediatamente a contagem de referência correspondente, mas, em vez disso, adiam isso até que seja necessário. Se essa referência for destruída rapidamente, não há necessidade de atualizar o contador. Isso elimina um grande número de atualizações associadas a referências de curta duração (como o exemplo de contagem de comprimento de lista acima). No entanto, se essa referência for copiada para uma estrutura de dados, o incremento adiado deve ser executado naquele momento. Também é crítico realizar o incremento adiado antes que a contagem do objeto caia para zero, resultando em uma liberação prematura.

Uma redução dramática na sobrecarga nas atualizações do contador foi obtida por Levanoni e Petrank . Eles introduzem o método de coalescência de atualização que aglutina muitas das atualizações redundantes de contagem de referência. Considere um ponteiro que em um determinado intervalo de execução é atualizado várias vezes. Ele primeiro aponta para um objeto O1, depois para um objeto O2e assim por diante, até que no final do intervalo aponte para algum objeto On. Um algoritmo de contagem de referência normalmente executar rc(O1)--, rc(O2)++, rc(O2)--, rc(O3)++, rc(O3)--, ..., rc(On)++. Mas a maioria dessas atualizações é redundante. Para que a contagem de referências seja devidamente avaliada ao final do intervalo basta realizar rc(O1)--e rc(On)++. O resto das atualizações são redundantes.

Levanoni e Petrank mostraram em 2001 como usar essa coalescência de atualização em um coletor de contagem de referência. Ao usar o update coalescing com um tratamento apropriado de novos objetos, mais de 99% das atualizações do contador são eliminadas para benchmarks Java típicos. Além disso, a necessidade de operações atômicas durante atualizações de ponteiro em processadores paralelos é eliminada. Finalmente, eles apresentaram um algoritmo aprimorado que pode ser executado simultaneamente com aplicativos multithread, empregando apenas sincronização fina.

O método ulterior de contagem de referência de Blackburn e McKinley em 2003 combina a contagem de referência diferida com um berçário de cópia, observando que a maioria das mutações de ponteiro ocorrem em objetos jovens. Este algoritmo alcança uma taxa de transferência comparável aos coletores de cópia de geração mais rápidos com os tempos de pausa limitados de contagem de referência.

Lidando com ciclos de referência

Talvez a maneira mais óbvia de lidar com os ciclos de referência seja projetar o sistema para evitar criá-los. Um sistema pode proibir explicitamente os ciclos de referência; os sistemas de arquivos com links físicos geralmente fazem isso. O uso criterioso de referências "fracas" (não contadas) também pode ajudar a evitar a retenção de ciclos; a estrutura Cocoa , por exemplo, recomenda o uso de referências "fortes" para relacionamentos de pai para filho e referências "fracas" para relacionamentos de filho para pai.

Os sistemas também podem ser projetados para tolerar ou corrigir os ciclos que criam de alguma forma. Os desenvolvedores podem projetar o código para "destruir" explicitamente as referências em uma estrutura de dados quando não forem mais necessárias, embora isso tenha o custo de exigir que eles controlem manualmente o tempo de vida dessa estrutura de dados. Essa técnica pode ser automatizada criando um objeto "proprietário" que faz a demolição quando é destruído; por exemplo, o destruidor de um objeto Graph poderia excluir as bordas de seus GraphNodes, quebrando os ciclos de referência no gráfico. Os ciclos podem até ser ignorados em sistemas com vida curta e uma pequena quantidade de lixo cíclico, particularmente quando o sistema foi desenvolvido usando uma metodologia de evitar estruturas de dados cíclicas sempre que possível, normalmente em detrimento da eficiência.

Os cientistas da computação também descobriram maneiras de detectar e coletar ciclos de referência automaticamente, sem exigir mudanças no design da estrutura de dados. Uma solução simples é usar periodicamente um coletor de lixo de rastreamento para recuperar ciclos; uma vez que os ciclos normalmente constituem uma quantidade relativamente pequena de espaço recuperado, o coletor pode ser executado com muito menos frequência do que com um coletor de lixo de rastreamento comum.

Bacon descreve um algoritmo de coleta de ciclo para contagem de referência com semelhanças com coletores de rastreamento, incluindo os mesmos limites de tempo teóricos. Baseia-se na observação de que um ciclo só pode ser isolado quando uma contagem de referência é diminuída para um valor diferente de zero. Todos os objetos nos quais isso ocorre são colocados em uma lista de raízes e, então, periodicamente o programa pesquisa os objetos alcançáveis ​​a partir das raízes por ciclos. Ele sabe que encontrou um ciclo que pode ser coletado ao diminuir todas as contagens de referência em um ciclo de referências e traz todas elas para zero. Uma versão aprimorada desse algoritmo por Paz et al. é capaz de operar simultaneamente com outras operações e melhorar sua eficiência usando o método de coalescência de atualização de Levanoni e Petrank.

Formas variantes

Embora seja possível aumentar contagens de referência simples de várias maneiras, geralmente uma solução melhor pode ser encontrada executando a contagem de referência de uma maneira fundamentalmente diferente. Aqui, descrevemos algumas das variantes da contagem de referência e suas vantagens e desvantagens.

Contagem de referência ponderada

Na contagem de referência ponderada, a cada referência é atribuído um peso , e cada objeto rastreia não o número de referências que se referem a ele, mas o peso total das referências que se referem a ele. A referência inicial a um objeto recém-criado tem um peso grande, como 2 16 . Sempre que esta referência é copiada, metade do peso vai para a nova referência e metade do peso fica com a referência antiga. Como o peso total não muda, a contagem de referência do objeto não precisa ser atualizada.

Destruir uma referência diminui o peso total pelo peso dessa referência. Quando o peso total torna-se zero, todas as referências foram destruídas. Se for feita uma tentativa de copiar uma referência com peso 1, a referência deve "obter mais peso" adicionando ao peso total e, em seguida, adicionando esse novo peso à referência e, em seguida, dividindo-o. Uma alternativa nesta situação é criar um objeto de referência de indireção , a referência inicial para o qual é criada com um grande peso que pode então ser dividido.

A propriedade de não precisar acessar uma contagem de referência quando uma referência é copiada é particularmente útil quando a contagem de referência do objeto é cara para acessar, por exemplo, porque está em outro processo, no disco ou mesmo através de uma rede. Também pode ajudar a aumentar a simultaneidade, evitando que muitos encadeamentos bloqueiem uma contagem de referência para aumentá-la. Portanto, a contagem de referência ponderada é mais útil em aplicativos paralelos, multiprocessos, de banco de dados ou distribuídos.

O principal problema com a contagem de referência ponderada simples é que a destruição de uma referência ainda requer o acesso à contagem de referência e, se muitas referências forem destruídas, isso pode causar os mesmos gargalos que procuramos evitar. Algumas adaptações da contagem de referência ponderada procuram evitar isso, transferindo o peso de uma referência que está morrendo para uma referência ativa.

A contagem de referência ponderada foi desenvolvida de forma independente por Bevan e Watson & Watson em 1987.

Contagem de referência indireta

Na contagem indireta de referência, é necessário manter o controle da fonte da referência. Isso significa que duas referências são mantidas para o objeto: uma direta que é usada para invocações; e um indireto que faz parte de uma árvore de difusão, como no algoritmo de Dijkstra-Scholten , que permite que um coletor de lixo identifique objetos mortos. Essa abordagem evita que um objeto seja descartado prematuramente.

Exemplos de uso

Coleta de lixo

Como um algoritmo de coleção, a contagem de referência rastreia, para cada objeto, uma contagem do número de referências a ele mantidas por outros objetos. Se a contagem de referência de um objeto chegar a zero, o objeto se tornou inacessível e pode ser destruído.

Quando um objeto é destruído, quaisquer objetos referenciados por aquele objeto também têm suas contagens de referência diminuídas. Por isso, a remoção de uma única referência pode potencialmente levar à liberação de um grande número de objetos. Uma modificação comum permite que a contagem de referência seja incremental: em vez de destruir um objeto assim que sua contagem de referência se tornar zero, ela é adicionada a uma lista de objetos não referenciados e periodicamente (ou conforme necessário) um ou mais itens desta lista são destruído.

Contagens de referência simples requerem atualizações frequentes. Sempre que uma referência é destruída ou substituída, a contagem de referência do objeto que ela faz referência é diminuída e, sempre que uma referência é criada ou copiada, a contagem de referência do objeto ao qual faz referência é incrementada.

A contagem de referência também é usada em sistemas de arquivos e sistemas distribuídos, onde a coleta de lixo de rastreamento não incremental completa consome muito tempo devido ao tamanho do gráfico do objeto e à baixa velocidade de acesso.

Component Object Model

O Component Object Model (COM) da Microsoft e o WinRT fazem uso generalizado da contagem de referência. Na verdade, dois dos três métodos que todos os objetos COM devem fornecer (na interface IUnknown ) aumentam ou diminuem a contagem de referência. Muito do Windows Shell e muitos aplicativos do Windows (incluindo MS Internet Explorer , MS Office e inúmeros produtos de terceiros) são construídos em COM, demonstrando a viabilidade da contagem de referência em sistemas de grande escala.

Uma motivação primária para a contagem de referência em COM é permitir a interoperabilidade entre diferentes linguagens de programação e sistemas de tempo de execução. Um cliente só precisa saber como invocar métodos de objeto para gerenciar o ciclo de vida do objeto; assim, o cliente é completamente abstraído de qualquer alocador de memória usado pela implementação do objeto COM. Como um exemplo típico, um programa Visual Basic usando um objeto COM é independente se esse objeto foi alocado (e deve ser desalocado posteriormente) por um alocador C ++ ou outro componente Visual Basic.

C ++

C ++ não realiza contagem de referência por padrão, cumprindo sua filosofia de não adicionar funcionalidade que possa incorrer em sobrecargas onde o usuário não a solicitou explicitamente. Objetos que são compartilhados, mas não possuídos, podem ser acessados ​​por meio de uma referência, ponteiro bruto ou iterador (uma generalização conceitual de ponteiros).

No entanto, da mesma forma, C ++ fornece maneiras nativas para os usuários optarem por essa funcionalidade: C ++ 11 fornece ponteiros inteligentes contados por referência , por meio da std::shared_ptrclasse, permitindo o gerenciamento automático de memória compartilhada de objetos alocados dinamicamente. Os programadores podem usar isso em conjunto com ponteiros fracos (via std::weak_ptr) para quebrar dependências cíclicas. Objetos que são alocados dinamicamente, mas não pretendem ser compartilhados, podem ter seu tempo de vida gerenciado automaticamente usando um std::unique_ptr.

Além disso, a semântica de movimento do C ++ 11 reduz ainda mais a extensão em que as contagens de referência precisam ser modificadas, removendo a cópia profunda normalmente usada quando uma função retorna um objeto, pois permite uma cópia simples do ponteiro do referido objeto.

Cacau (Objective-C)

As estruturas Cocoa e Cocoa Touch da Apple (e estruturas relacionadas, como Core Foundation ) usam contagem de referência manual, bem como COM . Tradicionalmente, isso era realizado pelo programador enviando mensagens retaine manualmente releasepara objetos, mas a contagem automática de referência , um recurso do compilador Clang que insere automaticamente essas mensagens conforme necessário, foi adicionado no iOS 5 e no Mac OS X 10.7 . O Mac OS X 10.5 introduziu um coletor de lixo de rastreamento como uma alternativa para a contagem de referência, mas foi descontinuado no OS X 10.8 e removido da biblioteca de tempo de execução Objective-C no macOS Sierra . iOS nunca suportou um coletor de lixo de rastreamento.

Delphi

Delphi geralmente não é uma linguagem com coleta de lixo, em que os tipos definidos pelo usuário ainda devem ser alocados e desalocados manualmente, no entanto, ele fornece coleta automática usando contagem de referência para alguns tipos embutidos, como strings, matrizes dinâmicas e interfaces, para facilidade de uso e para simplificar a funcionalidade do banco de dados genérico. Cabe ao programador decidir se usará os tipos integrados; Os programadores Delphi têm acesso completo ao gerenciamento de memória de baixo nível, como em C / C ++. Portanto, todos os custos potenciais da contagem de referência da Delphi podem, se desejado, ser facilmente contornados.

Algumas das razões pelas quais a contagem de referência pode ter sido preferida a outras formas de coleta de lixo em Delphi incluem:

  • Os benefícios gerais da contagem de referência, como a coleta imediata.
  • Os ciclos não podem ocorrer ou não ocorrem na prática porque nenhum dos tipos internos com coleta de lixo é recursivo. (usando interfaces pode-se criar tal cenário, mas isso não é um uso comum)
  • A sobrecarga no tamanho do código necessária para a contagem de referência é muito pequena (no x86 nativo, normalmente uma única instrução LOCK INC, LOCK DEC ou LOCK XADD, que garante atomicidade em qualquer ambiente), e nenhum thread de controle separado é necessário para a coleta como faria ser necessário para um coletor de lixo de rastreamento.
  • Muitas instâncias do tipo de coleta de lixo mais comumente usado, a string, têm uma vida útil curta, uma vez que são tipicamente valores intermediários na manipulação de string. Muito do uso de strings locais poderia ser otimizado, mas o compilador atualmente não faz isso.
  • A contagem de referência de uma string é verificada antes de transformar uma string. Isso permite que as sequências de contagem de referência 1 sejam alteradas diretamente, enquanto as sequências de contagem de referência superior são copiadas antes da mutação. Isso permite que o comportamento geral de strings pascal de estilo antigo seja preservado enquanto elimina o custo de copiar a string em cada atribuição.
  • Como a coleta de lixo é feita apenas em tipos integrados, a contagem de referência pode ser integrada de forma eficiente às rotinas da biblioteca usadas para manipular cada tipo de dados, mantendo baixa a sobrecarga necessária para atualização das contagens de referência. Além disso, grande parte da biblioteca de tempo de execução está em um assembler otimizado à mão.
  • O tipo de string pode ser convertido em um ponteiro para char, e operações de alto desempenho podem ser realizadas dessa maneira. Isso é importante, pois Delphi e FPC implementam seu RTL em Pascal. Vários outros tipos automatizados têm essas opções de fundição.

GObject

A estrutura de programação orientada a objetos GObject implementa a contagem de referência em seus tipos de base, incluindo referências fracas . O incremento e o decremento de referência usam operações atômicas para segurança de thread. Uma parte significativa do trabalho de escrever ligações para GObject a partir de linguagens de alto nível reside na adaptação da contagem de referência de GObject para funcionar com o próprio sistema de gerenciamento de memória da linguagem.

A linguagem de programação Vala usa a contagem de referência GObject como seu sistema de coleta de lixo principal, junto com o manuseio de string com muitas cópias.

Perl

Perl também usa contagem de referência, sem qualquer tratamento especial de referências circulares, embora (como em Cocoa e C ++ acima), Perl suporte referências fracas, o que permite aos programadores evitar a criação de um ciclo.

PHP

O PHP usa um mecanismo de contagem de referência para seu gerenciamento de variável interna. Desde o PHP 5.3, ele implementa o algoritmo do artigo de Bacon mencionado acima. PHP permite que você ligue e desligue a coleção de ciclo com funções de nível de usuário. Também permite que você force manualmente a execução do mecanismo de purga.

Pitão

Python também usa contagem de referência e oferece detecção de ciclo (e pode recuperá-los).

Ferrugem

Rust usa tempos de vida declarados no código para liberar memória. Rust tem uma estrutura Rce Arc.

O tipo Rc<T>fornece propriedade compartilhada de um valor do tipo T, alocado no heap.

use std::rc::Rc;

struct Cat {
    color: String,
}

fn main() {
    let cat = Cat { color: "black".to_string() };
    let cat = Rc::new(cat);
}

Esquilo

O Squirrel usa contagem de referência com detecção de ciclo. Essa linguagem minúscula é relativamente desconhecida fora da indústria de videogames; no entanto, é um exemplo concreto de como a contagem de referência pode ser prática e eficiente (especialmente em ambientes de tempo real).

Tcl

Tcl 8 usa contagem de referência para gerenciamento de memória de valores (Tcl Obj structs ). Uma vez que os valores de Tcl são imutáveis, os ciclos de referência são impossíveis de se formar e nenhum esquema de detecção de ciclo é necessário. As operações que substituiriam um valor por uma cópia modificada geralmente são otimizadas para modificar o original quando sua contagem de referência indica que ele não é compartilhado. As referências são contadas em um nível de estrutura de dados, portanto, os problemas com atualizações muito frequentes discutidos acima não surgem.

Xojo

Xojo também usa contagem de referência, sem qualquer tratamento especial de referências circulares, embora (como em Cocoa e C ++ acima), Xojo suporte referências fracas, o que permite aos programadores evitar a criação de um ciclo.

Sistemas de arquivos

Muitos sistemas de arquivos mantêm contagens de referência para qualquer bloco ou arquivo em particular, por exemplo, a contagem de links inode em sistemas de arquivos no estilo Unix , que geralmente são conhecidos como links físicos . Quando a contagem chega a zero, o arquivo pode ser desalocado com segurança. Embora ainda possam ser feitas referências de diretórios , alguns Unixes só permitem referências de processos ativos e pode haver arquivos fora da hierarquia do sistema de arquivos.

Referências

links externos