8

我正在用 Java 编写一个不可变的 DOM 树，以简化来自多个线程的访问。*

但是，它确实需要尽可能快地支持插入和更新。而且由于它是不可变的，如果我对树的第 N 级上的节点进行更改，我需要分配至少 N 个新节点才能返回新树。

我的问题是，每次修改树时预先分配节点而不是创建新节点会更快吗？这将相当容易 - 保留一个包含数百个未使用节点的池，并从池中拉出一个，而不是在需要修改操作时创建一个。当没有其他事情发生时，我可以补充节点池。（如果不是很明显，在这个应用程序中执行时间将比堆空间更宝贵）

这样做值得吗？还有其他加快速度的技巧吗？

或者，有人知道不可变的 DOM 库是否已经存在吗？我搜索了，但找不到任何东西。

*注意：对于那些不熟悉不变性概念的人来说，它基本上意味着在对更改它的对象的任何操作上，该方法返回一个具有更改的对象的副本，而不是更改的对象目的。因此，如果另一个线程仍在读取对象，它将继续愉快地在“旧”版本上运行，而不知道已经进行了更改，而不是可怕地崩溃。见http://www.javapractices.com/topic/TopicAction.do?Id=29

4

6 回答 6

12

这些天来，对象创建非常快，对象池的概念已经过时（至少在一般情况下；连接池当然仍然有效）。

避免过早优化。复制时在需要时创建节点，然后看看是否会变得异常缓慢。如果是这样，那么请研究一些技术来加快速度。但是除非你已经知道你所拥有的还不够快，否则我不会介绍你需要进行池化的所有复杂性。

于 2008-09-03T19:47:53.833 回答
3

我不想给出一个不回答的问题，但我认为回答此类性能问题的唯一确定方法可能是对这两种方法进行编码，对两者进行基准测试，然后比较结果。

于 2008-09-03T19:45:38.003 回答
1

我不确定您是否可以避免显式同步某些方法以确保一切都是线程安全的。

在一种特定情况下，您需要同步使新创建的节点可用于其他线程的一侧或另一侧，否则您可能会冒着 VM/CPU 在写入共享节点的引用之后重新排序字段写入的风险，从而暴露一方构造的对象。

尝试在更高的层次上思考。您有一个 IMMUTABLE 树（基本上是一组指向其子节点的节点）。您想在其中插入一个节点。然后，没有出路：您必须创建一个新的整个树。

如果您选择将树实现为一组指向子节点的节点，那么您必须沿着更改节点到根的路径创建新节点。其他的值和以前一样，通常是共享的。所以你需要创建一个部分新树，这通常意味着（编辑节点的深度）父节点。

如果您可以处理不太直接的实现，您应该能够摆脱只创建部分节点，使用类似于纯功能数据结构中描述的技术来降低创建的平均成本，或者您可以通过 -使用半功能方法传递它（例如创建一个包含现有迭代器的迭代器，但返回新节点而不是旧节点，以及随着时间的推移修复结构中此类补丁的机制）。在这种情况下，XPath 风格的 api 可能比 DOM api 更好——它可能会使节点与树的解耦更多，并更智能地处理变异的树。

于 2008-09-04T00:11:36.010 回答
0

我对您首先要尝试做的事情感到有些困惑。您希望所有节点都是不可变的并且您想将它们汇集在一起​​吗？这两个想法不是相互排斥的吗？当你从池中拉出一个对象时，你不需要调用一个 setter 来连接孩子吗？

我认为使用不可变节点可能不会首先为您提供所需的线程安全性。如果一个线程正在迭代节点（搜索或其他），而另一个线程正在添加/删除节点，会发生什么？搜索的结果会不会无效？我不确定您是否可以避免显式同步某些方法以确保一切都是线程安全的。

于 2008-09-03T19:59:59.797 回答
0

@Outlaw 程序员

当你从池中拉出一个对象时，你不需要调用一个 setter 来连接孩子吗？

每个节点不需要在包内部是不可变的，只需要对外接口。node.addChild()将是具有公共可见性并返回文档的不可变函数，而node.addChildInternal()将是具有包可见性的正常可变函数。但由于它在包的内部，它只能被称为的后代，addChild()并且整个结构被保证是线程安全的（假设我同步访问对象池）。你觉得这有什么缺陷吗……？如果是这样，请告诉我！

我认为使用不可变节点可能不会首先为您提供所需的线程安全性。如果一个线程正在迭代节点（搜索或其他），而另一个线程正在添加/删除节点，会发生什么？

整个树将是不可变的。假设我有 Thread1 和 Thread2，以及树 dom1。Thread1 开始对 dom1 进行读操作，同时，Thread2 开始对 dom1 进行写操作。但是，Thread2 所做的所有更改实际上都会对新对象 dom2 进行，并且 dom1 将是不可变的。确实，Thread1 读取的值将过期（几微秒），但它不会在 IndexOutOfBounds 或 NullPointer 异常或类似情况下崩溃，如果它正在读取正在写入的可变对象。然后，Thread2 可以向 Thread1 触发包含 dom2 的事件，以便它可以再次读取并在必要时更新其结果。

编辑：澄清

于 2008-09-03T20:25:49.220 回答
0

我认为@Outlaw 有道理。DOM 树的结构存在于节点本身中，有一个指向其子节点的节点。要修改树的结构，您必须修改节点，因此您不能将其合并，您必须创建一个新节点。

尝试在更高的层次上思考。您有一个 IMMUTABLE 树（基本上是一组指向其子节点的节点）。您想在其中插入一个节点。然后，没有出路：您必须创建一个新的整个树。

是的，不可变树是线程安全的，但它会影响性能。对象创建可能很快，但不会比没有对象创建更快。:)

于 2008-09-03T20:42:44.450 回答