5

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

然后我想测试读取性能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。

这个实验让我很尴尬。我做错了吗？如果我们有并发，使用不可变集合的原因是什么？什么时候更可取？

4

3 回答 3

5

不可变集合不能替代并发集合。并且它们旨在减少内存消耗的方式，它们必然会更慢，这里的权衡是使用更少的内存，因此使用更少的 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 始终只有一项。即使所有项目都被删除。

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

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

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

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

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

于 2018-10-01T05:23:18.457 回答
2

这是以前提出 的批评。

正如 Akash 已经说过的，ImmutableDictionary使用内部树而不是哈希集。

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

  immutable = concurrent.ToImmutableDictionary();

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

滴答计数与集合大小的关系图

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

为了确定在哪些场景中ImmutableDictionary胜出，我们需要包装一个并发字典以提供某种程度的不变性，并在面对读/写争用级别时测试这两个类。

不是一个严肃的建议，但与您的测试相反的是，通过比较使用不变性在多次迭代中“作弊” ：

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

这对后续调用对未更改的集合求和产生了很大的不同！

于 2018-10-01T12:02:49.430 回答
1

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

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

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

在实践中，我发现在很多情况下，我有大量更适合作为 ImmutableDictionary 的小型（或空）字典，以及一些需要使用 ConcurrentDictionary 的大型字典。

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

于 2021-12-27T09:05:28.967 回答