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

Question

以下 C# 代码在使用 VS2010 构建时似乎比使用 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
{
    /// <summary>
    /// Console app to test string sorting performance in C#.
    /// </summary>
    class Program
    {
        /// <summary>
        /// Displays the first lines from a vector of strings.
        /// </summary>
        /// <param name="wishedN">Number of lines to display.</param>
        /// <param name="lines">Source lines to display.</param>
        private static void DisplayFirst(int wishedN, List<string> lines)
        {
            int n = Math.Min(wishedN, lines.Count);
            for (int i = 0; i < n; i++)
            {
                Console.WriteLine("  " + lines[i]);
            }
            Console.WriteLine();
        }

        /// <summary>
        /// Used for random permutation.
        /// </summary>
        private static Random random = new Random();

        /// <summary>
        /// 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
        /// 
        /// </summary>
        /// <typeparam name="T">Type stored in the sequences.</typeparam>
        /// <param name="sequence">Input sequence.</param>
        /// <returns>Random permutation of the input sequence.</returns>
        private static IEnumerable<T> RandomPermutation<T>(IEnumerable<T> 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;
        }


        /// <summary>
        /// Builds a list of strings used in the performance benchmark.
        /// </summary>
        /// <returns>Test list of strings.</returns>
        private static List<string> 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<string>();

            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<string>(RandomPermutation(testLines));
            Console.WriteLine("done.");
            DisplayFirst(5, randomLines);
            Console.WriteLine();

            return randomLines;
        }


        /// <summary>
        /// Sort the input lines.
        /// </summary>
        /// <param name="lines">Input lines to sort.</param>
        private static void Test(List<string> 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<string> testLines = BuildTestLines();

            // Run the sort test
            Test(testLines);
        }
    }
}

Answer 1

这里是 .NET 版本中使用的排序算法的简要概述。记住 List<T>.Sort() 会很有帮助内部使用 Array<T>.Sort()

• 在 .NET 2.0-4.0 中，使用快速排序算法对 Array 进行排序.代码略有改动，但大部分代码保持不变。
• 在 .NET 4.5 中，数组排序算法从快速排序更改为内省(introspection)排序。与以前相比，这是一个更大的变化，至少在我的测试中，这一变化显示出相当大的性能改进。

排序算法在 VS2010 中有变化吗？

是的，但变化很小，不会影响性能。考虑对 2000 万个打乱的整数进行排序¹:

List<int>.Sort() (20 million).NET 3.5       .NET 4.0       .NET 4.5---------      ---------      --------- 2.564s         2.565s         2.337s

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

在我们进入您的下一个问题之前，让我分享一下我在我的机器上运行您的实际代码的结果:

List<string>.Sort() (1.6 million).NET 3.5       .NET 4.0       .NET 4.5---------      ---------      --------- 7.953s         11.267s        10.092s

我得到的结果与您相似。这些结果很好地引导了您的下一个问题:

底层 CLR 中是否有任何不同导致性能变差？

毫无疑问。那么区别是什么呢？区别在于字符串比较实现。在排序算法的每一步中，它都需要比较两个字符串，而它恰好在 v2.0 和 v4.0 运行时之间以不同的方式进行。 (请参阅下面的额外注释)

证明这一点的最简单方法是强制按顺序位置排序，而不是依赖文化。替换 lines.Sort();与 lines.Sort(StringComparer.Ordinal); .这是我测量的结果:

List<string>.Sort(StringComparer.Ordinal) (1.6 million).NET 3.5       .NET 4.0       .NET 4.5---------      ---------      --------- 4.088s         3.76s          3.454s

现在，看起来好多了!这或多或少是我所期望的；发布的每个版本的框架速度稳步提高。 MSDN Suggests如果您曾经对字符串进行非语言比较，您应该使用序数比较。

但是，只有当您的比较或排序不区分文化时，这才能解决问题。如果您需要区分文化的排序，似乎您将无法摆脱较慢的执行时间，除非您想恢复到 .NET 3.5 框架。

---

额外说明

当您不将比较器传递给 List<T>.Sort() 时或 Array.Sort ，它将使用默认比较器。 .NET 字符串的默认比较器使用线程当前区域性的比较器。从那里，它调用 .NET 运行时 native 库中的一些内部函数。

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

String.CompareTo(string)+--System.Globalization.CompareInfo.Compare(string,string,CompareOptions)   +--mscorwks.dll!COMNlsInfo::Compare      +--mscorwks.dll!COMNlsInfo::CompareFast

这些函数的类似源代码在 CLI (SSCLI) 的共享源代码实现中可见。它位于 sscli\clr\src\classlibnative\nls\comnlsinfo.cpp分别在第 1034 行和第 893 行。

然而，在 v4.0 中，调用树发生了相当大的变化:

String.CompareTo(string)+--System.Globalization.CompareInfo.Compare(string,string,CompareOptions)   +--clr.dll!COMNlsInfo::InternalCompareString      +--clr.dll!SortVersioning::SortDllCompareString         +--nlssorting.dll!_SortCompareString            +--nlssorting.dll!_AsciiCompareString

我希望我能告诉您为什么一个比另一个慢，但我一点头绪都没有，而且没有用于 .NET 4.0 的 SSCLI 可以与之比较。 .NET 4.0 中对字符串处理的主要更改并非没有问题。一直有性能问题related to strings in .NET 4.0 ，但是它们并不真正适用于此。

---

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