当不可变集合比并发更可取时

Question

最近阅读了有关不可变集合的内容。当读取操作比写入更频繁地执行时，建议将它们用作读取的线程安全。

然后我想测试读取性能 ImmutableDictionary 与 ConcurrentDictionary。这是这个非常简单的测试（在 .NET Core 2.1 中）：

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Diagnostics;
using System.Linq;
using System.Threading.Tasks;

namespace ImmutableSpeedTests
{
    class Program
    {
        public class ConcurrentVsImmutable
        {
            public int ValuesCount;
            public int ThreadsCount;

            private ImmutableDictionary<int, int> immutable = ImmutableDictionary<int, int>.Empty;
            private ConcurrentDictionary<int, int> concurrent = new ConcurrentDictionary<int, int>();

            public ConcurrentVsImmutable(int valuesCount, int threadsCount)
            {
                ValuesCount = valuesCount;
                ThreadsCount = threadsCount;
            }

            public void Setup()
            {
                // fill both collections. I don't measure time cause immutable is filling much slower obviously.
                for (var i = 0; i < ValuesCount; i++)
                {
                    concurrent[i] = i;
                    immutable = immutable.Add(i, i);
                }
            }

            public async Task<long> ImmutableSum() => await Sum(immutable);

            public async Task<long> ConcurrentSum() => await Sum(concurrent);

            private async Task<long> Sum(IReadOnlyDictionary<int, int> dic)
            {
                var tasks = new List<Task<long>>();

                // main job. Run multiple tasks to sum all values.
                for (var i = 0; i < ThreadsCount; i++)
                    tasks.Add(Task.Run(() =>
                    {
                        long x = 0;
                        foreach (var key in dic.Keys)
                        {
                            x += dic[key];
                        }
                        return x;
                    }));

                var result = await Task.WhenAll(tasks.ToArray());
                return result.Sum();
            }
        }

        static void Main(string[] args)
        {
            var test = new ConcurrentVsImmutable(1000000, 4);

            test.Setup();

            var sw = new Stopwatch();

            sw.Start();
            var result = test.ConcurrentSum().Result;
            sw.Stop();

            // Convince that the result of the work is the same
            Console.WriteLine($"Concurrent. Result: {result}. Elapsed: {sw.ElapsedTicks}.");

            sw.Reset();
            sw.Start();
            result = test.ImmutableSum().Result;
            sw.Stop();

            Console.WriteLine($" Immutable. Result: {result}. Elapsed: {sw.ElapsedTicks}.");

            Console.ReadLine();
        }
    }
}

您可以运行此代码。以滴答为单位的经过时间会不时不同，但 ConcurrentDictionary 花费的时间比 ImmutableDictionary 花费的时间少几倍。

这个实验让我很尴尬。我做错了吗？如果我们有并发，为什么要使用不可变集合？什么时候更受欢迎？

Answer 1

不可变集合不能替代并发集合。它们旨在减少内存消耗的方式必然会更慢，这里的权衡是使用更少的内存，因此使用更少的 n 操作来做任何事情。

我们通常将集合复制到其他集合以实现持久状态的不变性。让我们看看这意味着什么，

 var s1 = ImmutableStack<int>.Empty;
 var s2 = s1.Push(1);
 // s2 = [1]

 var s3 = s2.Push(2);
 // s2 = [1]
 // s3 = [1,2]

 // notice that s2 has only one item, it is not modified..

 var s4 = s3.Pop(ref var i);

 // s2 = [1];
 // still s2 has one item...

请注意，s2 始终只有一项。即使删除所有项目。

所有数据在内部存储的方式是一棵巨大的树，您的集合指向一个分支，该分支具有代表树初始状态的后代。

我认为性能无法与目标完全不同的并发收集相匹配。

在并发集合中，所有线程都访问一个集合副本。

在不可变集合中，您实际上拥有一棵树的孤立副本，导航该树总是代价高昂。

它在事务系统中很有用，如果必须回滚事务，集合状态可以保留在提交点中。

Answer 2

这是 made before 的批评。

正如 Akash 所说，ImmutableDictionary 使用内部树而不是哈希集。

其中一个方面是，如果您一步构建字典而不是迭代添加所有键，则可以略微提高性能：

  immutable = concurrent.ToImmutableDictionary();

枚举哈希集和平衡树都是O(n)操作。对于不同的容器大小，我在单个线程上取了几次运行的平均值，并得到了与此一致的结果：

我不知道为什么不变的斜率要陡峭 6 倍。现在我只是假设它在做棘手的非阻塞树的事情。我假设此 class 将针对随机存储和读取而不是枚举进行优化。

为了确定 ImmutableDictionary 在哪些场景中获胜，我们需要包装一个并发字典以提供一定程度的不变性，并在面对 class 的级别时测试两个 classes =38=]争.

这不是一个严肃的建议，但与您的测试相对应的是，通过比较 "cheat" 多次迭代 使用不变性：

        private ConcurrentDictionary<object, long> cache = new ConcurrentDictionary<object, long>();
        public long ImmutableSum() 
        {
            return cache.GetOrAdd(immutable, (obj) => (obj as ImmutableDictionary<int, int>).Sum(kvp => (long)kvp.Value));                
        }

        public long ConcurrentSum() => concurrent.Sum(kvp => (long)kvp.Value);

这对随后对未更改集合求和的调用产生了很大的影响！

Answer 3

两者并不相互排斥。我两个都用。

如果您的字典很小，ImmutableDictionary 的读取性能将优于 ConcurrentDictionary，因为 K1*Log(N) < K2 其中 Log(N) < K2/K1（当哈希table开销比树遍历还差。

我个人发现 Immutable 集合的写语义比并发集合的写语义更容易理解，因为它们往往更一致，尤其是在处理 AddOrUpdate() 和 GetOrAdd() 时。

在实践中，我发现在很多情况下，我有很多小的（或空的）词典更适合作为 ImmutableDictionary 和一些较大的词典，需要使用ConcurrentDictionary.

话虽如此，如果它们很小，那么您使用什么并没有多大区别。关于 Peter Wishart 的回答，ImmutableDictionary 的枚举性能高于 ConcurrentDictionary（对于合理的 N），因为树遍历在现代缓存架构的内存延迟方面是残酷的。

当不可变集合比并发更可取时

When immutable collections are preferable than concurrent

c#

.net

concurrency

concurrent-collections

immutable-collections