performance - Difícil de entender el comportamiento de asignación de memoria de Haskell

functional-programming lazy-evaluation

Question

Me topé con Haskell y FP y me sorprendí por las posibilidades. Y el viejo nerd de las matemáticas dentro de mí no tuvo problemas para escribir código ingenuo para propósitos reales. Sin embargo, a pesar de todas las lecturas, todavía me cuesta mucho entender cómo no alcanzar algunos cuellos de botella sorprendentes en el rendimiento.

Así que escribo piezas muy cortas de código con implementaciones ingenuas y luego intento pequeños cambios para ver cómo responde el rendimiento. Y aquí hay un ejemplo que realmente no puedo entender ... Escribí esta función que encuentra una solución al problema de Josephus , a propósito con una implementación de lista ingenua.

m = 3
n = 3000
main = putStr $ "Soldier #" ++ (show $ whosLeft [1..n]) ++ " survived.../n"

whosLeft [lucky] = lucky
whosLeft soldiers = whosLeft $ take (length soldiers -1) $ drop m $ cycle soldiers

Este último funciona en 190 ms, con una productividad del 63% según el RTS.

Luego, lo primero que quise probar fue eliminar (la longitud del soldado -1) y reemplazarlo con un entero decreciente.

¡El tiempo de ejecución aumentó hasta 900 ms y la productividad bajó a 16%, y usa 47 veces más memoria que el código más simple de arriba! Así que agregué una evaluación estricta, forcé el tipo Int, probé cosas como eliminar las variables globales y otras, pero no me sirvió de mucho. Y simplemente no puedo entender esta desaceleración.

m = 3::Int
n = 3000::Int
main = putStr $ "Soldier #" ++ (show $ whosLeft n [1..n]) ++ " survived.../n"

whosLeft 1 [lucky] = lucky
whosLeft n'' soldiers = n'' `seq` left `seq` whosLeft (n''-1) left
                where left = take (n''-1) $ drop m $ cycle soldiers

He revisado artículos y publicaciones relacionadas con el rendimiento, pero parece que no entiendo nada sobre esto. Aún siendo un noob de Haskell, debo estar perdiendo algo grande ... ¿Cómo puede este parámetro agregado (cálculo pre-masticado ...) reducir tanto la velocidad?

PD: Lo sé, si Josefo hubiera estado realmente con 3000 soldados, no habrían necesitado suicidarse ...

Answer 1

La primera solución obliga a toda la columna vertebral de la lista de soldados al tomar su longitud. La segunda solución solo fuerza (usando la seq ) al jefe de la lista de soldados. Reemplace la left entre las seq con una length left y recuperará su rendimiento.