Herramientas para analizar el rendimiento de un programa Haskell

Question

Mientras resuelvo algunos Problemas de Project Euler para aprender Haskell (por lo que actualmente soy un principiante), llegué a Problem 13. Escribí esta solución (ingenua):

--Get Number of Divisors of n 
numDivs :: Integer -> Integer 
numDivs n = toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2 

--Generate a List of Triangular Values 
triaList :: [Integer] 
triaList = [foldr (+) 0 [1..n] | n <- [1..]] 

--The same recursive 
triaList2 = go 0 1 
    where go cs n = (cs+n):go (cs+n) (n+1) 

--Finds the first triangular Value with more than n Divisors 
sol :: Integer -> Integer 
sol n = head $ filter (\x -> numDivs(x)>n) triaList2 

esta solución para n = 500 (sol 500) es extremadamente lenta (que se ejecuta durante más de 2 horas, ahora), por lo que se preguntó cómo averiguar por qué esta solución es tan lento. ¿Hay algún comando que me diga dónde se gasta la mayor parte del tiempo de cálculo para saber qué parte de mi programa haskell es lenta? Algo así como un simple generador de perfiles.

Para que quede claro, no estoy pidiendo para una solución más rápida, pero para una manera para encontrar esta solución. ¿Cómo comenzarías si no tuvieras conocimiento de Haskell?

Intenté escribir dos funciones triaList pero no encontré la manera de probar cuál es más rápido, por lo que es donde comienzan mis problemas.

Gracias

Answer 1

cómo saber por qué esta solución es tan lenta. ¿Hay algún comando que me diga dónde se gasta la mayor parte del tiempo de cálculo para saber qué parte de mi programa haskell es lenta?

Precisamente! GHC ofrece muchas herramientas excelentes, incluyendo:

• runtime statistics
• time profiling
• heap profiling
• thread analysis
• core analysis.
• comparative benchmarking
• GC tuning

Un tutorial sobre el uso de perfiles de tiempo y espacio es part of Real World Haskell.

Estadísticas GC

En primer lugar, asegurarse de que está compilar con -O2 GHC. Y es posible que se asegure de que sea un GHC moderno (por ejemplo, GHC 6.12.x)

Lo primero que podemos hacer es verificar que la recolección de basura no sea el problema. Ejecutar el programa con + RTS -s

