A blog about in-depth analysis and understanding of programming, with a focus on C++.

Wednesday, November 15, 2006

Pointers to Intelligence

Memory management. That's what those Java and C# programmers hang over our heads day in and day out. You can't kill a system on garbage collection, but you can on memory leaks.

Ignoring the inaccuracy of the last statement, having completely manual memory management does cause its problems with regard to C++. Which is why we're going to show you the tools to achieve perfect, provable memory protection. We're taking memory management to the limit!

And the path to that limit begins, along with so many other good things in C++, not in the C++ Standard Library (or, not yet), but in the Boost libraries. As far as I'm concerned, if you don't have Boost on your harddrive, you're not a C++ programmer. It is the rest of the C++ Standard Library; it's that vital.

For the purposes of memory management, Boost gives us 2 classes of vital importance. In the Boost::smart_ptr library, I present to you boost::shared_ptr and boost::weak_ptr.

Boost's shared_ptr class is a fairly simple construct. It's a templated class that takes a pointer to an object in its constructor. It has overloaded the pointer dereference operators (* and ->), so that you can use the shared_ptr as though it were a real pointer to that type. And when the shared_ptr object goes out of scope, the shared_ptr class thoughtfully deletes the object that was passed into its constructor.

Fairly dry, right? Well, I did miss one feature. You can freely copy this shared_ptr wherever you wish (it has a copy constructor). And, so long as any one remains in existence, so too will the object it points to.

Just think about that for a second. This sounds suspiciously like garbage collection, yes? Of course it does; that's what it is. It functions exactly like a reference counted garbage collector. With one exception: it always happens immediately when the last reference is removed. And personally, I consider that a feature.

So, what's the catch? Well, there's two issues, one of them shared with all reference counted deallocators: circular references.

If object A has a shared pointer to B, and object B has a shared pointer to A, and nobody else has any shared pointers to either, neither one will ever be destroyed (or probably called).

We'll come back to that in a second, because there's a second issue, one that will bite you sooner or later (probably sooner).

Go back to that paragraph where I described what a shared_ptr does. What do you suppose this code would do:
SomeObjectType *pSomeObj = new SomeObjectType();
boost::shared_ptr<SomeObjectType> sp1(pSomeObj);
boost::shared_ptr<SomeObjectType> sp2(pSomeObj);

Well, this is going to be bad. See, both of these shared_ptr objects think that they own that object, and at some point, both of them will try to delete it. One of them is going to succeed, and the other is going to cause the program to explode, behave erratically, or other such things.

Basically, you can only ever use the pointer constructor for a shared_ptr once. After that, you can only ever copy shared_ptr's from one place to another. You can create new instances, but only from old instances. For any one object, there can only ever be one evocation of the shared_ptr constructor.

On the surface, this doesn't sound so bad. But it can cause real problems, especially if you're not aware of it.

The biggest problem comes from wanting a shared_ptr when you're in the class's constructor. Maybe you want this class to register itself with some external (global) object somewhere, so that others may query it by name. Or other such things. In order to do that, you need to give it a shared_ptr.

However, most users use shared_ptr's like this:
shared_ptr<SomeObjType> pThePtr = new SomeObjType;

If SomeObjType's constructor created a shared_ptr from 'this', we'd be in trouble. Which means that the only way to deal with this is through a paradigm like this:
new SomeObjType(name); //trusting it to register itself.
shared_ptr<SomeObjType> pThePtr = GlobalRegistrar.GetObject(name);

This is fool-proof... except that you have to remember to do it. And you lose a bit of performance, in that the registrar object has to do a name search (a quick check for the last-added eliminates this performance loss, of course). If you forget to do this, strange bugs can happen; the best you can hope for is that the program will crash. Worst-case, it keeps running, but becomes unstable.

The following is also a trap:
SomeObjectType *pTheObj = otherObject.GetSomeObject();
shared_ptr<SomeObjectType> pThePtr = pTheObj;

This is an error, as that pointer may have previously been wrapped in a shared_ptr. Therefore, the error isn't in the second statement, but in the first.

The moment you wrap a pointer in a shared_ptr, you have entered into a binding contract, on penalty of incredibly difficult-to-find bugs, that states that you will never pass a bare pointer to this object to anything. Ever. I don't care how tired you get of writing, "shared_ptr<SomeObjectType>"; wrap it in a typedef if you have to (SomeObjectTypePtr, for example). You must never do that.

Shared pointers are viral, and like any good virus, it must infect everything or nothing. As Yoda said, "Try not. Do. Or Do Not; there is no Try." Which is why the best time to wrap an object in a shared_ptr is immediately upon creation.

The other problem with shared_ptr's is that of circular references. This one can actually be solved. The key to solving it lies both in Boost and in your own attitude.

The reason this problem comes up is usually for one reason: you've forgotten what it means to have a shared_ptr. If an object stores a shared_ptr to some other object, you are making a strong statement about the relationship between these objects (shared_ptr's are often called "strong pointers" for this reason). You are saying, "Object A cannot function in any way, shape, or form without Object B. Object B is an intrinsic part of A, and A would be absolutely, totally meaningless without B."

When phrased that way, you start to realize that you may be overusing shared_ptr's. For example, if you're writing a game AI, it has a reference to a target. Would it be so bad if that target entity just happen to vanish off the face of the code at some point? Probably not; the AI doesn't need a target in order to function (presumably). If it was about to fire and the target's gone (say, killed by something else), then the AI simply needs to be aware of it and move on to something else.

Boost, like many garbage-collected systems, has a way to express this concept. We represent this with a "weak pointer": boost::weak_ptr. A weak_ptr lives as a conceptual wrapper to shared_ptr. While shared_ptr implements the dereference operator, you need to call a function on a weak_ptr in order to get a shared_ptr. This is for a very good reason, because, unlike shared_ptr's, weak_ptr's may return nothing.

See, a weak_ptr refers to the shared pointer (or copies thereof) that it was given at construction time. But it does not store a copy of that shared_ptr; it simply knows (via some mechanism best left in the Boost library) that the shared_ptr exists and how to generate one. However, if you have the following:
weak_ptr<SomeObjectType> aWeakPtr;
shared_ptr<SomeObjectType> pThePtr = new SomeObjectType;
aWeakPtr = weak_ptr<SomeObjectType>(pThePtr);
shared_ptr<SomeObjectType> pNewPtr = aWeakPtr.lock();

This code will crash, guaranteed. The weak_ptr::lock() function retrieves a shared_ptr to the object held by the weak_ptr. However, if all non-weak references to that object have disappeared since the weak_ptr was created, the weak_ptr::lock() function returns an empty shared_ptr. And, of course, dereferencing an empty shared_ptr returns NULL, which means that the function call will give rise to an error.

This is good. This is exactly what we want, as it allows us to reserve shared_ptr use for when we really mean it, and just pass around weak_ptr's for when we don't. This should cover 99% of all circular reference cases.

For the rest... restructure your code. Most code is pretty easy to structure in a tree-like fashion. Each level represents a lower-level of code. In general, siblings in this tree should use weak_ptrs with one another, while parents should have strong_ptrs (or inheritance, where appropriate) to their children. And children should not need to know about their parents at all; that's what makes them children in a code sense.

FYI: the Boost::smart_ptr library is not thread safe. And there's about a thousand ways for multithreading to screw this whole reference-counting thing all up. So, I would strongly suggest you keep your shared_ptr's in different threads or avoid threading entirely if you use this library. Alternatively, you can hack the library to use a semaphore of some sort.

No comments: