CODEWITHSUNDEEP
shared-ptrc++11reference-counting
towi
towi

Reputation: 22337

shared_ptr<> is not required to use reference count?

Do I understand the new Std right that shared_ptr is not required to use a reference count? Only that it is likely that it is implemented this way?

I could imagine an implementation that uses a hidden linked-list somehow. In N3291 "20.7.2.2.5.(8) shared_ptr observers [util.smartptr.shared.obs]" The note says

[ Note: use_count() is not necessarily efficient. — end note ]

which gave me that idea.

Upvotes: 3

Views: 503

Answers (2)

curiousguy
curiousguy

Reputation: 8318

Abstract description

Some people say that shared_ptr is a "reference counter smart pointer". I don't think it is the right way to look at it.

Actually shared_ptr is all about (non-exclusive) ownership: all the shared_ptr that are copies of a shared_ptr initialised with a pointer p are owners.

shared_ptr keeps track of the set of owners, to guaranty that:

  • while the set of owners is non-empty, delete p is not called
  • when the set of owners becomes empty, delete p (or a copy of D the destruction functor) is called immediately;

Of course, to determine when the set of owners becomes empty, shared_ptr only needs a counter. The abstract description is just slightly easier to think about.

Possible implementations techniques

To keep track of the number of owners, a counter is not only the most obvious approach, it's also relatively obvious how to make thread-safe using atomic compare-and-modify.

To keep track all the owners, a linked list of owner is not only the obvious solution, but also an easy way to avoid the need to allocate any memory for each set of owners. The problem is that it isn't easy to make such approach efficiently thread safe (anything can be made thread safe with a global lock, which is against the very idea of parallelism).

In the case of multi-thread implementation

On the one hand, we have a small, fix-size (unless the custom destruction function is used) memory allocation, that's very easy to optimise, and simple integer atomic operations.

On the other hand, there is costly and complicated linked-list handling; and if a per owners set mutex is needed (as I think it is), the cost of memory allocation is back, at which point we can just replace the mutex with the counter!

About multiple possible implementations

How many times I have read that many implementations are possible for a "standard" class?

Who has never heard this fantasy that the complex class that could be implemented as polar coordinates? This is idiotic, as we all know. complex must use Cartesian coordinates. In case polar coordinates are preferred, another class must be created. There is no way a polar complex class is going to be used as a drop-in replacement for the usual complex class.

Same for a (non-standard) string class: there is no reason for a string class to be internally NUL terminated and not store the length as an integer, just for the fun and inefficiency of repeatedly calling strlen.

We now know that designing std::string to tolerate COW was a bad idea that is the reason for the unusual invalidation semantics of const iterators.

std::vector is now guaranteed to be continuous.

The end of the fantasy

At some point, the fantasy where standard classes have many significantly different reasonable implementations has to be dropped. Standard classes are primitive building blocks; not only they should be very efficient, they should have predictable efficiency.

A programmer should be able to make portable assumptions about the relative speed of basic operations. A complex class is useless for serious number crunching if even the simplest addition turns into a bunch a transcendental computations. If a string class is not guaranteed to have very fast copy via data sharing, the programmer will have to minimize string copies.

An implementer is free to choose a different implementation techniques only when it doesn't make a common cheap operation extremely costly (by comparison).

For many classes, this means that there is exactly one viable implementation strategy, with sometimes a few degrees of liberty (like the size of a block in a std::deque).

Upvotes: 5

一二三
一二三

Reputation: 21289

You're right, nothing in the spec requires the use of an explicit "counter", and other possibilities exist.

For example, a linked-list implementation was suggested for the implementation of boost's shared_ptr; however, the proposal was ultimately rejected because it introduced costs in other areas (size, copy operations, and thread safety).

Upvotes: 5

Related Questions