Allgemeiner Leistungsvergleich zwischen ImmutableList und List?

Question

Ich denke, ImmutableList ist viel langsamer als List beim Hinzufügen und Entfernen eines Elements. Ist das richtig?

Benchmarked. Perforamce of ImmutableList zum Hinzufügen und RemoveAt ist gut. RemoveAt ist sogar schneller als 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); 
    } 

Ergebnisse

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

Es ist ehrlich gesagt ein Mythos, dass Unveränderlichkeit mangelnde Leistung bedeutet.

Ich würde erwarten, dass viele Operationen mit einer unveränderlichen Liste schneller wären.

Die Implementierung der unveränderlichen Liste verwendet einen binären Suchbaum, der im Vergleich zu Arrays für Suchen, Einfügungen und Löschvorgänge günstige Leistungsmerkmale aufweist. Es gibt immer noch den Aufwand, diese Faktoren ins Spiel zu bringen. Es wird also einen Wendepunkt geben, in dem man besser als der andere ist.

Ergebnisse von meiner Maschine für Löschungen (Immutable/Regular) Millisekunden

 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. 

Answer 2

Von MSDN

Wenn Sie Elemente aus einer unveränderlichen Liste hinzuzufügen oder zu entfernen, wird eine Kopie der ursprünglichen Liste wird mit den Einzelteilen hinzugefügt oder entfernt gemacht, und Die ursprüngliche Liste ist unverändert.

Wegen der Kopie wird es langsamer.