Andreas Rumpf (Araq), autor da linguagem de programação Nim, anunciou um novo algoritmo de gerenciamento de memória YRC (pronunciado "Ürk"), que resolve um dos principais problemas dos mecanismos existentes em Nim: a impossibilidade de lidar corretamente com referências cíclicas que cruzam os limites das threads.
Antes da introdução do YRC nos algoritmos de gerenciamento de memória oferecidos em Nim, havia as seguintes limitações: ARC — não suportava nem multithreading nem o tratamento de ciclos; Atomic ARC — era seguro para threads, mas não lidava com referências cíclicas; ORC — processava referências cíclicas, mas fazia isso corretamente apenas dentro de uma única thread (ao usar referências compartilhadas entre threads, ocorriam vazamentos de memória).
O YRC proposto combina segurança para threads e tratamento de ciclos entre threads, utilizando uma abordagem combinada: para dados acíclicos, aplica-se contagem de referências atômica, e para cíclicos — uma barreira de gravação (write barrier), que é ativada apenas durante a atribuição de ponteiros. Na implementação proposta: o coletor é acionado apenas quando necessário (sem pausas stop-the-world); os objetos raiz RC são definidos explicitamente e unidos uma vez (não é necessário escanear as pilhas das threads); evita-se a exclusão multithread durante a iteração (não há fase global de varredura); os mutadores podem ler dados livremente; qualquer thread pode iniciar o coletor de lixo quando necessário (sem uma thread GC dedicada).
O YRC utiliza informações completas sobre os eventos incRef/decRef, que os coletores de lixo de rastreamento tradicionais (tracing GC) descartam e, em seguida, são obrigados a recuperar por meio da varredura das pilhas e da travessia do gráfico. A implementação consome apenas 550 linhas de código e possui verificação formal de segurança e ausência de interbloqueios por meio de uma especificação na linguagem TLA+ e prova na ferramenta Lean. O YRC é posicionado como "quase o último coletor de ciclos baseado em contagem de referências" (a letra Y vem antes de Z no alfabeto), além de ser o coletor de lixo mais simples e seguro para threads — segundo o autor, não requer um grande número de mecanismos complexos comuns aos coletores de lixo tradicionais de rastreamento.
O YRC fornece a mesma API que o ORC, executando destrutores durante a coleta de lixo. O coletor processa apenas aqueles subgrafos de objetos com os quais as threads trabalham, sem tocar nas estruturas de dados não relacionadas (caches, objetos de longa duração) — uma abordagem semelhante à de um coletor de lixo "ideal" geracional sem usar gerações. A principal desvantagem é o desempenho: o YRC mostra uma desaceleração de 1,5 a 2,0 vezes em comparação com o ORC no teste de desempenho orcbench. O autor considera isso um custo aceitável pela completa segurança de thread no processamento de referências cíclicas.
O YRC já está disponível na versão de desenvolvimento do Nim e é ativado com o sinalizador "—mm:yrc". No entanto, em comunicados posteriores, o autor reconheceu que a implementação inicial continha erros sérios e não lidava corretamente com ciclos. No momento da publicação, um conjunto de correções foi preparado para resolver os principais problemas. O autor continua ajustando as heurísticas de coleta e corrigindo os erros restantes, enquanto o algoritmo básico e sua verificação formal permanecem corretos.
Fonte: opennet.ru
