Gerenciamento dinâmico de memória baseado em regiões com contagem de referências cíclicas

Abstract

Desde o algoritmo de Mark-Scan desenvolvido para a linguagem LISP por John Mc- Marthy em 1960, diversas técnicas foram desenvolvidas para gerenciar dinamicamente a memória de forma automática. Tais técnicas buscam coletar todos os dados, mantendo as pausas do programa de usuário mínimo. A contagem de referência é um método simples, no qual o gerenciamento de memória é realizado em pequenas etapas intercaladas com computação. Esse método evita grandes pausas de programa introduzidas por outras técnicas, como a marcação e varredura e a coleta por cópia. No entanto, a versão original da contagem de referência é incapaz de recuperar estruturas cíclicas. A solução geral para tal problema foi a introdução da varredura local. Combinando a contagem de referência com detecção cíclica e o gerenciamento de memória baseado em região, é possível diminuir o número de verificações e atualizações nas contagens das células em heap, reduzindo a duração das pausas e o espaço em memória. O gerenciamento de memória baseado em região faz uso de análise estática e instrumentação de código. O compilador tenta identificar a vida útil dos objetos, agrupando aqueles de longevidade semelhante em uma mesma região (geralmente contígua) de memória a ser recuperada quando não forem mais necessárias. Esta tese propõe um novo algoritmo de gerenciamento de memória baseado na contagem de referências cíclicas, combinado com o gerenciamento de memória baseado em região, fazendo uso de técnicas estáticas e de tempo de execução, trabalhando em conjunto para reduzir os gargalos um do outro. A mesclagem de contagem de referência e gerenciamento de memória baseado em região foi usada para coletar os dados alocados em grupos. As duas técnicas são usadas para reciclar as diferentes partes da memória, aumentando a velocidade de recuperação de objetos e reduzindo o uso da memória. Com o compilador implementado em Go, são inseridas barreiras de gravação após cada operação de armazenamento de um ponteiro na memória, atualizando as contagens de referência de todas as células envolvidas. O alocador de células segrega os objetos por seu tamanho, gerenciando listas que contêm os blocos livres de um tamanho específico com a contagem de referência armazenada em cada objeto. Essa modificação limita a varredura de marca local apenas a ciclos de pesquisa preguiçosos, evitando varrer todo o heap. Em comparação com o algoritmo de contagem de referências e detecção de ciclos, observam-se ganhos de desempenho em até 30% em tempo de execução e 50% a menos de uso de memória para programas que exigem grandes quantidades de memória e não fazem pausas no processo do usuário, esses valores podem apresentar maiores ganhos quando são combinadas as técnicas de contagem de referências e o gerenciamento de memória baseado em regiões.