$ time ./A +RTS -s 
./A +RTS -s 
749700 
    9,961,432,992 bytes allocated in the heap 
     2,463,072 bytes copied during GC 
      29,200 bytes maximum residency (1 sample(s)) 
     187,336 bytes maximum slop 
       **2 MB** total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 19002 collections,  0 parallel, 0.11s, 0.15s elapsed 
    Generation 1:  1 collections,  0 parallel, 0.00s, 0.00s elapsed 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT time 13.15s (13.32s elapsed) 
    GC time 0.11s ( 0.15s elapsed) 
    RP time 0.00s ( 0.00s elapsed) 
    PROF time 0.00s ( 0.00s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 13.26s (13.47s elapsed) 

    %GC time  **0.8%** (1.1% elapsed) 

    Alloc rate 757,764,753 bytes per MUT second 

    Productivity 99.2% of total user, 97.6% of total elapsed 

./A +RTS -s 13.26s user 0.05s system 98% cpu 13.479 total 

cual ya nos da una gran cantidad de información: sólo tiene un montón 2M, y GC ocupa el 0,8% del tiempo. Entonces, no hay necesidad de preocuparse de que la asignación sea el problema.

tiempo Perfiles

Conseguir un perfil de tiempo para su programa es sencillo: compilar con -auto-toda -prof

$ ghc -O2 --make A.hs -prof -auto-all 
[1 of 1] Compiling Main    (A.hs, A.o) 
Linking A ... 

Y, para N = 200:

$ time ./A +RTS -p     
749700 
./A +RTS -p 13.23s user 0.06s system 98% cpu 13.547 total 

que crea un archivo, A.prof, que contiene:

Sun Jul 18 10:08 2010 Time and Allocation Profiling Report (Final) 

     A +RTS -p -RTS 

    total time =  13.18 secs (659 ticks @ 20 ms) 
    total alloc = 4,904,116,696 bytes (excludes profiling overheads) 

COST CENTRE   MODULE   %time %alloc 

numDivs   Main   100.0 100.0 

indicando que todo su tiempo se usa en numDivs, y también es la fuente de todas sus asignaciones.

Perfiles Montón

También puede obtener un desglose de esas asignaciones, mediante la ejecución de la estrategia en tiempo real + -hy -p, lo que crea A.hp, que se puede ver mediante la conversión a un archivo PostScript (hp2ps -c A.hp), generando:

que nos dice que no hay nada malo con el uso de memoria: se está asignando en el espacio constante.

Así que su problema es la complejidad algorítmica de numDivs:

toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2 

arreglar eso, que es 100% de su tiempo de ejecución, y todo lo demás es fácil.

optimizaciones

Esta expresión es un buen candidato para la optimización stream fusion, así que voy a volver a escribir utilizar Data.Vector, así:

numDivs n = fromIntegral $ 
    2 + (U.length $ 
     U.filter (\x -> fromIntegral n `rem` x == 0) $ 
     (U.enumFromN 2 ((fromIntegral n `div` 2) + 1) :: U.Vector Int)) 

Cuáles deberían fusionarse en un único bucle sin asignaciones de montón innecesarias. Es decir, tendrá una mejor complejidad (por factores constantes) que la versión de la lista. Puede usar la herramienta ghc-core (para usuarios avanzados) para inspeccionar el código intermedio después de la optimización.

Probando esto, ghc -O2 --haz Z.hs

$ time ./Z  
749700 
./Z 3.73s user 0.01s system 99% cpu 3.753 total 

Por lo tanto, reduce el tiempo de funcionamiento para N = 150 por 3.5x, sin cambiar el propio algoritmo.

Conclusión

Su problema es numDivs. Es el 100% de tu tiempo de ejecución y tiene una complejidad terrible. Piensa en numDivs, y cómo, por ejemplo, para cada N estás generando [2 .. n div 2 + 1] N veces. Intente recordar eso, ya que los valores no cambian.

Para medir cuál de sus funciones es más rápida, considere usar criterion, que proporcionará información estadísticamente sólida sobre las mejoras de sub-microsegundos en el tiempo de ejecución.

---

Adenda

Desde numDivs es el 100% de su tiempo de funcionamiento, tocar otras partes del programa no hará mucha diferencia, sin embargo, con fines pedagógicos, también puede volver a escribir los que utilizan fusión de corriente

También podemos reescribir triallist, y se basan en la fusión para convertirlo en el bucle se escribe a mano en trialList2, que es una función "prefijo de exploración" (también conocido como scanl):

triaList = U.scanl (+) 0 (U.enumFrom 1 top) 
    where 
     top = 10^6 

Del mismo modo para sol:

sol :: Int -> Int 
sol n = U.head $ U.filter (\x -> numDivs x > n) triaList 

Con el mismo tiempo de funcionamiento general, pero un código más limpio.

Answer 2

Haskell nota relacionada: triaList2 Por supuesto, es más rápido que triaList ya que este último lleva a cabo una gran cantidad de cálculos innecesarios. Tomará un tiempo cuadrático calcular n primeros elementos de triaList, pero lineales para triaList2. Hay otra manera elegante (y eficiente) para definir una infinita lista de perezoso de los números triangulares:

triaList = 1 : zipWith (+) triaList [2..] 

Matemáticas nota relacionada: no hay necesidad de revisar todos los divisores de hasta n/2, que es suficiente para comprobar hasta sqrt (n).

Answer 3

Puede ejecutar su programa con indicadores para habilitar la creación de perfiles de tiempo. Algo como esto:

./program +RTS -P -sprogram.stats -RTS 

que se debe ejecutar el programa y producir un archivo llamado program.stats que tendrán cuánto tiempo se gastó en cada función. Puede encontrar más información sobre la creación de perfiles con GHC en el GHC user guide. Para la evaluación comparativa, está la biblioteca Criterion. He encontrado this entrada de blog tiene una introducción útil.

Answer 4

La respuesta de Dons es excelente sin ser un spoiler al dar una solución directa al problema.
Aquí quiero sugerir un pequeño tool que escribí recientemente. Le ahorra tiempo para escribir anotaciones SCC a mano cuando desea un perfil más detallado que el predeterminado ghc -prof -auto-all. ¡Además de eso es colorido!

He aquí un ejemplo con el código que le dio (*), el verde es OK, el rojo es lenta:

Todo el que pasa el tiempo en la creación de la lista de divisores. Esto sugiere algunas cosas que puede hacer:
1. Haga que el filtrado n rem x == 0 sea más rápido, pero dado que es una función incorporada, probablemente ya sea rápido.
2. Cree una lista más corta. Ya ha hecho algo en esa dirección al marcar solo hasta n quot 2.
3. Deseche completamente la generación de listas y use algunos cálculos matemáticos para obtener una solución más rápida. Esta es la forma habitual de resolver problemas de Euler.

(*) Lo obtuve poniendo su código en un archivo llamado eu13.hs, agregando una función principal main = print $ sol 90. Luego ejecuta visual-prof -px eu13.hs eu13 y el resultado está en eu13.hs.html.