7
\$\begingroup\$

I find that I use this pattern a lot where I have a dictionary which I would only read from and update and wouldn't add/remove keys.

In that case, using ConcurrentDictionary is not necessary and could hinder performance.

I wrote a simple class which implements such dictionary by using a wrapper class as its values:

class ConstantKeysDictionary<TKey, TValue> : IDictionary<TKey, TValue> where TValue : class
    {
        #region Internal Classes

        class Wrapper
        {
            private TValue m_Val;

            public TValue Value
            {
                get
                {
                    return Volatile.Read<TValue>(ref m_Val);
                }
                set
                {
                    Volatile.Write(ref m_Val, value);
                }
            }
        }

        #endregion

        private Dictionary<TKey, Wrapper> m_InnerDictionary;

        public ConstantKeysDictionary(IDictionary<TKey, TValue> toCopy)
        {
            m_InnerDictionary = new Dictionary<TKey, Wrapper>();

            foreach (var pair in toCopy)
            {
                m_InnerDictionary.Add(pair.Key, new Wrapper() { Value = pair.Value });
            }
        }

        public ConstantKeysDictionary(IEnumerable<TKey> keys)
        {
            m_InnerDictionary = new Dictionary<TKey, Wrapper>();

            foreach (var key in keys)
            {
                m_InnerDictionary.Add(key, new Wrapper());
            }
        }

        public ConstantKeysDictionary(Action<Dictionary<TKey, TValue>> builder)
        {
            Dictionary<TKey, TValue> dict = new Dictionary<TKey, TValue>();
            builder(dict);

            m_InnerDictionary = new Dictionary<TKey, Wrapper>();
            foreach (var pair in dict)
            {
                m_InnerDictionary.Add(pair.Key, new Wrapper() { Value = pair.Value });
            }
        }

        public TValue this[TKey key]
        {
            get
            {
                return m_InnerDictionary[key].Value;
            }

            set
            {
                if (!m_InnerDictionary.ContainsKey(key))
                {
                    throw new KeyNotFoundException();
                }

                m_InnerDictionary[key].Value = value;
            }
        }

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

        public bool IsReadOnly
        {
            get
            {
                return false;
            }
        }

        public ICollection<TKey> Keys
        {
            get
            {
                return m_InnerDictionary.Keys;
            }
        }

        public ICollection<TValue> Values
        {
            get
            {
                return m_InnerDictionary.Values.Select(v => v.Value).ToList();
            }
        }

        public void Add(KeyValuePair<TKey, TValue> item)
        {
            throw new NotSupportedException();
        }

        public void Add(TKey key, TValue value)
        {
            throw new NotSupportedException();
        }

        public void Clear()
        {
            throw new NotSupportedException();
        }

        public bool Contains(KeyValuePair<TKey, TValue> item)
        {
            return ContainsKey(item.Key) &&
                   m_InnerDictionary[item.Key].Value.Equals(item.Value);
        }

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

        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            throw new NotSupportedException();
        }

        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            foreach (var pair in m_InnerDictionary)
            {
                yield return new KeyValuePair<TKey, TValue>(pair.Key, pair.Value.Value);
            }
        }

        public bool Remove(KeyValuePair<TKey, TValue> item)
        {
            throw new NotSupportedException();
        }

        public bool Remove(TKey key)
        {
            throw new NotSupportedException();
        }

        public bool TryGetValue(TKey key, out TValue value)
        {
            Wrapper wrapper;
            if (!m_InnerDictionary.TryGetValue(key, out wrapper))
            {
                value = default(TValue);
                return false;
            }

            value = wrapper.Value;
            return true;
        }

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

The point of this class is to be thread safe (given that you can't add/remove keys) without using locks/concurrent collections.

As you can see, many of the methods are not implemented because these are irrelevant for this kind of dictionary. In these methods, I throw NotSupportedException.

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you elaborate as to why a concurrent dictionary would hinder performance? \$\endgroup\$ – Paul Tsai Nov 2 '16 at 13:59
  • \$\begingroup\$ @PaulTsai Update operations in concurrent dictionary acquire locks, specifically, kernel mode locks (Monitor). This is bad by itself if you are inside a tight loop and performance are a concern. In addition to acquiring the lock, when running in parallel, the lock could cause blocking which is even worse. The point in my implementation is that locks can be avoided if you impose constraints such that you can't add/remove keys from the dictionary, but only update. \$\endgroup\$ – Arik Nov 2 '16 at 19:07
  • \$\begingroup\$ In Producer/Consumer scenarios where there is one producer (updater), the ConcurrentDictionary is overkill. In this case, use the default dictionary because volatile is overkill. stackoverflow.com/questions/4269498/… If there are multiple producers a ConcurrentDictionary would be necessary. \$\endgroup\$ – Paul Tsai Nov 3 '16 at 19:22
5
\$\begingroup\$

Principle of least astonishment

Since the ConstantKeysDictionary isn't a real dictionary and does not behave this way - it throws many exceptiosn for known operations. It would be safer from the user point of view to call it a collection and implement it like one.

The class' signature would then become:

class ConstantKeyValueCollection<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>> where TValue : class

This will allow you to remove all the unnecessary methods and thus prevent the confusion and desire to use for example the Remove. I'd rather don't have it then wonder why it throws an exception and having to look for it in some documentation.

By doing so you follow the Principle of least astonishment

If a necessary feature has a high astonishment factor, it may be necessary to redesign the feature.

and further:

In general engineering design contexts, the principle can be taken to mean that a component of a system should behave in a manner consistent with how users of that component are likely to expect it to behave; that is, users should not be astonished at the way it behaves.

(emphasis mine)

Your dictionary doesn't behave this way.

Of course you still can use internally whatever data structure you want but you should provide a public API that does exacly what is expected from it, nothing more and nothing less and especially doesn't throw any unexpected exception.

Liskov substitution principle

As @RJFalconer mentioned in his comment your class also vialotes the Liskov substitution principle.

Substitutability is a principle in object-oriented programming that states that, in a computer program, if S is a subtype of T, then objects of type T may be replaced with objects of type S (i.e., an object of the type T may be substituted with its subtype object of the type S) without altering any of the desirable properties of that program (correctness, task performed, etc.).

This means that you should be able to use your dictionary everywhere the IDictionary<TKey, TValue> interface is acceptable (your type is a subtype) and don't experience any side effects. But you cannot do this. It could throw exceptions all over the place.

\$\endgroup\$
  • 1
    \$\begingroup\$ More precisely the original design violates Liskov substitutibility \$\endgroup\$ – RJFalconer Nov 1 '16 at 9:36
  • \$\begingroup\$ @RJFalconer a good catch, I looked at it from the user's point of view and forgot about the code's point of view ;-] \$\endgroup\$ – t3chb0t Nov 1 '16 at 9:41

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.