Once again we consider some of the lesser known classes and keywords of C#. In the next few weeks, we will discuss the concurrent collections and how they have changed the face of concurrent programming.
This week’s post will begin with a general introduction and discuss the ConcurrentStack<T> and ConcurrentQueue<T>. Then in the following post we’ll discuss the ConcurrentDictionary<T> and ConcurrentBag<T>. Finally, we shall close on the third post with a discussion of the BlockingCollection<T>.
For more of the "Little Wonders" posts, see the index here.
A brief history of collections
In the beginning was the .NET 1.0 Framework. And out of this framework emerged the System.Collections namespace, and it was good. It contained all the basic things a growing programming language needs like the ArrayList and Hashtable collections. The main problem, of course, with these original collections is that they held items of type object which means you had to be disciplined enough to use them correctly or you could end up with runtime errors if you got an object of a type you weren't expecting.
Then came .NET 2.0 and generics and our world changed forever! With generics the C# language finally got an equivalent of the very powerful C++ templates. As such, the System.Collections.Generic was born and we got type-safe versions of all are favorite collections. The List<T> succeeded the ArrayList and the Dictionary<TKey,TValue> succeeded the Hashtable and so on. The new versions of the library were not only safer because they checked types at compile-time, in many cases they were more performant as well. So much so that it's Microsoft's recommendation that the System.Collections original collections only be used for backwards compatibility.
So we as developers came to know and love the generic collections and took them into our hearts and embraced them. The problem is, thread safety in both the original collections and the generic collections can be problematic, for very different reasons.
Now, if you are only doing single-threaded development you may not care – after all, no locking is required. Even if you do have multiple threads, if a collection is “load-once, read-many” you don’t need to do anything to protect that container from multi-threaded access, as illustrated below:
1: public static class OrderTypeTranslator
2: {
3: // because this dictionary is loaded once before it is ever accessed, we don't need to synchronize
4: // multi-threaded read access
5: private static readonly Dictionary<string, char> _translator = new Dictionary<string, char>
6: {
7: {"New", 'N'},
8: {"Update", 'U'},
9: {"Cancel", 'X'}
10: };
11:
12: // the only public interface into the dictionary is for reading, so inherently thread-safe
13: public static char? Translate(string orderType)
14: {
15: char charValue;
16: if (_translator.TryGetValue(orderType, out charValue))
17: {
18: return charValue;
19: }
20:
21: return null;
22: }
23: }
Unfortunately, most of our computer science problems cannot get by with just single-threaded applications or with multi-threading in a load-once manner. Looking at today's trends, it's clear to see that computers are not so much getting faster because of faster processor speeds -- we've nearly reached the limits we can push through with today's technologies -- but more because we're adding more cores to the boxes. With this new hardware paradigm, it is even more important to use multi-threaded applications to take full advantage of parallel processing to achieve higher application speeds.
So let's look at how to use collections in a thread-safe manner.
Using historical collections in a concurrent fashion
The early .NET collections (System.Collections) had a Synchronized() static method that could be used to wrap the early collections to make them completely thread-safe. This paradigm was dropped in the generic collections (System.Collections.Generic) because having a synchronized wrapper resulted in atomic locks for all operations, which could prove overkill in many multithreading situations. Thus the paradigm shifted to having the user of the collection specify their own locking, usually with an external object:
1: public class OrderAggregator
2: {
3: private static readonly Dictionary<string, List<Order>> _orders = new Dictionary<string, List<Order>>();
4: private static readonly _orderLock = new object();
5:
6: public void Add(string accountNumber, Order newOrder)
7: {
8: List<Order> ordersForAccount;
9:
10: // a complex operation like this should all be protected
11: lock (_orderLock)
12: {
13: if (!_orders.TryGetValue(accountNumber, out ordersForAccount))
14: {
15: _orders.Add(accountNumber, ordersForAccount = new List<Order>());
16: }
17:
18: ordersForAccount.Add(newOrder);
19: }
20: }
21: }
Notice how we’re performing several operations on the dictionary under one lock. With the Synchronized() static methods of the early collections, you wouldn’t be able to specify this level of locking (a more macro-level). So in the generic collections, it was decided that if a user needed synchronization, they could implement their own locking scheme instead so that they could provide synchronization as needed.
The need for better concurrent access to collections
Here’s the problem: it’s relatively easy to write a collection that locks itself down completely for access, but anything more complex than that can be difficult and error-prone to write, and much less to make it perform efficiently!
For example, what if you have a Dictionary that has frequent reads but in-frequent updates? Do you want to lock down the entire Dictionary for every access? This would be overkill and would prevent concurrent reads. In such cases you could use something like a ReaderWriterLockSlim which allows for multiple readers in a lock, and then once a writer grabs the lock it blocks all further readers until the writer is done (in a nutshell).
This is all very complex stuff to consider. Fortunately, this is where the Concurrent Collections come in. The Parallel Computing Platform team at Microsoft went through great pains to determine how to make a set of concurrent collections that would have the best performance characteristics for general case multi-threaded use.
Now, as in all things involving threading, you should always make sure you evaluate all your container options based on the particular usage scenario and the degree of parallelism you wish to acheive. This article should not be taken to understand that these collections are always supperior to the generic collections. Each fills a particular need for a particular situation. Understanding what each container is optimized for is key to the success of your application whether it be single-threaded or multi-threaded.
General points to consider with the concurrent collections
The MSDN points out that the concurrent collections all support the ICollection interface. However, since the collections are already synchronized, the IsSynchronized property always returns false, and SyncRoot always returns null. Thus you should not attempt to use these properties for synchronization purposes.
Note that since the concurrent collections also may have different operations than the traditional data structures you may be used to. Now you may ask why they did this, but it was done out of necessity to keep operations safe and atomic. For example, in order to do a Pop() on a stack you have to know the stack is non-empty, but between the time you check the stack’s IsEmpty property and then do the Pop() another thread may have come in and made the stack empty! This is why some of the traditional operations have been changed to make them safe for concurrent use.
In addition, some properties and methods in the concurrent collections achieve concurrency by creating a snapshot of the collection, which means that some operations that were traditionally O(1) may now be O(n) in the concurrent models. I’ll try to point these out as we talk about each collection so you can be aware of any potential performance impacts.
Finally, all the concurrent containers are safe for enumeration even while being modified, but some of the containers support this in different ways (snapshot vs. dirty iteration). Once again I’ll highlight how thread-safe enumeration works for each collection.
ConcurrentStack<T>: The thread-safe LIFO container
The ConcurrentStack<T> is the thread-safe counterpart to the System.Collections.Generic.Stack<T>, which as you may remember is your standard last-in-first-out container. If you think of algorithms that favor stack usage (for example, depth-first searches of graphs and trees) then you can see how using a thread-safe stack would be of benefit.
The ConcurrentStack<T> achieves thread-safe access by using System.Threading.Interlocked operations. This means that the multi-threaded access to the stack requires no traditional locking and is very, very fast!
For the most part, the ConcurrentStack<T> behaves like it’s Stack<T> counterpart with a few differences:
Pop() was removed in favor of TryPop()
Returns true if an item existed and was popped and false if empty.
PushRange() and TryPopRange() were added
Allows you to push multiple items and pop multiple items atomically.
Count takes a snapshot of the stack and then counts the items.
This means it is a O(n) operation, if you just want to check for an empty stack, call IsEmpty instead which is O(1).
ToArray() and GetEnumerator() both also take snapshots.
This means that iteration over a stack will give you a static view at the time of the call and will not reflect updates.
Pushing on a ConcurrentStack<T> works just like you’d expect except for the aforementioned PushRange() method that was added to allow you to push a range of items concurrently.
1: var stack = new ConcurrentStack<string>();
2:
3: // adding to stack is much the same as before
4: stack.Push("First");
5:
6: // but you can also push multiple items in one atomic operation (no interleaves)
7: stack.PushRange(new [] { "Second", "Third", "Fourth" });
For looking at the top item of the stack (without removing it) the Peek() method has been removed in favor of a TryPeek(). This is because in order to do a peek the stack must be non-empty, but between the time you check for empty and the time you execute the peek the stack contents may have changed. Thus the TryPeek() was created to be an atomic check for empty, and then peek if not empty:
1: // to look at top item of stack without removing it, can use TryPeek.
2: // Note that there is no Peek(), this is because you need to check for empty first. TryPeek does.
3: string item;
4: if (stack.TryPeek(out item))
5: {
6: Console.WriteLine("Top item was " + item);
7: }
8: else
9: {
10: Console.WriteLine("Stack was empty.");
11: }
Finally, to remove items from the stack, we have the TryPop() for single, and TryPopRange() for multiple items. Just like the TryPeek(), these operations replace Pop() since we need to ensure atomically that the stack is non-empty before we pop from it:
1: // to remove items, use TryPop or TryPopRange to get multiple items atomically (no interleaves)
2: if (stack.TryPop(out item))
3: {
4: Console.WriteLine("Popped " + item);
5: }
6:
7: // TryPopRange will only pop up to the number of spaces in the array, the actual number popped is returned.
8: var poppedItems = new string[2];
9: int numPopped = stack.TryPopRange(poppedItems);
10:
11: foreach (var theItem in poppedItems.Take(numPopped))
12: {
13: Console.WriteLine("Popped " + theItem);
14: }
Finally, note that as stated before, GetEnumerator() and ToArray() gets a snapshot of the data at the time of the call. That means if you are enumerating the stack you will get a snapshot of the stack at the time of the call. This is illustrated below:
1: var stack = new ConcurrentStack<string>();
2:
3: // adding to stack is much the same as before
4: stack.Push("First");
5:
6: var results = stack.GetEnumerator();
7:
8: // but you can also push multiple items in one atomic operation (no interleaves)
9: stack.PushRange(new [] { "Second", "Third", "Fourth" });
10:
11: while(results.MoveNext())
12: {
13: Console.WriteLine("Stack only has: " + results.Current);
14: }
The only item that will be printed out in the above code is "First" because the snapshot was taken before the other items were added. This may sound like an issue, but it’s really for safety and is more correct. You don’t want to enumerate a stack and have half a view of the stack before an update and half a view of the stack after an update, after all. In addition, note that this is still thread-safe, whereas iterating through a non-concurrent collection while updating it in the old collections would cause an exception.
ConcurrentQueue<T>: The thread-safe FIFO container
The ConcurrentQueue<T> is the thread-safe counterpart of the System.Collections.Generic.Queue<T> class. The concurrent queue uses an underlying list of small arrays and lock-free System.Threading.Interlocked operations on the head and tail arrays. Once again, this allows us to do thread-safe operations without the need for heavy locks!
The ConcurrentQueue<T> (like the ConcurrentStack<T>) has some departures from the non-concurrent counterpart.
Most notably:
Dequeue() was removed in favor of TryDequeue().
Returns true if an item existed and was dequeued and false if empty.
Count does not take a snapshot
It subtracts the head and tail index to get the count.
This results overall in a O(1) complexity which is quite good.
It’s still recommended, however, that for empty checks you call IsEmpty instead of comparing Count to zero.
ToArray() and GetEnumerator() both take snapshots.
This means that iteration over a queue will give you a static view at the time of the call and will not reflect updates.
The Enqueue() method on the ConcurrentQueue<T> works much the same as the generic Queue<T>:
1: var queue = new ConcurrentQueue<string>();
2:
3: // adding to queue is much the same as before
4: queue.Enqueue("First");
5: queue.Enqueue("Second");
6: queue.Enqueue("Third");
For front item access, the TryPeek() method must be used to attempt to see the first item if the queue. There is no Peek() method since, as you’ll remember, we can only peek on a non-empty queue, so we must have an atomic TryPeek() that checks for empty and then returns the first item if the queue is non-empty.
1: // to look at first item in queue without removing it, can use TryPeek.
2: // Note that there is no Peek(), this is because you need to check for empty first. TryPeek does.
3: string item;
4: if (queue.TryPeek(out item))
5: {
6: Console.WriteLine("First item was " + item);
7: }
8: else
9: {
10: Console.WriteLine("Queue was empty.");
11: }
Then, to remove items you use TryDequeue(). Once again this is for the same reason we have TryPeek() and not Peek():
1: // to remove items, use TryDequeue. If queue is empty returns false.
2: if (queue.TryDequeue(out item))
3: {
4: Console.WriteLine("Dequeued first item " + item);
5: }
Just like the concurrent stack, the ConcurrentQueue<T> takes a snapshot when you call ToArray() or GetEnumerator() which means that subsequent updates to the queue will not be seen when you iterate over the results. Thus once again the code below will only show the first item, since the other items were added after the snapshot.
1: var queue = new ConcurrentQueue<string>();
2:
3: // adding to queue is much the same as before
4: queue.Enqueue("First");
5:
6: var iterator = queue.GetEnumerator();
7:
8: queue.Enqueue("Second");
9: queue.Enqueue("Third");
10:
11: // only shows First
12: while (iterator.MoveNext())
13: {
14: Console.WriteLine("Dequeued item " + iterator.Current);
15: }
Using collections concurrently
You’ll notice in the examples above I stuck to using single-threaded examples so as to make them deterministic and the results obvious. Of course, if we used these collections in a truly multi-threaded way the results would be less deterministic, but would still be thread-safe and with no locking on your part required!
For example, say you have an order processor that takes an IEnumerable<Order> and handles each other in a multi-threaded fashion, then groups the responses together in a concurrent collection for aggregation. This can be done easily with the TPL’s Parallel.ForEach():
1: public static IEnumerable<OrderResult> ProcessOrders(IEnumerable<Order> orderList)
2: {
3: var proxy = new OrderProxy();
4: var results = new ConcurrentQueue<OrderResult>();
5:
6: // notice that we can process all these in parallel and put the results
7: // into our concurrent collection without needing any external locking!
8: Parallel.ForEach(orderList,
9: order =>
10: {
11: var result = proxy.PlaceOrder(order);
12:
13: results.Enqueue(result);
14: });
15:
16: return results;
17: }
Summary
Obviously, if you do not need multi-threaded safety, you don’t need to use these collections, but when you do need multi-threaded collections these are just the ticket! The plethora of features (I always think of the movie The Three Amigos when I say plethora) built into these containers and the amazing way they acheive thread-safe access in an efficient manner is wonderful to behold.
Stay tuned next week where we’ll continue our discussion with the ConcurrentBag<T> and the ConcurrentDictionary<TKey,TValue>.
For some excellent information on the performance of the concurrent collections and how they perform compared to a traditional brute-force locking strategy, see this wonderful whitepaper by the Microsoft Parallel Computing Platform team here.
Tweet
Technorati Tags: C#,.NET,Concurrent Collections,Collections,Multi-Threading,Little Wonders,BlackRabbitCoder,James Michael Hare
