Coleta de lixo

Lixo = objeto que nenhum código pode mais acessar

Um objeto é "lixo" quando não existe mais nenhum caminho a partir de uma variável ativa que chegue até ele. O programa não pode usá-lo, mas ele ainda ocupa memória. O trabalho do GC é identificar esses objetos e liberar o espaço.

O modelo mental é um grafo: os nós são objetos no heap, as arestas são referências entre eles. As raízes são os pontos de entrada — variáveis globais e frames de função ativos na stack. Um objeto é alcançável se existe um caminho das raízes até ele. Tudo que for inalcançável é lixo.

Mark-and-Sweep ao vivo

Clique em "Marcar" para ver o GC fazer DFS a partir das raízes, colorindo objetos alcançáveis (verde) e inalcançáveis (vermelho). Depois "Varrer" para coletar os inalcançáveis.

Mark-and-Sweep

// Mark-and-Sweep: o algoritmo GC clássico

// 1. PAUSA o programa ("stop-the-world")
// 2. MARCA: DFS/BFS a partir das raízes
//    Raízes = variáveis globais + variáveis nos stack frames ativos

def mark(obj):
    if obj.marcado: return
    obj.marcado = True
    for ref in obj.referencias:
        mark(ref)    // percorre todo o grafo de objetos

for raiz in todas_as_raizes:
    mark(raiz)

// 3. VARRE: percorre o heap e coleta os NÃO marcados
for obj in todo_o_heap:
    if not obj.marcado:
        liberar(obj)   // inalcançável → lixo

// 4. RETOMA o programa

Contagem de referências

// Contagem de referências: alternativa ao mark-and-sweep
// Cada objeto mantém um contador: quantas referências apontam para ele?

a = Obj()    // rc(a) = 1
b = a        // rc(a) = 2
b = None     // rc(a) = 1
a = None     // rc(a) = 0 → liberado IMEDIATAMENTE

// Vantagem: sem "stop-the-world", liberação determinística
// Desvantagem fatal: ciclos nunca chegam a rc = 0

a = Obj(); b = Obj()
a.outro = b; b.outro = a     // ciclo!
a = None; b = None
// rc(a_obj) = 1 (b_obj aponta), rc(b_obj) = 1 (a_obj aponta)
// Nenhum chega a 0 → leak permanente

// Solução: GC cíclico adicional (CPython faz isso)
// Swift/Rust: weak references quebram ciclos manualmente

Implementando um GC simples

Mini projeto: em Python, simule um grafo de objetos com um dicionário de listas de adjacência. Implemente mark_and_sweep(roots, graph) que retorna o conjunto de nós coletados. Teste com casos que incluam ciclos e confirme que mark-and-sweep os coleta enquanto contagem de referências falha.

Projeto principal: em C, implemente um GC Cheney (cópia de objetos) simplificado: dois semiespaços de memória. Durante a coleta, todos os objetos alcançáveis são copiados para o outro semiespaço (compactando o heap no processo). O semiespaço antigo é descartado inteiro. Meça a velocidade de alocação vs. mark-and-sweep.

Desafio extra: estude o código-fonte do GC do CPython (Modules/gc.c) ou do Go (runtime/mgc.go). Documente em um texto curto: qual algoritmo é usado, como ciclos são detectados, e como a implementação gerencia as pausas. Qual é a principal troca (tradeoff) de cada abordagem?

Teste sua intuição

Onde você encontra isso