字符串排序性能下降VS2010与VS2008(String sorting performance

2019-06-27 12:00发布

下面的C#代码似乎在与VS2010建比VS2008运行速度变慢 :在酷睿i5 X64 Win7的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,阵列排序算法从快速排序变更为内省排序。 这比从之前一个较大的改变,一个,至少在我的测试中,显示出相当大的性能提升。

难道在VS2010的排序算法的变化?

是的,但变化是微小的,并且不会影响性能。 考虑对2000万个洗牌整数1排序:

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:建议是,如果你曾经做的一个关于字符串非语言比较,你应该使用序号比较。

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


附加说明

当你不通过一个比较器对List<T>.Sort()Array.Sort ,它会使用默认的比较。 对于.NET字符串默认comparers使用从线程的当前区域性的比较器。 从那里,它调用.NET运行时的本机库内部的一些功能。

在v2.0-3.5,它调用COMNlsInfo::CompareCOMNlsInfo::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

我希望我能告诉你为什么一个比另一个更慢,但我根本不知道,也没有对SSCLI .NET 4.0进行比较的。 字符串在.NET 4.0中处理的主要变化是不是没有问题的。 已经有性能问题, 在.NET 4.0中涉及到的字符串 ,但他们并不真正适用于此处。


1个 所有的测试都是在虚拟机中运行。 赢2008R2 64瓦特/ 4GB RAM和虚拟四核处理器。 主机是X64 Win7的瓦特/ 24GB的RAM和一个至强W3540(2.93GHz的)四核(8个逻辑处理器)。 结果是5次用最好的和最差的时间取出的平均值。



文章来源: String sorting performance degradation in VS2010 vs. VS2008