Нет ConcurrentList <T>в .Net 4.0?

Question

Я был рад увидеть новое пространство имен System.Collections.Concurrent в .Net 4.0, довольно приятно!Я видел ConcurrentDictionary, ConcurrentQueue, ConcurrentStack, ConcurrentBag и BlockingCollection.

Одна вещь, которая, кажется, таинственно отсутствует - это ConcurrentList<T>.Я должен написать это сам (или убрать это из сети :))?

Я что-то упускаю здесь очевидное?

Answer 1

I попытался некоторое время назад (также: на GitHub ).В моей реализации были некоторые проблемы, о которых я не буду здесь говорить.Позвольте мне рассказать вам, что еще более важно, то, что я узнал.

Во-первых, вы не сможете получить полную реализацию IList<T> без блокировки и поточно-ориентированного потока.В частности, случайные вставки и удаления не будут работать, если только вы не забудете о O (1) произвольном доступе (т. Е. Если вы не «обманываете» и просто используете какой-то связанный список и позволяете индексацию).полный отстой)* только для чтения доступ по индексу (но не Insert, RemoveAt и т. д., а также без случайного запись доступ).

Это было целью моя ConcurrentList<T> реализация .Но когда я проверил его производительность в многопоточных сценариях, я обнаружил, что простая синхронизация добавляет к List<T> быстрее .По сути, добавление к List<T> молниеносно;сложность вычислительных шагов минимальна (увеличить индекс и присвоить элементу в массиве; это на самом деле ).Вам понадобится тонна одновременных записей, чтобы увидеть любой вид конфликта блокировки;и даже тогда средняя производительность каждой записи все равно побьет более дорогостоящую, хотя и без блокировки, реализацию в ConcurrentList<T>.

В относительно редком случае, когда внутренний массив списка должен сам себя изменить размер, вы платитенебольшая стоимостьВ итоге я пришел к выводу, что это был нишевый сценарий one , в котором имел бы смысл тип коллекции ConcurrentList<T> с возможностью добавления: когда вы хотите гарантированно низкие накладные расходы на добавление элемента на каждый звонок (так, в отличие от амортизированной цели производительности).

Это просто не такой полезный класс, как вы думаете.

Answer 2

Для чего бы вы использовали ConcurrentList?

Концепция контейнера произвольного доступа в многопоточном мире не так полезна, как может показаться.Оператор

  if (i < MyConcurrentList.Count)  
      x = MyConcurrentList[i]; 

в целом все равно не будет поточно-ориентированным.

Вместо создания ConcurrentList, попробуйте создать решения с тем, что там есть.Наиболее распространенными классами являются ConcurrentBag и особенно BlockingCollection.

Answer 3

При всем уважении к уже полученным отличным ответам, иногда мне просто нужен многопоточный IList.Ничего сложного или необычного.Производительность важна во многих случаях, но иногда это не является проблемой.Да, всегда будут проблемы без таких методов, как «TryGetValue» и т. Д., Но в большинстве случаев я просто хочу что-то, что я могу перечислить, не беспокоясь о том, чтобы наложить блокировки на все вокруг.И да, кто-то может найти какую-то «ошибку» в моей реализации, которая может привести к тупику или чему-то еще (я полагаю), но давайте будем честными: если речь идет о многопоточности, если вы не пишете свой код правильно, этов любом случае заходит в тупик.Имея это в виду, я решил сделать простую реализацию ConcurrentList, которая обеспечивает эти основные потребности.

И для чего это стоит: я провел базовый тест по добавлению 10 000 000 элементов в обычные List и ConcurrentList, и результаты были такими:1003 *

Список закончен: 7793 миллисекунды.Параллельное завершение: 8064 миллисекунды.

public class ConcurrentList<T> : IList<T>, IDisposable
{
    #region Fields
    private readonly List<T> _list;
    private readonly ReaderWriterLockSlim _lock;
    #endregion

    #region Constructors
    public ConcurrentList()
    {
        this._lock = new ReaderWriterLockSlim(LockRecursionPolicy.NoRecursion);
        this._list = new List<T>();
    }

