上次我们，并了解到类库会为一些特例而使用高性能的排序方式——int数组便是这样一例，因此其性能特别高。不过从数据上看，即便是在普通的情况下，Array.Sort<T>的性能也比LINQ排序要高。不过也有朋友从测试中得出的结论正好相反，这又是为什么呢？那么现在，我们再来分析一下LINQ排序的实现方式吧，希望这样可以了解到两者性能差别的秘密。
只可惜，LINQ排序的代码在System.Core.dll程序集中，微软没有发布这部分源代码，我们只得使用.NET Reflector来一探究竟了。
所谓LINQ排序，便是使用定义在System.Linq.Enumerable类中的几个扩展方法，它们是：
public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>( this IEnumerable<TSource> source, Func<TSource, TKey> keySelector); public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>( this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer); public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey>( this IEnumerable<TSource> source, Func<TSource, TKey> keySelector); public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey>( this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer);
为了使用时的方便，我往往会补充一些额外的接口，例如：
public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>( this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, bool decending) { return decending ? source.OrderByDescending(keySelector) : source.OrderBy(keySelector); }
这样在使用时，便可以使用一个布尔值来表示排序的方向（升序或是降序）而不需要从两个方法之间“手动”选择一个。此外，构造一个IComparer<TKey>类型也实在有些麻烦，于是我按照Array.Sort<T>的做法重新继续扩展了一个使用委托对象作为“比较器”的接口：
public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>( this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Comparison<TKey> compare, bool decending) { return decending ? source.OrderByDescending(keySelector, new FunctorComparer<TKey>(compare)) : source.OrderBy(keySelector, new FunctorComparer<TKey>(compare)); }
至于FunctorComparer类的实现，由于过于简单就省略了吧，贴出来也只是占用地方而已。有了这个接口，在排序的时候我们就可以这样使用了：
employee.OrderBy(p => p.Manager, (m1, m2) => ... /* 比较逻辑 */, false);
不过，无论是哪个接口、重载还是扩展，它的（除this外）的{dy}个参数便是keySelector，它的含义便是选择（select）出排序的“依据”。这个参数不可省略（除非您提供扩展），因此即便是int数组这样的类型，需要排序时也必须指定“自己”为排序依据：
intArray.OrderBy(i => i);
这也是LINQ排序和Array.Sort<T>的本质区别之一。
无论是哪个接口，最终创建的都是OrderedEnumerable<TElement, TKey>类型，例如：
public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>( this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) { return new OrderedEnumerable<TSource, TKey>(source, keySelector, null, false); }
OrderedEnumerable<TElement, TKey>的含义是“根据TKey排序TElement序列的结果”，它的构造函数仅仅是保留传入的参数：
internal OrderedEnumerable( IEnumerable<TElement> source, Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending) { // 省略参数校验 base.source = source; this.parent = null; this.keySelector = keySelector; this.comparer = (comparer != null) ? comparer : ((IComparer<TKey>) Comparer<TKey>.Default); this.descending = descending; }
可见，如果您没有提供比较器，类库会自动选用Comparer<TKey>.Default进行比较。这个类会尽可能地寻找可用的比较方式，在“万不得已”的情况下只得跑出异常。如果您对它的实现感兴趣可以自行阅读代码——甚至无需使用.NET Reflector。
事实上，在OrderedEnumerable<TElement, TKey>中并没有提供排序等关键性功能，它只是override了基类的GetEnumerableSorter方法，用于提供一个“排序器”。它的基类是OrderdEnumerable<TElement>，其含义是“排序TElement序列的结果”，它并不涉及到“排序方式”，而只是提供了一个抽象方法用于获得一个“排序器”——没错，这就是它的子类，如OrderedEnumerable<TElement, TKey>的职责了（还记得TKey的含义吗：“根据TKey进行排序”）。
不过，事实上除了OrderdEnumerable<TElement, TKey>以外也没有其他子类了，由于这些都是internal类型，因此我认为这样有些“过渡设计”。根据我们昨天“人肉反编译”的结果，可以得到OrderedEnumerable<TElement>的完整实现：
internal abstract class OrderedEnumerable<TElement> : IEnumerable<TElement>... { internal IEnumerable<TElement> source; internal abstract EnumerableSorter<TElement> GetEnumerableSorter(EnumerableSorter<TElement> next); public IEnumerator<TElement> GetEnumerator() { var buffer = new Buffer<TElement>(this.source); if (buffer.count <= 0) yield break; var sorter = this.GetEnumerableSorter(null); var map = sorter.Sort(buffer.items, buffer.count); for (var i = 0; i < buffer.count; i++) { yield return buffer.items[map[i]]; } } ... }
与我们平时接触到的排序算法不同，EnumerableSorter的Sort方法并不改变原数组，它只是生成根据buffer.items数组生成一个排序之后的“下标序列”——即map数组。当外部需要输出排序后的序列时，OrderedEnumerable<TElement>才会根据map中的下标顺序，依次输出buffer.items数组中的元素。
请注意，到目前为止我们还是没有接触到最终的排序实现。换句话说，现在我们还是不清楚LINQ排序性能高（或低）的关键。
LINQ排序的实现关键还是在于EnumerableSorter<TElement>，我们且看其Sort代码：
internal abstract class EnumerableSorter<TElement> { internal abstract int CompareKeys(int index1, int index2); internal abstract void ComputeKeys(TElement[] elements, int count); private void QuickSort(int[] map, int left, int right) { ... } internal int[] Sort(TElement[] elements, int count) { this.ComputeKeys(elements, count); int[] map = new int[count]; for (int i = 0; i < count; i++) { map[i] = i; } this.QuickSort(map, 0, count - 1); return map; } }
从之前的分析中得知，Sort方法的作用是返回一个排好序的下标数组。它会调用ComputeKeys抽象方法“事先”进行Key（也就是排序依据）的计算。然后再使用快速排序来排序map数组。在QuickSort中，它使用CompareKeys方法来获得“两个下标”所对应的元素的先后顺序。xx而已，没什么特别的。甚至我在这里都不打算分析ComputeKeys和CompareKeys两个方法的实现，因为他们实在过于直接：前者会把source序列中的元素依次调用keySelector委托，以此获得一个与source对应的TKey数组，而后者便是根据传入的下标来比较TKey数组中对应的两个元素的大小。
不过，我还是强烈建议您阅读一下EnumerableSorter<TElement>及其子类EnumerableSorter<TElement, TKey>的实现，以此了解LINQ to Object是如何优雅地支持以下表达式的：
var sorted = from p in people orderby p.Age orderby p.ID descending select p;
这个表达式的含义是“将Person序列首先根据Age属性进行升序排列，如果Age相同则再根据ID降序排”——类库在实现时使用了类似于“职责链模式”的做法，颇为美观。
如果您仔细阅读EnuerableSorter的QuickSort方法，会发现它使用的快速排序算法并不“标准”。快速排序的性能关键之一是选择合适的pivot元素，但是QuickSort方法总是选择最中间的元素——(left + right) / 2。此外，它也没有在元素小于一定阈值时使用xxx的插入排序。因此，从理论上来说，QuickSort方法使用的快速排序算法，其性能不如Array.Sort<T>。
不过，根据姜敏兄的测试结果，LINQ排序的性能超过Array.Sort<T>，这又是怎么回事呢？事实上，虽然姜兄的这个测试存在很大的问题（代码写错了），{zh1}得到的结论“性能高低和元素类型有关”的结论也不确切，但是它也的确能体现一些问题。这个问题事实上已经由老大解释过了，不过为了信息完整思维连贯，我在这里再进行详细说明一下。
从理论上来说，Array.Sort<T>和LINQ排序的时间复杂度是相同的，因此性能“似乎不会有太大不同”，但是从实验结果上看差距还是十分明显的。因为从实际上看，Array.Sort<T>对于特殊类型有特殊处理，此外LINQ排序会有复制元素的开销，因此我之前我认为“找不到LINQ排序的性能有优势的理由”。可惜这句话已经站不住脚了，我们来观察一下两种排序方式在实现上的主要区别：
- Array.Sort<T>：使用IComparer<T>对象比较两个元素的大小。
- LINQ排序：首先根据keySelector获得TKey序列，然后在排序时使用IComparer<TKey>比较两个TKey元素的大小。
那么，以此您是否可以判断出以下两个排序方法的性能高低？
public class Person { public int Age { get; set; } } public class PersonComparer : IComparer<Person> { public int Compare(Person x, Person y) { return x.Age - y.Age; } }
Person[] people = ... var byLinq = people.OrderBy(p => p.Age).ToList(); var byArray = Array.Sort(people, new PersonComparer());
在实际测试之前我无法做出判断，因为它们其实各有千秋：
- Array.Sort<T>：虽然不需要进行额外的元素复制，但是调用PersonComparer.Compare方法的开销较大——访问Age属性相当于调用get_Age方法。
- LINQ排序：虽然需要进行额外的元素复制，而且需要事先计算出排序用的键值（Age属性），但是在排序时只需直接比较int即可，效率较高。
这其实也就是某些测试中发现LINQ排序性能较高的“秘密”。为什么同样排序Person序列时，我的测试（）表明Array.Sort<T>较快，而其他一些朋友却得到LINQ排序较快的结果呢？这是因为我的Person类直接使用了公开字段而不是属性，这样避免了方法调用的开销。此外，另一些朋友的PersonComparer在比较两个int时使用了x.Age.CompareTo方法——这又比直接进行int减法要慢上一些了。
那么，还有影响两者性能的因素吗？我们有办法提高数组排序的性能吗？毕竟很多时候我们需要直接排序，而不是生成新的序列。下次我们再来讨论这些问题吧。
- 数组排序方法的性能比较（3）：LINQ排序实现分析
2010-01-27 00:41
有些细节描述好像不太对。一般调用getter都是被内联掉了的。CLRv2对小的、直线型、非虚方法会很“照顾”，如果是在循环中调用这样的方法会更加“照顾”。而自动生成的getter里就是一个成员变量访问+一个返回，除非作为某个基类型的虚属性的override实现，或者被打上了noinline标记，不然肯定是被内联的。using System; using System.Runtime.CompilerServices; namespace TestCLRv2JITInlinePropertyAccess { public class Person { public int _age; public int Age { get { return _age; } set { _age = value; } } } static class Program { [MethodImpl(MethodImplOptions.NoInlining)] static int Foo(Person p) { return p.Age; } [MethodImpl(MethodImplOptions.NoInlining)] static int Bar(Person p) { return p._age; } static void Main(string[] args) { var p = new Person(); Console.WriteLine(p.Age); Foo(p); Bar(p); } } }这里的Foo和Bar分别是：
是一样的对吧？
2010-01-27 00:54
老赵最近关注性能了 以前也做过不少测试 List<T> HashTable 等等 感觉各有有点吧 用的地方不一样 跟string 和 stringBuilder类似 ，最近想采用asp.net mvc和Linq 进行开发，老赵有推荐的demo或者开源代码么，我在codeplex上找了几个，感觉不太合适。[楼主] 2010-01-27 00:56
RednaxelaFX但实际测试Age是属性还是字段对性能有明显影响的说。
不知道是不是记错了，明天我试验一下吧。
[楼主] 2010-01-27 00:57
Leon Weng性能测试其实也不好说，比如现在这个明显是分情况有不同说法的。
如果int或Person类随便选一个，就算两个都选也不一定能得到正确结果的……
2010-01-27 01:01
哎 写错了应该是string的"+"和"apend()"2010-01-27 01:07
测试图个真实 公开字段用的频率远没有属性高吧2010-01-27 01:26
Int32.CompareTo()倒是确实比直接减一下“慢一些”using System; using System.Runtime.CompilerServices; namespace TestCLRv2JITInlinePropertyAccess { public class Person { public int _age; public int Age { get { return _age; } set { _age = value; } } } static class Program { [MethodImpl(MethodImplOptions.NoInlining)] static int Compare1(Person p1, Person p2) { return p1.Age.CompareTo(p2.Age); } [MethodImpl(MethodImplOptions.NoInlining)] static int Compare2(Person p1, Person p2) { if (p1.Age < p2.Age) return -1; if (p1.Age > p2.Age) return 1; return 0; } [MethodImpl(MethodImplOptions.NoInlining)] static int Compare3(Person p1, Person p2) { return p1.Age - p2.Age; } static void Main(string[] args) { var p = new Person(); Console.WriteLine(p.Age); Compare1(p, p); Compare2(p, p); Compare3(p, p); } } }其中的Compare1,2,3分别是：
Compare2()是我手动把Int32.CompareTo()内联到Compare1()的版本。试了会儿没能把两个版本调到xx一样……CLRv2的内联器看来还有点不顺，生成了少量无意义的代码。Anyway，可以看到这三个版本里get_Age()都是被内联了的，但要把比较值映射到-1、0、1上要比直接减多干点活儿。
不过这个差异到底在测试中占了多少分量我没把握……
2010-01-27 01:42
我访问博客园这么慢呀怎么，热了。RednaxelaFX的每个评论都很猛呀
2010-01-27 01:59
我只是贴了JIT后的机器码及其汇编而已……没技术含量的。要得到同样的信息很简单：
1、打开VS2008，建一个C#的命令行应用工程；
2、复制上面的代码；
3、确认在主菜单的Tools -> Options... -> Debugging -> Suppress JIT optimization on module load (Managed only)前的勾是去掉的；
4、在project的属性里，把Debug -> Enable unmanaged code debugging前的勾打上；
5、在要分析的方法的开始处设断点；
6、按F5或者那个绿色箭头执行程序，到断点之后，在Immediate Window里输入.load sos
7、在Registers窗口里复制下EIP的值，然后在Immediate Window输入!u 01B70129 （!u后的数字替换为EIP的实际值）；
8、应该能看到那个方法的机器码与汇编了。
只是机械性的完成了这些步骤而已……真正有技术含量的是后续的分析。这个还是交给老赵了，我提供炮弹。阅读别人的评测与分析后的好习惯是自己也动手做一做，看看能否得到一致的、可重复的结果。
2010-01-27 02:12
我调试的结果和RednaxelaFX一样，属性被内联了。并且我在老赵给出的测试代码中新加了一个xx用属性的Person类，测试结果也表明用属性和用字段进行linq排序的性能没有明显的区别，xx可以忽略它们之间的性能差别。
2010-01-27 02:13
恩，谢谢，我会在vs里加载sos和执行!u，就是还不太会看，呵呵。看个IL还凑合，汇编看不懂ing。
最近老赵更新了很多，还没来得及细看，抽空补补。
看你的评论很长知识呀。
2010-01-27 02:20
就目前讨论的问题来说，xx没必要看懂汇编语言。只要能明白属性在JIT时被内联了就行。
有两点都可以证明这个结论：1，访问属性和访问字段的方法JIT后的汇编xx一样；2,按理说访问属性其实是方法调用，但是汇编中没出现call指令，那么合理的解释应该是被调方法体已经内联进了调用方法体中。