Mehraufwand bei der Java-Objektzuweisung

Question

Ich schreibe einen unveränderlichen DOM-Baum in Java, um den Zugriff von mehreren Threads aus zu vereinfachen.*

Es muss jedoch Einfügungen und Aktualisierungen so schnell wie möglich unterstützen.Und da es unveränderlich ist, muss ich, wenn ich eine Änderung an einem Knoten auf der N-ten Ebene des Baums vornehme, mindestens N neue Knoten zuweisen, um den neuen Baum zurückzugeben.

Meine Frage ist: Wäre es wesentlich schneller, Knoten vorab zuzuweisen, anstatt bei jeder Änderung des Baums neue zu erstellen?Es wäre ziemlich einfach, einen Pool mit mehreren hundert ungenutzten Knoten zu behalten und einen aus dem Pool zu ziehen, anstatt immer dann einen zu erstellen, wenn er für eine Änderungsoperation benötigt wird.Ich kann den Knotenpool auffüllen, wenn sonst nichts los ist.(Falls es nicht offensichtlich ist, wird die Ausführungszeit in dieser Anwendung viel wichtiger sein als der Heap-Speicherplatz.)

Lohnt es sich, dies zu tun?Irgendwelche anderen Tipps zur Beschleunigung?

Weiß jemand alternativ, ob es bereits eine unveränderliche DOM-Bibliothek gibt?Ich habe gesucht, konnte aber nichts finden.

*Notiz:Für diejenigen unter Ihnen, die mit dem Konzept der Unveränderlichkeit nicht vertraut sind: Im Grunde bedeutet es, dass die Methode bei jeder Operation an einem Objekt, die es ändert, eine Kopie des Objekts mit den vorhandenen Änderungen zurückgibt und nicht das geänderte Objekt.Wenn also ein anderer Thread das Objekt noch liest, arbeitet er weiterhin problemlos mit der „alten“ Version, ohne zu bemerken, dass Änderungen vorgenommen wurden, und stürzt nicht schrecklich ab.Sehen http://www.javapractices.com/topic/TopicAction.do?Id=29

Answer 1

Heutzutage geht die Objekterstellung ziemlich schnell und das Konzept des Objekt-Poolings ist irgendwie veraltet (zumindest im Allgemeinen;(Verbindungspooling ist natürlich weiterhin gültig).

Vermeiden Sie eine vorzeitige Optimierung.Erstellen Sie Ihre Knoten, wenn Sie sie beim Erstellen Ihrer Kopien benötigen, und prüfen Sie dann, ob dies übermäßig langsam wird.Wenn ja, dann schauen Sie sich einige Techniken an, um es zu beschleunigen.Aber solange Sie nicht bereits wissen, dass das, was Sie haben, nicht schnell genug ist, würde ich nicht die ganze Komplexität einführen, die Sie benötigen, um das Pooling in Gang zu bringen.

Answer 2

Ich hasse es, keine Antwort zu geben, aber ich denke, die einzig definitive Möglichkeit, eine Leistungsfrage wie diese zu beantworten, könnte darin bestehen, beide Ansätze zu programmieren, die beiden zu vergleichen und die Ergebnisse zu vergleichen.

Answer 3

Ich bin mir nicht sicher, ob Sie die explizite Synchronisierung bestimmter Methoden vermeiden können, um sicherzustellen, dass alles Thread-sicher ist.

In einem bestimmten Fall müssen Sie die eine oder andere Seite synchronisieren, um einen neu erstellten Knoten für andere Threads verfügbar zu machen, da sonst das Risiko besteht, dass die VM/CPU die Schreibvorgänge der Felder nach dem Schreiben des Verweises auf den gemeinsam genutzten Knoten neu anordnet und offenlegt ein von einer Partei konstruiertes Objekt.

Versuchen Sie, auf einer höheren Ebene zu denken.Sie haben einen unveränderlichen Baum (das ist im Grunde eine Reihe von Knoten, die auf seine untergeordneten Knoten verweisen).Sie möchten darin einen Knoten einfügen.Dann gibt es keinen Ausweg mehr:Sie müssen einen neuen GANZEN Baum erstellen.

Wenn Sie den Baum als eine Reihe von Knoten implementieren möchten, die auf die untergeordneten Knoten verweisen, müssen Sie neue Knoten entlang des Pfads des geänderten Knotens zur Wurzel erstellen.Die anderen haben den gleichen Wert wie zuvor und werden normalerweise geteilt.Sie müssen also einen teilweise neuen Baum erstellen, was normalerweise (Tiefe des bearbeiteten Knotens) übergeordnete Knoten 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 Techniken verwenden, die den in beschriebenen ähneln Rein funktionale Datenstrukturen um entweder die durchschnittlichen Kosten der Erstellung zu reduzieren, oder Sie können es mit halbfunktionalen Ansätzen umgehen (z. B. indem Sie einen Iterator erstellen, der einen vorhandenen Iterator umschließt, aber den neuen Knoten anstelle des alten zurückgibt, zusammen mit einem Mechanismus zur Reparatur). solche Flecken in der Struktur im Laufe der Zeit).In diesem Fall ist eine API im XPath-Stil möglicherweise besser als eine DOM-API. Dadurch können Sie die Knoten etwas stärker vom Baum entkoppeln und den mutierten Baum intelligenter behandeln.

