Я был рад увидеть новое System.Collections.Concurrent
пространство имен в .Net 4.0, довольно приятно! Я видел ConcurrentDictionary
, ConcurrentQueue
,ConcurrentStack
, ConcurrentBag
и BlockingCollection
.
Одна вещь, которая, кажется, таинственно отсутствует, это ConcurrentList<T>
. Я должен написать это сам (или убрать это из сети :))?
Я что-то упускаю здесь очевидное?
Ответы:
Я дал ему попытку некоторое время назад (также: на GitHub ). В моей реализации были некоторые проблемы, о которых я не буду здесь говорить. Позвольте мне рассказать вам, что более важно, что я узнал.
Во-первых, вы не сможете получить полную реализацию без
IList<T>
блокировки и поточно-ориентированной обработки. В частности, случайные вставки и удаления не будут работать, если вы также не забудете о O (1) произвольном доступе (то есть, если вы не «обманываете» и просто используете какой-то связанный список и не позволяете индексированию сосать).То , что я думал , что может быть полезным было потокобезопасного, ограниченное подмножество
IList<T>
: в частности, один , что позволило быAdd
и не обеспечивают случайного чтения только доступ по индексу (но неInsert
,RemoveAt
и т.д., а также не случайная запись доступа).Это было целью моей
ConcurrentList<T>
реализации . Но когда я проверил его производительность в многопоточных сценариях, я обнаружил, что простая синхронизация добавления к aList<T>
была быстрее . По сути, добавление к ужеList<T>
молниеносно; сложность используемых вычислительных шагов очень мала (увеличить индекс и присвоить элементу в массиве; это действительно так ). Вам потребуется тонна одновременных записей, чтобы увидеть какие-либо конфликты блокировок по этому вопросу; и даже тогда средняя производительность каждой записи все равно побьет более дорогую, хотя и без блокировки, реализацию вConcurrentList<T>
.В относительно редком случае, когда внутренний массив списка должен изменить свой размер, вы платите небольшую цену. В итоге я пришел к выводу, что это был единственный нишевой сценарий, в котором имел
ConcurrentList<T>
бы смысл тип коллекции « только для добавления» : когда вы хотите гарантированно низкие накладные расходы на добавление элемента при каждом вызове (так, в отличие от амортизированной цели производительности).Это просто не такой полезный класс, как вы думаете.
источник
List<T>
что использует old-skool, синхронизацию на основе монитора,SynchronizedCollection<T>
в BCL есть скрытое: msdn.microsoft.com/en-us/library/ms668265.aspxConcurrentList
победа будет, - это когда в список добавляется не так много активности, но есть много одновременных читателей. Можно уменьшить накладные расходы читателей на один барьер памяти (и даже устранить это, если читателей не волнуют слегка устаревшие данные).ConcurrentList<T>
такой способ, чтобы читатели гарантированно видели согласованное состояние без какой-либо блокировки, с относительно небольшими дополнительными издержками. Когда список увеличится, например, с размера 32 до 64, сохраните массив размера 32 и создайте новый массив размера 64. При добавлении каждого из следующих 32 элементов поместите его в слот 32-63 нового массива и скопируйте старый элемент из массива размера 32 в новый. Пока 64-й элемент не будет добавлен, читатели будут искать в массиве размера 32 элементы 0-31 и в массиве размера 64 элементы 32-63.Для чего бы вы использовали ConcurrentList?
Концепция контейнера произвольного доступа в многопоточном мире не так полезна, как может показаться. Заявление
в целом все равно не будет потокобезопасным.
Вместо того, чтобы создавать ConcurrentList, попробуйте создать решения с тем, что там есть. Наиболее распространенными классами являются ConcurrentBag и особенно BlockingCollection.
источник
Monitor
это, в любом случае, нет причин для одновременного списка.При всем уважении к уже полученным отличным ответам, бывают моменты, когда я просто хочу многопоточный IList. Ничего сложного или необычного. Производительность важна во многих случаях, но иногда это не является проблемой. Да, всегда будут проблемы без таких методов, как «TryGetValue» и т. Д., Но в большинстве случаев я просто хочу что-то, что я могу перечислить, не беспокоясь о том, чтобы наложить блокировки на все вокруг. И да, кто-то может найти какую-то «ошибку» в моей реализации, которая может привести к тупику или чему-то еще (я полагаю), но давайте будем честными: когда речь идет о многопоточности, если вы не пишете свой код правильно, это в любом случае заходит в тупик. Имея это в виду, я решил сделать простую реализацию ConcurrentList, которая обеспечивает эти основные потребности.
И для чего это стоит: я сделал базовый тест по добавлению 10 000 000 элементов в обычный List и ConcurrentList, и результаты были следующими:
Список закончен: 7793 миллисекунды. Параллельное окончание: 8064 миллисекунды.
источник
RemoveAt(int index)
никогда не является потокобезопасным, безопасенInsert(int index, T item)
только для индекса == 0, возвратIndexOf()
сразу устарел и т. Д. Даже не начинайте сthis[int]
.ReaderWriterLockSlim
может быть тупиковой ситуации легко , используяEnterUpgradeableReadLock()
одновременно. Однако вы не используете его, вы не делаете блокировку доступной извне и, например, не вызываете метод, который вводит блокировку записи, удерживая блокировку чтения, поэтому использование вашего класса больше не приводит к блокировке скорее всего.var l = new ConcurrentList<string>(); /* ... */ l[0] += "asdf";
. В общем, любая комбинация чтения-записи может привести к серьезным проблемам при одновременном выполнении. Вот почему параллельные структуры данных обычно предоставляют методы для таких, какConcurrentDictionary
иAddOrGet
т. Д. NB. Ваше постоянное (и избыточное, потому что элементы уже помечены как таковое подчеркиванием) повторениеthis.
беспорядка.ConcurrentList
(как массив с изменяемым размером, а не связанный список) нелегко написать с помощью неблокирующих операций. Его API плохо переводится в «параллельную» версию.источник
Причина, по которой нет ConcurrentList, заключается в том, что он принципиально не может быть записан. Причина в том, что некоторые важные операции в IList основаны на индексах, и это просто не сработает. Например:
Эффект, который преследует автор, заключается в том, чтобы вставить «dog» перед «cat», но в многопоточной среде между этими двумя строками кода может произойти что угодно. Например, другой поток может сделать это
list.RemoveAt(0)
, сместив весь список влево, но, что важно, catIndex не изменится. Воздействие здесь является то , чтоInsert
операция будет на самом деле поставил «собаку» после того, как кошка, а не до него.Несколько реализаций, которые вы видите в качестве «ответов» на этот вопрос, являются благонамеренными, но, как показано выше, они не дают надежных результатов. Если вы действительно хотите использовать семантику в виде списков в многопоточной среде, вы не сможете добиться этого, установив блокировки внутри методов реализации списков. Вы должны убедиться, что любой используемый вами индекс полностью живет в контексте блокировки. В результате вы можете использовать List в многопоточной среде с правильной блокировкой, но сам список не может быть создан в этом мире.
Если вы считаете, что вам нужен параллельный список, на самом деле есть только две возможности:
Если у вас есть ConcurrentBag и вы находитесь в положении, когда вам нужно передать его как IList, у вас есть проблема, потому что метод, который вы вызываете, указал, что они могут попытаться сделать что-то, как я делал выше, с cat & собака. В большинстве миров это означает, что вызываемый вами метод просто не предназначен для работы в многопоточной среде. Это означает, что вы либо реорганизуете его так, чтобы оно было, либо, если вы не можете, вам придется обращаться с ним очень осторожно. Вы почти наверняка будете обязаны создать свою собственную коллекцию со своими собственными блокировками и вызвать вызывающий сбой метод внутри блокировки.
источник
В тех случаях, когда число операций чтения значительно превышает количество записей или (хотя и часто) записи выполняются не одновременно , копирование при записи подход « может быть уместным.
Реализация, показанная ниже
var snap = _list; snap[snap.Count - 1];
никогда не будет (ну, конечно, за исключением пустого списка) генерировать, и вы также бесплатно получаете потокобезопасное перечисление с семантикой моментальных снимков… как я ЛЮБЛЮ неизменность!Чтобы копирование при записи работало, вы должны поддерживать неизменную структуру ваших данных , то есть никому не разрешается изменять их после того, как вы сделали их доступными для других потоков. Когда вы хотите изменить, вы
Код
использование
Если вам нужна более высокая производительность, это поможет сгенерировать метод, например, создать один метод для каждого типа модификации (Add, Remove, ...), который вы хотите, и жестко кодировать указатели функций
cloner
иop
.NB # 1 Вы несете ответственность за то, чтобы никто не изменил (предположительно) неизменяемую структуру данных. Мы ничего не можем сделать в универсальной реализации, чтобы предотвратить это, но, специализируясь на этом
List<T>
, вы можете защититься от модификации, используя List.AsReadOnly ()NB # 2 Будьте осторожны со значениями в списке. Приведенный выше подход копирования при записи защищает только их членство в списке, но если вы поместите туда не строки, а некоторые другие изменяемые объекты, вы должны позаботиться о безопасности потоков (например, блокировка). Но это ортогонально этому решению, и, например, блокировка изменяемых значений может быть легко использована без проблем. Вам просто нужно знать об этом.
NB # 3. Если ваша структура данных огромна, и вы часто ее модифицируете, подход «копировать все при записи» может быть чрезмерным как с точки зрения потребления памяти, так и с точки зрения затрат на копирование ЦП. В этом случае вы можете использовать неизменные коллекции MS .
источник
System.Collections.Generic.List<t>
уже потокобезопасен для нескольких читателей. Попытка сделать это потокобезопасным для нескольких авторов не имеет смысла. (По причинам, которые Хенк и Стивен уже упоминали)источник
Некоторые люди высветили некоторые пункты товара (и некоторые мои мысли):
Это не ответ. Это только комментарии, которые не совсем соответствуют конкретному месту.
... Мой вывод, Microsoft должна внести некоторые глубокие изменения в "foreach", чтобы сделать коллекцию MultiThreaded более простой в использовании. Также он должен следовать собственным правилам использования IEnumerator. До этого мы можем легко написать MultiThreadList, который будет использовать блокирующий итератор, но он не будет следовать за «IList». Вместо этого вам придется определить собственный интерфейс «IListPersonnal», который может завершиться ошибкой при «вставке», «удалении» и произвольном доступе (индексаторе) без исключения. Но кто захочет использовать его, если он не стандартный?
источник
ConcurrentOrderedBag<T>
который будет включать реализацию только для чтенияIList<T>
, но также будет предлагать полностью потокобезопасныйint Add(T value)
метод. Я не понимаю, зачемForEach
нужны какие-то изменения. Хотя Microsoft явно не говорит об этом, их практика показывает, что вполне допустимоIEnumerator<T>
перечислять содержимое коллекции, существовавшее при ее создании; исключение, изменяющее коллекцию, требуется только в том случае, если перечислитель не сможет гарантировать работу без сбоев.GetEnumerator
методу очень плохо оставлять коллекцию заблокированной после ее возвращения; такие конструкции могут легко привести к тупику. ОнIEnumerable<T>
не указывает, можно ли ожидать завершения перечисления, даже если коллекция изменена; лучшее, что можно сделать, - это написать собственные методы, чтобы они это делали, и иметь методы, которые принимаютIEnumerable<T>
документ, тот факт, что он будет поточно-ориентированным, только еслиIEnumerable<T>
поддерживает поточно-перечислимое перечисление.IEnumerable<T>
бы включил метод «Снимок» с возвращаемым типомIEnumerable<T>
. Неизменные коллекции могут вернуть себя; ограниченная коллекция может, если больше ничего не скопировать себя вList<T>
илиT[]
и вызватьGetEnumerator
это. Могут быть реализованы некоторые неограниченные коллекцииSnapshot
, а те, которые не смогут создать исключение, не пытаясь заполнить список своим содержимым.В последовательно выполняемом коде используемые структуры данных отличаются от (хорошо написанного) параллельно исполняемого кода. Причина в том, что последовательный код подразумевает неявный порядок. Параллельный код, однако, не подразумевает какого-либо порядка; еще лучше это означает отсутствие какого-либо определенного порядка!
Из-за этого структуры данных с подразумеваемым порядком (например, List) не очень полезны для решения параллельных задач. Список подразумевает порядок, но он не дает четкого определения, что это за порядок. Из-за этого порядок выполнения кода, управляющего списком, будет определять (до некоторой степени) неявный порядок списка, который находится в прямом конфликте с эффективным параллельным решением.
Помните, что параллелизм - это проблема с данными, а не проблема с кодом! Вы не можете сначала реализовать код (или переписать существующий последовательный код) и получить хорошо спроектированное параллельное решение. Вы должны сначала спроектировать структуры данных, помня о том, что неявное упорядочение не существует в параллельной системе.
источник
Подход без блокировок Copy and Write отлично работает, если вы не имеете дело с слишком большим количеством элементов. Вот класс, который я написал:
пример использования: orders_BUY = CopyAndWriteList.Clear (orders_BUY);
источник
Я реализовал один похожий на Брайана . Мой отличается:
yield return
для производства перечислителя.DoSync
иGetSync
методы, допускающие последовательные взаимодействия, которые требуют эксклюзивного доступа к списку.Код :
источник
try
блокаRemove
или установщика индексатора одновременно?IList
семантики в параллельных сценариях в лучшем случае ограничена. Я написал этот код, вероятно, до того, как пришел к этой реализации. Мой опыт такой же, как и у автора принятого ответа: я попробовал то, что я знал о синхронизации и IList <T>, и я кое-что узнал, сделав это.