Hot Swap Thread Safe Collections

• Download source code and sample project - 14.03 KB

NOTE: The source code attached to this article contains a couple of classes from the Matrix Platform. The platform is completely free, open source software. To obtain its source and binaries, go to the www.matrixplatform.com web site and see the downloads section.

Introduction

With the growth of multi-core processors, the issue of multi-thread access to data is becoming very important. This article presents a simple, application specific solution to the problem of accessing a generic .NET data collection concurrently. Despite being designed prior to the release of the .NET 4.0 multi-thread capable collections, the Hot Swap collections still offer a viable alternative to the System.Collections.Concurrent namespace offerings. As with any tool, it is most important to use it where appropriate, so usage scenarios, advantages and disadvantages are outlined in this article, to help you with your choice.

What is the Problem with Accessing an Ordinary Collection from Multiple Threads at the Same Time?

The default generic collections from the System.Collections namespace are not thread safe, and if one tries to access a single collection instance from multiple threads at the same time, this will often lead to “collection modified” exception (System.InvalidOperationException).

Here is a very simple example where the problem arises:

void MethodOne(int x)
{ 
   _collection.Add(x);
}

void MethodTwo()
{
   foreach(int val in _collection)
   {
      // Do something with val.
   }
}  

If MethodOne() and MethodTwo() are executed at the same time by two (or more) different threads, this will surely lead to an exception occurring.

What Hot-swapping Does?

Hot-swapping is a programming technique that allows to build collections capable of working simultaneously with as many threads as needed, with no danger of exceptions. These collections are designed to looks a lot like normal generic collections; the provided implementations in the source code attached to the article provide list IList and dictionary IDictionary collections, however the same mechanism can also be applied to other types of collections. Hot-swap collections have one great advantage – lock-less read access. This ensures the absolute maximum performance possible when concurrent read access is done.

How It Works?

The principle behind hot-swapping is very simple. It is based on the fact that while operations like modifying or clearing an existing collection are time consuming and require explicit thread access control, but the operation of “swapping” is performed on a single step. In our case, “swapping” refers to changing a class instance variable value from one instance to another. If we mark the field with the “volatile” key word, this instructs the compiler to make executable code such that “…the system always reads the current value of a volatile object at the point it is requested” (according to the MSDN). The actual operation of changing between the old and the new value is always thread safe, since the .NET environment guarantees to have the managed pointer always pointing to an actual value if one has been assigned.

The core operation principle of hot swapping is as follows:

When a modification to the collection is requested, the hot swapping collection prepares a brand new copy of the internal collection and swaps this new copy with the existing instance.

All read-only operations are pointed toward the currently used instance.

These two simple steps are enough to make sure the collection is thread-safe, since all access is performed on existing static versions of the collection. As a result of this - once a thread starts iterating the collection, it is guaranteed that it will work on the same version of the collection that it started upon. If changes occur during this iteration, those changes will be accessible to all subsequent iteration attempts.

The only locking occurs when the collection is being modified. This is required to make sure all changes are properly reflected in the final version of the collection.

In the implementations provided in this article, there have also been added a few extra methods, that allow to take into consideration the fact that the collection may change while a thread is accessing it. Those are the TryAdd() and TryGet() methods; similar methods can often be found in multi-thread able collections, since the nature of working with them is a little different as compared to conventional collections.

Implementation

The implementation of the hot swap technique is very straightforward. What follows is a partial view of the HotSwapList implementation, you can see the rest in the code attached to the article. I have selected a couple of methods that show the two aspects of the implementation - a hot swap list operates in two directions – one is providing internal data, based on the current internal reference, and the other modifying the internal reference.

This is an extract from the hot swap list implementation, showing some of the key features implemented:

public class HotSwapList<TType> : IList<TType>
{
    // The internal instance of the list. This is where items are actually kept.
    // This instance will never be changed, only swapped when a new one is generated.
    volatile List<TType> _instance = new List<TType>();
    
    /// <summary>
    /// This is a typical example of the operation of the hot swap list.
    /// Internal instance is used for data access.
    /// </summary>
    public int Count
    {
        get { return _instance.Count; }
    }
    
    /// <summary>
    /// This method demonstrates the operation of the hot-swap mechanism.
    /// The existing instance is kept, for as long as the new one is 
    /// created, then a fast swap is made.
    /// </summary>
    public void Add(TType item)
    {
        lock (this)
        {
            List<TType> items = new List<TType>(_instance);
            items.Add(item);
            _instance = items;
        }
        
        ItemUpdateDelegate del = ItemAddedEvent;
        if (del != null)
        {
            del(this, item);
        }
        
        RaiseCollectionUpdateEvent();
    }
    
    { REMAINING METHODS, PROPERTIES ETC. }
    
}

HotSwap Collections vs .NET System.Collections.Concurrent Collections

The Microsoft .NET 4.0 introduced a set of collections designed for working with concurrent thread access, namely: BlockingCollection, ConcurrentBag, ConcurrentDictionary, ConcurrentQueue and ConcurrentStack. There is a big difference as to how HotSwap collections and .NET concurrent collections approach the same problem, and this results in fairly different results when it comes to usage and features. Here is a list of the advantages and disadvantages of the HowSwap collections, as compared to .NET 4.0 ones:

