analiza Przestrzeń dla parfib na przykład monada-par

Question

Po przeczytaniu parfib.hs code na github, widziałem ten komentarz o alokacji pamięci dla monadycznej wersji:

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** 

Czy istnieje jakiś papier lub blogu, że wyjaśnia to ogromne zużycie pamięci ? Przydzielanie pamięci w wersji niemonadycznej jest udokumentowane w komentarzu kodowym jako 17 GB (dla fib (42)). Przeszukałem papiery par monady i prezentację Simona Marlowa, ale nie widziałem żadnej analizy śladów pamięciowych dla parfib.

Answer 1

Myślę, że to był mój komentarz w kodzie źródłowym. Największym problemem jest to, że domyślna implementacja monad-par wykorzystuje elegancką, ale potencjalnie nieefektywną architekturę, w której obliczenia Par generują ślad działań Par jako leniwą strukturę danych. To świetnie nadaje się do oddzielenia logiki programu planującego, ale kompilator nie całkowicie eliminuje (eliminuje) pośrednią strukturę danych.

Istnieje wiele dobrze znanych sposobów, aby to poprawić. Po prostu potrzeba czasu, aby je wdrożyć. Jeśli spojrzysz na niektóre z ostatnich prac rozwojowych (w oddziałach) w repozytorium github, zaczynamy wypełniać monad-par z alternatywnymi strategiami planowania odkrytymi w jego poprzedniej pracy ("Haskell CnC").

Mamy nadzieję na zmianę domyślnego harmonogramu w następnej wersji głównej na coś z zachowaniem parfibu znacznie bliżej "surowego" par/pseq.