Prática recomendada para criar milhões de pequenos objetos temporários

Quais são as "melhores práticas" para criar (e liberar) milhões de pequenos objetos?

Estou escrevendo um programa de xadrez em Java e o algoritmo de pesquisa gera um único objeto "Mover" para cada movimento possível, e uma pesquisa nominal pode facilmente gerar mais de um milhão de objetos de movimento por segundo. O JVM GC foi capaz de lidar com a carga em meu sistema de desenvolvimento, mas estou interessado em explorar abordagens alternativas que:

1. Minimize a sobrecarga da coleta de lixo e
2. reduzir o consumo de memória de pico para sistemas de baixo custo.

A grande maioria dos objetos tem vida muito curta, mas cerca de 1% dos movimentos gerados são persistidos e retornados como o valor persistente, portanto, qualquer técnica de pooling ou cache teria que fornecer a capacidade de excluir objetos específicos de serem reutilizados .

Não espero um exemplo de código totalmente desenvolvido, mas gostaria de receber sugestões para leituras / pesquisas adicionais ou exemplos de código aberto de natureza semelhante.

Execute o aplicativo com coleta de lixo detalhada:

java -verbose:gc

E ele vai dizer quando ele coleta. Haveria dois tipos de varredura, uma varredura rápida e uma varredura completa.

[GC 325407K->83000K(776768K), 0.2300771 secs]
[GC 325816K->83372K(776768K), 0.2454258 secs]
[Full GC 267628K->83769K(776768K), 1.8479984 secs]

A seta está antes e depois do tamanho.

Contanto que seja apenas fazendo GC e não um GC completo, você estará seguro em casa. O GC regular é um coletor de cópias na 'geração jovem', então objetos que não são mais referenciados são simplesmente esquecidos, que é exatamente o que você deseja.

Ler o ajuste de coleta de lixo da máquina virtual Java SE 6 HotSpot provavelmente é útil.

Desde a versão 6, o modo servidor da JVM emprega uma técnica de análise de escape . Usando isso, você pode evitar GC todos juntos.

Bem, há várias perguntas em uma aqui!

1 - Como os objetos de curta duração são gerenciados?

Como afirmado anteriormente, a JVM pode perfeitamente lidar com uma grande quantidade de objetos de vida curta, uma vez que segue a Hipótese Geracional Fraca .

Observe que estamos falando de objetos que atingiram a memória principal (heap). Isso não é sempre o caso. Muitos objetos que você cria nem mesmo deixam um registro da CPU. Por exemplo, considere este for-loop

for(int i=0, i<max, i++) {
  // stuff that implies i
}

Não vamos pensar no desenrolamento de loop (uma otimização que a JVM executa fortemente em seu código). Se maxfor igual a Integer.MAX_VALUE, o loop pode levar algum tempo para ser executado. No entanto, a ivariável nunca escapará do bloco de loop. Portanto, a JVM colocará essa variável em um registro de CPU, incrementará regularmente, mas nunca a enviará de volta para a memória principal.

Portanto, criar milhões de objetos não é um grande negócio se eles forem usados ​​apenas localmente. Eles estarão mortos antes de serem armazenados no Éden, então o CG nem vai notar.

2 - É útil reduzir a sobrecarga do GC?

Como de costume, depende.

Primeiro, você deve habilitar o registro do GC para ter uma visão clara sobre o que está acontecendo. Você pode habilitá-lo com -Xloggc:gc.log -XX:+PrintGCDetails.

Se seu aplicativo está gastando muito tempo em um ciclo de GC, então, sim, ajuste o GC, caso contrário, pode não valer a pena.

Por exemplo, se você tem um GC jovem a cada 100 ms que leva 10 ms, você gasta 10% do seu tempo no GC e tem 10 coleções por segundo (o que é huuuuuge). Nesse caso, eu não gastaria nenhum tempo ajustando GC, uma vez que aqueles 10 GC / s ainda estariam lá.

3 - Alguma experiência

Tive um problema semelhante em um aplicativo que estava criando uma grande quantidade de uma determinada classe. Nos logs do GC, percebi que a taxa de criação do aplicativo era em torno de 3 GB / s, o que é muito (vamos lá ... 3 gigabytes de dados a cada segundo?!).

O problema: muitos GC frequentes causados ​​pela criação de muitos objetos.

No meu caso, anexei um criador de perfil de memória e percebi que uma classe representava uma grande porcentagem de todos os meus objetos. Rastreei as instanciações para descobrir que essa classe era basicamente um par de booleanos envolvidos em um objeto. Nesse caso, duas soluções estavam disponíveis:

• Retrabalhe o algoritmo para que eu não retorne um par de booleanos, mas, em vez disso, tenho dois métodos que retornam cada booleano separadamente

• Armazene os objetos em cache, sabendo que havia apenas 4 instâncias diferentes

Escolhi o segundo, pois teve o menor impacto no aplicativo e foi fácil de introduzir. Levei minutos para colocar uma fábrica com um cache não seguro para thread (eu não precisava de segurança de thread, pois acabaria tendo apenas 4 instâncias diferentes).

A taxa de alocação caiu para 1 GB / s, assim como a frequência de jovens GC (dividido por 3).

Espero que ajude !

Se você tiver apenas objetos de valor (ou seja, nenhuma referência a outros objetos) e realmente, mas realmente me refiro a toneladas e toneladas deles, você pode usar direto ByteBufferscom ordenação de bytes nativa [o último é importante] e você precisa de algumas centenas de linhas de código para alocar / reutilizar + getter / setters. Getters parecem semelhantes along getQuantity(int tupleIndex){return buffer.getLong(tupleInex+QUANTITY_OFFSSET);}

Isso resolveria o problema de GC quase inteiramente, desde que você aloque apenas uma vez, ou seja, uma grande parte e, em seguida, gerencie os objetos você mesmo. Em vez de referências, você teria apenas o índice (ou seja, int) no ByteBufferque deve ser transmitido. Você também pode precisar fazer o alinhamento de memória.

A técnica gostaria de usar C and void*, mas com um pouco de embalagem é suportável. Uma desvantagem de desempenho pode ser a verificação de limites se o compilador falhar em eliminá-la. Uma grande vantagem é a localidade, se você processar as tuplas como vetores, a falta do cabeçalho do objeto também reduz a área de cobertura da memória.

Fora isso, é provável que você não precise de tal abordagem, já que a geração mais jovem de praticamente todas as JVM morre trivialmente e o custo de alocação é apenas um aumento de ponteiro. O custo de alocação pode ser um pouco mais alto se você usar finalcampos, pois eles exigem limite de memória em algumas plataformas (nomeadamente ARM / Power), no entanto, em x86 é gratuito.

Supondo que você descubra que GC é um problema (como outros apontam que pode não ser), você implementará seu próprio gerenciamento de memória para seu caso especial, ou seja, uma classe que sofre grande rotatividade. Dê uma chance ao pool de objetos. Já vi casos em que funciona muito bem. A implementação de pools de objetos é um caminho bem conhecido, então não há necessidade de visitá-lo novamente aqui, preste atenção em:

• multi-threading: usar pools locais de thread pode funcionar para o seu caso
• estrutura de dados de apoio: considere o uso de ArrayDeque, pois ele tem um bom desempenho na remoção e não tem sobrecarga de alocação
• limite o tamanho da sua piscina :)

Meça antes / depois etc, etc

Eu encontrei um problema semelhante. Em primeiro lugar, tente reduzir o tamanho dos pequenos objetos. Introduzimos alguns valores de campo padrão fazendo referência a eles em cada instância do objeto.

