[Из песочницы] Изменение ConcurrentDictionary во время перебора04.11.2014 21:03

Недавно решил разобраться с внутренним устройством потокобезопасных коллекций, отправной точкой в изучении устройства 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 dictionary = new ConcurrentDictionary(); 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]

Исключения не возникло, соответственно, 18 элемент в коллекцию был вставлен успешно, но итератор его не увидел, почему?

Давайте заглянем в исходники данной коллекции, а именно на реализацию метода GetEnumerator:

public IEnumerator> 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(ref buckets[i]);

while (current!= null) { yield return new KeyValuePair(current.m_key, current.m_value); current = current.m_next; } } } Поле m_tables помечено ключевым словом volatile, поэтому изменение содержащегося в нем массива Node[] m_buckets видны всем потокам. Каждый элемент этого массива представляет собой первый элемент в односвязном списке и содержит ссылку на следующий элемент в списке. Далее легко догадаться, что до тех пор, пока добавление/изменение элементов приводит к изменению самих односвязных списков, итератор «видит» эти изменения, но изменения самого массива для итератора не видны.Изменение массива m_buckets происходит в двух случаях. Первый — это увеличение размера при вставке элементов, второй — вызов метода Clear () (сбрасывает размер массива до значения по-умолчанию).Операции Update и Remove не изменяют размера массива и, соответственно, эти изменения всегда будут видны для итератора (конечно, если речь идет о изменение элемента, до которого итератор еще «не добрался»).

Заключение Несмотря на то, что мы теперь знаем, когда изменения, внесенные во время перебора коллекции, будут видны, а когда нет, учитывать данные знания при программировании с использованием ConcurrentDictionary не стоит. Лучше всего придерживаться правила описанного на MSDN, что внесенные изменения могут быть видны, а могут и нет.