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.
