Деформация производительности сортировки строк в VS2010 по сравнению с VS2008

Следующий код С# работает медленнее при построении с VS2010, чем с VS2008: на операционном ПК Core i5 Win7 x64 8 ГБ построенная версия 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/info/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);
        }
    }
}

Ответы

Ответ 1

Ниже приведен краткий обзор алгоритмов сортировки, используемых в версиях .NET. Полезно помнить, что List<T>.Sort() внутренне использует Array<T>.Sort()

  • В .NET 2.0-4.0 для сортировки Array используется быстрый алгоритм сортировки. Были внесены незначительные изменения в код, но по большей части код остается тем же.
  • В .NET 4.5 алгоритм сортировки массивов изменился с быстрой сортировки на интроспективный. Это большее изменение, чем раньше, это, по крайней мере, в моих тестах, показывает значительные улучшения в производительности.

Изменен ли алгоритм сортировки в VS2010?

Да, но изменения были незначительными и не влияют на производительность. Рассмотрим сорт против 20 миллионов перетасованных целых чисел 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 использует сопоставитель из текущей текущей культуры. Оттуда он вызывает некоторые внутренние функции в собственных библиотеках среды выполнения .NET.

В версии 2.0-3.5 он вызывает COMNlsInfo::Compare и COMNlsInfo::CompareFast. Здесь выглядит стек вызовов (kinda):

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 соответственно.

Однако в версии 4.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 Все тесты выполнялись на виртуальной машине. Win 2008R2 x64 w/4GB RAM и виртуальный четырехъядерный процессор. Хост-компьютер - это Win7 x64 w/24GB RAM и четырехъядерный процессор Xeon W3540 (2.93ghz) (8 логических процессоров). Результаты в среднем составляют 5 прогонов с удалением лучших и худших времен.