Surcharge d'allocation d'objet Java

Question

J'écris une arborescence DOM immuable en Java, pour simplifier l'accès à partir de plusieurs threads.*

Cependant, il doit prendre en charge les insertions et les mises à jour aussi rapidement que possible.Et comme il est immuable, si j'apporte une modification à un nœud au Nième niveau de l'arborescence, je dois allouer au moins N nouveaux nœuds afin de renvoyer le nouvel arbre.

Ma question est la suivante : serait-il considérablement plus rapide de pré-attribuer des nœuds plutôt que d'en créer de nouveaux à chaque fois que l'arborescence est modifiée ?Ce serait assez simple à faire : conserver un pool de plusieurs centaines de nœuds inutilisés et en retirer un du pool plutôt que d'en créer un chaque fois que cela est nécessaire pour une opération de modification.Je peux reconstituer le pool de nœuds lorsqu'il ne se passe rien d'autre.(au cas où cela ne serait pas évident, le temps d'exécution sera beaucoup plus limité dans cette application que l'espace de stockage)

Est-ce que cela vaut la peine de faire ça ?Avez-vous d'autres conseils pour l'accélérer ?

Sinon, est-ce que quelqu'un sait s'il existe déjà une bibliothèque DOM immuable ?J'ai cherché, mais je n'ai rien trouvé.

*Note:Pour ceux d'entre vous qui ne sont pas familiers avec le concept d'immuabilité, cela signifie essentiellement que lors de toute opération sur un objet qui le modifie, la méthode renvoie une copie de l'objet avec les modifications en place, plutôt que l'objet modifié.Ainsi, si un autre thread est encore en train de lire l'objet, il continuera à fonctionner avec plaisir sur "l'ancienne" version, ignorant que des modifications ont été apportées, plutôt que de planter horriblement.Voir http://www.javapractices.com/topic/TopicAction.do?Id=29

Answer 1

De nos jours, la création d’objets est assez rapide et le concept de pooling d’objets est plutôt obsolète (du moins en général ;le pooling de connexions est bien entendu toujours valable).

Évitez une optimisation prématurée.Créez vos nœuds lorsque vous en avez besoin lors de vos copies, puis voyez si cela devient trop lent.Si tel est le cas, étudiez quelques techniques pour l’accélérer.Mais à moins que vous ne sachiez déjà que ce que vous avez n'est pas assez rapide, je n'introduireais pas toute la complexité dont vous aurez besoin pour lancer la mise en commun.

Answer 2

Je déteste donner une non-réponse, mais je pense que la seule manière définitive de répondre à une question de performance comme celle-ci pourrait être de coder les deux approches, de les comparer et de comparer les résultats.

Answer 3

Je ne sais pas si vous pouvez éviter de synchroniser explicitement certaines méthodes afin de vous assurer que tout est thread-safe.

Dans un cas spécifique, vous devez synchroniser d'un côté ou de l'autre la mise à disposition d'un nœud nouvellement créé pour d'autres threads, sinon vous risquez que la VM/CPU réorganise les écritures des champs après l'écriture de la référence sur le nœud partagé, exposant un objet construit par le parti.

Essayez de penser à un niveau supérieur.Vous disposez d'un arbre IMMUTABLE (c'est essentiellement un ensemble de nœuds pointant vers ses enfants).Vous souhaitez y insérer un nœud.Ensuite, il n'y a pas d'issue :vous devez créer un nouvel arbre ENTIER.

Si vous choisissez d'implémenter l'arborescence comme un ensemble de nœuds pointant vers les enfants, vous devrez alors créer de nouveaux nœuds le long du chemin du nœud modifié vers la racine.Les autres ont la même valeur qu’auparavant et sont normalement partagés.Vous devez donc créer un nouvel arbre partiel, ce qui signifie généralement (profondeur du nœud modifié) les nœuds parents.

