c# java - .NET 4.0中没有ConcurrentList<T>?




parallel-processing task-parallel-library (9)

我很高兴在.NET 4.0中看到新的System.Collections.Concurrent命名空间,相当不错! 我见过ConcurrentDictionaryConcurrentQueueConcurrentStackConcurrentBagBlockingCollection

似乎神秘缺失的一件事是ConcurrentList<T> 。 我必须自己写(或从网上下载:))?

我在这里错过了很明显的东西吗


Answers

System.Collections.Generic.List<t>对多个读者来说已经是线程安全的。 试图使它对多个作者是安全的,这是没有意义的。 (由于Henk和Stephen已经提到的原因)


ConcurrentList (作为可调整大小的数组,不是链接列表)不容易使用非阻塞操作进行编写。 其API不能很好地转换为“并发”版本。


没有ConcurrentList的原因是因为它从根本上不能写。 之所以这样,是因为IList中的一些重要操作依赖于索引,而这种简单的操作不起作用。 例如:

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

作者追求的效果是在“猫”之前插入“狗”,但在多线程环境中,这两行代码之间的列表可能会发生任何变化。 例如,另一个线程可能会做list.RemoveAt(0) ,将整个列表向左移动,但关键的是, catIndex不会改变。 这里的影响是Insert操作实际上会把“狗”放在猫后面 ,而不是放在它之前。

您所看到的针对此问题提供的“答案”的几种实现方式是良好的,但如上所示,它们不提供可靠的结果。 如果你真的想在多线程环境中使用类列表语义,你不能通过在列表实现方法中加入锁达到目的。 您必须确保您使用的任何索引完全位于锁的上下文中。 结果是您可以在多线程环境中使用带有正确锁定的List,但是该列表本身无法在该世界中存在。

如果你认为你需要一个并发列表,那实际上只有两种可能性:

  1. 你真正需要的是一个ConcurrentBag
  2. 您需要创建自己的集合,可能使用List和您自己的并发控制来实现。

如果你有一个ConcurrentBag并且处于需要将它作为IList传递的位置,那么你有一个问题,因为你调用的方法已经指定他们可能会尝试像上面那样用cat&狗。 在大多数世界中,这意味着你所调用的方法根本不是为了在多线程环境中工作而构建的。 这意味着你要么重构它,要么就是,如果你不能,你必须非常小心地处理它。 你几乎肯定会被要求用自己的锁创建你自己的集合,并在锁内调用违规方法。


如果读取数量大大超过写入数量,或者(无论频繁)写入是否是非并行的 ,则写入时复制方法可能是适当的。

下面显示的实现是

  • 无锁
  • 并发读取速度非常快 ,即使正在进行并发修改 - 无论它们需要多长时间
  • 因为“快照”是不可变的, 无锁原子性是可能的,即var snap = _list; snap[snap.Count - 1]; var snap = _list; snap[snap.Count - 1]; 将永远不会(当然,除了一个空的列表)抛出,并且你还可以免费获得快照语义的线程安全枚举..我是如何爱不变的!
  • 通用实施 ,适用于任何数据结构任何类型的修改
  • 死简单 ,即易于测试,调试,通过阅读代码进行验证
  • 可在.Net 3.5中使用

要使写入时复制起作用,必须使数据结构有效地保持不变 ,即在让其他线程可用后,不允许更改它们。 当你想修改时,你

  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"));

如果你需要更多的性能,这将有助于ungenerify方法,例如为每种类型的修改(Add,Remove,...)创建一个方法,并且硬编码函数指针clonerop

NB#1您有责任确保没有人修改(据称)不可变的数据结构。 我们没有办法在通用的实现中做到这一点,但是当专注于List<T> ,您可以使用List.AsReadOnly()来防止修改。

注意#2小心列表中的值。 上面的写入复制方法仅保护其列表成员资格,但如果您不放置字符串,但其中还有其他可变对象,则必须注意线程安全性(例如锁定)。 但是这与这个解决方案是正交的,例如,可以毫无问题地容易地使用可变值的锁定。 你只需要知道它。

注意#3如果您的数据结构非常庞大并且经常修改它,则无论是在内存消耗还是所涉及的复制CPU成本方面,全副本复制方法都可能会令人望而却步。 在这种情况下,您可能想使用MS的不可变集合


有些人看到了一些商品点(以及我的一些想法):

  • 它可能看起来疯狂无法随机accesser(索引),但对我来说似乎很好。 你只需要认为在多线程集合上有很多方法可能会像Indexer和Delete一样失败。 您还可以定义写入访问器的失败(回退)操作,如“失败”或简单地“添加到最后”。
  • 这不是因为它是一个多线程集合,它将始终用于多线程环境中。 或者它也可以被一个作者和一个读者使用。
  • 另一种能够以安全的方式使用索引器的方法是使用其根(如果公开的话)将操作包装到集合的锁中。
  • 对于很多人来说,制作rootLock是可行的。 我并不十分确定这一点,因为如果它隐藏起来,您可以为用户消除很多灵活性。 我们必须记住,多线程编程不适合任何人。 我们无法防止各种错误的使用。
  • 微软将不得不做一些工作并定义一些新标准来介绍适当使用Multithreaded集合。 首先,IEnumerator不应该有一个moveNext,但应该有一个返回true或false的GetNext,并获得一个T型的out参数(这样迭代不会再被阻塞)。 此外,微软已经在foreach中内部使用“using”,但有时直接使用IEnumerator而没有用“使用”(集合视图中的错误,可能在更多地方)包装它 - 包装IEnumerator的使用是Microsoft推荐的做法。 这个bug消除了安全迭代器的潜力......迭代器在构造函数中锁定集合,并在其Dispose方法上解锁 - 用于阻塞foreach方法。

