sintaxis - Sobrecarga de asignación de objetos Java
sobrecarga polimorfismo java (6)
Estoy escribiendo un árbol DOM inmutable en Java para simplificar el acceso desde múltiples hilos. *
Sin embargo, necesita admitir inserciones y actualizaciones lo más rápido posible. Y dado que es inmutable, si realizo un cambio en un nodo en el N-ésimo nivel del árbol, necesito asignar al menos N nuevos nodos para devolver el nuevo árbol.
Mi pregunta es, ¿sería mucho más rápido preasignar nodos en lugar de crear nuevos cada vez que se modifique el árbol? Sería bastante fácil de hacer: mantener un grupo de varios cientos de nodos no utilizados y extraer uno del grupo en lugar de crear uno cuando sea necesario para una operación de modificación. Puedo reponer el grupo de nodos cuando no hay nada más en marcha. (en caso de que no sea obvio, el tiempo de ejecución va a ser mucho más importante en esta aplicación que el espacio de almacenamiento dinámico)
¿Vale la pena hacer esto? ¿Algún otro consejo para acelerarlo?
Alternativamente, ¿alguien sabe si ya hay una biblioteca DOM inmutable? Busqué, pero no pude encontrar nada.
* Nota: Para aquellos de ustedes que no están familiarizados con el concepto de inmutabilidad, básicamente significa que en cualquier operación a un objeto que lo cambie, el método devuelve una copia del objeto con los cambios en su lugar, en lugar de los cambios objeto. Por lo tanto, si otro hilo todavía está leyendo el objeto, continuará operando felizmente en la versión "anterior", sin darse cuenta de que se han realizado cambios, en lugar de estrellarse de forma horrible. Ver http://www.javapractices.com/topic/TopicAction.do?Id=29
Creo que @Outlaw tiene un punto. La estructura del árbol DOM reside en los nodos, teniendo un nodo apuntando a sus hijos. Para modificar la estructura de un árbol, debe modificar el nodo para que no pueda agruparse, debe crear uno nuevo.
Intenta pensar en un nivel superior. Tienes un árbol IMMUTABLE (que básicamente es un conjunto de nodos que apunta a sus hijos). Desea insertar un nodo en él. Entonces, no hay salida: tienes que crear un nuevo árbol ENTERO.
Sí, el árbol inmutable es seguro para hilos, pero tendrá un impacto en el rendimiento. La creación de objetos puede ser rápida, pero no más rápida que la creación de objetos NO. :)
Estoy un poco confundido acerca de lo que estás tratando de hacer en primer lugar. ¿Desea que todos los nodos sean inmutables Y desea agruparlos? ¿No son estas 2 ideas mutuamente excluyentes? Cuando sacas un objeto de la piscina, ¿no deberás invocar a un colocador para vincular a los niños?
Creo que el uso de nodos inmutables probablemente no le proporcionará el tipo de seguridad de hilo que necesita en primer lugar. ¿Qué sucede si un hilo se itera sobre los nodos (una búsqueda o algo), mientras que otro hilo está agregando / eliminando nodos? ¿No serán inválidos los resultados de la búsqueda? No estoy seguro si puede evitar la sincronización explícita de ciertos métodos para asegurarse de que todo esté seguro para subprocesos.
Hoy en día, la creación de objetos es bastante rápida, y el concepto de agrupamiento de objetos es obsoleto (al menos en general, la agrupación de conexiones sigue siendo válida, por supuesto).
Evite la optimización prematura. Cree sus nodos cuando los necesite cuando haga sus copias, y luego vea si eso se vuelve prohibitivamente lento. Si es así, busca algunas técnicas para acelerarlo. Pero a menos que ya sepas que lo que tienes no es lo suficientemente rápido, no iría presentando toda la complejidad que vas a necesitar para poner en marcha la agrupación.
Odio dar una falta de respuesta, pero creo que la única manera definitiva de responder una pregunta de rendimiento como esta podría ser codificar ambos enfoques, compararlos y comparar los resultados.
No estoy seguro si puede evitar la sincronización explícita de ciertos métodos para asegurarse de que todo esté seguro para subprocesos.
Un caso específico necesita sincronizar un lado o el otro para hacer que un nodo recién creado esté disponible para otros subprocesos, ya que de lo contrario corre el riesgo de que la VM / CPU reordene las escrituras de los campos después de la escritura de la referencia al nodo compartido, exponiendo un objeto construido por una fiesta.
Intenta pensar en un nivel superior. Tienes un árbol IMMUTABLE (que básicamente es un conjunto de nodos que apunta a sus hijos). Desea insertar un nodo en él. Entonces, no hay salida: tienes que crear un nuevo árbol ENTERO.
Si elige implementar el árbol como un conjunto de nodos que apuntan a los elementos secundarios, entonces deberá crear nuevos nodos a lo largo de la ruta del nodo modificado a la raíz. Los otros tienen el mismo valor que antes, y normalmente son compartidos. Por lo tanto, debe crear un árbol nuevo parcial, lo que generalmente significaría (profundidad del nodo editado) nodos principales.
Si puede hacer frente a una implementación menos directa, debe poder crear solo partes de nodos, utilizando técnicas similares a las descritas en Estructuras de Datos Puramente Funcionales para reducir el costo promedio de la creación, o bien puede: pasarlo usando enfoques semifuncionales (como crear un iterador que envuelve un iterador existente, pero devuelve el nuevo nodo en lugar del anterior, junto con un mecanismo para reparar dichos parches en la estructura a medida que pasa el tiempo). Una api de estilo XPath podría ser mejor que una API DOM en ese caso: podría desacoplar los nodos del árbol un poco más y tratar el árbol mutado de forma más inteligente.
Cuando sacas un objeto de la piscina, ¿no deberás invocar a un colocador para vincular a los niños?
No es necesario que cada nodo sea inmutable internamente en el paquete, solo en la interfaz hacia afuera. node.addChild() sería una función inmutable con visibilidad pública y devolvería un Documento, mientras que node.addChildInternal() sería una función normal y mutable con visibilidad del paquete. Pero dado que es interno al paquete, solo se puede llamar como un descendiente de addChild() y se garantiza que la estructura en su totalidad es segura para subprocesos (siempre que sincronice el acceso al grupo de objetos). ¿Ves un defecto en esto ...? ¡Si es así, por favor dígame!
Creo que el uso de nodos inmutables probablemente no le proporcionará el tipo de seguridad de hilo que necesita en primer lugar. ¿Qué sucede si un hilo se itera sobre los nodos (una búsqueda o algo), mientras que otro hilo está agregando / eliminando nodos?
El árbol como un todo será inmutable. Digamos que tengo Thread1 y Thread2, y tree dom1. Thread1 inicia una operación de lectura en dom1, mientras que, al mismo tiempo, Thread2 inicia una operación de escritura en dom1. Sin embargo, todos los cambios que hace Thread2 se realizarán en un nuevo objeto, dom2, y dom1 será inmutable. Es cierto que los valores leídos por Thread1 estarán (unos microsegundos) desactualizados, pero no se bloquearán en una excepción IndexOutOfBounds o NullPointer o algo así como si estuviera leyendo un objeto mutable en el que se estaba escribiendo. Luego, Thread2 puede disparar un evento que contenga dom2 a Thread1 para que pueda leerlo nuevamente y actualizar sus resultados, si es necesario.
Editar: aclarado