Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The standard does in theory allow a linked list to be used, but because copying a <code>shared_ptr</code> 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 <code>shared_ptr</code> is copied or goes out of scope the list can be safely modified by multiple threads.</p> <p>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.</p> <p><strong>Edit:</strong> 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 <code>use_count</code>) you would need to update two pointers atomically, to adjust the links in the nodes before and after the one being added/removed. <code>std::atomic&lt;T*&gt;</code> 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.</p> <p>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 <code>use_count()</code> less than or equal to five then copying/destroying any one <code>shared_ptr</code> 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 <code>shared_ptr</code> 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.</p> <p>Last time I mentioned on the committee reflector that <code>shared_ptr</code> isn't required to use ref counts and could use a list I got the replies:</p> <blockquote> <p>Does anyone actually do that, given that the Standard recognizes multithreading now?</p> </blockquote> <p>and (in reference to the thread-safety requirements): </p> <blockquote> <p>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.</p> </blockquote>
    singulars
    1. This table or related slice is empty.
    1. POWhy doesn't std::shared_ptr use reference linking?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJonathan Wakely
    1. USJonathan Wakely
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POWhy doesn't std::shared_ptr use reference linking?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWhy are atomic pointers harder than atomic refcounts? I imagine the list could reduce contention for shared cachelines. (Just playing devil's advocate.)
      singulars
      1. PO
      1. USPotatoswatter
    2. COYou need to update _two_ pointers atomically to add or remove a list node.
      singulars
      1. PO
      1. USJonathan Wakely
    3. CO@Potatoswatter, more detail added to the answer
      singulars
      1. PO
      1. USJonathan Wakely
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload