Laszlo - ConcurrentDictionary over List 3

ConcurrentDictionary over List 3

11/15/2018

3 minutes

Doing it one way

In the previous post, I have shown why the following type can be dangerous:

ConcurrentDictionary<string, List>

The problem starts when we have multiple threads using (writing and reading) this dictionary at the same time. To avoid state corruption, we need to control this access by making it thread-safe.

In this post and the coming posts, I will show different ways to make this thread-safe. I will measure the performance solution on different use cases. There is no ultimate solution, each one has some advantages and disadvantages.

Creating a new List

The idea for this solution is that AddOrUpdate method on the ConcurrentDictionary is thread safe, though it might run our delegate multiple times. To utilize this, we can modify our delegate, such that instead of modifying the original list, we create a new one.

public class Concurrent
{
  public ConcurrentDictionary<string, List> _data = new ConcurrentDictionary<string, List>();

  public void TestAdd()
  {
    _data.AddOrUpdate("key", key => new List(), (key, list) =>
    {
      return list.Concat(new[] { 100 }).ToList();
    });
  }

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

This works, because when two operations runs simultaneously, neither of them modifies the original list. Both of them only creates a copy of it, which is modified. Having this solution has a huge price though: we do a lot of work with the memory. Having a new List created can be very expensive when the list is large.

Testing the solution

I will test a couple of use cases to see how this performs in different scenarios:

1 writer thread
2 writer threads
1 writer thread, 1 reader thread
2 writer threads, 1 reader thread
1 writer thread, 2 reader threads

Testing environment is the same as described in the previous posts.

1 writer thread

On thread is adding items 2*50000 times, this takes on my machine in an average of 4213 ms.

2 writer threads

In this case, 2 threads adding items to the list, each 50000. This takes an average of 12433 ms, significantly slower, as a good portion of the work (creating new Lists) is wasted.

1 writer thread, 1 reader thread

In this scenario 1 thread is reading and one thread is writing the list. Note, that even if they work on the same instance of the List, they only both read it.This takes an average of 42943 ms for 100000 iterations each.

2 writers threads, 1 reader thread

This takes about a 60 seconds to run.

1 writer thread, 2 reader threads

The last use case takes an average of 23 seconds.

Note, that in the last two case we have higher contamination on the ConcurrentDictionary which distorts the test.

As a slight optimization: giving a capacity to list based on the estimated items can improve the performance according to my measurements.

Scenarios (w: writer, r: reader):

1 w 0 r 4213ms
2 w 0 r 12433ms
1 w 1 r 42943ms
2 w 1 r ~60sec
1 w 2 r ~23sec

In the following posts I show some different solutions which has different performance characteristics.

async ConcurrentDictionary List

Hello, I am Laszlo

.NET developer