Недавно решил разобраться с внутренним устройством потокобезопасных коллекций, отправной точкой в изучении устройства ConcurrentDictionary была выбрана публикация на Хабре. Принцип его работы описан просто и понятно, за что отдельное спасибо автору.
Мне показалось, один момент в публикации освещен не достаточно полно и я решил восполнить данный пробел.
Потокобезопасные коллекции рассчитаны на использование в многопоточной среде и должны иметь возможность изменения в любой момент времени. Соответственно, их можно изменять даже в момент их перебора. Отсюда у меня возник вопрос, если во время перебора коллекция будет изменена, увидит ли итератор эти изменения?
Обратимся к статье, указанной выше:
GetEnumerator — может возвращать старые значения в случае, если изменения были сделаны другим потоком после вызова метода и того как итератор прошел этот элемент.
Ну весьма логично, что изменения элементов которые итератор уже прошел не будут учтены при переборе коллекции. А что будет, если изменить элемент до которого итератор еще «не добрался» или если вставить новый элемент в коллекцию?
Обратимся к MSDN (русский перевод данной заметки сделан не очень хорошо, поэтому я также вставлю заметку на языке оригинала):
Перечислитель, возвращенный из словаря, безопасно использовать одновременно с чтением из словаря и записью в него, однако он не представляет моментальный снимок словаря. Содержимое, доступное через перечислитель, может содержать изменения, внесенные в словарь, после вызова GetEnumerator.
The enumerator returned from the dictionary is safe to use concurrently with reads and writes to the dictionary, however it does not represent a moment-in-time snapshot of the dictionary. The contents exposed through the enumerator may contain modifications made to the dictionary after GetEnumerator was called.
Меня, как человека с техническим образованием, смущает формулировка «может содержать». Т.е. может содержать, а может и не содержать? Давайте проверим:
ConcurrentDictionary<int, string> dictionary = new ConcurrentDictionary<int, string>();
dictionary.TryAdd(0, "item0");
int x = 1;
foreach (var element in dictionary)
{
var tmp = x++;
if (!dictionary.TryAdd(tmp, "item" + tmp.ToString()))
{
throw new Exception("Вставить элемент не удалось");
}
Console.WriteLine(element);
}
Что же будет выведено в консоль? Один элемент или программа войдет в бесконечный цикл? Ни то, ни другое. Будет выведено следующее:
[0, item0]
[1, item1]
[2, item2]
[3, item3]
[4, item4]
[5, item5]
[6, item6]
[7, item7]
[8, item8]
[9, item9]
[10, item10]
[11, item11]
[12, item12]
[13, item13]
[14, item14]
[15, item15]
[16, item16]
Исключения не возникло, соответственно, 17 элемент в коллекцию был вставлен успешно, но итератор его не увидел, почему?
Давайте заглянем в исходники данной коллекции, а именно на реализацию метода GetEnumerator:
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
Node[] buckets = m_tables.m_buckets;
for (int i = 0; i < buckets.Length; i++)
{
// The Volatile.Read ensures that the load of the fields of 'current' doesn't move before the load from buckets[i].
Node current = Volatile.Read<Node>(ref buckets[i]);
while (current != null)
{
yield return new KeyValuePair<TKey, TValue>(current.m_key, current.m_value);
current = current.m_next;
}
}
}Поле m_tables помечено ключевым словом volatile, поэтому изменение содержащегося в нем массива Node[] m_buckets видны всем потокам. Каждый элемент этого массива представляет собой первый элемент в односвязном списке и содержит ссылку на следующий элемент в списке. Далее легко догадаться, что до тех пор, пока добавление/изменение элементов приводит к изменению самих односвязных списков, итератор «видит» эти изменения, но изменения самого массива для итератора не видны.
Изменение массива m_buckets происходит в двух случаях. Первый — это увеличение размера при вставке элементов, второй — вызов метода Clear() (сбрасывает размер массива до значения по-умолчанию).
Операции Update и Remove не изменяют размера массива и, соответственно, эти изменения всегда будут видны для итератора (конечно, если речь идет о изменение элемента, до которого итератор еще «не добрался»).
Заключение
Несмотря на то, что мы теперь знаем, когда изменения, внесенные во время перебора коллекции, будут видны, а когда нет, учитывать данные знания при программировании с использованием ConcurrentDictionary не стоит. Лучше всего придерживаться правила описанного на MSDN, что внесенные изменения могут быть видны, а могут и нет.
Автор: a_mastrakov
