Почему ConcurrentWhwhat.Count делает снимок

Question

В статье C # / .NET Little Wonders для ConcurrentStack / Concurrent Queue , упоминается следующее относительно операции .Count в ConcurrentStack:

Счетчик занимаетснимок стека, а затем подсчитывает элементы.Это означает, что это операция O (n), если вы просто хотите проверить наличие пустого стека, вместо этого вызовите IsEmpty, который равен O (1).

Я не очень разбираюсь вмногопоточное программирование, но я понимаю, почему нельзя просто циклически просматривать элементы в коллекции и считать их, потому что коллекция может изменяться одновременно другими потоками.Однако, если вам нужно заблокировать ConcurrentStack достаточно долго, чтобы сделать снимок, не будет ли проще просто посчитать элементы, пока он у вас заблокирован, вернуть этот счет и снять блокировку, вместо того, чтобы использовать накладные расходы ивремя, затрачиваемое на создание полного снимка перед снятием блокировки?

Возможно, мне не хватает какой-то базовой информации о том, как это работает, и я был бы признателен за любые мысли или идеи, которые у вас могут возникнуть.

Answer 1

Я не знаю, реализован ли он таким образом, но если вы реализуете его как односвязный список с неизменяемыми узлами, тогда снимок практически бесплатен и не требует блокировки. Вы просто получаете текущий верхний элемент. А затем следуйте по связанному списку в начало.

Вы можете сохранить положение каждого узла в стеке узла, но это приведет к обмену памяти на производительность Count. И, вероятно, count не вызывается достаточно часто, чтобы гарантировать наличие дополнительной памяти на узел.

Большинство ConcurrentCollection работают без блокировок вообще. Такой стек с поддержкой связанного списка можно, например, построить с использованием Interlocked.CompareExchange в поле, указывающем на текущий узел. И если вы делаете некоторые операции без блокировки, вам обычно нужно сделать все они без блокировки, так как операции без блокировки не будут учитывать блокировку.

Answer 2

Вы предполагаете, что для того, чтобы рассчитывать на снимок, он должен снять большую блокировку.

I считаю, параллельные коллекции разработаны с дешевыми - возможно, оптимистичными -снимок в виду.Например, если вы перебираете ConcurrentStack через GetEnumerator(), это также использует снимок.Я очень сомневаюсь, что для создания этого снимка всегда используется операция O (n).

Answer 3

Не знаю точно, но вот предположение.

Стек может быть реализован в виде односвязного списка, состоящего из неизменяемых ячеек, где каждая ячейка указывает наклетка под ним в стеке.Тогда «снимком» будет просто сделать копию вершины стека;поскольку ячейки являются неизменяемыми, это также перемещает оставшуюся часть текущего стека.

Таким образом, снимок будет операцией O (1), но подсчет фактических элементов по-прежнему равен O (n).

Answer 4

ConcurrentStack и ConcurrentQueue являются потокобезопасными коллекциями, поэтому блокировка не требуется.в ConcurrentStack, например, подсчет рассчитывается путем считывания головного узла, а затем пересекает накопление списка по количеству

Answer 5

Я полагаю, что самая большая причина в том, что запрос параллельной очереди (где два или более потока всегда манипулируют содержимым) для подсчета количества элементов является ошибочной концепцией для начала. Я подозреваю, что они только предоставили свойство Count для соответствия существующим интерфейсам. Таким образом, если единственная причина существования API-интерфейса - это требование к интерфейсу, то кого это волнует, так как вам не следует использовать его с самого начала.

При работе с объектами, которые изменены несколькими потоками, никогда не следует спрашивать объект о каком-либо состоянии / значении, которое другой поток может изменить. Поскольку к тому времени, когда на ваш вопрос ответят, он может перестать быть правильным ответом. Это похоже на фундаментальную проблему в свойстве WinForm «InvokeRequired». Некоторые API - это просто плохая идея в многопоточной среде, и я думаю, что это число относится к этой категории.

В конечном счете, довольно странно, что разработчики не использовали явный элемент интерфейса для свойства ICollection.Count, а не делали его общедоступным. Тогда, по крайней мере, вы знаете, что не должны его использовать. Они указали использовать IsEmpty на MSDN; однако это легко не заметить.