CowDictionary

Benchmarks.md

|       Method |                           Kind | Items |              Mean |          StdDev |            Median |     Gen 0 | Allocated |
|------------- |------------------------------- |------ |------------------ |---------------- |------------------ |---------- |---------- |
|        Write | CachedReadConcurrentDictionary |  1000 |   225,437.8898 ns |   2,301.2916 ns |   224,307.7639 ns |   19.9219 | 125.19 kB |
| RandomAccess | CachedReadConcurrentDictionary |  1000 |        38.1510 ns |       0.3593 ns |        38.1710 ns |         - |       0 B |
|      ForEach | CachedReadConcurrentDictionary |  1000 |    12,751.5773 ns |     581.2744 ns |    12,767.5491 ns |         - |      48 B |
|    WriteRead | CachedReadConcurrentDictionary |  1000 |        78.9771 ns |       0.9068 ns |        79.0207 ns |         - |       0 B |
|        Write |           ConcurrentDictionary |  1000 |   220,681.6271 ns |   3,044.1570 ns |   220,026.7558 ns |   19.9219 |  125.2 kB |
| RandomAccess |           ConcurrentDictionary |  1000 |     5,807.7157 ns |      41.7800 ns |     5,811.4640 ns |         - |       0 B |
|      ForEach |           ConcurrentDictionary |  1000 |    13,586.0970 ns |     175.7761 ns |    13,615.1609 ns |         - |      56 B |
|    WriteRead |           ConcurrentDictionary |  1000 |        68.9538 ns |       0.7999 ns |        68.8947 ns |         - |       0 B |
|        Write |          CopyOnWriteDictionary |  1000 | 6,350,240.2794 ns | 193,564.5990 ns | 6,330,832.4428 ns | 2412.5000 |  11.35 MB |
| RandomAccess |          CopyOnWriteDictionary |  1000 |        31.4763 ns |       0.6182 ns |        31.4896 ns |         - |       0 B |
|      ForEach |          CopyOnWriteDictionary |  1000 |    11,074.5537 ns |     116.0739 ns |    11,057.0825 ns |         - |      48 B |
|    WriteRead |          CopyOnWriteDictionary |  1000 |    12,470.0901 ns |     192.2935 ns |    12,453.9565 ns |    4.9215 |  22.17 kB |
|        Write |             DictionaryWithLock |  1000 |    31,443.7087 ns |   1,932.9458 ns |    30,448.1770 ns |         - |       0 B |
| RandomAccess |             DictionaryWithLock |  1000 |        54.2393 ns |       1.0159 ns |        54.0626 ns |         - |       0 B |
|      ForEach |             DictionaryWithLock |  1000 |    23,488.3526 ns |     309.3112 ns |    23,436.6925 ns |    3.9795 |  22.21 kB |
|    WriteRead |             DictionaryWithLock |  1000 |        61.3252 ns |       1.9332 ns |        61.0353 ns |         - |       0 B |

CachedReadConcurrentDictionary.cs

using System.Collections;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Threading;

namespace CowDictionary
{
    /// <summary>
    /// A threadsafe dictionary for read-heavy workloads where the data is relatively small (under 10 thousand entries) and very rarely modified.
    /// </summary>
    /// <typeparam name="TKey">The key type.</typeparam>
    /// <typeparam name="TValue">The value type.</typeparam>
    public class CachedReadConcurrentDictionary<TKey, TValue> : IDictionary<TKey, TValue>
    {
        /// <summary>
        /// The number of cache misses which are tolerated before the cache is regenerated.
        /// </summary>
        private const int CacheMissesBeforeCaching = 10;
        private readonly ConcurrentDictionary<TKey, TValue> dictionary;
        private readonly IEqualityComparer<TKey> keyComparer;

        /// <summary>
        /// Approximate number of reads which did not hit the cache since it was last invalidated.
        /// This is used as a heuristic that the dictionary is not being modified frequently with respect to the read volume.
        /// </summary>
        private int cacheMissReads;

