Creating a Weak List

• Download sample - 142.03 KB

Introduction

This article explains how to create a weak list (a list that allows items to be collected by the GC).

I already wrote an article about WeakArrays, but the problem of weak arrays is that they have fixed length. Now, I will explain how to create a weak list.

First, how can we create a weak list?

Solution 1: In our class, we create a list of WeakReferences, but we implement all methods to get and set values of the data type, so the weak references are not seen. This one has the problem that each WeakReference has a destructor.

Solution 2: In our class, we create a list of GCHandles. We also implement all methods to get and set values of the data type, so the GCHandles are not seen. We must then implement the finalizer to free all GCHandles at once.

Solution 3: In our class, we create an Array of GCHandles, and control when such array must be resized, in a process similar to the original list. We must also implement the finalizer.

I must say that all of the solutions work but the first one is the slowest and the last one is the one that allows better control of everything. But, I will try to explain only the last one, which is the approach I use.

So, the things needed to write a weak list are:

• How a normal list works
• How to make the "weak" part work
• And how to make it thread-safe. Even if the list is theoretically only used by one Thread, the GC always runs as another thread at unexpected times.

The Normal List

The normal list, in practice, is very simple. It contains an array (in my case, I initialize it with length 32) and a Count. Every time an item is added, it tries to put the item into the actual count and then increase the count. Of course, if there are more items than count, then a new array is created, with double the size, and the item is put at the Count position and Count is incremented. Of course, there are a lot of methods, like IndexOf, Remove and others, but they find items sequentially and, if one item is removed, all items are copied to one position before, and then the Count is decremented. Simple, isn't it?

Now, how do we make it weak?

As I said earlier, I will use GCHandles. So, instead of having a Button[] (if we have an WeakList<button>) or a string[] (if we have a WeakList<string>), we will always have a GCHandle[]. Then, to get a value at a given index, we will have a code that follows this pattern:

public T this[int index]
{
  get
  {
    // validates if the index is not out of range.
    return (T)fHandles[index].Target;
  }
  set
  {
    // validates if the index is not out of range.

    // checks if the GCHandle is initialized.
    // if it is, set is Target.
    // if it is not, then Alloc a new Weak GCHandle and set it to that position.
  }
}

But, two important things:

First, this "pattern" is not yet thread-safe, and it must be. Second, the Count will be a fake value. It will only tell how many Items where added that we do not know to have been collected. So, a list with count 5 can, in fact, have 0 real items because all of them where collected.

And, finally, we must make it thread-safe.

The simplest way to make things thread-safe is to use Locks. And that's what I do. I don't use ReaderWriterLocks because they are slower than custom locks, and their benefit is only useful when the write operations are really slow, which is not the case. So, each method should lock the object (or better, some internal synchronization object), check if the object was not disposed, and then do its real work.

Ok... I said finally, but there are 2 more steps:

1. Implement IDispose. This is only needed to follow the guideline that, instead of counting on the GarbageCollector to finalize our object, if we know it will not be used anymore, we can free it immediately, and so the entire object will be collected in the next collection (if we run the finalizer, the object will only be collected one generation after that in which its finalizer was run).
2. Know when items were collected, so all the GCHandles that are now null can be removed.

To do this, we can constantly check the number of collection counts (at each insert method, for example), we can use a secondary thread with a timer, or we can discover when a collection was done to call an event. I already created a class (GCUtils) which has the Collected event. This is almost a hack, as I create an object without strong references (so it is always collected) and, in its finalize, I re-register it for finalize (so it does not die) and call set a ManualResetEvent object. So, as soon the GC terminates and all threads start to run again, my thread that is waiting on such ManualResetEvent calls the Collected event. Such event has the advantage that, if collections happen frequently, then the extra items will be removed frequently. And, if collections take long time to happen, then there will not be a process trying to remove them for nothing. But any method will work. So, the object must be locked, the number of non-collected items must be counted, then a new array must be created with, at least, the number of non-collected items and, finally, all valid handles must be copied and null handles must be freed. Note that between the count and the copy to the new array, more items can be collected, so the count must only be set after such copy is done.

And, that's finally it.

Now I will show the code for some key-methods:

// This is the constructor that allows you to set its initial capacity.
// The default constructor calls this with a value of 32.
public WeakList(int initialCapacity)
{
	if (initialCapacity < 1)
		throw new ArgumentOutOfRangeException
		("initialCapacity", "The initial accepted capacity value is 1.");

	fHandles = new GCHandle[initialCapacity];
	GCUtils.Collected += p_Collected;
}

// This will free all handles. It is already inside a lock 
// (if called manually) or runs single-threaded (if from finalizer).
protected override void Dispose(bool disposing)
{
	// if the dispose was called manually,
	// we must unregister ourselves from the GCUtils.Collected method.
	// we do not need to do this if this object is being collected,
	// as the Collected event is also we and, so,
	// it was already removed from there.
	if (disposing)
		GCUtils.Collected -= p_Collected;

	// here we will free all allocated handles.
	// After all, even if the objects can be collected,
	// the handles must be freed.
	var handles = fHandles;
	if (handles != null)
	{
		int count = handles.Length;
		for (int i=0; i<count; i++)
		{
			var handle = handles[i];
			if (handle.IsAllocated)
				handle.Free();
		}

		fHandles = null;
	}

	base.Dispose(disposing);
}

public void Add(T item)
{
	if (item == null)
		throw new ArgumentNullException("item");

	lock(DisposeLock) // the original code use AbortSafe.Lock,
	                  // but that is because I am paranoic about Thread.Abort.
	{
		CheckUndisposed();

		int count = Count;
		if (count == fHandles.Length)
			Array.Resize(ref fHandles, count * 2);

		try
		{
		}
		finally
		{
			// again, I am paranoic about Thread.Abort.
			// If one happens after the Alloc and before the
			// handle is set, then thanks to this finally
			// block the exception will only happen after
			// setting the handle in the array.
			fHandles[count] = GCHandle.Alloc(item, GCHandleType.Weak);
		}
		Count++;
	}
}

To see the full implementation, download the library and look at Caching\WeakList.cs.

The Future

Well, I don't know when I will publish the other articles, but I plan to explain how a WeakHashSet and a WeakDictionary work, as I think both are more useful than weak-lists.

History

• 26^th March, 2010: Initial version