Advantages of Hot Swap

• Maximum read speed

  Due to its design, hot swap collections offer the best theoretically possible read speed. This is often a very small advantage, only a few percent, however it can really make a difference in very high performance applications. It can also prove beneficial if using a very large number of concurrently accessing threads (for ex. 6-8 or more), a scenario that would become more common in the near future with the introduction of massively multi-core CPUs.

• Full support for alternative operating systems

  Mono has full support for the .NET 2.0 Framework, and full support for the .NET 4.0 is still to be given a due date (by the time of writing of this article), so in case you plan to use concurrent collections on anything different than Microsoft Windows, this article is an excellent solution.

• Iterating a fixed version of the collection

  Once an iterator is generated, it goes through the collection that existed at the moment the iterator was created.

• Simplicity

  You only use what you need, and you have all the source code for it; this improves manageability and reduces risk in the long run.

Disadvantages of Hot Swap

• Very low write/modification speed, especially with large set of items

  Again due to its design, modifying a hot swap collection is a very slow process, since a full duplicate is being made. This can be partially solved, by using the methods that allow to add multiple items at once – for example, AddRange() in the HotSwapList.

• Conditional usage

  There are a few cases where using a list hot swap collection can bring erroneous results; these cases are easily predictable and are described in detail in the “Do’s and Don’ts” section of this article.

Application

The HotSwap technique is used widely in the components of the Matrix Platform (www.matrixplatform.com) and has proven to be an overall excellent solution. Being aware of their advantages and disadvantages is very important, since they slightly differ from the general usability of generic .NET collections, and offer a more of a “specialized” solution.
The general rule for HotSwap usage is to look for cases where there is a small to medium amount of modifications to a collection or the collection is small in size.

Other Possibilities for the Usage of the Technique

The hot swapping technique can also be used in other scenarios, for example, in accessing class member instance, with no explicit locking. Here is an example:

void MyMethod()
{
   // Grabbing the instance and storing it in separate local variable prior to using it, 
   // guarantees we shall always use a valid instance, 
   // and there is no danger if other threads change the _instance member 
   // while we are operating.
   CustomClass instance = this._instance;
   If (instance != null)
   {
      instance.PerformAction();
   }
} 

Having a minimum number of lock sections (using the lock() keyword, a Monitor class or other synchronization item) guarantees optimum performance of your application, and most importantly greatly reduces the chance of dead-locks occurring. It also simplifies code and relieves the programmer from constantly checking for possible multi-tread issues.
Using this technique, along with a few others, allows us to build a full multi-thread access strategy, that greatly simplifies the process of multi-thread application development, however this deviates greatly from the current topic and shall be the topic of another separate article.

Examples – DO's and DON'Ts

HotSwapDictionary

Due to its implementation nature, all operations on the Hot Swap dictionary implementation are thread-safe in all possible scenarios.

HotSwapList

The hot swap list needs to be used with caution in 2 special cases, where it may lead to errors occurring if used improperly.

Let's assume we have the following member:

HotSwapList<int> _list = new HotSwapList<int>();

Case 1: Cloning of a hot swap list collection

• CORRECT
  C#

  List<int> clone = new List<int>(_list.AsReadOnly()); 

• INCORRECT

  C#

  List<int> clone = new List<int>(_list); 

Why?

The List constructor takes IEnumerable as argument, so iteration should be thread safe, even if we pass only _list. However, internally the List constructor tests the class for IList interface, and uses it if found. This may cause the collection to be iterated incorrectly while being modified and cause an exception.

Case 2: Iteration

• CORRECT since once an enumerator is generated, it will always point to the initial version of the collection
  C#

  foreach(int item in _list)
  {// Use item.
     int p = item;
  }

• CORRECT since creating a read only wrapper fixed to the current instance of the collection
  C#

  ReadOnlyCollection<int> clone2 = _list.AsReadOnly();
  for (int i = 0; i < clone2.Count; i++)
  {
      int p = clone2[i];
  }

• IN-CORRECT
  C#

  for (int i = 0; i < _list.Count; i++)
  {
      int p = _list[i];
  }

Why?

In the last scenario, the collection may change while running the “for” loop. If this happens, there is no guarantee that the _list[i] will actually point to an existing member, and this may cause an exception. This is one of the reasons there are no index[] capable collections in the .NET 4.0 System.Collections.Concurrent namespace.

Case 3: Exposing to external access is always safe

• CORRECT
  C#

  IEnumerable<int> List
  {
      get
      {
          return _list;
      }
  }

Why?

All of the IEnumerable members of the hot swap collection are safe for usage in any scenario, since they rely on the usage of Enumerators, and those point to the same sub-instance once they are created.

Usage

To use the source code of the collections attached to this article, simply add them to your project and use the classes in your multh-thread environment; the only thing to keep in mind are the couple of cases where the usage of the HotSwapList needs to be done properly to evade possible exceptions.