函数式/不可变数据结构对于非垃圾回收上下文中的并发仍然有用吗？

Question

不可变数据结构的卖点之一是它们可以自动并行化。如果没有发生变化，那么对函数式数据结构的引用可以在线程之间传递，而不需要任何锁定。

我开始思考如何在c++中实现函数式数据结构。假设我们在数据结构的每个节点上都有一个引用计数。(函数式数据结构在数据结构的旧成员和更新成员之间共享结构，因此节点不会唯一地属于一个特定的数据结构。)

问题是，如果引用计数在不同的线程中更新，那么我们的数据结构就不再是线程安全的。而且，将互斥锁附加到每个节点都是昂贵的，并且违背了使用不可变数据结构进行并发的目的。

有没有一种方法可以让并发不可变数据结构在c++ (和其他非垃圾回收环境)中工作？

Answer 1

有无锁引用计数算法，参见例如Lock-Free Reference Counting，Atomic Reference Counting Pointers。

还要注意，C++0x (可能很快就会变成C++11 )包含原子整数类型，特别是为了这样的目的。

Answer 2

那么，垃圾收集语言也有多线程环境的问题(对于可变结构来说并不容易)。

您已经忘记了，与任意数据不同，计数器可以自动递增和递减，因此互斥是不必要的。这仍然意味着需要维护处理器之间的缓存同步，如果单个节点不断更新，这可能会带来很大的成本。