这不是一个答案。 这只是一些不适合特定地点的评论。

......我的结论是,微软必须对“foreach”进行一些深层次的改变,以使MultiThreaded集合更易于使用。 它也必须遵循自己的IEnumerator使用规则。 在此之前,我们可以轻松编写一个MultiThreadList,它将使用阻塞迭代器,但不会遵循“IList”。 相反,你将不得不定义自己的“IListPersonnal”接口,它可能无法在“插入”,“删除”和随机访问器(索引器)上失败。 但是,如果不是标准,谁会想要使用它?


在顺序执行代码时,所使用的数据结构不同于(良好编写的)并行执行的代码。 原因是顺序代码隐含着顺序。 然而,并发代码并不意味着任何顺序; 更好但它意味着缺乏任何明确的顺序!

由于这个原因,隐含顺序的数据结构(如列表)对于解决并发问题并不是很有用。 列表意味着顺序,但它没有明确定义该顺序是什么。 因此,操作列表的代码的执行顺序将(在一定程度上)确定列表的隐式顺序,这与有效的并行解决方案直接冲突。

记住并发是数据问题,而不是代码问题! 您无法首先实现代码(或重写现有的顺序代码)并获得设计良好的并行解决方案。 您需要首先设计数据结构,同时牢记并发系统中不存在隐式排序。


尽管已经提供了很好的答案,但有时我只想要一个线程安全的IList。 没有什么先进或看中。 在很多情况下,性能很重要,但有时候这并不是问题。 是的,没有诸如“TryGetValue”之类的方法总会遇到挑战,但大多数情况下,我只想要一些我可以枚举的东西,而无需担心将所有东西都锁定。 是的,有人可能会在我的实现中发现一些可能导致死锁或某些事情(我想)的“bug”,但让我们诚实:当涉及到多线程时,如果您没有正确编写代码,无论如何,它正在陷入僵局。 考虑到这一点,我决定做一个简单的ConcurrentList实现来提供这些基本需求。

对于它的价值:我做了一个基本的测试,将10,000,000项添加到常规List和ConcurrentList中,结果是:

列表完成时间: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
}

试了一会儿 (也是: 在GitHub上 )。 我的实现有一些问题,我不会在这里介绍。 让我告诉你,更重要的是,我学到了什么。

首先,你不可能完全实现无锁和线程安全的IList<T> 。 特别是,随机插入和删除不会起作用,除非你也忘记了O(1)随机存取(即,除非你“欺骗”并且只是使用某种链接列表并让索引吸引)。

认为可能值得的是IList<T>一个线程安全的,有限的子集:特别是一个允许Add并通过索引提供随机只读访问的Insert (但不包含InsertRemoveAt等,还有没有随机访问)。

这是我的ConcurrentList<T>实现的目标。 但是当我在多线程场景中测试它的性能时,我发现简单地同步添加到List<T>更快 。 基本上,添加到List<T>已经很快闪电; 所涉及的计算步骤的复杂性很小(增加一个索引并将其分配给数组中的一个元素; 实际上就是这样 )。 你需要大量的并发写操作才能看到任何种类的锁争用; 即使如此,每次写入的平均性能仍然会在ConcurrentList<T>击败更昂贵但尽管无锁的实现。

在列表的内部阵列需要调整自身大小的相对罕见的事件中,您确实付出了很小的代价。 因此,最终我得出结论:这是一个小众场景,其中只有ConcurrentList<T>集合类型才有意义:当您希望保证每次调用时添加元素的开销较低(因此,与摊销的性能目标相反)。

这不像你想象的那样有用。


I think I don't agree with your generalization. A team isn't just a collection of players. A team has so much more information about it - name, emblem, collection of management/admin staff, collection of coaching crew, then collection of players. So properly, your FootballTeam class should have 3 collections and not itself be a collection; if it is to properly model the real world.

You could consider a PlayerCollection class which like the Specialized StringCollection offers some other facilities - like validation and checks before objects are added to or removed from the internal store.

Perhaps, the notion of a PlayerCollection betters suits your preferred approach?

public class PlayerCollection : Collection<Player> 
{ 
}

And then the FootballTeam can look like this:

public class FootballTeam 
{ 
    public string Name { get; set; }
    public string Location { get; set; }

    public ManagementCollection Management { get; protected set; } = new ManagementCollection();

    public CoachingCollection CoachingCrew { get; protected set; } = new CoachingCollection();

    public PlayerCollection Players { get; protected set; } = new PlayerCollection();
}




c# .net parallel-processing task-parallel-library