Hello, I am Laszlo

ConcurrentDictionary over List 4

12/15/2018

4 minutes

In the previous post I have shown how we can use a new List with a ConcurrentDictionary in a thread safe manner.In this post I will show to other methods, to achieve the same.

Immutable Structures

One way to make our intentions clearer is to use immutabe collections. One package is right away available: System.Collections.Immutable

Here is an implementation for the test class to be used. According to my testing the ImmutableArray seems to be the immutable collection, that performs the fastest in this use cases I test.

public class ConcurrentImmutable
{
  public ConcurrentDictionary<string, ImmutableArray> _data = new ConcurrentDictionary<string, ImmutableArray>();
  public void TestAdd()
  {
    _data.AddOrUpdate("key", key => ImmutableArray.Create(), (key, immutable) =>
    {
      var newImmutable = immutable.Add(100);
      return newImmutable;
    });
  }

  public int TestRead()
  {
    int sum = 0;
    if(_data.TryGetValue("key", out var immutable))
    {
      foreach(var item in immutable)
      {
        sum += item;
      }
    }
    return sum;
  }
}

Note, the solution is very similar to the List implementation, but the API of immutable arrays restrict modifications. When changes are made, Add invoked, a new immutable array is returned.

Immutables not necessary mean to create a full copy of the data structure. Let's take an immutable stack implementation, where stack items are linked similar to a linked list. A Pop() in this case can simply move the stack's pointer to the next item in the chain, while a Push() adds a new Item to the beginning of the links, and sets the stack's pointer to the new item. Note, how the rest of the items remain unchanged.

The performance of the above structure is tested on the same scenarios as detailed in the previous post. The results are appended to the Immutable column of the table.

Adding additional threads over the ConcurrentDictionary can highly affect the contamination on the underlying operation of adding new items to our data structure. In case of the List we can see that the full copy results a huge execution time when we have 2 writers and 1 reader, which cascades as a higher contamination on the ConcurrentDictionary as well.

ConcurrentBag

In the final solution I will use ConcurrentBag. It is special in a way that it is optimized for scenarios where the same thread will be both producing and consuming of the items. Note, that this is not our case, but will see the affect of this when we only have concurrent writers.

public class Concurrent2
{
  public ConcurrentDictionary<string, ConcurrentBag> _data = new ConcurrentDictionary<string, ConcurrentBag>();
  public void TestAdd()
  {
    _data.AddOrUpdate("key", key => new ConcurrentBag(), (key, bag) =>
    {
      bag.Add(100);
      return bag;
    });
  }
  public int TestRead()
  {
    int sum = 0;
    if(_data.TryGetValue("key", out var myBag))
    {
      foreach(var item in myBag)
      {
        sum += item;
      }
    }
    return sum;
  }
}

Finally, the test results with ConcurrentBag:

Conclusion

As always we cannot explicitly say that one structure is better over the other. All previous solutions had advantages and disadvantages. When choosing the data structure to use, we shall consider our use-case very carefully, and choose the best data structure for that. Also note, that testing these use-cases are not simple either. Having multiple threads executing at the same time results in a non-deterministic behavior. For example we cannot be sure in case of two threads that they run parallel or just after each other. As a result we should always test with a large enough data set, so these edge cases are omitted.