Pas de ConcurrentList<T> en .Net 4.0 ?

Question

J'ai été ravie de voir le nouveau System.Collections.Concurrent dans .Net 4.0, très bien ! J'ai déjà vu ConcurrentDictionary , ConcurrentQueue , ConcurrentStack , ConcurrentBag et BlockingCollection .

Une chose qui semble manquer mystérieusement est une ConcurrentList<T> . Dois-je l'écrire moi-même (ou le récupérer sur le web :) ) ?

Est-ce que je rate quelque chose d'évident ici ?

Answer 1

I J'ai fait un essai il y a quelque temps (également : sur GitHub ). Ma mise en œuvre a connu quelques problèmes, que je n'aborderai pas ici. Laissez-moi vous dire, plus important encore, ce que j'ai appris.

Tout d'abord, il n'y a aucune chance que vous obteniez une implémentation complète de IList<T> qui est sans verrou et sans risque pour les fils. En particulier, les insertions et suppressions aléatoires sont pas ne va pas fonctionner, à moins que vous n'oubliiez également l'accès aléatoire O(1) (c'est-à-dire, à moins que vous ne "trichiez" et n'utilisiez qu'une sorte de liste liée et que l'indexation soit nulle).

Ce que je pensée pourrait être utile, c'est un sous-ensemble limité, à l'abri des threads, de IList<T> en particulier, une qui permettrait à un Add et fournir des données aléatoires en lecture seule accès par index (mais pas de Insert , RemoveAt etc., et pas de hasard non plus écrire accès).

C'était le but de mon ConcurrentList<T> mise en œuvre . Mais lorsque j'ai testé ses performances dans des scénarios multithreads, j'ai constaté que la simple synchronisation ajoute à un List<T> était plus rapide . Fondamentalement, l'ajout à un List<T> est déjà rapide comme l'éclair ; la complexité des étapes de calcul impliquées est minuscule (incrémenter un index et assigner à un élément dans un tableau ; c'est Vraiment. ). Vous auriez besoin d'un tonne d'écritures simultanées pour voir une quelconque forme de conflit de verrouillage ; et même dans ce cas, les performances moyennes de chaque écriture seraient toujours supérieures à celles de l'implémentation plus coûteuse, bien que sans verrouillage, de la solution ConcurrentList<T> .

Dans le cas relativement rare où le tableau interne de la liste doit se redimensionner, vous payez un petit prix. J'ai donc fini par conclure que c'était la un scénario de niche dans lequel un add-on ConcurrentList<T> aurait un sens : lorsque vous voulez garanti faible coût d'ajout d'un élément sur chaque appel (donc, par opposition à un objectif de performance amorti).

C'est tout simplement une classe qui n'est pas aussi utile qu'on pourrait le croire.

Answer 2

À quoi servirait une ConcurrentList ?

Le concept de conteneur à accès aléatoire dans un monde threadé n'est pas aussi utile qu'il n'y paraît. La déclaration

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

dans son ensemble ne serait toujours pas thread-safe.

Au lieu de créer une ConcurrentList, essayez de construire des solutions avec ce qui existe déjà. Les classes les plus courantes sont le ConcurrentBag et surtout le BlockingCollection.

Answer 3

Avec tout le respect que je dois aux excellentes réponses déjà fournies, il arrive que je veuille simplement une IList à sécurité thread. Rien d'avancé ou de fantaisiste. Les performances sont importantes dans de nombreux cas, mais parfois, ce n'est pas une préoccupation. Oui, il y aura toujours des problèmes sans des méthodes comme "TryGetValue", etc., mais dans la plupart des cas, je veux simplement quelque chose que je puisse énumérer sans avoir à me soucier de mettre des verrous autour de tout. Et oui, quelqu'un peut probablement trouver un "bug" dans ma mise en œuvre qui pourrait conduire à une impasse ou quelque chose (je suppose), mais soyons honnêtes : quand il s'agit de multithreading, si vous n'écrivez pas votre code correctement, il va se bloquer de toute façon. Avec cela en tête, j'ai décidé de faire une simple implémentation de ConcurrentList qui fournit ces besoins de base.

Et pour ce que ça vaut : J'ai fait un test de base en ajoutant 10 000 000 d'éléments à une liste ordinaire et à une liste concurrente et les résultats ont été les suivants :

Liste terminée en : 7793 millisecondes. Concurrent terminé en : 8064 millisecondes.

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 (comme un tableau redimensionnable, et non une liste chaînée) n'est pas facile à écrire avec des opérations non bloquantes. Son API ne se traduit pas bien en une version "concurrente".

Answer 5

System.Collections.Generic.List<t> est déjà thread safe pour les lecteurs multiples. Essayer de le rendre thread safe pour plusieurs auteurs n'aurait pas de sens. (Pour les raisons déjà mentionnées par Henk et Stephen).