Answer 4

Ich bin ein wenig verwirrt darüber, was Sie überhaupt tun wollen.Sie möchten, dass alle Knoten unveränderlich sind UND Sie möchten sie in einem Pool zusammenfassen?Schließen sich diese beiden Ideen nicht gegenseitig aus?Wenn Sie ein Objekt aus dem Pool ziehen, müssen Sie dann nicht einen Setter aufrufen, um die untergeordneten Elemente zu verknüpfen?

Ich denke, dass die Verwendung unveränderlicher Knoten wahrscheinlich nicht die Art von Thread-Sicherheit bietet, die Sie überhaupt benötigen.Was passiert, wenn ein Thread die Knoten durchläuft (eine Suche oder ähnliches), 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 die explizite Synchronisierung bestimmter Methoden vermeiden können, um sicherzustellen, dass alles Thread-sicher ist.

Answer 5

@Outlaw Programmer

Wenn Sie ein Objekt aus dem Pool ziehen, müssen Sie dann keinen Setter aufrufen, um die Kinder zu verknüpfen?

Jeder Knoten muss nicht intern für das Paket unveränderlich sein, sondern nur für die nach außen gerichtete Schnittstelle. node.addChild() wäre eine unveränderliche Funktion mit öffentlicher Sichtbarkeit und würde ein Dokument zurückgeben, wohingegen node.addChildInternal() wäre eine normale, veränderbare Funktion mit Paketsichtbarkeit.Da es jedoch paketintern ist, kann es nur als Nachkomme von aufgerufen werden addChild() und die Struktur als Ganzes ist garantiert threadsicher (vorausgesetzt, ich synchronisiere den Zugriff auf den Objektpool).Sehen Sie darin einen Fehler?Wenn ja, sagen Sie es mir bitte!

Ich denke, dass die Verwendung unveränderlicher Knoten wahrscheinlich nicht die Art von Thread-Sicherheit bietet, die Sie überhaupt benötigen.Was passiert, wenn ein Thread die Knoten durchläuft (eine Suche oder ähnliches), während ein anderer Thread Knoten hinzufügt/entfernt?

Der Baum als Ganzes wird unveränderlich sein.Angenommen, ich habe Thread1 und Thread2 und Baum dom1.Thread1 startet einen Lesevorgang für dom1, während Thread2 gleichzeitig einen Schreibvorgang für dom1 startet.Allerdings werden alle Änderungen, die Thread2 vornimmt, tatsächlich an einem neuen Objekt, dom2, vorgenommen, und dom1 ist unveränderlich.Es ist wahr, dass die von Thread1 gelesenen Werte (einige Mikrosekunden) veraltet sind, aber es stürzt nicht bei einer IndexOutOfBounds- oder NullPointer-Ausnahme oder etwas Ähnlichem ab, wie es der Fall wäre, wenn ein veränderliches Objekt gelesen würde, in das geschrieben wurde.Anschließend kann Thread2 ein Ereignis, das dom2 enthält, an Thread1 auslösen, damit dieser den Lesevorgang erneut durchführen und bei Bedarf seine Ergebnisse aktualisieren kann.

Bearbeiten:geklärt

Answer 6

Ich denke, @Outlaw hat recht.Die Struktur des DOM-Baums liegt in den Knoten selbst, wobei ein Knoten auf seine untergeordneten Knoten zeigt.Um die Struktur eines Baums zu ändern, müssen Sie den Knoten ändern. Sie können ihn also nicht zusammenfassen, sondern müssen einen neuen erstellen.

Versuchen Sie, auf einer höheren Ebene zu denken.Sie haben einen unveränderlichen Baum (das ist im Grunde eine Reihe von Knoten, die auf seine untergeordneten Knoten verweisen).Sie möchten darin einen Knoten einfügen.Dann gibt es keinen Ausweg mehr:Sie müssen einen neuen GANZEN Baum erstellen.

Ja, der unveränderliche Baum ist threadsicher, beeinträchtigt jedoch die Leistung.Die Objekterstellung ist möglicherweise schnell, aber nicht schneller als die Erstellung von KEINEN Objekten.:) :)