Slow performance from ImmutableList<T> Remove method in Microsoft.Bcl.Immutable
c#, immutability, immutablelist, performance
Solution
The `Remove` method has to scan the entire list to find the element to remove. The removal itself is O(1) because only the last element needs to be popped off. Both algorithms have quadratic performance.
Why the enormous difference in run time? Probably, because `ImmutableList` is a tree structure internally. This means that to scan the list there are high amounts of pointer dereferencing and unpredictable branches and memory accesses. That is very slow.
Problem
Experiencing some unexpected performance from Microsoft `ImmutableList` from NuGet package Microsoft.Bcl.Immutable version 1.0.34 and also 1.1.22-beta When removing items from the immutable list the performance is very slow. For an `ImmutableList` containing 20000 integer values (1...20000) if starting to remove from value 20000 to 1 it takes about 52 seconds to remove all items from the list. If I do the same with a generic `List<T>` where I create a copy of the list after each remove operation it takes about 500 ms. I was a bit surprised by these results since I thought the `ImmutableList` would be faster than copying a generic `List<T>`, but perhaps this is to be expected? Example Code ``` // Generic List Test var genericList = new List<int>(); var sw = Stopwatch.StartNew(); for (int i = 0; i < 20000; i++) { genericList.Add(i); genericList = new List<int>(genericList); } sw.Stop(); Console.WriteLine("Add duration for List<T>: " + sw.ElapsedMilliseconds); IList<int> completeList = new List<int>(genericList); sw.Restart(); // Remove from 20000 -> 0. for (int i = completeList.Count - 1; i >= 0; i--) { genericList.Remove(completeList[i]); genericList = new List<int>(genericList); } sw.Stop(); Console.WriteLine("Remove duration for List<T>: " + sw.ElapsedMilliseconds); Console.WriteLine("Items after remove for List<T>: " + genericList.Count); // ImmutableList Test var immutableList = ImmutableList<int>.Empty; sw.Restart(); for (int i = 0; i < 20000; i++) { immutableList = immutableList.Add(i); } sw.Stop(); Console.WriteLine("Add duration for ImmutableList<T>: " + sw.ElapsedMilliseconds); sw.Restart(); // Remove from 20000 -> 0. for (int i = completeList.Count - 1; i >= 0; i--) { immutableList = immutableList.Remove(completeList[i]); } sw.Stop(); Console.WriteLine("Remove duration for ImmutableList<T>: " + sw.ElapsedMilliseconds); Console.WriteLine("Items after remove for ImmutableList<T>: " + immutableList.Count); ``` Update If removing items from the start of the `ImmutableList`, like with a normal foreach loop, then performance is a lot better. Removing all items then takes less than 100 ms. This is not something you can do in all scenarios, but can be good to know.