Why is List<>.OrderBy LINQ faster than ICompara

问题:

I was interested in whether it would be faster to sort my classes using LINQ, or by implementing the IComparable interface and List.Sort. I was quite surprised when the LINQ code was faster.

To do the test, I made a very simple class with the not-so-apt name of TestSort, implementing 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);
    }
}

Then a simple program to sort it many times - the sort was much more expensive than copying the list, so the effect of that can be ignored.

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

I was quite surprised to receive the following output:

IComparable<T>:
2965.1696

LINQ:
2181.1248

Sometimes LINQ would go below 2000, and sometimes IComparable would go about 3000.

When I tested it with a normal List<Int> the List.Sort was 1/4 the speed of LINQ, which remained at about 2000.

So why is LINQ only about 66% the speed of the normal sort for my class? Am I doing something wrong with my implementation of IComparable?

Update: I just thought to try doing it in release mode, and yes, the results were different:

IComparable<T>:
1593.0911

Linq:
1958.1119

But I am still very interested to know why IComparable is slower in debug mode.

回答1:

If you make sure everything is JITed before starting the measure, you might get different results (I also recommend using the Stopwatch class to measure time):

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

According to my measurements (after adding the above code), IComparable is always faster (even in debug).

回答2:

Sort uses unoptimized quicksort, which has a n*n complexity in its worst case. I don't know what orderby uses but I know it doesn't use the same method since it's a stable sort, unlike array.sort.

回答3:

For me, I will use Linq with IComparable(when this is the most or only way to sort). In this case, item is a TestSort: IComparable<TestSort>

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

ll can be any IEnumerable: List, Array, etc.

Also in CompareTo you can have multiple way to compare... for instance, you can do something like this:

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

回答4:

This could it be the overhead of calling the method CompareTo which would be replaced with an inline when compile and run in release mode.