.NET 4.0 and ConcurrentStack

In .NET 4.0 we have several new collection types that have been introduced inside of the System.Collections.Concurrent namespace. The one that we are here to talk about today is the ConcurrentStack. The ConcurrentStack is a lock-free thread-safe implementation of the standard stack data structure. (As a side note, when I say “lock-free”, I mean that they don’t leverage traditional locks using the “lock” keyword or using Monitors. They do however use the System.Threading.Interlocked class to perform compare and swap operations.)

A stack is a data structure that performs operations in LIFO (Last In First Out) order, and it has two main operations, push and pop. Push puts a new item on the top of the stack, and Pop takes the item on the top of the stack and removes it.

You can think about it like a stack of plates:

The last item put on the stack, is the first item that is popped off the stack. As we said, Last In First Out. In the ConcurrentStack implementation we have two main methods that we will use when interacting with it. First is the “Push” method and second is the “TryPop” method.

The Push method merely puts a new item on the top of the stack, and it is the most simple to use:

var cs = new ConcurrentStack<string>();
cs.Push("test");

This will place the string “test” at the top of the stack. If we wanted to pop this item off of the stack, then we can call TryPop like this:

string value;
if (cs.TryPop(out value))
{
    Console.WriteLine(value);
}

As you can see, we have to check the result of “TryPop” to see if it returned true or false. The reason is that we don’t know if there will be anything on the stack for us to pop or not. Even if we just pushed an item on the stack, or we just checked the count of items, in a multi-threaded implementation we can never be sure that some other thread won’t perform some operation at the same time and take the last item.

There are also times where we might want to look at the top item on the stack, but not remove it from the stack. Usually when working with stack data structures we call this operation a “peek”. Because peek has the same issues in a multi-threaded implementation that a “pop” does, the method on the ConcurrentStack is called “TryPeek” and operates in the exact same manner:

string value;
if (cs.TryPeek(out value))
{
    Console.WriteLine(value);
}

Another thing that we might want to consider is that we might want to be able to push a series of items onto the stack in a particular order. If we were to push them on one by one then we can’t be guaranteed that some other thread won’t push items in the middle of the operation. Because of this, the ConcurrentStack implements the PushRange method. This method allows us to push an array of items onto the stack in one operation:

cs.PushRange(new[] { "test1", "test2", "test3" });

We might also want to be able to atomically pop off more than one item from the stack. In order to allow for this operation, we have the TryPopRange method. The TryPopRange method takes an array that will be filled from the stack and returns an integer of the number of items that it was actually able to remove. The number of items that it will try to pop off the stack is determined by the size of the array:

var cs = new ConcurrentStack<string>();
cs.PushRange(new [] {"item1", "item2", "item3", "item4", "item5"});

string[] values = new string[4];
int num = cs.TryPopRange(values);
if (num > 0)
{
    for (int i = 0; i < num; i++)
    {
        Console.WriteLine(values[i]);
    }
}

In the example above, only the last 4 items that were pushed onto the stack would be popped off. If you didn’t want to fill the entire array though, but instead wanted to only fill a part of an array, then an overload is available to us that takes a start index and a count of items to pop off the stack:

var cs = new ConcurrentStack<string>();
cs.PushRange(new [] {"item1", "item2", "item3", "item4", "item5"});

string[] values = new string[4];
int num = cs.TryPopRange(values, 2, 2);
if (num > 0)
{
    for (int i = 2; i < num + 2; i++)
    {
        Console.WriteLine(values[i]);
    }
}

In this case, we would only pop two items off the stack and fill the last two items in the array.

There are other properties and operations that are available to us like Count, IsEmpty, and Clear(); but I feel like those are self explanatory enough that we don’t really need to cover them. It is important to note though, that since these are thread safe implementations of stack, doing things like checking the Count or IsEmpty properties on a stack like this:

if (!cs.IsEmpty)
{
    string value;
    cs.TryPop(out value);
    Console.WriteLine(value);
}

Does not guarantee that you are going to find items inside of the stack, since at any point another thread could be removing items from the list. In this way, you can’t just try to directly translate code which was originally using the Stack<T> class and expect it to work properly with the ConcurrentStack<T> class.

One last thing to note is that the ConcurrentStack class does support IEnumerable, which means that you can iterate over it using a foreach loop or any other method of iterating over an IEnumerable. It also means that you can run LINQ queries against items in the stack. Getting an enumerator from a ConcurrentStack is a moment-in-time snapshot of the ConcurrentStack and therefore won’t reflect any changes made after GetEnumerator was called. This is accomplished by capturing the current head of the stack, and so when enumeration starts occurring over the stack you will always get the state of the stack at the point where GetEnumerator was called.

Summary

The ConcurrentStack is an excellent new tool in our parallel programming toolset which allows us to get the LIFO behavior we want, all without having to worry about locking. I hope you enjoyed this little tutorial on the ConcurrentStack class, and I hope that you’ll join us next time when we take a look at the ConcurrentQueue.