为什么std :: shared_ptr不使用引用链接？ [英] Why doesn't std::shared_ptr use reference linking?
问题描述
std :: shared_ptr 需要在保存引用计数的堆上分配控制块。还有另一种方法，我从 http://ootips.org/yonat/4dev/smart- pointers.html ，它将所有引用保存在双向链表中。它不需要额外的分配或计数器，但引用对象本身更大。
有一个基准或任何明确的原因显示一个实现比其他更好吗？
标准在理论上允许使用链表，但是因为复制 shared_ptr 必须是线程安全的，它将更难实现与链表。该列表需要由互斥锁保护（或者是一个无锁的列表，这是更困难的），这样每次 shared_ptr 被复制或超出范围可以通过多个线程安全地修改。
使用原子类型和引用计数更新使用原子操作更简单，更有效率。 p>
编辑：要回答下面的注释，只是使用原子指针来实现链表是不够的。要从列表中添加或删除一个节点（对应于增加和减少 use_count ），您需要原子地更新两个指针，以调整节点中的链接之后添加/删除。 std :: atomic< T *> 允许您以原子方式更新单个指针，但是如果您需要以原子方式更新两个这样的对象，则没有帮助。因为这两个指针存在于不同的节点中，所以它们不是相邻的，所以即使一个四字CAS也不会帮助。
替代方法是保护整个列表的互斥争用）或每个列表节点的互斥锁，其中锁定任何更新中涉及的每个节点的互斥，这使用更多的内存并且一次影响多达三个节点，即需要锁定三个互斥体。如果您有 use_count（）小于或等于五，则复制/销毁任何一个 shared_ptr 任何共享同一指针的所有权的其他实例。您可能会获得较少的争用与高使用计数，其中大多数更新是到彼此远离的非相邻节点，但可能不是在一般情况下。许多程序使用 shared_ptr 和单位数字的使用计数。即使使用计数很高，并且在任何节点上没有争用，您仍然必须锁定三个互斥体并创建/销毁列表节点（可能需要堆分配），并更新其相邻节点中的指针，因此原子递增/递减
上一次我在委员会提到反映 shared_ptr 不需要使用引用计数，并可以使用列表我得到的答复：
没有人真的这样做，考虑到该标准现在可以识别多线程？
和（参考线程安全要求）：
对于一个引用链接的实现来说，这是非常困难的。我甚至不确定它是可能的，虽然它可能是。
std::shared_ptr needs to allocate a control block on the heap which holds the reference count. There was another approach I learnt from http://ootips.org/yonat/4dev/smart-pointers.html which keeps all the references in a doubly linked list. It doesn't need additional allocations nor a counter but the reference object itself is larger.
Is there a benchmark or any clear reason showing one implementation is better than the others?
The standard does in theory allow a linked list to be used, but because copying a shared_ptr must be threadsafe it would be harder to implement that with a linked list. The list would need to be protected by a mutex (or be a lockfree list, which is much harder) so that every time a shared_ptr is copied or goes out of scope the list can be safely modified by multiple threads.
It's much simpler and in general more efficient to do reference counting using atomic types and use atomic operations for the ref count updates.
Edit: To answer the comment below, just using atomic pointers to implement the linked list wouldn't be enough. To add or remove a node from the list (which correspond to increasing and decreasing the use_count) you would need to update two pointers atomically, to adjust the links in the nodes before and after the one being added/removed. std::atomic<T*> allows you to update a single pointer atomically, but doesn't help if you need to update two such objects atomically. Since those two pointers live in separate nodes they're not adjacent so even a quadword CAS won't help.
Alternatives are a mutex protecting the whole list (obviously bad for contention) or a mutex per list node where you lock the mutex of each node involved in any update, which uses more memory and affects up to three nodes at a time, i.e. requires locking three mutexes. If you have use_count() less than or equal to five then copying/destroying any one shared_ptr contends with copying/destroying any of the other instances that shares ownership of the same pointer. You might get less contention with high use counts where most updates are to non-neighbour nodes distant from each other, but probably not in the general case. Plenty of programs use shared_ptr with use counts in single digits. Even when use counts are high and there's no contention on any nodes, you still have to lock three mutexes and create/destroy a list node (possibly requiring a heap allocation) and update the pointers in its neighbouring nodes, so an atomic increment/decrement is much simpler and could still be faster despite the contention on the atomic integers.
Last time I mentioned on the committee reflector that shared_ptr isn't required to use ref counts and could use a list I got the replies:
Does anyone actually do that, given that the Standard recognizes multithreading now?
and (in reference to the thread-safety requirements):
It's much harder to make that work (efficiently) for a reference-linked implementation. I'm not even sure that it's possible, though it may be.
这篇关于为什么std :: shared_ptr不使用引用链接？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
