Objeto Java de asignación de gastos generales

Question

Estoy escribiendo una inmutable árbol DOM en Java, para simplificar el acceso de múltiples subprocesos.*

Sin embargo, se hace necesario el apoyo de inserciones y actualizaciones tan rápido como sea posible.Y puesto que es inmutable, si puedo hacer un cambio a un nodo en la N-esima nivel del árbol, necesito asignar por lo menos el N de nuevos nodos con el fin de devolver el nuevo árbol.

Mi pregunta es, ¿sería mucho más rápido para pre-asignar nodos en lugar de crear otros nuevos cada vez que el árbol está modificado?Sería bastante fácil de hacer, mantener un grupo de varios cientos de inusitada nodos, y sacar uno de la piscina en lugar de crear uno cada vez que fue requerido para una operación de modificación.Puedo reponer el nodo de la piscina cuando no hay nada más.(en caso de que esto no es obvio, el tiempo de ejecución va a ser mucho más escaso en esta aplicación que montón de espacio)

Vale la pena hacer esto?Algunos otros consejos sobre la aceleración hacia arriba?

Alternativamente, ¿alguien sabe si una inmutable DOM biblioteca ya?He buscado, pero no pudo encontrar nada.

*Nota:Para aquellos de ustedes que no están familiarizados con el concepto de inmutabilidad, que básicamente significa que en cualquier operación a un objeto que cambia, el método devuelve una copia del objeto con los cambios en el lugar, más que el objeto que se ha cambiado.Por lo tanto, si otro hilo sigue leyendo el objeto seguirá felizmente operar en el "antiguo" de la versión, conscientes de que los cambios se han hecho, en vez de estrellarse horriblemente.Ver http://www.javapractices.com/topic/TopicAction.do?Id=29

Answer 1

En estos días, la creación de objetos es bastante dang rápido, y el concepto de agrupación de objetos es obsoleto (al menos en general;la agrupación de conexiones sigue siendo válido).

Evitar la prematura optimización.Crear los nodos cuando usted los necesita a la hora de copias y, a continuación, ver si se convierte en excesivamente lento.Si es así, entonces mirar en algunas técnicas para acelerar.Pero a menos que usted ya sabe que lo que tienes no es lo suficientemente rápido, no me vaya introduciendo toda la complejidad que vas a necesitar para conseguir que la agrupación va.

Answer 2

Yo odio a dar un no-respuesta, pero creo que la única manera definitiva para responder a un rendimiento pregunta como esta podría ser para usted el código de ambos enfoques, puntos de referencia de los dos, y comparar los resultados.

Answer 3

No estoy seguro de si se puede evitar de forma explícita la sincronización de ciertos métodos con el fin de asegurarse de que todo es thread-safe.

Un caso específico que usted necesita para sincronizar un lado o al otro de hacer que se creará un nuevo nodo disponible para otros hilos ya que de lo contrario el riesgo de la VM/CPU re-ordenar las escrituras de los campos pasado, la escritura de la referencia al nodo compartido, la exposición de una de las partes objeto construido.

Trate de pensar en un nivel superior.Usted tiene una INMUTABLE árbol (que es, básicamente, un conjunto de nodos que se apuntan a sus hijos).Desea insertar un nodo en ella.Entonces, no hay forma de salir:tienes que crear un nuevo árbol en su TOTALIDAD.

Si decide implementar el árbol como un conjunto de nodos que apunta a los niños, entonces usted tendría que crear nuevos nodos a lo largo de la ruta de los cambios en el nodo de la raíz.Los demás tienen el mismo valor que antes, y normalmente son compartidos.Por lo que necesita para crear un parcial de árbol nuevo, que normalmente significaría (profundidad de editar nodo) de los padres de los nodos.

