Warum ist List <> .OrderBy LINQ schneller als IComparable + List <> Sortieren im Debug-Modus?

Question

Ich war interessiert, ob es schneller wäre, meine Klassen mit LINQ zu sortieren, oder indem ich die IComparable-Schnittstelle und List.Sort implementiere. Ich war ziemlich überrascht, als der LINQ-Code schneller war.

Um den Test durchzuführen, habe ich eine sehr einfache Klasse mit dem nicht so passenden Namen von TestSort, die IComparable implementiert.

class TestSort: IComparable<TestSort> { 
    private int age; 
    private string givenName; 

    public int Age { 
     get { 
      return age; 
     } 
     set { 
      age = value; 
     } 
    } 

    public string GivenName { 
     get { 
      return givenName; 
     } 
     set { 
      givenName = value; 
     } 
    } 

    public TestSort(int age, string name) { 
     this.age = age; 
     this.givenName = name; 
    } 

    public int CompareTo(TestSort other) { 
     return this.age.CompareTo(other.age); 
    } 
} 

Dann ein einfaches Programm, es oft zu sortieren - die Sorte war viel teurer als die Liste zu kopieren, so dass der Effekt davon ignoriert werden kann.

class Program { 
    static void Main(string[] args) { 
     // Create the test data 
     string name = "Mr. Bob"; 

     Random r = new Random(); 
     var ts2 = new List<TestSort>(); 

     for (int i = 0; i < 100; i++) { 
      ts2.Add(new TestSort(r.Next(), name)); 
     } 

     DateTime start, end; 

     // Test List<>.Sort 
     start = DateTime.Now; 
     for (int i = 0; i < 100000; i++) { 
      var l = ts2.ToList(); 
      l.Sort(); 
     } 
     end = DateTime.Now; 

     Console.WriteLine("IComparable<T>: "); 
     Console.WriteLine((end - start).TotalMilliseconds); 


     // Test Linq OrderBy 
     start = DateTime.Now; 
     for (int i = 0; i < 100000; i++) { 
      var l = ts2.ToList(); 
      l = l.OrderBy(item => item.Age).ToList(); 
     } 
     end = DateTime.Now; 

     Console.WriteLine("\nLINQ: "); 
     Console.WriteLine((end - start).TotalMilliseconds); 

     Console.WriteLine("Finished."); 
     Console.ReadKey(); 
    } 
} 

war ich ziemlich überrascht, die folgende Ausgabe zu erhalten:

IComparable<T>: 
2965.1696 

LINQ: 
2181.1248 

Manchmal würde LINQ unter 2000, gehen und manchmal würde IComparable gehen etwa 3000.

Wenn ich es mit einem normalen getestet List<Int> der List.Sort war 1/4 der Geschwindigkeit von LINQ, die bei etwa 2000 blieb.

Also warum ist LINQ nur ab out 66% die Geschwindigkeit der normalen Art für meine Klasse? Mache ich etwas falsch mit meiner Implementierung von IComparable?

Update: Ich dachte nur, um zu versuchen, es im Release-Modus zu tun, und ja, die Ergebnisse waren unterschiedlich:

IComparable<T>: 
1593.0911 

Linq: 
1958.1119 

Aber ich bin immer noch sehr daran interessiert zu wissen, warum IComparable langsamer im Debug-Modus ist .

Answer 1

Wenn Sie sicherstellen, dass alles vor dem Start der Maßnahme JITed ist, können Sie unterschiedliche Ergebnisse erhalten (ich empfehle auch die Stopwatch-Klasse Zeit zu messen):

var ll = ts2.ToList(); 
ll.Sort(); 
ll.OrderBy(item => item.Age).ToList(); 

Nach meinen Messungen (nach der obigen Zugabe Code), IComparable ist immer schneller (auch im Debug).

Answer 2

Dies könnte der Aufwand für den Aufruf der Methode CompareTo sein, die beim Kompilieren und Ausführen im Freigabemodus durch eine Inline ersetzt würde.

Answer 3

Sortierung verwendet nicht optimierten Quicksort, der im schlimmsten Fall eine n * n Komplexität hat. Ich weiß nicht, welche Reihenfolge verwendet, aber ich weiß, dass es nicht die gleiche Methode verwendet, da es eine stabile Art ist, im Gegensatz zu array.sort.

Answer 4

Für mich werde ich Linq mit IComparable verwenden (wenn dies die meiste oder einzige Art zu sortieren ist). In diesem Fall ist Artikel ein TestSort: IComparable<TestSort>

var sorted = ll.OrderBy(item => item); // This automatically used age to compare, as it's defined in CompareTo 

ll sein kann IEnumerable jede: Liste, Array usw.

Auch in CompareTo Sie mehrere Art und Weise ... zum Beispiel zu vergleichen haben, können Sie tun etwas wie dieses: