Today I had a suspicion that the List<T>.AddRange method might not be safe to use with a concurrent collection as argument, so I made an experiment to find out:
ConcurrentDictionary<int, int> dictionary = new();
for (int i = 1; i <= 50_000; i++)
dictionary.TryAdd(i, default);
List<KeyValuePair<int, int>> list = new();
Thread thread = new(() =>
{
for (int i = -1; i >= -50_000; i--)
dictionary.TryAdd(i, default);
});
thread.Start();
list.AddRange(dictionary); // Throws
thread.Join();
Console.WriteLine($"dictionary.Count: {dictionary.Count:#,0}, list.Count: {list.Count:#,0}");
The ConcurrentDictionary is initialized with 50,000 positive keys. Then 50,000 additional negative keys are added on a different thread, concurrently with adding the dictionary in the list with the AddRange method. I was expecting that eventually the dictionary would have 100,000 keys, and the list somewhere between 50,000 and 100,000 items. In reality I got an ArgumentException:
Unhandled exception. 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.ConcurrentDictionary`2.System.Collections.Generic.ICollection<System.Collections.Generic.KeyValuePair<TKey,TValue>>.CopyTo(KeyValuePair`2[] array, Int32 index)
at System.Collections.Generic.List`1.InsertRange(Int32 index, IEnumerable`1 collection)
at System.Collections.Generic.List`1.AddRange(IEnumerable`1 collection)
at Program.Main()
My question is: Why is this happening, and how can I prevent it from happening? Is there any way to ensure that the list.AddRange(dictionary); line will be always successful, with no exceptions thrown?
Imagine that the dictionary might have been given to me as an IEnumerable<T>, and I have no idea about its underlying type. The same exception is thrown in this case as well:
IEnumerable<KeyValuePair<int, int>> enumerable = dictionary;
list.AddRange(enumerable); // Throws
This behavior reduces my confidence about using the List<T>.AddRange API in general.
Context: A similar symptom is mentioned in this question, but a minimal and reproducible example is not provided, so I am not sure that the scenario is the same. Another related question is this, about calling the LINQ ToList on a ConcurrentDictionary<TKey, TValue>. Nevertheless the documentation warns about using extension methods on concurrent collections, but I am not seeing any warning against using a concurrent collection with the List<T>.AddRange method.
What's happening is fairly straightforward.
List<T>.AddRange has a check to see whether the thing it was passed is an ICollection<T>. If so, it can optimize by using ICollection<T>.Count to allocate enough space for the new range in one go (instead of potentially resizing the list multiple times), and ICollection<T>.CopyTo to copy the collection's elements in one go, instead of adding them one-by-one.
The code is here:
if (collection is ICollection<T> c)
{
int count = c.Count;
if (count > 0)
{
if (_items.Length - _size < count)
{
Grow(checked(_size + count));
}
c.CopyTo(_items, _size);
_size += count;
_version++;
}
}
ConcurrentDictionare<TKey, TValue> implements ICollection<KeyValuePair<TKey, TValue>>, and its implementations of Count and CopyTo are safe in themselves, but there's no inherent synchronization between them.
So List<T>.AddRange asks the dictionary for its size, allocates that number of new elements, then asks the dictionary to copy itself into that newly-allocated space. However, the dictionary has grown by that point, and throws an exception here:
int count = GetCountNoLocks();
if (array.Length - count < index)
{
throw new ArgumentException(SR.ConcurrentDictionary_ArrayNotLargeEnough);
}
As for who's to "blame" here, I'm not sure. The optimization which List<T> is doing is sensible most of the time, and as a non-thread-safe collection it's not trying to be thread-safe. As @shingo notes, ConcurrentDictionary doesn't guarantee thread-safety when accessed through one of its interfaces, although it does its best. ICollection<T>.CopyTo is documented as throwing if the space it's being asked to copy into isn't large enough.
As for workarounds, the simplest and most obviously correct is to create an intermediate collection: list.AddRange(dict.ToArray()). However, this of course comes with the cost of an intermediate allocation, which may be large.
You could also wrap loop over the dictionary and use Add with each element (ConcurrentDictionary's GetEnumerator() is thread-safe), and this is effectively what you're expecting AddRange to do anyway.
I think in general you just need to be careful when mixing thread-safe and non-thread-safe types in this way. Make sure that you understand exactly what's going on, and exactly what thread-safe guarantees the types involved do and don't make.