Si usted puede hacer frente con una manera menos directa aplicación, usted debería ser capaz de salirse con sólo la creación de piezas de nodos, usando técnicas similares a las descritas en Puramente Funcional De Las Estructuras De Datos para reducir el costo promedio de la creación, o puede pasar que el uso de semi-enfoques funcionales (tales como la creación de un iterador que se ajusta a una ya existente iterador, pero devuelve el nuevo nodo en lugar de la antigua, junto con un mecanismo para la reparación de dichos parches en la estructura como pasa el tiempo).Una expresión XPath estilo api podría ser mejor que una api del DOM en ese caso - podría disociar los nodos del árbol un poco más, y el tratamiento de la mutado árbol de forma más inteligente.

Answer 4

Estoy un poco confundido acerca de lo que estamos tratando de hacer en el primer lugar.Desea que todos los nodos a ser inmutable Y desea piscina ellos?No son estas 2 ideas que se excluyen mutuamente?Cuando usted tira de un objeto fuera de la piscina, no tiene que invocar un setter para vincular a los niños?

Yo creo que el uso de inmutable nodos es, probablemente, no va a dar la clase de hilo de seguridad que usted necesita en el primer lugar.¿Qué sucede si 1 hilo es iterar sobre los nodos (una búsqueda o algo), mientras que el otro hilo se pueden añadir o quitar nodos?No los resultados de la búsqueda de ser válida?No estoy seguro de si se puede evitar de forma explícita la sincronización de ciertos métodos con el fin de asegurarse de que todo es thread-safe.

Answer 5

@Outlaw Programador

Cuando usted tira de un objeto fuera de la piscina, no tiene que invocar un setter para vincular a los niños?

Cada nodo no tiene que ser inmutable internamente en el paquete, sólo para el que mira hacia el exterior de la interfaz. node.addChild() sería una inmutable de la función pública con la visibilidad y la devolución de un Documento, mientras que node.addChildInternal() sería normal, mutable con la función de visibilidad de paquete.Pero desde que se interna en el paquete, sólo puede ser llamado como un descendiente de addChild() y la estructura como un todo está garantizado para los subprocesos (siempre que puedo sincronizar el acceso al objeto de la piscina).¿Ve usted una falla en esto...?Si es así, por favor dime!

Yo creo que el uso de inmutable nodos es, probablemente, no va a dar la clase de hilo de seguridad que usted necesita en el primer lugar.¿Qué sucede si 1 hilo es iterar sobre los nodos (una búsqueda o algo), mientras que el otro hilo se pueden añadir o quitar nodos?

El árbol como un todo, será inmutable.Decir que tengo Thread1 y Thread2, y el árbol de dom1.Thread1 inicia una operación de lectura en dom1, mientras que, al mismo tiempo, Thread2 se inicia una operación de escritura en dom1.Sin embargo, todos los cambios Thread2 hace que en realidad no se realizará un nuevo objeto, dom2, y dom1 será inmutable.Es cierto que los valores leídos por Thread1 será (un par de microsegundos) fuera de fecha, pero no bloquearse en una IndexOutOfBounds o NullPointer excepción o algo como lo haría si fue la lectura de un objeto mutable que estaba siendo escrito.Entonces, Thread2 puede disparar un evento que contiene dom2 a Thread1 para que pueda hacer su lectura de nuevo y actualización de sus resultados, si es necesario.

Editar:aclaró

Answer 6

Creo que @Forajido tiene un punto.La estructura del árbol DOM reside en los nodos de sí mismo, tener un nodo apunta a sus hijos.Para modificar la estructura de un árbol, tienes que modificar el nodo, por lo que no se puede tener agrupadas, usted tiene que crear una nueva.

Trate de pensar en un nivel superior.Usted tiene una INMUTABLE árbol (que es, básicamente, un conjunto de nodos que se apuntan a sus hijos).Desea insertar un nodo en ella.Entonces, no hay forma de salir:tienes que crear un nuevo árbol en su TOTALIDAD.

Sí, el inmutable árbol es thread-safe, pero tendrá un impacto en el rendimiento.Objeto de la creación, puede ser rápido, pero no más rápido que NINGÚN objeto de la creación.:)