Herramientas para analizar el rendimiento de un programa Haskell

Mientras resolvía algunos problemas del Proyecto Euler para aprender Haskell (por lo que actualmente soy un principiante) me encontré con el Problema 12 . 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 n=500 (sol 500)es extremadamente lenta (se está ejecutando durante más de 2 horas), así que me preguntaba cómo averiguar por qué esta solución es tan lenta. ¿Hay comandos que me digan dónde se gasta la mayor parte del tiempo de cálculo para saber qué parte de mi programa haskell es lento? Algo así como un simple perfilador.

Para que quede claro, no estoy pidiendo para una solución más rápida, pero para una forma de encontrar esta solución. ¿Cómo empezaría si no tuviera conocimientos de Haskell?

Intenté escribir dos triaListfunciones pero no encontré forma de probar cuál es más rápida, así que aquí es donde comienzan mis problemas.

Gracias

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

¡Precisamente! GHC proporciona muchas herramientas excelentes, que incluyen:

• estadísticas de tiempo de ejecución
• perfil de tiempo
• perfiles de montón
• análisis de hilo
• análisis del núcleo.
• evaluación comparativa
• Ajuste de GC

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

Estadísticas de GC

En primer lugar, asegúrese de compilar con ghc -O2. Y puede asegurarse 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. Ejecute su 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

Lo que ya nos da mucha información: solo tiene un montón de 2M y GC ocupa el 0.8% del tiempo. Así que no hay que preocuparse de que la asignación sea el problema.

Perfiles de tiempo

Obtener un perfil de tiempo para su programa es sencillo: compile con -prof -auto-all

 $ 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

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

Perfiles de montón

También puede obtener un desglose de esas asignaciones, ejecutando con + RTS -p -hy, que crea A.hp, que puede ver convirtiéndolo en un archivo postscript (hp2ps -c A.hp), generando:

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

Entonces, su problema es la complejidad algorítmica de numDivs:

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

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

Optimizaciones

Esta expresión es una buena candidata para la optimización de la fusión de flujo , así que la reescribiré para usar 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))

Que debería fusionarse en un solo bucle sin asignaciones de montón innecesarias. Es decir, tendrá mayor complejidad (por factores constantes) que la versión de lista. Puede utilizar la herramienta ghc-core (para usuarios avanzados) para inspeccionar el código intermedio después de la optimización.

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

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

Por lo tanto, redujo el tiempo de ejecución para N = 150 en 3,5 veces, sin cambiar el algoritmo en sí.

Conclusión

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

Para medir cuál de sus funciones es más rápida, considere la posibilidad de utilizar un criterio , que proporcionará información estadísticamente sólida sobre mejoras de menos de microsegundos en el tiempo de ejecución.

Adenda

Dado que numDivs es el 100% de su tiempo de ejecución, tocar otras partes del programa no hará mucha diferencia, sin embargo, con fines pedagógicos, también podemos reescribir las que utilizan stream fusion.

También podemos reescribir trialList y confiar en fusion para convertirlo en el bucle que escribe a mano en trialList2, que es una función de "exploración de prefijo" (también conocida 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 ejecución general, pero un código un poco más limpio.

La respuesta de Dons es genial sin ser un spoiler al dar una solución directa al problema.
Aquí quiero sugerir una pequeña herramienta que escribí recientemente. Le ahorra tiempo al 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!

Aquí hay un ejemplo con el código que proporcionó (*), el verde está bien, el rojo es lento:

Todo el tiempo se dedica a crear la lista de divisores. Esto sugiere algunas cosas que puede hacer:
1. Haga que el filtrado sea n rem x == 0má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 comprobando solo hasta n quot 2.
3. Deseche la generación de listas por completo y use algunas matemáticas para obtener una solución más rápida. Esta es la forma habitual para los problemas del proyecto Euler.

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

Nota relacionada con Haskell: triaList2por supuesto, es más rápido que triaListporque este último realiza muchos cálculos innecesarios. Se necesitará un tiempo cuadrático para calcular n primeros elementos de triaList, pero lineal para triaList2. Hay otra forma elegante (y eficiente) de definir una lista perezosa infinita de números triangulares:

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

Nota relacionada con las matemáticas: no es necesario verificar todos los divisores hasta n / 2, es suficiente verificar hasta sqrt (n).

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

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

Eso debería ejecutar el programa y producir un archivo llamado program.stats que tendrá cuánto tiempo se dedicó a cada función. Puede encontrar más información sobre la creación de perfiles con GHC en la guía del usuario de GHC . Para la evaluación comparativa, existe la biblioteca Criterion. Encontré que esta publicación de blog tiene una introducción útil.