Dificultad para comprender el comportamiento de asignación de memoria de Haskell

Question

Me tropecé con Haskell y FP y quedé aturdido por las posibilidades. Y el viejo nerd matemático dentro de mí no tuvo problemas para escribir código ingenuo para fines realmente útiles. Sin embargo, a pesar de todas las lecturas, todavía me cuesta entender cómo no dar algunos sorprendentes cuellos de botella en el rendimiento.

Así que escribo fragmentos de código muy cortos con implementaciones ingenuas y luego trato de hacer 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 para Josephus problem, con propósito con una implementación ingenua de listas.

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 quería probar era eliminar el (soldado de longitud -1) y reemplazarlo por un entero decreciente.

¡El tiempo de ejecución aumentó hasta 900 ms y la productividad bajó al 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 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 los artículos y las publicaciones relacionadas con el rendimiento, pero parece que no tengo una pista al respecto. Aún siendo un novato de Haskell, me falta algo grande ... ¿Cómo puede este parámetro añadido (computación pre-masticada ...) reducir la velocidad tanto?

PD: Sé que, si Josefo realmente había estado con 3000 soldados, no habrían necesitado al suicidio ...

Answer 1

La primera solución obliga a toda la columna vertebral de la lista soldados tomando su longitud. La segunda solución solo fuerza (usando seq) la cabeza de la lista de soldados. Reemplace el left entre el seq s con un length left y recuperará su rendimiento.