Ich schreibe einen unveränderlichen DOM-Baum in Java, um den Zugriff von mehreren Threads zu vereinfachen. *
Allerdings müssen Einfügungen und Aktualisierungen so schnell wie möglich unterstützt werden. Und da es unveränderlich ist, wenn ich einen Knoten auf der N-ten Ebene des Baumes ändere, muss ich mindestens N neue Knoten zuweisen, um den neuen Baum zurückzugeben.
Meine Frage ist, wäre es dramatisch schneller, Knoten vorab vorzubelegen, anstatt jedes Mal, wenn der Baum geändert wird, neue Knoten zu erstellen? Es wäre ziemlich einfach zu tun - behalte einen Pool von mehreren hundert ungenutzten Knoten und ziehe einen Pool aus dem Pool, anstatt einen Pool zu erstellen, wann immer es für einen Änderungsvorgang benötigt wird. Ich kann den Knotenpool auffüllen, wenn nichts anderes passiert. (Für den Fall, dass es nicht offensichtlich ist, wird die Ausführungszeit in dieser Anwendung viel mehr als der Heap-Platz sein)
Lohnt es sich, das zu tun? Irgendwelche anderen Tipps, um es zu beschleunigen?
Oder weiß jemand, ob eine unveränderliche DOM-Bibliothek bereits existiert? Ich suchte, konnte aber nichts finden.
* Hinweis: Für diejenigen unter Ihnen, die mit dem Konzept der Unveränderlichkeit nicht vertraut sind, bedeutet dies im Grunde, dass bei jeder Operation für ein Objekt, das sie ändert, die Methode eine Kopie des Objekts mit den Änderungen an Ort und Stelle zurückgibt als das geänderte Objekt. Wenn also ein anderer Thread das Objekt noch liest, wird es weiterhin glücklich mit der "alten" Version arbeiten, ohne zu wissen, dass Änderungen vorgenommen wurden, anstatt schrecklich zu stürzen. Siehe Ссылка
Heutzutage ist die Objekterstellung ziemlich schnell, und das Konzept des Objekt-Poolings ist irgendwie obsolet (zumindest im Allgemeinen; Verbindungspooling ist natürlich immer noch gültig).
Vermeiden Sie eine vorzeitige Optimierung. Erstellen Sie Ihre Knoten, wenn Sie sie benötigen, wenn Sie Ihre Kopien erstellen, und sehen Sie dann, ob dies zu langsam wird. Wenn ja, dann schauen Sie sich einige Techniken an, um es zu beschleunigen. Aber wenn Sie nicht bereits wissen, dass das, was Sie haben, nicht schnell genug ist, würde ich Ihnen nicht die ganze Komplexität vorstellen, die Sie brauchen, um das Pooling in Gang zu bringen.
Ich denke @Outlaw hat einen Punkt. Die Struktur des DOM-Baums befindet sich in den Knoten selbst, wobei ein Knoten auf seine untergeordneten Elemente zeigt. Um die Struktur eines Baumes zu ändern, müssen Sie den Knoten ändern, damit Sie ihn nicht zusammenführen können, müssen Sie einen neuen erstellen.
Versuchen Sie, auf einer höheren Ebene zu denken. Sie haben einen IMMUTABLE-Baum (das ist im Grunde eine Menge von Knoten, die auf seine Kinder zeigen). Sie möchten einen Knoten einfügen. Dann gibt es keinen Ausweg mehr: Sie müssen einen neuen GANZEN Baum erstellen.
Ja, der unveränderliche Baum ist Thread-sicher, aber er beeinträchtigt die Leistung. Die Objekterstellung kann schnell sein, aber nicht schneller als die Erstellung von NO-Objekten. :)
Ich bin nicht sicher, ob Sie vermeiden können, bestimmte Methoden explizit zu synchronisieren, um sicherzustellen, dass alles threadsicher ist.
In einem bestimmten Fall müssen Sie die eine oder die andere Seite synchronisieren, um einen neu erstellten Knoten für andere Threads verfügbar zu machen, da Sie sonst riskieren, dass die VM / CPU die Schreibvorgänge der Felder nach dem Schreiben des Verweises auf den Shared neu anordnet Knoten, ein von einer Partei konstruiertes Objekt auszusetzen.
Versuchen Sie, auf einer höheren Ebene zu denken. Sie haben einen IMMUTABLE-Baum (das ist im Grunde eine Menge von Knoten, die auf seine Kinder zeigen). Sie möchten einen Knoten einfügen. Dann gibt es keinen Ausweg mehr: Sie müssen einen neuen GANZEN Baum erstellen.
Wenn Sie den Baum als eine Gruppe von Knoten implementieren, die auf die untergeordneten Elemente verweisen, müssen Sie neue Knoten entlang des Pfads des geänderten Knotens zum Stamm erstellen. Die anderen haben den gleichen Wert wie zuvor und werden normalerweise geteilt. Sie müssen also einen teilweise neuen Baum erstellen, der normalerweise die übergeordneten Knoten (Tiefe des bearbeiteten Knotens) bedeuten würde.
Wenn Sie mit einer weniger direkten Implementierung zurechtkommen, sollten Sie in der Lage sein, nur Teile von Knoten zu erstellen, indem Sie ähnliche Techniken wie in Rein funktionale Datenstrukturen , um entweder die durchschnittlichen Kosten der Erstellung zu reduzieren, oder Sie können sie mithilfe semi-funktionaler Ansätze umgehen (z. B. Erstellen ein Iterator, der einen vorhandenen Iterator umschließt, aber anstelle des alten den neuen Knoten zusammen mit einem Mechanismus zum Reparieren solcher Patches in der Struktur im Laufe der Zeit zurückgibt. Ein XPath-Stil api könnte in diesem Fall besser sein als ein DOM-api - Sie könnten die Knoten ein wenig mehr vom Baum trennen und den mutierten Baum intelligenter behandeln.
Ich bin ein wenig verwirrt darüber, was Sie überhaupt machen wollen. Sie möchten, dass alle Knoten unveränderlich sind und Sie sie zusammenfassen möchten? Schließen sich diese beiden Ideen nicht gegenseitig aus? Wenn Sie ein Objekt aus dem Pool ziehen, müssen Sie nicht einen Setter aufrufen, um die untergeordneten Objekte zu verknüpfen?
Ich denke, dass die Verwendung von unveränderlichen Knoten Ihnen wahrscheinlich nicht die Art von Thread-Sicherheit geben wird, die Sie in erster Linie brauchen. Was passiert, wenn 1 Thread über die Knoten (eine Suche oder etwas) iteriert, während ein anderer Thread Knoten hinzufügt / entfernt? Werden die Ergebnisse der Suche nicht ungültig sein? Ich bin mir nicht sicher, ob Sie es vermeiden können, bestimmte Methoden explizit zu synchronisieren, um sicherzustellen, dass alles threadsicher ist.
Wenn Sie ein Objekt aus der Pool, müssen Sie nicht ein aufrufen Setzer, um die Kinder zu verbinden?
Jeder Knoten muss nicht innerhalb des Pakets unveränderlich sein, nur zu der nach außen weisenden Schnittstelle. node.addChild() wäre eine unveränderliche Funktion mit öffentlicher Sichtbarkeit und gibt ein Dokument zurück, wobei node.addChildInternal() eine normale, veränderbare Funktion mit Paketsichtbarkeit wäre. Da es jedoch intern im Paket ist, kann es nur als Abkömmling von addChild() aufgerufen werden, und die Struktur als Ganzes ist garantiert Thread-sicher (vorausgesetzt, ich synchronisiere den Zugriff auf den Objekt-Pool). Siehst du einen Fehler in diesem ...? Wenn ja, bitte sag es mir!
Ich denke, dass die Verwendung von unveränderlichen Knoten Ihnen wahrscheinlich nicht die Art von Thread-Sicherheit geben wird, die Sie in erster Linie brauchen. Was passiert, wenn 1 Thread über die Knoten (eine Suche oder etwas) iteriert, während ein anderer Thread Knoten hinzufügt / entfernt?
Der Baum als Ganzes wird unveränderlich sein. Angenommen, ich habe Thread1 und Thread2 und tree dom1. Thread1 startet eine Leseoperation für dom1, während Thread2 gleichzeitig eine Schreiboperation für dom1 startet. Alle Änderungen, die an Thread2 vorgenommen werden, werden jedoch tatsächlich an einem neuen Objekt vorgenommen, dom2 und dom1 werden unveränderlich sein. Es stimmt, dass die von Thread1 gelesenen Werte (einige Mikrosekunden) veraltet sind, aber bei einer IndexOutOfBounds- oder NullPointer-Ausnahme oder so etwas wie beim Lesen eines veränderbaren Objekts, in das geschrieben wurde, stürzt es nicht ab. Dann kann Thread2 ein Ereignis, das dom2 enthält, an Thread1 absetzen, so dass es seinen Lesevorgang wiederholen und gegebenenfalls seine Ergebnisse aktualisieren kann.
Bearbeiten: geklärt
Tags und Links java xml dom concurrency