    public ConcurrentList(int capacity)
    {
        this._lock = new ReaderWriterLockSlim(LockRecursionPolicy.NoRecursion);
        this._list = new List<T>(capacity);
    }

    public ConcurrentList(IEnumerable<T> items)
    {
        this._lock = new ReaderWriterLockSlim(LockRecursionPolicy.NoRecursion);
        this._list = new List<T>(items);
    }
    #endregion

    #region Methods
    public void Add(T item)
    {
        try
        {
            this._lock.EnterWriteLock();
            this._list.Add(item);
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public void Insert(int index, T item)
    {
        try
        {
            this._lock.EnterWriteLock();
            this._list.Insert(index, item);
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public bool Remove(T item)
    {
        try
        {
            this._lock.EnterWriteLock();
            return this._list.Remove(item);
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public void RemoveAt(int index)
    {
        try
        {
            this._lock.EnterWriteLock();
            this._list.RemoveAt(index);
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public int IndexOf(T item)
    {
        try
        {
            this._lock.EnterReadLock();
            return this._list.IndexOf(item);
        }
        finally
        {
            this._lock.ExitReadLock();
        }
    }

    public void Clear()
    {
        try
        {
            this._lock.EnterWriteLock();
            this._list.Clear();
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public bool Contains(T item)
    {
        try
        {
            this._lock.EnterReadLock();
            return this._list.Contains(item);
        }
        finally
        {
            this._lock.ExitReadLock();
        }
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        try
        {
            this._lock.EnterReadLock();
            this._list.CopyTo(array, arrayIndex);
        }
        finally
        {
            this._lock.ExitReadLock();
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        return new ConcurrentEnumerator<T>(this._list, this._lock);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return new ConcurrentEnumerator<T>(this._list, this._lock);
    }

    ~ConcurrentList()
    {
        this.Dispose(false);
    }

    public void Dispose()
    {
        this.Dispose(true);
    }

    private void Dispose(bool disposing)
    {
        if (disposing)
            GC.SuppressFinalize(this);

        this._lock.Dispose();
    }
    #endregion

    #region Properties
    public T this[int index]
    {
        get
        {
            try
            {
                this._lock.EnterReadLock();
                return this._list[index];
            }
            finally
            {
                this._lock.ExitReadLock();
            }
        }
        set
        {
            try
            {
                this._lock.EnterWriteLock();
                this._list[index] = value;
            }
            finally
            {
                this._lock.ExitWriteLock();
            }
        }
    }

    public int Count
    {
        get
        {
            try
            {
                this._lock.EnterReadLock();
                return this._list.Count;
            }
            finally
            {
                this._lock.ExitReadLock();
            }
        }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }
    #endregion
}

    public class ConcurrentEnumerator<T> : IEnumerator<T>
{
    #region Fields
    private readonly IEnumerator<T> _inner;
    private readonly ReaderWriterLockSlim _lock;
    #endregion

    #region Constructor
    public ConcurrentEnumerator(IEnumerable<T> inner, ReaderWriterLockSlim @lock)
    {
        this._lock = @lock;
        this._lock.EnterReadLock();
        this._inner = inner.GetEnumerator();
    }
    #endregion

    #region Methods
    public bool MoveNext()
    {
        return _inner.MoveNext();
    }

    public void Reset()
    {
        _inner.Reset();
    }

    public void Dispose()
    {
        this._lock.ExitReadLock();
    }
    #endregion

    #region Properties
    public T Current
    {
        get { return _inner.Current; }
    }

    object IEnumerator.Current
    {
        get { return _inner.Current; }
    }
    #endregion
}

Answer 4

ConcurrentList (как массив с изменяемыми размерами, а не как связанный список) нелегко написать с помощью неблокирующих операцийЕго API плохо переводится в «параллельную» версию.

Answer 5

Причина, по которой не существует ConcurrentList, заключается в том, что он принципиально не может быть записан. Причина в том, что некоторые важные операции в IList основаны на индексах, и это просто не сработает. Например:

int catIndex = list.IndexOf("cat");
list.Insert(catIndex, "dog");

Эффект, который преследует автор, заключается в том, чтобы вставить «dog» перед «cat», но в многопоточной среде со списком между этими двумя строками кода может произойти что угодно. Например, другой поток может сделать list.RemoveAt(0), сместив весь список влево, но, что важно, catIndex не изменится. В результате, операция Insert фактически ставит «собаку» после кошки, а не перед ней.

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

Если вы считаете, что вам нужен параллельный список, на самом деле есть только две возможности:

1. Что вам действительно нужно, так это ConcurrentBag
2. Вам необходимо создать собственную коллекцию, возможно, реализованную с помощью List и собственного управления параллелизмом.

Если у вас есть ConcurrentBag и вы находитесь в положении, когда вам нужно передать его как IList, у вас есть проблема, потому что метод, который вы вызываете, указал, что они могут попытаться сделать что-то, как я делал выше кошка и собака. В большинстве миров это означает, что вызываемый вами метод просто не предназначен для работы в многопоточной среде. Это означает, что вы либо реорганизуете его так, чтобы оно было, либо, если вы не можете, вам придется обращаться с ним очень осторожно. Вы почти наверняка будете обязаны создавать свою собственную коллекцию со своими собственными блокировками и вызывать вызывающий сбой метод внутри блокировки.

Answer 6

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

Реализация, показанная ниже,

• без блокировки
• невероятно быстро для одновременных операций чтения , даже когда одновременные модификации продолжаются - независимо от того, какдолго они занимают
• , потому что "снимки" неизменны, атомарность без блокировки возможна, то есть var snap = _list; snap[snap.Count - 1]; никогда не будет (ну, кроме, конечно, пустого списка) бросать, и вы также получитеПотоково-безопасное перечисление с семантикой снимков бесплатно .. как я ЛЮБЛЮ неизменность!
• реализовано в общем , применимо к любой структуре данных и любого типа модификации
• очень просто , то есть легко тестировать, отлаживать, проверять, читая код
• можно использовать в .Net 3.5

Чтобы копирование при записи работало, вы должны хранить свои данные вtructures фактически неизменяемый , т.е. никто не может изменять их после того, как вы сделали их доступными для других потоков.Когда вы хотите изменить, вы

1. клонируете структуру
2. , вносите изменения в клон
3. , атомарно меняете местами ссылку на модифицированный клон

Код

static class CopyOnWriteSwapper
{
    public static void Swap<T>(ref T obj, Func<T, T> cloner, Action<T> op)
        where T : class
    {
        while (true)
        {
            var objBefore = Volatile.Read(ref obj);
            var newObj = cloner(objBefore);
            op(newObj);
            if (Interlocked.CompareExchange(ref obj, newObj, objBefore) == objBefore)
                return;
        }
    }
}

Использование

CopyOnWriteSwapper.Swap(ref _myList,
    orig => new List<string>(orig),
    clone => clone.Add("asdf"));

Если вам нужна более высокая производительность, это поможет отключить метод,например, создать один метод для каждого типа модификации (Add, Remove, ...), который вы хотите, и жестко закодировать указатели функций cloner и op.

NB # 1 Вы несете ответственность за то, чтобы никто не изменил (предположительно) неизменную структуру данных.Мы ничего не можем сделать в универсальной реализации , чтобы предотвратить это, но при специализации на List<T> вы могли бы защититься от модификации, используя List.AsReadOnly ()

NB # 2 Будьте осторожны со значениями в списке.Приведенный выше подход копирования при записи защищает только их членство в списке, но если вы поместите туда не строки, а некоторые другие изменяемые объекты, вы должны позаботиться о безопасности потоков (например, блокировка).Но это ортогонально этому решению, и, например, блокировка изменяемых значений может быть легко использована без проблем.Вам просто нужно знать об этом.

NB # 3 Если ваша структура данных огромна и вы часто ее изменяете, подход "копировать все при записи" может быть непомерным как вУсловия использования памяти и затраты на копирование процессора.В этом случае вы можете вместо этого использовать неизменные коллекции MS .

Answer 7

System.Collections.Generic.List<t> уже безопасна для нескольких читателей.Попытка сделать это потокобезопасным для нескольких авторов не имеет смысла.(По причинам, которые Хенк и Стивен уже упоминали)

Answer 8

Некоторые люди подсвечивают некоторые пункты товара (и некоторые из моих мыслей):

• Это может выглядеть безумным для неспособного случайного доступа (индексатора), но мне кажется, это нормально.Нужно только думать, что в многопоточных коллекциях существует множество методов, которые могут завершиться с ошибкой, например, Indexer и Delete.Вы также можете определить действие сбоя (откат) для средства доступа к записи, например «сбой» или просто «добавить в конце».
• Не потому, что это многопоточная коллекция, она всегда будет использоваться в многопоточном контексте.Или же он может быть использован только одним писателем и одним читателем.
• Другим способом безопасного использования индексатора может быть оборачивание действий в блокировку коллекции с использованием ее корня (если она сделана общедоступной).).
• Для многих людей сделать руткил видимым - это хорошая идея.Я не уверен на 100% в этом вопросе, потому что, если он скрыт, вы лишаете пользователя большей гибкости.Мы всегда должны помнить, что программирование многопоточности не для кого-либо.Мы не можем предотвратить любое неправильное использование.
• Microsoft придется проделать определенную работу и определить новый стандарт, чтобы ввести правильное использование многопоточной коллекции.Во-первых, IEnumerator не должен иметь moveNext, но должен иметь GetNext, который возвращает true или false и получает выходной параметр типа T (таким образом, итерация больше не будет блокировать).Кроме того, Microsoft уже использует «использование» внутри себя в foreach, но иногда использует IEnumerator напрямую, не заключая его в «использование» (ошибка в представлении коллекции и, вероятно, в других местах). Использование IEnumerator в качестве обертки рекомендуется Microsoft.Эта ошибка удаляет хороший потенциал для безопасного итератора ... Итератор, который блокирует коллекцию в конструкторе и разблокирует его методом Dispose - для блокирующего метода foreach.

Это не ответ.Это только комментарии, которые на самом деле не соответствуют конкретному месту.

... Мой вывод, Microsoft должна внести некоторые глубокие изменения в «foreach», чтобы сделать коллекцию MultiThreaded более легкой в ​​использовании.Также он должен следовать собственным правилам использования IEnumerator.До этого мы можем легко написать MultiThreadList, который будет использовать блокирующий итератор, но он не будет следовать за «IList».Вместо этого вам придется определить собственный интерфейс «IListPersonnal», который может завершиться ошибкой при «вставке», «удалении» и произвольном доступе (индексаторе) без исключения.Но кто захочет использовать его, если он не стандартный?

Answer 9

Lockless Copy и Write подход отлично работает, если вы не имеете дело с слишком многими предметами.Вот класс, который я написал:

public class CopyAndWriteList<T>
{
    public static List<T> Clear(List<T> list)
    {
        var a = new List<T>(list);
        a.Clear();
        return a;
    }

    public static List<T> Add(List<T> list, T item)
    {
        var a = new List<T>(list);
        a.Add(item);
        return a;
    }

    public static List<T> RemoveAt(List<T> list, int index)
    {
        var a = new List<T>(list);
        a.RemoveAt(index);
        return a;
    }

    public static List<T> Remove(List<T> list, T item)
    {
        var a = new List<T>(list);
        a.Remove(item);
        return a;
    }

}

пример использования: orders_BUY = CopyAndWriteList.Clear (orders_BUY);

Answer 10

В последовательно выполняемом коде используемые структуры данных отличаются от (хорошо написанного) параллельно исполняемого кода. Причина в том, что последовательный код подразумевает неявный порядок. Параллельный код, однако, не подразумевает какого-либо порядка; еще лучше это означает отсутствие какого-либо определенного порядка!

Из-за этого структуры данных с подразумеваемым порядком (например, List) не очень полезны для решения одновременных задач. Список подразумевает порядок, но он не дает четкого определения, что это за порядок. Из-за этого порядок выполнения кода, управляющего списком, будет определять (до некоторой степени) неявный порядок списка, который находится в прямом конфликте с эффективным параллельным решением.

Помните, что параллелизм - это проблема с данными, а не проблема с кодом! Вы не можете сначала реализовать код (или переписать существующий последовательный код) и получить хорошо спроектированное параллельное решение. Сначала необходимо спроектировать структуры данных, помня о том, что неявное упорядочение не существует в параллельной системе.