Implementación manual de algoritmos de alto rendimiento en .NET

Question

Como experiencia de aprendizaje, recientemente intenté implementar Quicksort con partición de 3 vías Cía#.

Además de necesitar agregar una verificación de rango adicional en las variables izquierda/derecha antes de la llamada recursiva, parece funcionar bastante bien.

Sabía de antemano que el marco proporciona un Implementación de QuickSort incorporado en la lista <>. Sort (a través de Array.Sort). Así que probé algunos perfiles básicos para comparar el rendimiento. Resultados: el método de clasificación de la lista incorporada <>., Que funciona en las mismas listas, funciona aproximadamente 10 veces más rápido que mi propia implementación manual.

Usando Reflector, descubrí que la clasificación real en la lista <>. Sort se implementa en código externo, no IL (en una función llamada tryszSort ()).

Mirando mi propia implementación de Quicksort, esperaría que reemplazar las llamadas recursivas con la iteración pueda dar alguna mejora. Además, deshabilitar la verificación de los límites de la matriz (si es posible) también podría dar algunos beneficios. Tal vez esto se acercaría a la implementación incorporada, pero no estoy seguro.

Entonces, mi pregunta: ¿es realista esperar el rendimiento en un algoritmo optimizado (escrito en .NET IL, JITT al código nativo) puede competir con el rendimiento de un algoritmo implementado externamente?

Una vez más, me doy cuenta de que QuickSort se proporciona como parte del marco, esta fue solo una experiencia de aprendizaje para mí. Sin embargo, también hay muchos algoritmos (CRC32 viene a la mente) que no se proporcionan, pero que aún podrían tener mucho valor para muchas aplicaciones. Aquí hay una pregunta relacionada con respecto a Implementación de CRC32 en .NET y problemas de rendimiento.

Entonces, si necesita implementar dicho algoritmo en .NET, ¿cuáles son las principales consideraciones de rendimiento para comprender, para que su algoritmo pueda al menos abordar el rendimiento del código externo?

Actualizar

He mejorado la velocidad de ejecución dentro de aproximadamente el 10% de la matriz incorporada. En Reflector, puedo ver que esto evita una operación Callvirt () en cada get o establecido en la lista. Pensé que esto podría mejorar las cosas, pero me sorprende cuánto.

Answer 1

Mediante el uso de código no recursivo y, especialmente, utilizando bloques "inseguros" y aritmética de puntero (si corresponde) usted pudo En realidad, vea una ganancia de rendimiento X5 o X10 con un algoritmo escrito en C#. Como siempre con el rendimiento (y aún más cuando se trata de un entorno administrado), nunca lo sabe hasta que lo pruebe y lo compare.

Ahora, en términos generales, debe escribir cosas en C#, luego optimizarlo, optimizarlo un poco más, y si aún no es lo suficientemente bueno, identifique la pieza de código crítica exacta y la transfiera a C ++ (sin tener cuidado al limitar el número. de límites de llamada administrados/nativos).

Answer 2

Solo por curiosidad, ya que a pesar de mis 9 años de experiencia con .NET, todavía cometo constantemente este error: ¿compiló su código en modo de lanzamiento con optimizaciones encendidas? El código de depuración funciona significativamente peor que el código de lanzamiento optimizado.

Suponiendo que compiló en el modo de lanzamiento, no debería haber una gran diferencia en el rendimiento si implementa el algoritmo de manera similar (es decir, iterativa versus iterativa o recursiva versus recursiva). Si desea ver la implementación de .NET y descubrir, puede descargar el SSCLI, Infraestructura de lenguaje común de origen compartido. Esta es la implementación CLI compatible con el estándar de ECMA de Microsoft. No es el 100% del marco .NET que todos conocemos y amamos, pero es una parte significativa de ello. Puede proporcionar mucha información que Reflector no pueda, incluidas las implementaciones internas. Todos los tipos de código están disponibles, incluidos C#, C ++ e incluso algunos ensambladores en un par de casos.

Answer 3

Asegúrese de que esté comparando manzanas y manzanas.

Al clasificar, es posible que la función de comparación sea dominante, y eso podría diferir entre las implementaciones.

Suponiendo que la función de comparación en ambos casos es lo suficientemente rápida como para no ser un problema, entonces el tiempo puede estar dominado por cosas como la verificación de los límites de la matriz, lo que puede hacer una gran diferencia fácilmente.