Si vous pouvez gérer une implémentation moins directe, vous devriez pouvoir vous contenter de créer uniquement des parties de nœuds, en utilisant des techniques similaires à celles décrites dans Structures de données purement fonctionnelles soit pour réduire le coût moyen de la création, soit pour le contourner en utilisant des approches semi-fonctionnelles (telles que la création d'un itérateur qui encapsule un itérateur existant, mais renvoie le nouveau nœud au lieu de l'ancien, ainsi qu'un mécanisme de réparation ces correctifs dans la structure au fil du temps).Une API de style XPath pourrait être meilleure qu'une API DOM dans ce cas - vous pourriez découpler un peu plus les nœuds de l'arborescence et traiter l'arborescence muté plus intelligemment.

Answer 4

Je suis un peu confus quant à ce que vous essayez de faire en premier lieu.Vous voulez que tous les nœuds soient immuables ET vous souhaitez les regrouper ?Ces 2 idées ne s'excluent-elles pas mutuellement ?Lorsque vous sortez un objet de la piscine, ne devrez-vous pas faire appel à un passeur pour relier les enfants ?

Je pense que l'utilisation de nœuds immuables ne vous offrira probablement pas le type de sécurité des threads dont vous avez besoin en premier lieu.Que se passe-t-il si un thread parcourt les nœuds (une recherche ou quelque chose du genre), tandis qu'un autre thread ajoute/supprime des nœuds ?Les résultats de la recherche ne seront-ils pas invalides ?Je ne sais pas si vous pouvez éviter de synchroniser explicitement certaines méthodes afin de vous assurer que tout est thread-safe.

Answer 5

@Programmeur hors-la-loi

Lorsque vous sortez un objet de la piscine, n'aurez-vous pas à invoquer un pasteur pour relier les enfants?

Chaque nœud n'a pas besoin d'être immuable en interne pour le package, uniquement pour l'interface orientée vers l'extérieur. node.addChild() serait une fonction immuable avec une visibilité publique et renverrait un document, alors que node.addChildInternal() serait une fonction normale et mutable avec une visibilité sur les packages.Mais comme il est interne au package, il ne peut être appelé que comme descendant de addChild() et la structure dans son ensemble est garantie pour être thread-safe (à condition de synchroniser l'accès au pool d'objets).Voyez-vous un défaut dans cela... ?Si c'est le cas, dites-le-moi !

Je pense que l'utilisation de nœuds immuables ne vous offrira probablement pas le type de sécurité des threads dont vous avez besoin en premier lieu.Que se passe-t-il si un thread parcourt les nœuds (une recherche ou quelque chose du genre), tandis qu'un autre thread ajoute/supprime des nœuds ?

L'arbre dans son ensemble sera immuable.Disons que j'ai Thread1 et Thread2, et l'arbre dom1.Thread1 démarre une opération de lecture sur dom1, tandis que, simultanément, Thread2 démarre une opération d'écriture sur dom1.Cependant, toutes les modifications apportées par Thread2 seront en réalité apportées à un nouvel objet, dom2 et dom1 seront immuables.Il est vrai que les valeurs lues par Thread1 seront (quelques microsecondes) obsolètes, mais elles ne planteront pas en cas d'exception IndexOutOfBounds ou NullPointer ou quelque chose comme ce serait le cas s'il lisait un objet mutable sur lequel il était écrit.Ensuite, Thread2 peut déclencher un événement contenant dom2 sur Thread1 afin qu'il puisse refaire sa lecture et mettre à jour ses résultats, si nécessaire.

Modifier:clarifié

Answer 6

Je pense que @Outlaw a raison.La structure de l'arborescence DOM réside dans les nœuds eux-mêmes, un nœud pointant vers ses enfants.Pour modifier la structure d'un arbre, vous devez modifier le nœud, vous ne pouvez donc pas le regrouper, vous devez en créer un nouveau.

Essayez de penser à un niveau supérieur.Vous disposez d'un arbre IMMUTABLE (c'est essentiellement un ensemble de nœuds pointant vers ses enfants).Vous souhaitez y insérer un nœud.Ensuite, il n'y a pas d'issue :vous devez créer un nouvel arbre ENTIER.

Oui, l’arborescence immuable est thread-safe, mais cela aura un impact sur les performances.La création d'objets peut être rapide, mais pas plus rapide qu'AUCUNE création d'objet.:)