¿Por qué List <>. OrderBy LINQ es más rápido que IComparable + List <>. ¿Ordenar en modo Debug?

Question

Estaba interesado en si sería más rápido ordenar mis clases utilizando LINQ, o implementando la interfaz IComparable y List.Sort. Me sorprendió bastante cuando el código LINQ fue más rápido.

Para hacer la prueba, hice una clase muy simple con el nombre no tan apropiado de TestSort, implementando IComparable.

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); 
    } 
} 

A continuación, un programa simple para solucionar el problema muchas veces - el tipo era mucho más caro que la copia de la lista, por lo que el efecto de que puede ser ignorada.

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(); 
    } 
} 

Me ha sorprendido mucho recibir el siguiente resultado:

IComparable<T>: 
2965.1696 

LINQ: 
2181.1248 

veces LINQ iría por debajo de 2000, y en ocasiones IComparable iría 3000.

Cuando lo probé con una normalidad List<Int> el List.Sort era 1/4 de la velocidad de LINQ, que permaneció en aproximadamente 2000.

¿Por qué LINQ es tan solo ab 66% de la velocidad del tipo normal para mi clase? ¿Estoy haciendo algo mal con mi implementación de IComparable?

Actualización: simplemente pensé que trata de hacerlo en modo de lanzamiento, y sí, los resultados fueron diferentes:

IComparable<T>: 
1593.0911 

Linq: 
1958.1119 

Pero todavía estoy muy interesado en saber qué IComparable es más lenta en el modo de depuración .

Answer 1

Si se asegura de que todo está JITed antes de comenzar la medida, es posible obtener resultados diferentes (también recomiendan el uso de la clase Stopwatch para medir el tiempo):

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

Según mis medidas (después de la adición de los anteriores código), IComparable es siempre más rápido (incluso en depuración).

Answer 2

Esto podría ser la sobrecarga de llamar al método CompareTo que se reemplazará con un en línea al compilar y ejecutar en modo de lanzamiento.

Answer 3

La clase utiliza un quicksort no optimizado, que tiene una complejidad n * n en el peor de los casos. No sé qué orden utiliza pero sé que no utiliza el mismo método ya que es un tipo estable, a diferencia de array.sort.

Answer 4

Para mí, usaré Linq con IComparable (cuando esta es la manera más o la única de ordenar). En este caso, este elemento es un TestSort: IComparable<TestSort>

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

ll puede ser cualquier IEnumerable: Lista, Array, etc.

También en CompareTo se puede tener de forma múltiple para comparar ... por ejemplo, se puede hacer algo como esto:

public int CompareTo(TestSort other) { 
     return this.age != other.age ? this.age.CompareTo(other.age) : this.dateOfBirth.CompareTo(other.dateOfBirth); 
    }