Por exemplo, MouseEvent tem uma referência à classe Point. Armazenamos pontos em cache e os referenciamos em vez de criar novas instâncias. O mesmo para, por exemplo, strings vazias.

Outra fonte foram vários booleanos que foram substituídos por um int e para cada booleano usamos apenas um byte do int.

Lidei com esse cenário com algum código de processamento XML há algum tempo. Eu me peguei criando milhões de objetos de tag XML que eram muito pequenos (geralmente apenas uma string) e de vida extremamente curta (a falha de uma verificação XPath significava sem correspondência, então descarte).

Fiz alguns testes sérios e cheguei à conclusão de que só poderia alcançar uma melhoria de 7% na velocidade usando uma lista de tags descartadas em vez de fazer novas. No entanto, uma vez implementada, descobri que a fila livre precisava de um mecanismo adicionado para removê-la se ficasse muito grande - isso anulou completamente minha otimização, então mudei para uma opção.

Em resumo - provavelmente não vale a pena - mas fico feliz em ver que você está pensando nisso, isso mostra que você se importa.

Visto que você está escrevendo um programa de xadrez, existem algumas técnicas especiais que você pode usar para um desempenho decente. Uma abordagem simples é criar um grande array de longs (ou bytes) e tratá-lo como uma pilha. Cada vez que seu gerador de movimentos cria movimentos, ele empurra alguns números para a pilha, por exemplo, mover de um quadrado para outro. À medida que avalia a árvore de pesquisa, você exibe movimentos e atualiza uma representação do conselho.

Se você quiser objetos de uso de poder expressivo. Se você quiser velocidade (neste caso), vá para o nativo.

Uma solução que usei para esses algoritmos de pesquisa é criar apenas um objeto Mover, alterá-lo com o novo movimento e desfazer o movimento antes de sair do escopo. Você provavelmente está analisando apenas um movimento de cada vez e, em seguida, apenas armazenando o melhor movimento em algum lugar.

Se isso não for viável por algum motivo e você quiser diminuir o uso de memória máxima, um bom artigo sobre a eficiência da memória está aqui: http://www.cs.virginia.edu/kim/publicity/pldi09tutorials/memory-efficient-java- tutorial.pdf

Basta criar seus milhões de objetos e escrever seu código da maneira adequada: não mantenha referências desnecessárias a esses objetos. GC fará o trabalho sujo para você. Você pode brincar com o GC detalhado, conforme mencionado, para ver se eles são realmente GC. Java É sobre como criar e liberar objetos. :)

Acho que você deve ler sobre alocação de pilha em Java e análise de escape.

Porque se você se aprofundar neste tópico, poderá descobrir que seus objetos nem mesmo estão alocados no heap e não são coletados pelo GC da maneira que os objetos no heap são.

Há uma explicação na Wikipedia sobre a análise de escape, com um exemplo de como isso funciona em Java:

http://en.wikipedia.org/wiki/Escape_analysis

Não sou um grande fã do GC, então sempre tento encontrar maneiras de contornar isso. Nesse caso, eu sugeriria o uso do padrão Object Pool :

A ideia é evitar a criação de novos objetos, armazenando-os em uma pilha para que você possa reutilizá-los posteriormente.

Class MyPool
{
   LinkedList<Objects> stack;

   Object getObject(); // takes from stack, if it's empty creates new one
   Object returnObject(); // adds to stack
}

Os pools de objetos fornecem melhorias enormes (às vezes 10x) sobre a alocação de objetos no heap. Mas a implementação acima usando uma lista vinculada é ingênua e errada! A lista vinculada cria objetos para gerenciar sua estrutura interna anulando o esforço. Um Ringbuffer usando uma série de objetos funciona bem. No exemplo dar (um programa de xadrez que gerencia os movimentos), o Ringbuffer deve ser embrulhado em um objeto de suporte para a lista de todos os movimentos computados. Apenas as referências do objeto titular de movimentos seriam então passadas.