Analogs of concurrent collections in Portable .NET Framework

Question

Moving my code to portable framework, I found that there are no Concurrent collections available at all in Portable Class Library (PCL), this discussion explains it very well.

But still I need concurrent dictionary analog to run there. And I'm more interested in read/contains performance than in modifying performance.

Answer 1

If you're more interested in reading, you should use a ReaderWriterLockSlim.

This is a locking primitive that allows multiple readers or one writer to enter the critical region at any given time. This will incur virtually no performance hit while the dictionary is being read by multiple threads, and apply mutual exclusion only when a thread tries to write.

You would implement it as so (I omitted most methods for brevity - I left Add as a writer example, and Contains as a reader example):

public class CustomDictionary<TKey, TValue> : IDictionary<TKey, TValue>
{
    private readonly ReaderWriterLockSlim _lock = new ReaderWriterLockSlim();
    private readonly IDictionary<TKey, TValue> _dictionary = new Dictionary<TKey, TValue>(); 

    public bool Contains(KeyValuePair<TKey, TValue> item)
    {
        _lock.EnterReadLock();
        try
        {
            return _dictionary.Contains(item);
        }
        finally
        {
            _lock.EnterReadLock();
        }
    }

    public void Add(KeyValuePair<TKey, TValue> item)
    {
        _lock.EnterWriteLock();
        try
        {
            _dictionary.Add(item);
        }
        finally
        {
            _lock.ExitWriteLock();
        }
    }
}

Now, the GetEnumerator is a little trickier to lock, because the dictionary will actually be read after calling GetEnumerator, not while it's being called.

So you should implement the enumerator yourself and apply a read-lock like this, so that the lock will be held while the collection is being enumerated:

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        _lock.EnterReadLock();
        try
        {
            foreach (var entry in _dictionary)
                yield return entry;
        }
        finally
        {
            _lock.ExitReadLock();
        }
    }

Answer 2

The great benefits of Dictionary collections are fast key access and fast contains evaluation. All dictionaries uses different complicated algorithms (check this one) and it will be very hard to write your own from the scratch.

So I've tried to reuse source code of original ConcurrentDictionary from BCL (you can get source code for every base class). But, it is very complicated and uses dozens of private classes and low level functions to manage the memory. It is not accident, that it is not available in PCL from the beginning :)

Second thought was to make wrapper of ordinary dictionary and add lock section to every method invocation. Despite the fact that critical sections are not expensive it led to dramatic performance decrease.

So I've ended with clear interlocked implementation of Dictionary<,> wrapper. It happens so, that normal dictionary supports reading and enumeration from different threads, as far it is not modified in same time. So, on every change we cloning all dictionary. All threads which reading it in that time will continue iterate older copy.

public class InterlockedDictionary<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
{
    private Dictionary<TKey, TValue> _dictionary = new Dictionary<TKey, TValue>();


    public TValue this[TKey key]
    {
        get
        {
            return _dictionary[key];
        }
        set
        {                
            ApplyAndChange(dict => dict[key] = value);
        }
    }

    public Dictionary<TKey, TValue>.KeyCollection Keys
    {
        get
        {
            return _dictionary.Keys;
        }
    }

    public Dictionary<TKey, TValue>.ValueCollection Values
    {
        get
        {
            return _dictionary.Values;
        }
    }

    public int Count
    {
        get
        {
            return _dictionary.Count;
        }
    }


    public void Add(KeyValuePair<TKey, TValue> item)
    {
        ApplyAndChange(dict => dict.Add(item.Key, item.Value));
    }

    public void Clear()
    {
        _dictionary = new Dictionary<TKey, TValue>();
    }

    public bool ContainsKey(TKey key)
    {
        return _dictionary.ContainsKey(key);
    }

    public void Add(TKey key, TValue value)
    {
        ApplyAndChange(dict => dict.Add(key, value));
    }

    public bool Remove(TKey key)
    {
        bool result = false;
        ApplyAndChange(dict => result = dict.Remove(key));
        return result;
    }


    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        return _dictionary.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }


    private void ApplyAndChange(Action<Dictionary<TKey, TValue>> action)
    {
        Dictionary<TKey, TValue> initialDictionary, updatedDictionary, replacedDictionary;
        do
        {
            initialDictionary = _dictionary;
            updatedDictionary = new Dictionary<TKey, TValue>(initialDictionary);
            action(updatedDictionary);
        } while (Interlocked.CompareExchange(ref _dictionary, updatedDictionary, initialDictionary) != initialDictionary);
    }
}

This implementation does not implement IDictionary<,> as a lots of not required members there. But it can be easily done by invoking directly underlying dictionary for all non modifying methods and wrapping all modifying methods with ApplyAndChange(dict => ...).

N.B. - As for performance, comparing to original Dictionary<,> this implementation has worse Set, Add and Remove and equal to Read and Contains performance.