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

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

我的问题是，每次修改树时，预分配节点比创建新节点快得多吗？保留一个包含数百个未使用节点的池，然后从池中拉出一个而不是在进行修改操作所需的时间创建一个池，这将是相当容易的。当没有其他事情发生时，我可以补充节点池。 (以防万一，与堆空间相比，此应用程序的执行时间将是非常宝贵的)

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

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

*注：对于那些不了解不变性概念的人，这基本上意味着对更改它的对象执行任何操作时，该方法会返回该对象的副本，其中包含已更改的内容，而不是已更改的内容目的。因此，如果另一个线程仍在读取该对象，它将继续在"旧"版本上愉快地操作，而不知道已进行了更改，而不是可怕地崩溃。参见http://www.javapractices.com/topic/TopicAction.do?Id=29

解决方案

回答

我不想给出一个无答案的问题，但是我认为回答这样一个性能问题的唯一确定的方法可能是让我们对两种方法进行编码，对两种方法进行基准测试并比较结果。

回答

如今，对象创建非常快，对象池的概念已经过时了(至少一般而言；连接池当然仍然有效)。

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

回答

首先，我对我们要尝试执行的操作感到困惑。我们希望所有节点都是不可变的，并希望将它们合并？这两个想法不是互斥的吗？当我们从池中拉出一个对象时，我们是否不必调用setter来链接子级？

我认为使用不可变节点可能不会一开始就为我们提供所需的线程安全性。如果有一个线程在节点上进行迭代(搜索或者其他操作)，而另一个线程正在添加/删除节点，会发生什么情况？搜索结果不会无效吗？我不确定是否可以避免显式同步某些方法以确保所有内容都是线程安全的。

回答

@Outlaw程序员

When you pull an object out of the
  pool, won't you have to invoke a
  setter to link up the children?

每个节点不必在包内部保持不变，而只需在向外接口上保持不变。 node.addChild()将是一个具有公共可见性的不可变函数，并返回一个文档，而`node.addChildInternal()'将是一个具有包可见性的普通可变函数。但是由于它在包的内部，因此只能作为addChild()的后代来调用，并且可以保证整个结构是线程安全的(前提是我同步对对象池的访问)。我们看到这方面的缺陷了吗？如果是这样，请告诉我！

I think that using immutable nodes is probably not going to give you the kind of thread-safety you need in the first place. What happens if 1 thread is iterating over the nodes (a search or something), while another thread is adding/removing nodes?

整个树将是不可变的。假设我有Thread1和Thread2，以及树dom1. 线程1在dom1上启动读取操作，同时，线程2在dom1上启动写入操作。但是，Thread2所做的所有更改实际上将对一个新对象dom2进行，而dom1将是不可变的。确实，Thread1读取的值将过时(几微秒)，但不会因IndexOutOfBounds或者NullPointer异常而崩溃，也不会像读取正在写入的可变对象时那样崩溃。然后，Thread2可以将包含dom2的事件激发到Thread1，以便它可以再次读取并更新其结果(如有必要)。

编辑：澄清

回答

我认为@Outlaw有一点。 DOM树的结构位于节点本身中，节点指向其子节点。要修改树的结构，我们必须修改节点，这样就无法将其池化，我们必须创建一个新节点。

尝试更高层次的思考。我们有一棵IMMUTABLE树(基本上是指向其子节点的一组节点)。我们要在其中插入一个节点。然后，就没有出路了：我们必须创建一个新的WHOLE树。

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

回答

I'm not sure if you can avoid explicitly synchronizing certain methods in order to make sure everything is thread-safe.

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

Try to think in a higher level. You have an IMMUTABLE tree (that is basically a set of nodes pointing to its children). You want to insert a node in it. Then, there's no way out: you have to create a new WHOLE tree.

如果选择将树实现为指向子节点的一组节点，则必须沿着更改后的节点到根的路径创建新节点。其他具有与以前相同的值，并且通常是共享的。因此，我们需要创建一个局部的新树，这通常意味着(已编辑节点的深度)父节点。

如果我们可以应付不太直接的实现，则应该使用纯功能数据结构中描述的技术减少仅创建部分节点的工作量，以降低创建的平均成本，或者可以通过以下方式避免：使用半功能方法(例如，创建包装现有迭代器的迭代器，但返回新节点而不是旧节点，以及随时间推移修复结构中此类补丁的机制)传递给它。在这种情况下，XPath样式api可能比DOM api更好，因为它可能使节点与树的耦合程度更高，并更智能地处理变异的树。