Sobrecarga de alocação de objetos Java

Question

Estou escrevendo uma árvore DOM imutável em Java, para simplificar o acesso de vários threads.*

No entanto, ele precisa oferecer suporte a inserções e atualizações o mais rápido possível.E como é imutável, se eu fizer uma alteração em um nó no enésimo nível da árvore, preciso alocar pelo menos N novos nós para retornar a nova árvore.

Minha pergunta é: seria dramaticamente mais rápido pré-alocar nós em vez de criar novos sempre que a árvore fosse modificada?Seria bastante fácil de fazer - manter um pool de várias centenas de nós não utilizados e retirar um do pool em vez de criar um sempre que fosse necessário para uma operação de modificação.Posso reabastecer o pool de nós quando não há mais nada acontecendo.(caso não seja óbvio, o tempo de execução será muito mais valioso neste aplicativo do que o espaço de heap)

Vale a pena fazer isso?Alguma outra dica para acelerar?

Alternativamente, alguém sabe se já existe uma biblioteca DOM imutável?Procurei, mas não consegui encontrar nada.

*Observação:Para aqueles que não estão familiarizados com o conceito de imutabilidade, isso basicamente significa que em qualquer operação em um objeto que o altere, o método retorna uma cópia do objeto com as alterações em vigor, em vez do objeto alterado.Assim, se outro thread ainda estiver lendo o objeto, ele continuará operando na versão "antiga", sem saber que alterações foram feitas, em vez de travar horrivelmente.Ver http://www.javapractices.com/topic/TopicAction.do?Id=29

Answer 1

Hoje em dia, a criação de objetos é muito rápida e o conceito de pooling de objetos é meio obsoleto (pelo menos em geral;o pool de conexões ainda é válido).

Evite otimização prematura.Crie seus nós quando precisar deles ao fazer suas cópias e veja se isso se torna proibitivamente lento.Nesse caso, procure algumas técnicas para acelerá-lo.Mas, a menos que você já saiba que o que você tem não é rápido o suficiente, eu não introduziria toda a complexidade necessária para iniciar o pooling.

Answer 2

Detesto não responder, mas acho que a única maneira definitiva de responder a uma pergunta de desempenho como essa seria codificar as duas abordagens, comparar as duas e comparar os resultados.

Answer 3

Não tenho certeza se você pode evitar a sincronização explícita de determinados métodos para garantir que tudo seja seguro para threads.

Em um caso específico, você precisa sincronizar um lado ou outro para disponibilizar um nó recém-criado para outros threads, caso contrário você corre o risco de a VM/CPU reordenar as gravações dos campos após a gravação da referência ao nó compartilhado, expondo um objeto construído pelo partido.

Tente pensar em um nível superior.Você tem uma árvore IMMUTABLE (que é basicamente um conjunto de nós apontando para seus filhos).Você deseja inserir um nó nele.Então não há saída:você tem que criar uma nova árvore INTEIRA.

Se você optar por implementar a árvore como um conjunto de nós apontando para os filhos, será necessário criar novos nós ao longo do caminho do nó alterado até a raiz.Os demais têm o mesmo valor de antes e normalmente são compartilhados.Portanto, você precisa criar uma nova árvore parcial, o que normalmente significaria (profundidade do nó editado) nós pais.

Se você conseguir lidar com uma implementação menos direta, deverá conseguir criar apenas partes de nós, usando técnicas semelhantes às descritas em Estruturas de dados puramente funcionais para reduzir o custo médio da criação, ou você pode contorná-lo usando abordagens semifuncionais (como criar um iterador que envolve um iterador existente, mas retorna o novo nó em vez do antigo, junto com um mecanismo para reparar tais manchas na estrutura com o passar do tempo).Nesse caso, uma API de estilo XPath pode ser melhor que uma API DOM - você pode desacoplar um pouco mais os nós da árvore e tratar a árvore mutada de maneira mais inteligente.

Answer 4

Estou um pouco confuso sobre o que você está tentando fazer em primeiro lugar.Você deseja que todos os nós sejam imutáveis ​​E deseja agrupá-los?Essas duas ideias não são mutuamente exclusivas?Ao retirar um objeto da piscina, você não terá que invocar um levantador para conectar os filhos?

Acho que o uso de nós imutáveis ​​provavelmente não fornecerá o tipo de segurança de thread que você precisa em primeiro lugar.O que acontece se um thread estiver iterando nos nós (uma pesquisa ou algo assim), enquanto outro thread estiver adicionando/removendo nós?Os resultados da pesquisa não serão inválidos?Não tenho certeza se você pode evitar a sincronização explícita de determinados métodos para garantir que tudo seja seguro para threads.

Answer 5

@Programador Fora da Lei

Quando você puxa um objeto para fora da piscina, você não terá que invocar um setter para vincular as crianças?

Cada nó não precisa ser imutável internamente ao pacote, apenas à interface externa. node.addChild() seria uma função imutável com visibilidade pública e retornaria um Documento, enquanto node.addChildInternal() seria uma função normal e mutável com visibilidade do pacote.Mas como é interno ao pacote, só pode ser chamado como descendente de addChild() e a estrutura como um todo é garantida como thread-safe (desde que eu sincronize o acesso ao pool de objetos).Você vê uma falha nisso...?Se assim for, por favor me diga!

Acho que o uso de nós imutáveis ​​provavelmente não fornecerá o tipo de segurança de thread que você precisa em primeiro lugar.O que acontece se um thread estiver iterando nos nós (uma pesquisa ou algo assim), enquanto outro thread estiver adicionando/removendo nós?

A árvore como um todo será imutável.Digamos que eu tenha Thread1 e Thread2 e árvore dom1.Thread1 inicia uma operação de leitura no dom1, enquanto, simultaneamente, Thread2 inicia uma operação de gravação no dom1.No entanto, todas as alterações que Thread2 fizer serão, na verdade, feitas em um novo objeto, dom2, e dom1 será imutável.É verdade que os valores lidos por Thread1 estarão (alguns microssegundos) desatualizados, mas não travarão em uma exceção IndexOutOfBounds ou NullPointer ou algo parecido se estivesse lendo um objeto mutável no qual estava sendo gravado.Então, Thread2 pode disparar um evento contendo dom2 para Thread1 para que ele possa fazer sua leitura novamente e atualizar seus resultados, se necessário.

Editar:esclarecido

Answer 6

Acho que @Outlaw tem razão.A estrutura da árvore DOM reside nos próprios nós, possuindo um nó apontando para seus filhos.Para modificar a estrutura de uma árvore você tem que modificar o nó, então você não pode agrupá-lo, você tem que criar um novo.

Tente pensar em um nível superior.Você tem uma árvore IMMUTABLE (que é basicamente um conjunto de nós apontando para seus filhos).Você deseja inserir um nó nele.Então não há saída:você tem que criar uma nova árvore INTEIRA.

Sim, a árvore imutável é segura para threads, mas afetará o desempenho.A criação de objetos pode ser rápida, mas não mais rápida do que NÃO criar objetos.:)