        /// <summary>
        /// Cached version of <see cref="dictionary"/>.
        /// </summary>
        private volatile Dictionary<TKey, TValue> readCache;

        public CachedReadConcurrentDictionary()
        {
            this.dictionary = new ConcurrentDictionary<TKey, TValue>();
        }

        public CachedReadConcurrentDictionary(IDictionary<TKey, TValue> dictionary)
        {
            this.dictionary = new ConcurrentDictionary<TKey, TValue>(dictionary);
        }

        public CachedReadConcurrentDictionary(IEqualityComparer<TKey> keyComparer)
        {
            this.keyComparer = keyComparer;
            this.dictionary = new ConcurrentDictionary<TKey, TValue>(keyComparer);
        }

        public CachedReadConcurrentDictionary(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> keyComparer)
        {
            this.keyComparer = keyComparer;
            this.dictionary = new ConcurrentDictionary<TKey, TValue>(dictionary, keyComparer);
        }

        /// <inheritdoc />
        IEnumerator IEnumerable.GetEnumerator() => this.GetEnumerator();

        /// <inheritdoc />
        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() => this.GetReadDictionary().GetEnumerator();

        /// <inheritdoc />
        public void Add(KeyValuePair<TKey, TValue> item)
        {
            ((IDictionary<TKey, TValue>) this.dictionary).Add(item);
            this.InvalidateCache();
        }

        /// <inheritdoc />
        public void Clear()
        {
            this.dictionary.Clear();
            this.InvalidateCache();
        }

        /// <inheritdoc />
        public bool Contains(KeyValuePair<TKey, TValue> item) => this.GetReadDictionary().Contains(item);

        /// <inheritdoc />
        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            this.GetReadDictionary().CopyTo(array, arrayIndex);
        }

        /// <inheritdoc />
        public bool Remove(KeyValuePair<TKey, TValue> item)
        {
            var result = ((IDictionary<TKey, TValue>) this.dictionary).Remove(item);
            if (result) this.InvalidateCache();
            return result;
        }

        /// <inheritdoc />
        public int Count => this.GetReadDictionary().Count;

        /// <inheritdoc />
        public bool IsReadOnly => false;

        /// <inheritdoc />
        public void Add(TKey key, TValue value)
        {
            ((IDictionary<TKey, TValue>) this.dictionary).Add(key, value);
            this.InvalidateCache();
        }

        /// <inheritdoc />
        public bool ContainsKey(TKey key) => this.GetReadDictionary().ContainsKey(key);

        /// <inheritdoc />
        public bool Remove(TKey key)
        {
            var result = ((IDictionary<TKey, TValue>) this.dictionary).Remove(key);
            if (result) this.InvalidateCache();
            return result;
        }

        /// <inheritdoc />
        public bool TryGetValue(TKey key, out TValue value) => this.GetReadDictionary().TryGetValue(key, out value);

        /// <inheritdoc />
        public TValue this[TKey key]
        {
            get { return this.GetReadDictionary()[key]; }
            set
            {
                this.dictionary[key] = value;
                this.InvalidateCache();
            }
        }

        /// <inheritdoc />
        public ICollection<TKey> Keys => this.GetReadDictionary().Keys;

        /// <inheritdoc />
        public ICollection<TValue> Values => this.GetReadDictionary().Values;
        
        private IDictionary<TKey, TValue> GetReadDictionary()
        {
            // If the cache is valid, return it.
            var cache = this.readCache;
            if (cache != null) return cache;

            // If the dictionary was recently modified or the cache is being recomputed, return the dictionary directly.
            if (Interlocked.Increment(ref this.cacheMissReads) < CacheMissesBeforeCaching) return this.dictionary;
            
            // Recompute the cache if it hasn't been written to in RecomputeCacheTicks ticks.
            this.cacheMissReads = 0;
            return this.readCache = new Dictionary<TKey, TValue>(this.dictionary, this.keyComparer);
        }

        private void InvalidateCache()
        {
            this.cacheMissReads = 0;
            this.readCache = null;
        }
    }
}