shared_ptr implementation

Question

I've written a linked-list version of something like shared_ptr, which gets destroyed when the last copy of a pointer is destroyed.

Aside from the thread-unsafety, is it a fine implementation? Anything I could improve?

Also, what's the best way to extend it to make it work with HANDLEs, etc., without repeating (or limiting) myself unnecessarily, while avoiding excess verbosity (e.g. auto_<HANDLE, custom_deallocator<HANDLE> > is considered too verbose)?

template<typename T>
class auto_
{
 T *pValue;
 mutable const auto_<T> *pPrev, *pNext;
public:
 auto_() : pValue(new T()), pPrev(NULL), pNext(NULL) { }
 auto_(T *pValue) : pValue(pValue), pPrev(NULL), pNext(NULL) { }
 auto_(const T &v) : pValue(new T(v)), pPrev(NULL), pNext(NULL) { }
 auto_(const auto_<T> &o) : pValue(o.pValue), pPrev(&o), pNext(NULL) { o.pNext = this; }
 virtual ~auto_()
 {
 const auto_<T> *const pPrev = this->pPrev, *const pNext = this->pNext;
 if (pPrev != NULL) { pPrev->pNext = pNext; }
 if (pNext != NULL) { pNext->pPrev = pPrev; }
 if (pPrev == NULL && pNext == NULL) { delete this->pValue; }
 this->pPrev = this->pNext = NULL;
 this->pValue = NULL;
 }
 auto_<T>& operator=(const auto_<T>& other)
 {
 if (this != &other)
 {
 this->~auto_();
 this->pValue = other.pValue;
 this->pPrev = &other;
 this->pNext = other.pNext;
 if (other.pNext != NULL) { other.pNext->pPrev = this; }
 other.pNext = this;
 }
 return *this;
 }
 operator T&() /*also const version*/ { return *this->pValue; }
 operator T*() /*also const version*/ { return this->pValue; }
 T* operator->() /*also const version*/ { return this->pValue; }
 T& operator *() /*also const version*/ { return *this->pValue; }
};

Sample usage:

template<typename T>
T recurse(T value, int depth)
{
 if (depth > 0) { T result = recurse(value, depth - 1); return result; }
 else { return value; }
}
auto_<int> test()
{
 printf("Value: %d\n", *recurse(auto_<int>(10), 3));
 auto_<int> p1 = recurse<auto_<int> >(5, 3);
 printf("Value: %d\n", *p1);
 auto_<int> p2 = 3;
 p1 = p2;
 p2 = p1;
 return p2;
}

• ronag: Why a linked list? Instead of a reference counter which would be more effective and simpler?
• user541686: @ronag: Because this is purely stack-based. Using a reference counter would require heap allocation.
• ronag: I'm not convinced that a "purely stack based" implementation is better. Firstly because if it was better then shared_ptr would probably have used it. Secondly, a reference counter would require a single heap allocation, whereas your stack-based solution requires several extra assignments and checks for every copy.
• ronag: If you want to use this class I would strongly suggest that you write unit tests for this class, as it might be easier to verify its correctness.
• Omnifarious: @Mehrdad: shared_ptr has one big advantage over your class. It is thread safe, which means that more than one thread can share the object being pointed to. Yours cannot do that. Being able to do that incurs significant overhead when fiddling with the reference count.

Answer 1

Implementing your own smart pointer is very hard please don't try.

If it is just to try and learn then fine you may learn something but after practicing go back to one that has been tested and is know to work.

20 seconds into looking Bug 1:

int main()
{
 auto_<int> x;
 auto_<int> y(x);
 auto_<int> z(x);
}

Problem caused by this line:

auto_(const auto_<T> &o)
 : pValue(o.pValue)
 , pPrev(&o)
 , pNext(NULL)
{
 o.pNext = this; // Here you are overwriting x.pNext when building z
} // It may or may not cause a bug but it was definitely
 // not what you intended to do.

You now have

pNext List
[X] -> [Z] -> | Y/Z point at nothing
 [Y] -> | X points at Z
pPrev List
[Y] -> [X] -> | Y/Z point at X
[Z] ----^ X points at nothing.
 One assumes you are trying to create a circular list!

Don't use hungarian notation

pValue

Do you really want to bind your object to always using pointers?
Just use logical names for the members try not to encode type information into the name of the member it already has that information in its type.

Style Tip

Don;t do this:

 const auto_<T> *const pPrev = this->pPrev, *const pNext = this->pNext;

It really hard to read. You are doing complex enough stuff try and make it easy to read

 auto_<T> const* const pPrev = this->pPrev
 auto_<T> const* const pNext = this->pNext;

Don't do pointless work

 this->pPrev = this->pNext = NULL;
 this->pValue = NULL;

This does nothing. This object is going to be destroyed. Therefore these variables do not exist after the destructor exists. So little point in playing with their values just before destruction.

Don't manually call the destructor

 this->~auto_();

Nobody expects people to do this. Its just confusing. Move the code in the destructor into another method and call that.

Broken link

If sombody inserts a NULL pointer into your smart pointer you are asking for trouble when they de-reference it.

auto_<int> x(NULL); // valid constructor

This is going to blow up

operator T&() /*also const version*/ { return *this->pValue; }

You either need to check the ptr on construction (to make sure it is never NULL) or if you allow NULL pointers then you need to check when the object is used.

Specialization

To avoid repeating yourself allow your code to be specialized by a second template parameter that understands how to reclaim the resources of different types. The default version just calls delete but this allows you to use specialize it for handles etc.

