.NET ConcurrentDictionary.ToArray() ArgumentException

Question

Sometimes I get the error below when I call ConcurrentDictionary.ToArray. Error Below:

System.ArgumentException: The index is equal to or greater than the length of the array, or the number of elements in the dictionary is greater than the available space from index to the end of the destination array. at System.Collections.Concurrent.ConcurrentDictionary2.System.Collections.Generic.ICollection<System.Collections.Generic.KeyValuePair<TKey,TValue>>.CopyTo(KeyValuePair2[] array, Int32 index) at System.Linq.Buffer1..ctor(IEnumerable1 source) at System.Linq.Enumerable.ToArray[TSource](IEnumerable1 source) at ...Cache.SlidingCache2.RemoveExcessAsync(Object state) in ...\SlidingCache.cs:line 141 at System.Threading.ExecutionContext.RunInternal(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx) at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx) at System.Threading.QueueUserWorkItemCallback.System.Threading.IThreadPoolWorkItem.ExecuteWorkItem() at System.Threading.ThreadPoolWorkQueue.Dispatch()

I noticed that in multithreaded scenarios you sometimes get exceptions when sorting the ConcurrentDictionary. See stack overflow question here. So I started using ConcurrentDictionary.ToArray before sorting instead. It appears there are still problems while creating the array as well.

The concurrent dictionary is being used for a cache that maintains objects and flushes the last accessed objects when the set maximum number of elements for the cache is reached. The cache is accessed by multiple threads and the above error occurs when trying to remove older elements so new elements can be added to the array. Please see some code snippets below:

public class SlidingCache<TKey, TValue> : IDictionary<TKey, TValue>
{
    public int MinCount { get; private set; }
    public int MaxCount { get; private set; }
    private readonly IDictionary<TKey, CacheValue> _cache = new ConcurrentDictionary<TKey, CacheValue>();

    public SlidingCache(int minCount=75000, int maxCount=100000)
    {
        if (minCount <= 2)
            throw new ArgumentException("minCount");

        if (maxCount <= minCount)
            throw new ArgumentException("maxCount");

        MinCount = minCount;
        MaxCount = maxCount;
    }

    #region IDictionary<TKey, TValue>

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

    public TValue this[TKey key]
    {
        get
        {
            return _cache[key].Value;
        }
        set
        {
            _cache[key]=new CacheValue(value);
            RemoveExcess();
        }
    }
...

    #endregion

    private void RemoveExcess()
    {
        if (this.Count <= this.MaxCount || Interlocked.Increment(ref _removingExcess) != 1)
            return;

        ThreadPool.QueueUserWorkItem(RemoveExcessAsync, null);
    }

    private int _removingExcess;
    private void RemoveExcessAsync(object state)
    {
        var remove = _cache.ToArray().OrderByDescending(i => i.Value.LastRequestTime).Take(MaxCount - MinCount);
        foreach (var pair in remove)
        {
            _cache.Remove(pair.Key);
        }

        Interlocked.Exchange(ref _removingExcess, 0);
    }

Can anyone kindly explain the potential reason for the above exception and any workarounds?

Thanks.

Answer 1

That is because Enumerable.ToArray is not safe to use with concurrent collections.

You should declare your internal variable to be of type ConcurrentDictionary and not IDictionary, as this would use the ToArray implementation implemented by the dictionary itself, instead of relying on the extension method:

private readonly IDictionary<TKey, CacheValue> _cache = new ConcurrentDictionary<TKey, CacheValue>();

In particular, Enumerable.ToArray ends up using a Buffer class internally, and here is how the constructor of that class is defined (the start of it):

(from Enumerable.cs - reference source)

internal Buffer(IEnumerable<TElement> source) {
    TElement[] items = null;
    int count = 0;
    ICollection<TElement> collection = source as ICollection<TElement>;
    if (collection != null) {
        count = collection.Count;
        if (count > 0) {
            items = new TElement[count];
            collection.CopyTo(items, 0);
        }
    }

As you can see, it uses the Count property of the dictionary, creates an array, then copies the elements to the array. If the underlying dictionary has gotten at least one other item after reading Count but before CopyTo you get your problem.

You can contrast that with the implementation of ToArray inside the dictionary itself which uses locking:

(from ConcurrentDictionary.cs - reference source)

public KeyValuePair<TKey, TValue>[] ToArray()
{
    int locksAcquired = 0;
    try
    {
        AcquireAllLocks(ref locksAcquired);
        int count = 0;
        checked
        {
            for (int i = 0; i < m_tables.m_locks.Length; i++)
            {
                count += m_tables.m_countPerLock[i];
            }
        }

        KeyValuePair<TKey, TValue>[] array = new KeyValuePair<TKey, TValue>[count];

        CopyToPairs(array, 0);
        return array;
    }
    finally
    {
        ReleaseLocks(0, locksAcquired);
    }
}