VS2010与VS2008中的字符串排序性能下降

使用VS2010构建时，以下C＃代码似乎比使用VS2008 慢 ：在Core i5 Win7 x64 8 GB RAM PC上，VS2008内置版本在大约7.5秒内对字符串进行排序，而VS2010内置版本需要大约9秒。 这是为什么？

我的代码有什么问题吗？

排序算法是否在VS2010中发生了变化？

底层CLR中有什么不同会使性能变差吗？

using System; using System.Collections.Generic; using System.Diagnostics; using System.Globalization; using System.Linq; namespace StringSortCSharp { /// 
 /// Console app to test string sorting performance in C#. /// 
 class Program { /// 
 /// Displays the first lines from a vector of strings. /// 
 /// Number of lines to display. /// Source lines to display. private static void DisplayFirst(int wishedN, List lines) { int n = Math.Min(wishedN, lines.Count); for (int i = 0; i < n; i++) { Console.WriteLine(" " + lines[i]); } Console.WriteLine(); } /// 
 /// Used for random permutation. /// 
 private static Random random = new Random(); /// 
 /// Computes a random permutation of the input sequence. /// /// From: /// http://stackoverflow.com/questions/375351/most-efficient-way-to-randomly-sort-shuffle-a-list-of-integers-in-c-sharp /// /// 
 /// Type stored in the sequences. /// Input sequence. /// Random permutation of the input sequence. private static IEnumerable RandomPermutation(IEnumerable sequence) { T[] retArray = sequence.ToArray(); for (int i = 0; i < retArray.Length - 1; i += 1) { int swapIndex = random.Next(i + 1, retArray.Length); T temp = retArray[i]; retArray[i] = retArray[swapIndex]; retArray[swapIndex] = temp; } return retArray; } /// 
 /// Builds a list of strings used in the performance benchmark. /// 
 /// Test list of strings. private static List BuildTestLines() { // Start with "Lorem ipsum", and repeat it several times, adding some suffix strings. var lorem = new string[] { "Lorem ipsum dolor sit amet, consectetuer adipiscing elit.", "Maecenas porttitor congue massa. Fusce posuere, magna sed", "pulvinar ultricies, purus lectus malesuada libero,", "sit amet commodo magna eros quis urna.", "Nunc viverra imperdiet enim. Fusce est. Vivamus a tellus.", "Pellentesque habitant morbi tristique senectus et netus et", "malesuada fames ac turpis egestas. Proin pharetra nonummy pede.", "Mauris et orci." }; int repeatCount = 200 * 1000; Console.Write("Building test strings"); var testLines = new List(); Console.Write(" (total string count = {0})", repeatCount * lorem.Length); Console.Write("..."); for (int i = 0; i < repeatCount; i++) { for (int j = 0; j < lorem.Length; j++) { // Add more stuff to Lorem strings testLines.Add(lorem[j] + " (#" + i + ")"); } } Console.WriteLine("done."); DisplayFirst(5, testLines); Console.WriteLine(); // Shuffle the previously built strings. Console.Write("Shuffling strings..."); var randomLines = new List(RandomPermutation(testLines)); Console.WriteLine("done."); DisplayFirst(5, randomLines); Console.WriteLine(); return randomLines; } /// 
 /// Sort the input lines. /// 
 /// Input lines to sort. private static void Test(List lines) { // Stopwatch to measure time performance var timer = new Stopwatch(); Console.Write("Sorting " + lines.Count + " lines..."); // Sort benchmark timer.Start(); lines.Sort(); timer.Stop(); Console.WriteLine("done."); // Display results DisplayFirst(5, lines); Console.WriteLine(); Console.WriteLine((timer.ElapsedMilliseconds / 1000.0).ToString(CultureInfo.InvariantCulture) + " seconds elapsed."); } static void Main(string[] args) { Console.WriteLine("*** Testing String Sorting in C# ***"); Console.WriteLine(); // Build test lines used for the sort benchmark List testLines = BuildTestLines(); // Run the sort test Test(testLines); } } } 

Answer 1

以下是.NET版本中使用的排序算法的简要概述。 记住List.Sort()内部使用Array.Sort()

• 在.NET 2.0-4.0中，使用快速排序算法对Array进行排序。 代码有一些细微的变化，但在大多数情况下，代码保持不变。
• 在.NET 4.5中，数组排序算法从快速排序更改为内省排序。 这是一个比以前更大的变化，至少在我的测试中，它表现出相当大的性能改进。

排序算法是否在VS2010中发生了变化？

是的，但变化很小，并不影响性能。 考虑对2000万个洗牌整数进行排序¹ ：

 List  .Sort（）（2000万）

 .NET 3.5 .NET 4.0 .NET 4.5
 --------- --------- ---------
  2.564s 2.565s 2.337s

在性能方面，v3.5和v4.0之间没有任何变化。 v4.5的速度明显提高。 很明显，实际的排序算法不是产生差异。

在我们跳到下一个问题之前，让我分享一下在我的机器上运行实际代码的结果：

 List  .Sort（）（160万）

 .NET 3.5 .NET 4.0 .NET 4.5
 --------- --------- ---------
  7.953s 11.267s 10.092s

我和你一样得到了类似的结果。 这些结果是您下一个问题的一个很好的引导：

底层CLR中有什么不同会使性能变差吗？

毫无疑问。 那么区别是什么呢？ 不同之处在于字符串比较实现。 在排序算法的每个步骤中，它需要比较两个字符串，并且它恰好在v2.0和v4.0运行时之间做了不同的操作。 （见下面的额外说明）

certificate这一点的最简单方法是强制按顺序排序，而不是文化依赖。 替换lines.Sort(); with lines.Sort(StringComparer.Ordinal); 。 这是我测量的：

 List  .Sort（StringComparer.Ordinal）（160万）

 .NET 3.5 .NET 4.0 .NET 4.5
 --------- --------- ---------
  4.088s 3.76s 3.454s

现在，这看起来更好！ 这或多或少是我的期望; 每个版本的框架都会稳步提高速度。 MSDN建议如果您对字符串进行非语言比较， 则应使用序数比较。

但是，如果您的比较或排序不是文化敏感的，那么这只能解决问题。 如果您需要对文化敏感的排序，除非您想要恢复到.NET 3.5框架，否则您似乎无法摆脱较慢的执行时间。

---

额外的笔记

如果未将比较器传递给List.Sort()或Array.Sort ，它将使用默认比较器。 .NET字符串的默认比较器使用Thread当前文化中的比较器。 从那里，它调用.NET运行时本机库中的一些内部函数。

在v2.0-3.5中，它调用COMNlsInfo::Compare和COMNlsInfo::CompareFast 。 这是调用堆栈（有点）的样子：

 String.CompareTo（串）
 +  -  System.Globalization.CompareInfo.Compare（字符串，字符串，CompareOptions）
    +  - 的Mscorwks.dll COMNlsInfo ::比较
       +  - 的Mscorwks.dll COMNlsInfo :: CompareFast

在CLI的共享源实现（SSCLI）中可以看到这些函数的类似源。 它分别位于第1034和893行的sscli\clr\src\classlibnative\nls\comnlsinfo.cpp 。

但是，在v4.0中，该调用树发生了相当大的变化：

 String.CompareTo（串）
 +  -  System.Globalization.CompareInfo.Compare（字符串，字符串，CompareOptions）
    +  - ！clr.dll COMNlsInfo :: InternalCompareString
       +  -  clr.dll SortVersioning :: SortDllCompareString！
          +  - ！nlssorting.dll _SortCompareString
             +  - ！nlssorting.dll _AsciiCompareString

我希望我能告诉你为什么一个比另一个慢，但我根本没有任何线索，并且没有用于.NET 4.0的SSCLI进行比较。 .NET 4.0中字符串处理的主要变化并非没有问题。 .NET 4.0中存在与字符串相关的性能问题，但它们并不适用于此处。

---

¹ _{所有测试都在虚拟机中运行。 赢得2008R2 x64 w / 4GB RAM和虚拟四核处理器。 主机是Win7 x64 w / 24GB RAM和Xeon W3540（2.93ghz）四核（8个逻辑处理器）。 结果是平均5次运行，最佳和最差时间被删除。}