经常看到有人因为使用.net中的集合类处理海量数据时性能不够理想，就武断的得出.net不行，c#也不行这样的结论。对于.net framework这样的类库来说，除了性能以外，通用性和安全性同样重要，而为了后者，有时就不得不牺牲性能。如果你的程序核心就是处理大量数据集合，并且对.net内置类库性能不满意，那么这时候就应该考虑为特定类型实现一个优化的版本了。
事情的由来是我需要对若干个（<10）集合进行排序，每个集合中的元素不会超过2k，老实说，所要处理的数据并不多，但我希望在1ms之内完成所有操作，这就成了挑战。也许有人觉得1ms的要求有些苛刻，但对我的应用来说，1ms已经很些奢侈了. 所要处理的数据非常简单，大部分都是一些数据集对象，每个对象都有一个uint类型的id，并以此为key进行排序：
- public class KeyValuePair
- {
- public uint id;
- public string s = string.Empty;
- public float d;
- public double c;
- }
复制代码
集合大小是不固定的，List自然就是最合适的容器，并且有现成的方法用于排序List.Sort()。我使用了以Comparison委托为参数的版本，并定义了如下函数：
- public static int Compare(KeyValuePair v1,KeyValuePair v2)
- {
- return v1.id.CompareTo(v2.id);
- }
复制代码
我知道，这是一个非常不规范的Comparison定义，应该先检查对象是否为null等等。不过这里只是测试而已，我只想看看List.Sort最快能到什么程度。测试数据为一个有5k元素的List，和5个每个有1k元素的List。通过多次测试，以减少噪音干扰，结果都在2～3ms之间，令人印象非常深刻，足以满足大部份应用的需求。可惜对我的目标来说，还是差了一点。
于是我决定自己写一个函数。List.Sort内部使用了Array.Sort，而后者的实现则是传统快速排序（quicksort）算法。在众所周知的几种排序算法中，quicksort是平均情况下最好的，因此我将仍旧使用这一算法，只是删除List.Sort内一些不必要的检查。代码如下：
- public static void QuickSort(List<KeyValuePair> list, int start,int end)
- {
- if (end <= start)
- return;
- int pivotIndex = FindPivot(list, start, end);
- swap(list, pivotIndex, end);
- int k = Partition(list, start, end, list[end].id);
- swap(list, k, end);
- QuickSort(list, start, k - 1);
- QuickSort(list, k + 1, end);
- }
- public static int Partition(List<KeyValuePair> list, int start, int end, uint piovtValue)
- {
- start--;
- while (true)
- {
- do { start++; }
- while (list[start].id < piovtValue);
- if (start > end)
- break;
- do { end--; }
- while (end > 0 && list[end].id > piovtValue);
- if (start > end)
- break;
- swap(list, start, end);
- }
- return start;
- }
- public static int FindPivot(List<KeyValuePair> list, int start, int end)
- {
- int a = (int)list[start].id;
- int b = (int)list[end].id;
- int middle = (start+end)/2;
- int c = (int)list[middle].id;
- if ((a - b) * (a - c) < 0)
- return start;
- if ((b - a) * (b - c) < 0)
- return end;
- return middle;
- }
- public static void swap(List<KeyValuePair> list, int a, int b)
- {
- KeyValuePair temp = list[a];
- list[a] = list;
- list = temp;
- }
复制代码
这里并没有使用任何特别的技巧，几乎是按数据结构书中的例子照搬过来。它的性能如何呢？以下是测试结果：
list size list.sort myQuickSort
5k 2ms 4ms
10k 6ms 5ms
100k 58ms 26ms
200k 132ms 58ms
非常有趣，当列表元素小于10k时，list.sort比myQuickSort快，而随着元素的增加，myQuickSort将快2～4倍。第二种情况是意料之中的，用reflector查看list.sort的源码就能发现，我的quickSort实现显然要简洁很多。但为什么当元素不多时，会出现如此明显的反差呢？起初我尝试用DotTrace分析两个函数所执行的时间，不幸的是由于此时数据太少，排序执行的太快，DotTrace分析的结果是完全错误的: 总是显示quickSort比list.sort所用的时间少。看来只有查看IL了，于是以下代码引起了我的注意：
IL_0002: callvirt instance !0 class [mscorlib]System.Collections.Generic.List`1<class Console4Test.KeyValuePair>::get_Item(int32)
这是swap函数中，访问列表元素所产生的代码。过去，我一直认为访问list元素和访问数组元素是相同的，此时，我开始有所怀疑了。居然出现了callvirt这样的指令，虽然在IL中，callvirt并不意味着一定是虚函数调用，reflector也证明List.get_item并不是一个虚方法。直觉告诉我应该对这行代码深究下去，看看JIT究竟把它编译为了什么样的指令：
- swap(list, k, end);
- 000000c7 cmp eax,dword ptr [esi+0Ch]
- 000000ca jb 000000D1
- 000000cc call 787E9A3C
- 000000d1 mov eax,dword ptr [ebp-14h]
- 000000d4 mov edx,dword ptr [esi+4]
- 000000d7 cmp eax,dword ptr [edx+4]
- 000000da jae 0000015E
- 000000e0 mov eax,dword ptr [edx+eax*4+0Ch]
- 000000e4 mov dword ptr [ebp-20h],eax
- 000000e7 cmp edi,dword ptr [esi+0Ch]
- 000000ea jb 000000F1
- 000000ec call 787E9A3C
- 000000f1 mov eax,dword ptr [esi+4]
- 000000f4 cmp edi,dword ptr [eax+4]
- 000000f7 jae 0000015E
- 000000f9 mov eax,dword ptr [eax+edi*4+0Ch]
- 000000fd mov dword ptr [ebp-24h],eax
- 00000100 mov eax,dword ptr [ebp-14h]
- 00000103 cmp eax,dword ptr [esi+0Ch]
- 00000106 jb 0000010D
- 00000108 call 787E9A3C
- 0000010d mov ecx,dword ptr [esi+4]
- 00000110 push dword ptr [ebp-24h]
- 00000113 mov edx,dword ptr [ebp-14h]
- 00000116 call 78F1B384
- 0000011b inc dword ptr [esi+10h]
- 0000011e cmp edi,dword ptr [esi+0Ch]
- 00000121 jb 00000128
- 00000123 call 787E9A3C
- 00000128 mov ecx,dword ptr [esi+4]
- 0000012b push dword ptr [ebp-20h]
- 0000012e mov edx,edi
- 00000130 call 78F1B384
- 00000135 inc dword ptr [esi+10h]
复制代码
这段代码确实让人有些惊奇。首先，swap函数被内联了，这正是我们所希望的；其次，list元素访问也被正确内联了，没有发生我们之前担心的函数调用。这里确实有几条call指令，不过这是在发生异常才会调用的地址。另外，虽然这里没有列出，但值得一提的是FindPivot中的list元素访问则没有内联，每次访问list元素都意味着执行一次函数调用以及这个函数中的16条汇编指令。 最后，2个简单的list元素交换竟然产生了30条以上的汇编代码，我想这也是所有人所料未及的。
看来list元素访问确实是一个潜在的问题。为了证明这一点，我把quickSort中，所有list都改为了array。再次测试，果然，我自己的版本无论在任何情况下都比list.sort快，同时，也比array.sort快。这里不再列出实际的测试数据，只贴出array版本的swap汇编代码：
- swap(list, k, end);
- 00000070 cmp eax,dword ptr [esi+4]
- 00000073 jae 000000BE
- 00000075 mov eax,dword ptr [esi+eax*4+0Ch]
- 00000079 mov dword ptr [ebp-1Ch],eax
- 0000007c mov ecx,dword ptr [esi+edi*4+0Ch]
- 00000080 mov eax,dword ptr [ebp-10h]
- 00000083 lea edx,[esi+eax*4+0Ch]
- 00000087 call 78F11F98
- 0000008c push dword ptr [ebp-1Ch]
- 0000008f mov edx,edi
- 00000091 mov ecx,esi
- 00000093 call 78F1B384
复制代码
可以看到，代码减少为了原来的1/3。两个call同样是.net内部的一些安全检查代码。
好了，现在知道我的代码慢在哪里了，但这并不能解释list.sort为什么在元素少的时候比较快，难道它不受list元素访问效率的影响吗？是的，list本身并不会受到自身元素访问机制的影响，因为他调用Array.sort时，传递的是内部储存的私有元素数组成员，而不是他自己。因此，可以猜测，当元素较少时，排序算法执行的非常快，此时，元素访问方式的不同，就成了明显的瓶颈，而当处理元素较多时，大部分时间都用在排序上，元素访问的代价则逐渐变小。
以上手写的quickSort方法还能进一步优化吗？显然是可以的：
1，当quickSort中的分组元素小于10时，改用插入排序,可以带来大约5~10%的性能提升:
- public static void QuickSort(List<KeyValuePair> list, int start,int end)
- {
- if (end <= start)
- return;
- int pivotIndex = FindPivot(list, start, end);
- swap(list, pivotIndex, end);
- int k = Partition(list, start, end, list[end].id);
- swap(list, k, end);
- if (k - start <= 10)
- InsertSort(list, start, k - 1);
- else
- QuickSort(list, start, k - 1);
- if (end - k - 1 <= 10)
- InsertSort(list, start, k - 1);
- else
- QuickSort(list, k + 1, end);
- }
复制代码
2，把FindPivot函数手动内两到QuickSort中。
3. 用栈模拟递归，本人不是太推荐这种做法。
4. 也许还能用指针优化关键操作，不过似乎c#不允许对reference type使用指针L
小结：
在极端性能要求下，需要对元素进行排序时：
当n< ~5k时，用array代替list，或者为array写一个简单的wrapper，并且自己实现sort；或者直接使用list.sort
当 n > 10k时, 实现自己的sort方法，至少能得到2~4倍的提速。