Sunday, August 30, 2009

A Weak Smart Pointer, or a Smart Weak Pointer

Smart pointers simplify many lifetime management scenarios, especially when designing modular components and systems with a multitude of lifetime dependency options available to final applications. Weak pointers are also useful, but are flawed in a multithreaded environment.

The other day a hybrid smart/weak pointer occurred to me, I'll present it here.

A refresher:
  • A smart pointer is an object that acts like a native pointer, but whose lifetime controls a dynamically allocated object's lifetime. As long as you hold a smart pointer to an object, it continues to live. Multiple smart pointers can point to one dynamically allocated object, and it will not be deallocated until all smart pointers are released. Implementations typically maintain a reference count and delete the dynamic object when that ref count goes to zero.
  • A weak pointer is an object that acts like a native pointer, but whose value is changed to NULL if the object pointed to is deallocated. Holding onto this type of pointer does not keep an object alive, but you can check it's value and see that it is NULL when the object has been destroyed (a normal pointer would still point to the memory the object used to reside in).

Discussion:
Smart pointers are sometimes used for code safety, even when a system does not desire lifetime management responsibility. Weak pointers are a better solution here, allowing a system to keep a reference that will go NULL when the object dies.

In multithreaded systems weak pointers lose their benefit if the dynamic object can be freed from another thread. A portion of code may check the value of the weak pointer and find the object exists. However, as the object is accessed another thread may free it.

One work around is to use a short lived smart pointer, which will keep the dynamic object alive from the weak pointer dereference until work is complete. This requires a smart and weak pointer pair implementation designed to support this use case in a multithreaded system, and is also likely quite a performance burden due to the additional reference count manipulation.

For code that runs infrequently, the smart & weak pointer pair is a good option though. Without any smart or weak pointers the system would need to implement thread-safe API to register and deregister objects, and the systems would need to be tightly coupled (or perhaps use a message system).

My Idea:
A smart weak pointer to the rescue? It would be nice to have the same functionality of a smart pointer, knowing that as long as you hold it the object will live, but also indicate to the system that you're willing to let the object die. The only catch is that you need to let the object die at a convenient time for you, so that you can safely handle the situation, but not be required to safely handle it everywhere you use the object.

Start with a smart pointer implementation. Add an additional ref counter for the smart weak pointers, call it WeakRef. Any smart pointer pointing to an object acts as before. Any smart weak pointer acts the same as a smart pointer, but also increments WeakRef counter. Add a method to check the ref and WeakRef counters to see if they are equal, and if so set the smart weak pointer to NULL and decrement the two counters.

A system then could use the smart weak pointers just as if they were typical smart pointers, and occasionally check if the smart weak pointer should release it's reference.

System::OnTick()
{
for (lots of work to do)
{
Look up the right smart weak pointers to dereference, and use them as normal
}

for (all smart weak pointers)
{
CheckForRelease(p)
}
}
This works out well for a multithreaded system that accesses a large number of smart pointers frequently, and has a regular opportunity to release them.

If your system only infrequently dereferences pointers, is single threaded, or performance isn't an issue; the discussion's example of weak pointers with temporary smart pointers would be great for you.

9 comments:

  1. So it means that now next to the extra access time and next to the cache contention because of the ref counters, you have to register/deregister every weak pointer to/from a global array and then postprocess this array?
    Seriously, ever heard of managed languages? :)

    ReplyDelete
  2. So basically you're talking about implementing garbage collection?

    ReplyDelete
  3. kezesb: There is some additional access time, in the CheckForRelease, but most systems I'm considering this for already know all the objects they're working on, so no additional cost for that.

    I love C#, but it's not suitable for high performance systems that we build for the game engine.

    My proposal here is really an alternative to adding API to the systems and having one inform the other when objects are added and removed. That solution is OK, but I don't like the redundant code that has to be written over and over to manage it for every new system.

    Simon: It's much more explicit than general garbage collection, faster, and easy to make play well with everything else you're doing. I'm fine using GC in hobby games, low impact tools, etc... just not high performance code.

    ReplyDelete
  4. We actually had a ton of problems assuming our smart pointers were thread safe without creating a critical section around them, which could take up lots of time we couldn't afford. What would happen was this:

    Thread 2 begins an attempt to grab a smart pointer, it is locked by thread 1 releasing its reference.
    Thread 1 releases a reference to it's smart pointer, bringing the count to 0, which begins the deletion process of the object.
    Thread 2 increases the reference count on the object, trashing memory.

    This wasn't as rare as you might believe, and it was pointed out to me that, because the Decrement + delete are not an atomic operation, you can not assume smart pointers are thread safe. They're useful, but not thread safe. Thankfully, well architected code makes this occurance so rare as to be almost non-existant.

    That said, I think the CLR's method to do this works well. For unmanaged code, the CLR uses weak pointers at all times, and you have to "pin" objects that you do not want moving in memory. Pinning an object checks for null and increases the reference count in an atomic operation (which is also hard, but possible) and so long as you own that pin, the object can't be moved (or deleted) C++/CLI has scoped pinning as well using some templating magic, which is kind of awesome.

    ReplyDelete
  5. Basically you're adding a sync point and delaying deletions until that. That certainly works fine but there are more straightforward ways to do that. You can just have a normal smart pointer class and push items to a deletion queue instead of deleting immediately. It also requires you to figure out when it's safe to do a sync deletion.

    Also :

    "knowing that as long as you hold it the object will live, but also indicate to the system that you're willing to let the object die"

    this seems contradictory.

    You may as well just take a temp smart pointer to the object on the stack to hold its lifetime.

    ReplyDelete
  6. Jeff:
    Our smart pointer implementation is thread safe, which means that adding or decrementing references is a bit costly, but it's easy to avoid so doesn't impact system performance.

    You only need to do this when a system takes interest in an object. Per frame operations and most situations of passing references through the call stack can use just normal pointers or const references to smart pointers.

    ReplyDelete
  7. cbloom:
    You have the jist of it, and finding a safe sync point is easy. Each individual system knows when it can handle the loss of one of the resources it was interating with.

    Your deletion queue approach doesn't solve the situation I'm targeting well, were several systems that don't know about each other need safe access to resources and must coordinate on their release.

    Let me clarify "knowing that as long as you hold it the object will live, but also indicate to the system that you're willing to let the object die":

    Consider a system that needs to know about the existence of many objects, but does not own them or control their lifetime. The owning system runs on another thread, but since you only need read access to some object members, there's no thread safety required other than ensuring that the objects you're reading are still there. Your system would like simple code that keeps those objects alive until after it has completed a batch of processing. At that point, if everyone else has agreed to let the object die, you'll release your reference. Otherwise you'll keep that reference and thus keep the object alive until the next time it's safe for you to let it die.

    ReplyDelete
  8. 1 - I agree with Charles, you're just adding a garbage-list to your system.

    2 - Also you're forcing the system to have RC in a middle class instead of having a RC object that is the base of all your RC system.

    The latter is generally a better idea, and unfortunately precludes the use of safe weak pointers...

    3 - In most RC systems I've seen, even the generic smart pointer class is not threadsafe anyway :) It's not entirely trivial to fix that.

    I guess what you could also look into, if you want to have more powerful memory management, is to have a real GC system. Anyway most game engines do implement some sort of serialization/reflection. That means that somewere, you already know which memebers are references... You can use that to traverse the heap, and fix not only threading problems, but also nasty circular reference ones...

    ReplyDelete
  9. Vince, don't overlook the obvious. When you say "you need to let the object die at a convenient time for you" that, to me, is a strong indication that what you really want is traditional new/delete. After all, calling delete is the perfect way of ensuring the object dies when you want it to die!

    ReplyDelete