General performance comparison between ImmutableList and List?

Question

I think ImmutableList is much slower than List in adding and removing an element. Is that right?

Benchmarked. Perforamce of ImmutableList to add and RemoveAt is good. RemoveAt is even faster than List.

    static void Main(string[] args)
    {
        // Generic List Test
        var genericList = new List<int>();

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < 20000; i++)
        {
            genericList.Add(i);
        }
        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.RemoveAt(0);
        }
        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.RemoveAt(0);
        }
        sw.Stop();
        Console.WriteLine("Remove duration for ImmutableList<T>: " + sw.ElapsedMilliseconds);
        Console.WriteLine("Items after remove for ImmutableList<T>: " + immutableList.Count);
    }

Results

Add duration for List<T>: 0
Remove duration for List<T>: 37
Items after remove for List<T>: 0
Add duration for ImmutableList<T>: 22
Remove duration for ImmutableList<T>: 14
Items after remove for ImmutableList<T>: 0

Answer 1

It's honestly a myth that immutability means lacking performance.

I would expect that many operations would be faster with an immutable list.

The implementation of immutable list uses a binary search tree, which has favorable performance characteristics compared to arrays for searches, inserts, and deletes. There still is the overhead from copying that factors into play. So, there will be a tipping point in which one will perform better than the other.

Results from my machine for deletes (Immutable/Regular) milliseconds

     Deletes  100       1000      10000     100000
Count         
 1000         4/0       na        na        na
10000         4/0       5/1       na        na  
  1e5         4/2       5/23      22/215    na  
  1e6         7/44      8/431     37/4676   118/44081 
  1e7         8/718     7/7363    36/77638  110/x*
  1e8         8/7594    9/76200   31/781349 113/x* 

* I didn't have the patience to finish benchmarking here.