COLETA DE LIXO NA JVM
Adriano da Silva Castro
Introdução
• Gerenciamento de memória: técnicas de
manutenção de memória;
• Objetivos
– alocação de blocos de endereçamento para os processos
em execução;
– Liberação de blocos não mais utilizados;
• Crescente demanda de memória nas aplicações mais
recentes;
• Crescente necessidade de gerenciamento de
memória satisfatório;
Introdução
• Gerenciamento realizado pelo desenvolvedor?
– Gerenciar a alocação e liberação da memória;
– Nada confiável;
– Dificulta a redigibilidade;
• Solução:
Coleta de Lixo
Introdução
Objetivos do Trabalho
•
•
•
•
•
•
•
Estudo dos mecanismos de coleta atuais;
Mecanismos implementados na JVM;
Desempenho dos mecanismos;
Foco no algoritmo Mark-sweep presente na JVM;
Dificuldades em sua otimização;
Desenvolvimento de um simulador de heap;
Comparações JVM – Simulador;
Introdução
Coletores de Lixo
• Automatizam o processo de limpeza da memória;
• Parte integral de muitas das linguagens a partir dos
anos 60;
• Reduzem tempo de desenvolvimento de aplicações;
• Ações transparentes;
• Idealmente, não devem causar impactos no
desempenho da aplicação;
Introdução
Conceitos
• Objetos;
• Heap
– Trecho de memória alocado pelo processo;
– Alocação dinâmica de blocos de dados;
– Array contínuo de slots;
• Relação objeto-heap
– Objetos são mantidos nela!
– Acesso aleatório;
Objeto não mais usado pela
aplicação presente na heap: LIXO
Estratégias de Coleta
• Reference Counting (Contagem por Referência)
– Contador para cada objeto;
– Número de ponteiros que apontam para o objeto;
– Auxílio do compilador
• Nova instância  incremento do contador;
– Objeto lixo: contador = 0;
– Principal Limitação: detecção de referências cíclicas;
Estratégias de Coleta
• Tracing (Rastreamento)
–
–
–
–
–
Relações entre objetos: grafo;
Percurso do grafo a partir dos nós-raíz;
Perda de desempenho;
Pausas na aplicação durante processo de rastreamento;
Mesmo com as perdas, foi a opção escolhida pela JVM.
Estratégias de Coleta
• Mark-sweep
– Forma mais básica de algoritmos de rastreamento;
– Introduzido na linguagem LISP;
– Fase de Marcação (mark)
•
•
•
•
Percorre todos os nós a partir dos nós-raíz;
Marca cada objeto alcançado;
Ao final, heap contém objetos marcados e não marcados;
Não marcados = Não percorridos = LIXO;
– Fase de Varredura (sweep)
• Percorre a heap linearmente liberando todos os objetos não-marcados;
– Fragmentação;
Estratégias de Coleta
Estratégias de Coleta
• Copying Collectors (Coletores por Cópia)
– Duas regiões de memória (heap dividida);
– Região ativa a inativa;
– Execução:
• Busca por objetos não mais alcançáveis;
• Copia objetos alcançáveis para a nova região de memória;
• Troca entre as regiões ativa e inativa;
– Reduz fragmentação;
Estratégias de Coleta
Estratégias de Coleta
• Mark-sweep gera fragmentação;
• Coletores por cópia necessitam de uma fase
para verificar quais objetos ainda estão em
uso;
• Solução:
– Aplicar técnicas de cópia ao Mark-sweep
Mark-compact
Coleta de Lixo na JVM
Coleta de Lixo na JVM
• Distintas implementações visam distintos
perfis de aplicação;
• Coletores exatos
– Garantem que todos os objetos não mais usados
serão coletados;
• Usuário pode escolher qual coletor usará;
Coleta de Lixo na JVM
• Generational Collection (Coletas por Geração);
• Gerações
– Geração Jovem
•
•
•
•
•
•
Objetos recém-criados;
Tempo de vida curto;
Constante alocação de Blocos;
Maior número de coletas;
Éden;
Espaço de Sobreviventes (origem e destino);
Coleta de Lixo na JVM
• Gerações (continuação)
– Geração Jovem
• Quanto mais coletas um objeto sobrevive, maiores são
as chances desse objeto sobreviver por ainda mais
tempo;
• Éden  Espaço de Sobreviventes;
• Origem  Destino;
Coleta de Lixo na JVM
• Gerações (continuação)
– Geração Antiga
•
•
•
•
•
Objetos sobreviventes;
Promovidos;
Região “amadurecida”;
Objetos de vida longa;
Espaço contíguo (diferente da geração jovem);
– Geração Permanente
• Objetos de tempo de vida permanente;
Coleta de Lixo na JVM
Coleta de Lixo na JVM
O Mark-sweep na JVM
• Adaptação do Mark-sweep para o Markcompact;
• Implementado em 4 fases:
– Marcação e reciclagem;
– Computação dos novos endereços de memória
dos objetos vivos;
– Ajuste dos ponteiros;
– Compactação;
Coleta de Lixo na JVM
O Mark-sweep na JVM
• Mapa de bits
– Bit de marcação em um objeto: vivo ou morto;
– Mapas de bits podem ser listas lineares, por exemplo;
– Centralização das informações a respeito do estado dos
objetos;
– JVM implementa Mapa de bits como forma de manter um
sumário dos objetos vivos presentes na heap;
– Lazy Sweeping
• “Varredura preguiçosa”
Desempenho
• Coleta dos tempos de execução do coletor
Mark-sweep implementado pela JVM;
• Marcação no código da máquina virtual;
– Ciclos de Clock
• Foco nas 4 fases;
• 1ª fase é a mais custosa;
Desempenho
• Lista Encadeada;
• Benchmark GCBench;
– Arrays de vida longa;
– Árvores binárias;
• Java Grande Forum Benchmark Suite
– Operações simples;
– Kernels;
– Aplicações de Larga Escala
Desempenho
Desempenho
Desempenho
Desempenho
Simulador
Simulador
• Aplicação em Java;
• Mark-sweep, mark-compact, mark-lazysweep;
• Comparação dos custos na JVM com os custos
no Simulador;
• Simplificação dos algoritmos;
• Tentativa de replicação dos benchmarks;
Simulador
• Objetos: Oops;
– Bit de marcação;
• Heap
– Estrutura estática (array de tamanho n);
– Singleton;
• Coletores
– Interface (abstração do coletor);
– Medição de tempo;
Simulador
• Scripts
– Interface (abstração de scripts);
– Benchmarks;
– Exemplo: instanciação de objetos em forma de lista
encadeada;
• GUI
– Componente gráfico para chamar scripts e coletores;
– Herança entre o componente visual da Heap com JPanel;
Simulador
Simulador
Simulador
• Mark-compact concorrente
– Utiliza threads para copiar os objetos vivos;
– Realiza testes durante a cópia para não conflitar com a instanciação
em paralelo;
• Mark-lazy-sweep
– Manipulação de mapas de bits;
– Realizam a marcação apenas na primeira vez;
– Varredura se baseia no mapa de bits gerado pela última fase de
marcação;
– Nova fase de marcação só é realizada quando o mapa está cheio;
– Alocação sob demanda;
Simulações
Lista Encadeada
Simulações
Árvores Binárias
Simulações
Instanciações de Objeto
Conclusões
• Custo entre fases diferentes;
– Diferenças na implementação na JVM/Simulador;
– Padrões de projeto na JVM;
• Aplicações (prevalecem as listas encadeadas):
– Mark-compact Concorrente
• Possibilidade de se trabalhar com concorrência;
– Mark-lazy-sweep
• Pequenas pausas são aceitáveis;
Conclusões
• Aplicações onde prevalecem estruturas em
forma de árvore binária:
– Mark-compact concorrente;
– Fase de marcação simples;
– Não há necessidade de manipulação de mapas de
bits;
• Mark-lazy-sweep apresentou baixa
fragmentação
– Alocação sob-demanda;
Conclusões
• Aplicações com um grande número de
instanciações de objetos
– Mark-lazy-sweep;
– Custo se resume à manipulação do mapa de bits;
– Mark-compact concorrente demanda
gerenciamento complexo de threads;
• Cópia executada em paralelo;
Considerações Finais
• Idéia inicial: propor melhorias nos algoritmos
de coleta na JVM;
– Mark-sweep  Mark-lazy-sweep;
– Dificuldade (ou até mesmo impossibilidade)
devido à fase 4 (compactação);
– Necessidade de melhorias na primeira fase;
– Dificuldade de otimização pelo fato do Marksweep trabalhar com bits de marcação
vivo/morto;
Considerações Finais
• Mark-compact
–
–
–
–
Padrão (algoritmo por cópia);
Execução em paralelo;
Implementações eficientes;
Pouco espaço para melhorias;
• Simulador
–
–
–
–
Comparações entre os algoritmos presentes;
Maior custo na quarta fase;
Complexidade das estruturas na JVM;
Implementação simplificada na JVM poderia otimizar o processo;
Considerações Finais
• Após as simulações
– Algoritmo concorrente muito mais eficiente que o padrão;
– Possibilidade ou não de se trabalhar com concorrência
pode se tornar um empecilho;
– Tempo total da coleta do não-concorrente é maior!
• Cálculos efetuados para a gravação correta dos objetos no concorrente;
• Mark-compact concorrente e Mark-lazy-sweep são ainda
as melhores opções para a maioria dos cenários vistos no
trabalho;
Trabalhos Futuros
• Otimizar processo de marcação dos
objetos na JVM;
• Melhorias no Simulador para
melhor reflexão do
comportamento na JVM;
• Procurar novas maneiras de se
realizar coletas de lixo a serem,
inicialmente aplicadas no
Simulador;