2
\$\begingroup\$

I've been agonizing over this for an hour or two. I require a bidirectional dictionary that was thread safe. From what I understand about dictionaries, they're thread safe when being read from, but no so much when being written to. I've tried to write this code snippet to my understanding of correct, but a review would be excellent if possible.

class ConcurrentBidirectionalDictionary<TKey,UKey>
{
    private Dictionary<TKey, UKey> BackingDictionary;

    public ConcurrentBidirectionalDictionary()
    {
        BackingDictionary = new Dictionary<TKey, UKey>();
    }

    //Adding to dictionaries is not thread-safe ergo, lock when adding
    private readonly object _SyncLock = new object();
    public void Add(TKey item1, UKey item2)
    {
        if (!BackingDictionary.ContainsKey(item1) && !BackingDictionary.ContainsValue(item2))
        {
            lock (_SyncLock)
            {
                if (!BackingDictionary.ContainsKey(item1) && !BackingDictionary.ContainsValue(item2))
                {
                    BackingDictionary.Add(item1, item2);
                }
                else
                {
                    ThrowNewDuplicateKeyException(item1, item2);
                }
            }
        }
        else
        {
            ThrowNewDuplicateKeyException(item1, item2);
        }
    }

    private void ThrowNewDuplicateKeyException(TKey item1, UKey item2)
    {
        if (BackingDictionary.ContainsKey(item1) && BackingDictionary.ContainsValue(item2))
        {
            throw new ArgumentException("Duplicate Keys not allowed", "item1, item 2", null);
        }
        else if (BackingDictionary.ContainsKey(item1))
        {
            throw new ArgumentException("Duplicate Keys not allowed", "item1", null);
        }
        else if (BackingDictionary.ContainsValue(item2))
        {
            throw new ArgumentException("Duplicate Keys not allowed", "item 2", null);
        }
    }

    //Reading is thread safe, no lock needed
    public TKey GetFromUKey(UKey UKey)
    {
        var Record = BackingDictionary.FirstOrDefault(x => EqualityComparer<UKey>.Default.Equals(x.Value, UKey));
        if (Record.Equals(default(KeyValuePair<TKey,UKey>)))
        {
            throw new IndexOutOfRangeException($"Unable to find UKey {UKey}");
        }
        return Record.Key;
    }

    public UKey GetFromTKey(TKey TKey)
    {
        return BackingDictionary[TKey];
    }
}
\$\endgroup\$
  • \$\begingroup\$ Just a thought, might be useful to look at System.Collections.Concurrent.ConcurrentDictionary<TKey, TValue> msdn.microsoft.com/en-us/library/dd287191(v=vs.110).aspx \$\endgroup\$ – Gareth Jun 23 '16 at 21:16
  • \$\begingroup\$ @Gareth I'd considered it, but I also need to look up items in reverse. \$\endgroup\$ – Sidney Jun 23 '16 at 21:17
  • \$\begingroup\$ @Sidney - reviewing your code - for me it's not entirely clear why you have a primary and reverse dictionary? \$\endgroup\$ – BKSpurgeon Jun 23 '16 at 21:23
  • \$\begingroup\$ so you could have U:"alpha", T:"beta", and U:"beta", T:"alpha" as 2 distinct pairs, but you can't have U:"alpha", T:"beta" and U:"beta", T:"gamma" \$\endgroup\$ – Gareth Jun 23 '16 at 21:23
  • \$\begingroup\$ If the latter is not valid, then a single inner dictionary is only required. ie adding both [alpha] = beta and [beta] = alpha \$\endgroup\$ – Gareth Jun 23 '16 at 21:27
4
\$\begingroup\$

It is better to use CouncurrentDictionary to reduce lock contention:

class Map<X, Y>
{
    public X this[Y y]
    {
        get { return YX[XY[YX[y]]]; } // Ensure Set completion
        set { Set(value, y); }
    }

    public Y this[X x]
    {
        get { return XY[x]; }
        set { Set(x, value); }
    }

    void Set(X x, Y y)
    {
        if (!YX.GetOrAdd(y, x).Equals(x))
            throw new InvalidOperationException();

        if (!XY.GetOrAdd(x, y).Equals(y))
            throw new InvalidOperationException();
    }

    ConcurrentDictionary<X, Y> XY { get; } = new ConcurrentDictionary<X, Y>();
    ConcurrentDictionary<Y, X> YX { get; } = new ConcurrentDictionary<Y, X>();
}
\$\endgroup\$
  • \$\begingroup\$ Using two dictionaries instead of one definitely makes things easier. What bothers me is YX[XY[YX[y]]] as it greatly increases lookup time. If you want to ensure something - I think you should do it once the item is added or removed, not every time it is read. Also your code won't throw if the same key-vlaue pair added multiple times and it won't work for Map<int, int> (original code does not have those issues). \$\endgroup\$ – Nikita B Jun 24 '16 at 7:36
  • \$\begingroup\$ 1)O(3f(n)) = O(f(n)) - it is usually nothing to optimize here. I cannot see a way to ensure that update is atomic (symmetry of operations) without checking other dictionary. 2, 3) Yep, agree, thanks (TryAdd should help reproducing the behavior of the original code). \$\endgroup\$ – Dmitry Nogin Jun 24 '16 at 7:50
  • \$\begingroup\$ I wasn't talking about complexity, I was talking about performance. Decent lookup times is one of the major reasons people use dictionaries in the first place. You take this advantage away. And why can't you check the other dictionary, when you update?.. \$\endgroup\$ – Nikita B Jun 24 '16 at 8:08
  • \$\begingroup\$ We will need to lock other dictionary to prevent racing condition then. It creates point of contention, which is usually influences performance much more than executing a very cheap operation three times. \$\endgroup\$ – Dmitry Nogin Jun 24 '16 at 8:31
2
\$\begingroup\$

I think you have some misconceptions regarding thread safety. Check out MSDN page about Dictionary. Thread Safety section states:

A Dictionary can support multiple readers concurrently, as long as the collection is not modified. Even so, enumerating through a collection is intrinsically not a thread-safe procedure. In the rare case where an enumeration contends with write accesses, the collection must be locked during the entire enumeration. To allow the collection to be accessed by multiple threads for reading and writing, you must implement your own synchronization.

This is because when you write to dictionary it can,for example, increase the size of underlying collections or reorganize internal "buckets" where items are stored. Those operation will move items around which can break a concurrent read operation in unpredictable way. Enumerations on the other hand will throw straight away, if you modify the collection during enumeration process.

The bottom line is: your GetFromTKey (read) and GetFromUKey (enumeration) are not thread safe. You must synchronize them with your Add method if you want to read and write concurrently.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.