List<T>.AddRange выдает ArgumentException при передаче ConcurrentDictionary в качестве аргумента
Сегодня у меня возникло подозрение, что метод List<T>.AddRange может быть небезопасно использовать с параллельной коллекцией в качестве аргумента, поэтому я провел эксперимент, чтобы выяснить:
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}");
Онлайн-демо.
ConcurrentDictionary инициализируется 50 000 положительными ключами. Затем в другой поток добавляются 50 000 дополнительных отрицательных ключей одновременно с добавлением словаря в список с помощью метода AddRange. Я ожидал, что в конечном итоге в словаре будет 100 000 ключей, а в списке — от 50 000 до 100 000 элементов. На самом деле я получил 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()
Мой вопрос: почему это происходит и как я могу предотвратить это? Есть ли способ гарантировать, что строка list.AddRange(dictionary); всегда будет успешной, без каких-либо исключений?
Представьте, что мне дали словарь как IEnumerable<T>, и я понятия не имею о его базовом типе. В этом случае выдается то же исключение:
IEnumerable<KeyValuePair<int, int>> enumerable = dictionary;
list.AddRange(enumerable); // Throws
Такое поведение снижает мою уверенность в использовании List<T>.AddRange API в целом.
Контекст: аналогичный симптом упоминается в этом вопросе, но минимальный и воспроизводимый пример не предоставлен, поэтому я не уверен, что сценарий тот же. Еще один связанный с этим вопрос: это о вызове LINQ ToList на ConcurrentDictionary<TKey, TValue>. Тем не менее, документация предупреждает об использовании методов расширения в параллельных коллекциях, но я не вижу никаких предупреждений против использования параллельной коллекции с методом List<T>.AddRange.
@shingo, ты имеешь в виду, что я не должен передавать ConcurrentDictionary<TKey,TValue> методу AddRange, потому что аргументом этого метода является IEnumerable<T>?
Мало того, поскольку нет никаких указаний на то, что AddRange является потокобезопасным, его следует избегать.
@shingo в моем примере я не использую List<T> одновременно. Все операции с List<T> вызываются в основном потоке консольного приложения. Одновременно я использую ConcurrentDictionary<TKey,TValue>, который предназначен для такого использования.
Позвольте мне перефразировать мое слово: нет никаких указаний на то, что AddRange будет использовать потокобезопасные методы. Для ConcurrentDictionary документ предупреждает, что доступ через интерфейс не является потокобезопасным, тогда как AddRange принимает интерфейс. Итак, можно сделать вывод, что вызов AddRange не гарантирует потокобезопасности.
@shingo, вы бы посоветовали не использовать List<T>.AddRange вообще или только в сочетании с ConcurrentDictionary<TKey,TValue> в частности?
Ответы 2
То, что происходит, довольно просто.
List<T>.AddRange имеет проверку, является ли переданная вещь ICollection<T>. Если это так, его можно оптимизировать, используя ICollection<T>.Count, чтобы выделить достаточно места для нового диапазона за один раз (вместо потенциального изменения размера списка несколько раз), и ICollection<T>.CopyTo, чтобы скопировать элементы коллекции за один раз, вместо добавления их по одному. один.
Код здесь:
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> реализует ICollection<KeyValuePair<TKey, TValue>>, а его реализации Count и CopyTo безопасны сами по себе, но между ними нет внутренней синхронизации.
Итак, List<T>.AddRange запрашивает у словаря его размер, выделяет это количество новых элементов, а затем просит словарь скопировать себя в это вновь выделенное пространство. Однако к этому моменту словарь вырос и выдает исключение здесь:
int count = GetCountNoLocks();
if (array.Length - count < index)
{
throw new ArgumentException(SR.ConcurrentDictionary_ArrayNotLargeEnough);
}
Насчет того, кто здесь «виноват», я не уверен. Оптимизация, которую выполняет List<T>, в большинстве случаев разумна, и, поскольку коллекция не является потокобезопасной, она не пытается быть потокобезопасной. Как отмечает @shingo, ConcurrentDictionary не гарантирует потокобезопасность при доступе через один из своих интерфейсов, хотя и делает все возможное. ICollection<T>.CopyToдокументируется как выброс, если пространство, в которое его просят скопировать, недостаточно велико.
Что касается обходных путей, то самый простой и очевидно правильный — создать промежуточную коллекцию: list.AddRange(dict.ToArray()). Однако это, конечно, связано с затратами на промежуточное распределение, которые могут быть большими.
Вы также можете обернуть словарь циклом и использовать Add с каждым элементом (ConcurrentDictionaryGetEnumerator() является потокобезопасным), и это в любом случае фактически то, что вы ожидаете AddRange.
Я думаю, что в целом вам просто нужно быть осторожным при смешивании потокобезопасных и непотокобезопасных типов таким образом. Убедитесь, что вы точно понимаете, что происходит, и какие именно потокобезопасные гарантии выполняются и не выполняются задействованными типами.
Спасибо canton7 за ответ. Я думаю, что вы достаточно хорошо объяснили причину проблемы. Есть ли у вас какие-либо предложения о том, как облегчить проблему? Может быть, перестанем использовать List<T>.AddRange с аргументами неизвестного происхождения?
@TheodorZoulias Я добавил комментарий внизу
@TheodorZoulias Можно также просто просмотреть словарь и вместо этого использовать Add. ConcurrentDictionary.GetEnumerator согласно документации безопасен в использовании. Хотя это может увеличить список в несколько раз, его можно несколько смягчить, если сначала сделать EnsureCapacity.
@Sweeper Правда, это лучше, чем я предлагаю. Отредактировано, чтобы добавить.
Кантон ToArray работает, если я вызываю его непосредственно на dictionary, но если dictionary передается мне как IEnumerable<T>, то он терпит неудачу аналогичным образом (демо). Думаю, мне следует выбрать другой обходной путь в зависимости от ситуации.
Да: Enumerable.ToArray() проделает то же самое с ICollection<T>. ConcurrentDictionary.ToArray однако документально подтверждено, что он безопасен
В конечном счете, резьба — это сложно. Мы можем многое сделать, чтобы скрыть некоторые сложные моменты, но по сути это сложная задача, и вам нужно тщательно понимать все, что происходит.
Кантон, проблема в том, что я не использую List<T> одновременно. Единственная сомнительная вещь, которую я делаю в своей демонстрации, — это передача ConcurrentDictionary<TKey,TValue> в качестве аргумента в метод с параметром типа IEnumerable<T>. Думаю, мне не следует этого делать. Вероятно, предупреждение в документации также включает этот случай.
@TheodorZoulias Проблема в том, что List не обращается к ConcurrentDictionary потокобезопасным способом. Потокобезопасные коллекции являются потокобезопасными только при использовании определенными способами, что документировано. Я бы не ожидал, что непотокобезопасная коллекция будет знать, как безопасно получить доступ к потокобезопасной коллекции. Использование потокобезопасной коллекции не гарантирует, что ваш код теперь является потокобезопасным: с помощью потокобезопасной коллекции очень легко делать вещи, которые нарушают потокобезопасность. Нарезка по-прежнему затруднена.
Кантон Я согласен, что многопоточная обработка — это сложно, но для людей не должно быть невозможно написать правильный многопоточный код, если они читают документацию и проявляют осторожность. Я считаю, что предупреждение в документации о невозможности доступа к членам ConcurrentDictionary<TKey,TValue> через один из интерфейсов, которые он реализует, может быть недостаточно убедительным, чтобы коллекцию нельзя было передавать в качестве аргумента в методах с параметром IEnumerable<T>.
Вы можете поднять вопрос по этому поводу перед командой документации, но, к сожалению, я не могу с этим помочь!
Кантон, честно говоря, я тоже не особо склонен это делать. :-)
В качестве дополнения к ответу Canton7 вы можете «скрыть» тип от оптимизации, вызывающей проблему, используя такой метод:
public static IEnumerable<T> Enumerate<T>(IEnumerable<T> sequence)
{
foreach (var item in sequence)
{
yield return item;
}
}
Затем вы можете вызвать: list.AddRange(Enumerate(dictionary)); и исключение не возникнет. Это позволит избежать необходимости делать копию коллекции.
В моем ответе у меня было что-то похожее на это предложение, но я удалил его на том основании, что использование цикла с Add было более понятным и немного более производительным.
Спасибо Мэтью за ответ. Я мог бы принять и ваш ответ, но Кантон ответил первым. :-)
ИМО, ответ Кантона был правильным, это была просто дополнительная информация, которая не поместилась в комментарий.
Однако члены, доступ к которым осуществляется через один из интерфейсов, реализуемых ConcurrentDictionary<TKey,TValue>, включая методы расширения, не гарантированно являются потокобезопасными и могут нуждаться в синхронизации вызывающей стороной.