8

В .NET есть такая структура как потокобезопасный словарь ConcurrentDictionary. А вот потокобезопасного списка почему-то нет? Может кто-то знает почему? Заранее спасибо

15
  • 1
  • 2
    Думаю, потому что индекс элемента, в отличие от ключа, не является безопасным. Если вы добавляете элемент с ключом в Dictionary, и потом удаляете элемент по другому ключу, вы сможете получить доступ по старому ключу. А вот удаление элемента из списка инвалидирует все индексы.
    – VladD
    Commented 15 февр. 2016 в 14:15
  • 1
    @andreycha, если только вечером :-) по первой ссылке, кстати, цитата из книжки C# 5.0 Unleashed 1st Edition by Bart De Smet (Author)
    – Grundy
    Commented 15 февр. 2016 в 14:20
  • 1
    @ixSci Grundy имхо не совсем верно перевел. Там написано, что сделать эффективную реализацию ConcurrentList непросто, и что такая реализация будет не сильно быстрее обычного листа с локами (в отличие от стэка и очереди), поэтому решили не запариваться.
    – andreycha
    Commented 15 февр. 2016 в 14:47
  • 1
    @ixSci: Возможно, это из-за меньшей нагрузки на аллокатор. Стандартный аллокатор в C++ медленный, так что 10-кратное увеличение может быть лишь из-за этого. Интересно сравнить по скорости List<int> с lock'ом и ту самую имплементацию, которая в 10 раз быстрее :-D
    – VladD
    Commented 15 февр. 2016 в 15:37

4 ответа 4

11

Почему нет ConcurrentList<T>?
Ответ в том, что все Concurrent* коллекции в пространстве имен System.Collections.Concurrent имеют чрезвычайно эффективные и масштабируемые реализации. То есть, внутри они используют такие облегченные примитивы синхронизации, как SpinLock и SpinWait. Фактически, реализации ConcurrentQueue<T> и ConcurrentStack<T> не используют вообще никаких локов.
Это привело к тому, что написание такого же эффективного списка стало нелегкой задачей.
Как результат, отсутствует тип ConcurrentList<T>, потому что его реализация не будет ощутимо лучше List<T> с классическим локом (который будет довольно тяжелым)

C# 5.0 Unleashed
Bart De Smet

3

В интерфейсе IList<T> есть методы для работы с элементами по их индексу. Однако в многопоточной среде элементы в любой момент могут быть удалены или сдвинуты со своего места, а значит доступ по индексу теряет смысл. Поэтому потокобезопасного списка ConcurrentList<T> нет, но есть потокобезопасная коллекция BlockingCollection<T>.

0

Я не знаю точной причины, остаётся только гадать. На мой взгляд, такой структуры нет из-за того, что List в C# содержит элементы одним куском(contiguous memory), а реализовать такую структуру в терминах lock-free довольно сложно, видимо. Все примеры lock-free или wait-free структур, что я видел были основаны на узлах, которые ссылались друг на друга. Видимо, это довольно сложно сделать со структурой, у которой нет узлов, поэтому решили, что «овчинка выделки не стоит».

Вот нашёл описание lock-free vector для С++, что подойдёт для List из C#, в целом.

-1

Это сделано в угоду производительности. Если есть именно необходимость потокобезопасного списка используйте CopyOnWriteArrayList

A thread-safe variant of {@link java.util.ArrayList} in which all mutative operations ({@code add}, {@code set}, and so on) are implemented by making a fresh copy of the underlying array.

1
  • 3
    сдесь вообще речь про .NET и c# :-)
    – Grundy
    Commented 16 февр. 2016 в 7:23

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.