CODEWITHSUNDEEP
c#performancestackimmutabilityimmutable-collections
ODotN
ODotN

Reputation: 145

C# ImmutableStack<T> Performance

I have a need to use the System.Collections.Immutable ImmutableStack<T> in my code however I have noticed that there has been some performance hit since using it. I was wondering if there is an alternative to this that could provide a better performance?

I tested Stack<T> vs ImmutableStack<T> with the following

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

On average Stack<T> was about 20%-25% faster than ImmutableStack<T>. I am using this all over my application and so the performance hit takes it's toll. It needs to be a stack and it needs to be immutable. Are there any suggestions as to what could be done to improve this performance?

Upvotes: 2

Views: 543

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726967

Immutability comes with a cost: unlike the regular stack, which is implemented using arrays, immutable stack uses a linked list under the hood. immStack = immStack.Push(i); needs to allocate memory for the new node, which takes asymptotically longer than simply adding a single item to a mutable stack.

You can improve on the timing by allocating arrays of several list nodes, rather than allocating each individual node. This will reduce the allocation hit, but it would not eliminate it completely.

You can also use faux immutability by designing your own immutable interface for the stack, and providing a mutable implementation. The code that needs to modify the stack writes directly to the stack, while the code that is supposed to see immutable stack programs to its immutable interface.

Upvotes: 0

Related Questions