函数/不可变数据结构对于非垃圾收集上下文中的并发仍然有用吗？
不可变数据结构的卖点之一是它们可以自动并行化。如果没有发生突变，那么对功能数据结构的引用可以在线程之间传递，而无需任何锁定。
我开始思考如何在 C++ 中实现函数式数据结构。假设我们的数据结构的每个节点都有一个引用计数。 （功能数据结构在数据结构的旧成员和更新成员之间共享结构，因此节点不会唯一地属于一个特定的数据结构。）
问题是，如果在不同的线程中更新引用计数，那么我们的数据结构不再是线程安全。将互斥体附加到每个单个节点既昂贵又违背了使用不可变数据结构实现并发的目的。
有没有办法使并发不可变数据结构在 C++（和其他非垃圾收集环境）中工作？
One of the selling points of immutable data structures is that they are automatically parallelizable. If no mutation is going on, then references to a functional data structure can be passed around between threads without any locking.
I got to thinking about how functional data structures would be implemented in c++. Suppose that we have a reference count on each node of our data structure. (Functional data structures share structure between old and updated members of a data structure, so nodes would not belong uniquely to one particular data structure.)
The problem is that if reference counts are being updated in different threads, then our data structure is no longer thread safe. And attaching a mutex to every single node is both expensive and defeats the purpose of using immutable data structures for concurrency.
Is there a way to make concurrent immutable data structures work in c++ (and other non-garbage collected environments)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
有无锁引用计数算法，请参见，例如 无锁引用计数，原子引用计数指针。
另请注意，C++0x（可能很快就会成为 C++11）包含原子整数类型，特别是对于像这样的用途。
There are lock-free reference counting algorithms, see, e.g. Lock-Free Reference Counting, Atomic Reference Counting Pointers.
Also note that C++0x (which will probably become C++11 soon) contains atomic integer types especially for purposes like this one.
好吧，垃圾收集语言也存在多线程环境的问题（对于可变结构来说这并不容易）。
您忘记了，与任意数据不同，计数器可以原子地递增和递减，因此不需要互斥体。这仍然意味着需要维持处理器之间的缓存同步，如果单个节点不断更新，这可能会造成严重的成本。
Well, garbage collected languages also have the issue of multi-threaded environments (and it is not easy for mutable structures).
You have forgotten that unlike arbitrary data, counters can be incremented and decremented atomically, so a mutex would be unnecessary. It still means that cache synchro between processors need be maintained, which may cost badly if a single node keeps being updated.