C# 不可变堆栈<T>性能

Question

我需要在我的代码中使用System.Collections.Immutable ImmutableStack<T>，但是我注意到自从使用它以来有一些性能下降。我想知道是否有另一种方法可以提供更好的性能？

我用以下内容测试了Stack<T>与ImmutableStack<T>

        static void Main(string[] args)
        {
            const int c_loopCount = 10000000;
            var watch = new Stopwatch();
            watch.Start();
            ImmutableStack<int> immStack = ImmutableStack<int>.Empty;
            for (int i = 0; i < c_loopCount; i++)
            {
                immStack = immStack.Push(i);
            }
            watch.Stop();
            TimeSpan ts = watch.Elapsed;
            string elapsedTime = $"{ts.Hours:00}:{ts.Minutes:00}:{ts.Seconds:00}.{ts.Milliseconds / 10:00}";
            Console.WriteLine($"ImmutableStack<T> RunTime {elapsedTime}");
            var watch2 = new Stopwatch();
            watch2.Start();
            var normalStack = new Stack<int>();
            for (int i = 0; i < c_loopCount; i++)
            {
                normalStack.Push(i);
            }
            TimeSpan ts2 = watch2.Elapsed;
            string elapsedTime2 = $"{ts2.Hours:00}:{ts2.Minutes:00}:{ts2.Seconds:00}.{ts2.Milliseconds / 10:00}";
            Console.WriteLine($"Stack<T> RunTime {elapsedTime2}");

            Console.ReadLine();
        }

平均而言，Stack<T>比ImmutableStack<T>快约20%-25%。我在我的应用程序中使用它，因此性能下降会付出代价。它需要是一个堆栈，并且需要是不可变的。对于如何提高这种性能，是否有任何建议？

Answer 1

不可变性是有代价的：与使用数组实现的常规堆栈不同，不可变堆栈在后台使用链表。 immStack = immStack.Push(i);需要为新节点分配内存，这比简单地将单个项目添加到可变堆栈需要更长的时间。

您可以通过分配多个列表节点的数组来改进计时，而不是分配每个单独的节点。这将减少分配命中，但不会完全消除它。

您还可以通过为堆栈设计自己的不可变接口并提供可变实现来使用假不可变性。需要修改堆栈的代码直接写入堆栈，而应该看到不可变堆栈的代码将程序编程到其不可变接口。