análisis espacial para parfib en el ejemplo mónada-par

Question

Al leer a través parfib.hs code en github, vi este comentario acerca de la asignación de memoria para la versión monádico:

Monad-par version: 
fib(38) non-threaded: 23.3s 23.1s 
fib(38) 1 thread : 24.7s 24.5s 
fib(38) 4 threads:  8.2s 31.3s 
fib(40) 4 threads: 20.6s 78.6s **240GB allocated** 

¿Hay algún papel poste o blog que explica esta gran capacidad de memoria ? La asignación de memoria de la versión no monádica se documenta en el comentario del código como 17 GB (para fib (42)). Busqué a través de documentos de monad y presentación de Simon Marlow, pero no he visto ningún análisis de las huellas de memoria para parfib.

Answer 1

Creo que ese fue mi comentario en el código fuente. El mayor problema es que la implementación predeterminada de monad-par usa una arquitectura elegante pero potencialmente ineficiente donde el cálculo de Par genera un rastro de acciones Par como una estructura de datos vagos. Esto es ideal para separar la lógica del planificador, pero el compilador no está deforestando (eliminando) completamente la estructura de datos intermedia.

Existen varias formas bien conocidas de mejorar esto. Nos está tomando el tiempo para implementarlos. Si nos fijamos en algunos de los desarrollos recientes (en las ramas) en el repositorio de github estamos comenzando a poblar la monad-par con algunas de las estrategias de programación alternativas exploradas en su trabajo predecesor ("Haskell CnC").

Esperamos cambiar el programador predeterminado en la próxima versión principal a algo con un comportamiento parfib significativamente más cercano al par/pseq "en bruto".