c# - ordenar - Degradación del rendimiento de clasificación de cadenas en VS2010 vs. VS2008
sort array c# descending (1)
El siguiente código C # parece funcionar más lento cuando se compila con VS2010 que con VS2008: en una PC Core i5 Win7 x64 8 GB RAM, la versión construida VS2008 ordena cadenas en aproximadamente 7,5 segundos, en cambio la versión construida VS2010 requiere unos 9 segundos. ¿Porqué es eso?
¿Hay algo mal con mi código?
¿El algoritmo de clasificación cambió en VS2010?
¿Hay algo diferente en el CLR subyacente que empeora el rendimiento?
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);
}
}
}
Aquí hay un breve resumen de los algoritmos de clasificación utilizados en las versiones de .NET. Es útil recordar que List<T>.Sort() usa internamente Array<T>.Sort()
- En .NET 2.0-4.0, se usa un algoritmo de ordenación rápida para ordenar una
Array. Se han producido cambios menores en el código, pero en su mayor parte, el código sigue siendo el mismo. - En .NET 4.5, el algoritmo de ordenación de matriz cambió de ordenación rápida a una clasificación introspectiva. Este es un cambio más grande que antes, uno que, al menos en mis pruebas, muestra mejoras considerables en el rendimiento.
¿El algoritmo de clasificación cambió en VS2010?
Sí, pero los cambios fueron menores y no afectan el rendimiento. Considere un género contra 20 millones de enteros mezclados 1 :
List<int>.Sort() (20 million) .NET 3.5 .NET 4.0 .NET 4.5 --------- --------- --------- 2.564s 2.565s 2.337s
No hay cambios entre v3.5 y v4.0 en términos de rendimiento. Hay un aumento notable en la velocidad para v4.5. Está claro que no es el algoritmo de clasificación real el que está marcando la diferencia.
Antes de saltar a su próxima pregunta, permítame compartir los resultados de ejecutar su código actual en mi máquina:
List<string>.Sort() (1.6 million) .NET 3.5 .NET 4.0 .NET 4.5 --------- --------- --------- 7.953s 11.267s 10.092s
Obtengo resultados similares, como tú. Estos resultados son una buena introducción a su próxima pregunta:
¿Hay algo diferente en el CLR subyacente que empeora el rendimiento?
Sin duda. ¿Entonces cuál es la diferencia? La diferencia está en la implementación de comparación de cadenas. En cada paso del algoritmo de clasificación, necesita comparar las dos cadenas, y sucede que lo hace de manera diferente entre el tiempo de ejecución v2.0 y v4.0. (Ver notas adicionales a continuación)
La forma más fácil de probar esto es forzar la ordenación por posición ordinal, en lugar de depender de la cultura. Reemplazar lines.Sort(); con lines.Sort(StringComparer.Ordinal); . Esto es lo que medí:
List<string>.Sort(StringComparer.Ordinal) (1.6 million) .NET 3.5 .NET 4.0 .NET 4.5 --------- --------- --------- 4.088s 3.76s 3.454s
¡Ahora, eso se ve mejor! Es más o menos lo que esperaba; un aumento constante en la velocidad para cada versión del marco lanzado. MSDN sugiere que si alguna vez hace una comparación no lingüística en una cadena, debe usar una comparación ordinal.
Sin embargo, eso solo resuelve el problema si su comparación o clasificación no es culturalmente sensible. Si necesita una ordenación sensible a la cultura, parece que no podrá deshacerse del tiempo de ejecución más lento a menos que desee volver al marco .NET 3.5.
Notas adicionales
Cuando no pasa un comparador a List<T>.Sort() o Array.Sort , utilizará el comparador predeterminado. Comparadores por defecto para .NET Strings utiliza el comparador de la cultura actual del Thread. A partir de ahí, llama a algunas funciones internas en las bibliotecas nativas de tiempo de ejecución de .NET.
En v2.0-3.5, llama COMNlsInfo::Compare y COMNlsInfo::CompareFast . Esto es lo que parece la pila de llamadas (un poco):
String.CompareTo(string) +--System.Globalization.CompareInfo.Compare(string,string,CompareOptions) +--mscorwks.dll!COMNlsInfo::Compare +--mscorwks.dll!COMNlsInfo::CompareFast
Una fuente similar para estas funciones es visible en la implementación de fuente compartida de la CLI (SSCLI). Se encuentra en sscli/clr/src/classlibnative/nls/comnlsinfo.cpp en las líneas 1034 y 893, respectivamente.
En v4.0, sin embargo, ese árbol de llamadas cambió bastante significativamente:
String.CompareTo(string) +--System.Globalization.CompareInfo.Compare(string,string,CompareOptions) +--clr.dll!COMNlsInfo::InternalCompareString +--clr.dll!SortVersioning::SortDllCompareString +--nlssorting.dll!_SortCompareString +--nlssorting.dll!_AsciiCompareString
Desearía poder decirte por qué uno es más lento que el otro, pero no tengo ni idea y no hay ningún SSCLI para comparar con .NET 4.0. Los principales cambios en el manejo de cadenas en .NET 4.0 no fueron sin problemas. Ha habido problemas de rendimiento relacionados con cadenas en .NET 4.0 , sin embargo, en realidad no se aplican aquí.
1 Todas las pruebas se realizaron en una máquina virtual. Gane 2008R2 x64 con 4 GB de RAM y un procesador virtual quad-core. La máquina host es Win7 x64 con 24 GB de RAM y un Xeon W3540 (2.93 ghz) de cuatro núcleos (8 procesadores lógicos). Los resultados son un promedio de 5 carreras con los mejores y peores momentos eliminados.