Circular lists are easier with no NULL pointers.

template<typename T>
struct Deleter
{
 void operator()(T* ptr) const { delete ptr;}
};
template<typename T, typename D = Deleter<T> >
class my_auto
{
 T *value;
 mutable const my_auto<T>* prev;
 mutable const my_auto<T>* next;
 public:
 // set up the chain to be circular pointing at just itself.
 // This way next/prev will never be NULL and we don't need to test
 my_auto() : value(new T()), prev(this), next(this) { }
 my_auto(T *value) : value(value), prev(this), next(this) { if (value == 0) throw int(1);}
 my_auto(const T &v) : value(new T(v)), prev(this), next(this) { }
 // insertInto() will do that appropriate set up.
 // We are currently not in a chain and have no value to release.
 my_auto(const my_auto<T> &o)
 {
 insertInto(o);
 }
 my_auto<T>& operator=(const my_auto<T>& other)
 {
 // Check for assignment to self
 if (this != &other)
 {
 testAndDestroy();
 removeFromChain();
 insertInto(other);
 }
 return *this;
 }
 ~my_auto()
 {
 testAndDestroy();
 removeFromChain();
 }
 private:
 // If next == this then this is the only node in the chain
 // So we destroy the data portion.
 void testAndDestroy()
 {
 if (next == this)
 {
 D deleter;
 deleter(value);
 }
 }
 // Unlink this node from the chain.
 // If we are the only link in the chain it still works
 // we just remain linked to ourselves.
 void removeFromChain()
 {
 // Remove this node from the chain
 prev->next = next;
 next->prev = prev;
 }
 // Insert into another chain.
 // Assumes that we are not part of another chain
 // and that our data has already been released as required.
 void insertInto(const my_auto<T>& other)
 {
 value = other.value;
 next = other.next;
 other.next.prev = this;
 prev = other;
 other.next = this;
 }
};

If you want to use a non circular list (then you need to fix the constructor)

auto_(const auto_<T> &o)
 : pValue(o.pValue)
 , pPrev(&o)
 , pNext(o.pNext) // Fix this line
{
 if (o.pNext) { o.pNext.prev = this;} // Add this line
 o.pNext = this;
}
// Your code assumes the node is always added to the end of the list
// You can not guarantee this. So you need to take account of being
// inserted into the middle.

• ronag: I second "Implementing your own smart pointer is very hard please don't try.".
• user541686: Ah, I think you're right about pNext(NULL) -- I think it should have said pNext(other.pNext) instead; thanks for catching that! Regarding Hungarian notation: I don't normally use it, but I make an exception for pointers... I feel like it makes more sense, since pValue has to be a pointer (since my auto_ is wrapping pointers).
• user541686: @ronag: I feel that's a depressing answer. "You can't write good code, so don't try."
• Loki Astari: @Mehrdad: Even with that fix your code is wrong. You never update enough pointer to maintain the list correctly.
• Jagannath: @Tux-D Why is the destructor virtual ? Well it helps if someone wants to inherit my_auto, then it is useful. For me, removing the virtual will make people stop inheriting this class w/o any necessity.

Answer 2

You post a link to benchmark results, which are very interesting. They show your pointer class to be significantly faster than the boost shared_ptr class.

There are a few critiques here. Your benchmarking technique is a bit crude, and it's very heavily oriented towards making copies of the pointer. While most pointers are copied a bit more than they're created, the ratio is more like 5 to 1, not 16 million to 1.

But, of course, that makes your benchmark all the more interesting since shared_ptrs big weakness as compared to yours is the requirement of allocating memory when the pointer is first created. Of course, using make_shared gets rid of this overhead and, as a bonus, increases locality of reference since the reference count and data pointed at are close to each other in memory.

I ran this benchmark on a Linux Opteron based system with Boost 1.47 and got nearly identical results to yours.

Then I transformed your program slightly. C++11 has a shared_ptr as part of the standard library. I changed your program to use this instead and compiled for C++11.

After this, the performance of your class was only slightly better than the standard library class. 960ms vs. 800ms.

I then recompiled with the -pthread option and the performance of the standard library shared_ptr dropped drastically. 1660ms vs 820ms.

This confirms my theory that Boost's poor performance is very likely due to thread safety. Changing a reference count in a thread-safe way is much slower because the CPU is force to use atomic memory operations.

Anyway, the difference between your class and the standard library class is so small in a non-threaded context that I wouldn't feel it was worth it to use your special class vs. one that was part of the standard library.

If you want to re-create the benchmark I ran, change these lines in your benchmark:

#include <boost/shared_ptr.hpp>
#include <boost/make_shared.hpp>
using namespace boost;

to

#include <memory>
using ::std::shared_ptr;
using ::std::make_shared;

And compile with a compiler that supports C++11. g++ can be made to support C++11 by passing the -std=gnu++0x or -std=c++0x options. By default the GNU compiler will compile in single-threaded mode. In order to get it to compile programs that will run properly with multiple threads, the -pthread option needs to be passed to both the compiler and linker.

• user541686: Oh lol, so it really wasn't different. xD I just tried it on MSVC 2010 (it only comes with a multithreaded library -- but that's what I'm using for my projects) and got 610 ms vs 1595 ms. So I guess it's a factor of ~3 difference for MSVC projects?
• Omnifarious: @Mehrdad: nod Apparently so. Do you realize why the multi-threaded implementation is so much slower?
• user541686: lol, of course; I knew it before I posted this.