Space analysis for parfib in monad-par example

Question

When reading through parfib.hs code on github, I saw this comment about memory allocation for monadic version:

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

Is there any paper or blog post that explains this huge memory footprint? The memory allocation of non-monadic version is documented in the code comment as 17GB (for fib(42)). I searched through par monad papers and presentation by Simon Marlow but I haven't seen any analysis of the memory footprints for parfib.

Answer 1

I think that was my comment in the source code. The biggest problem is that the default implementation of monad-par uses an elegant but potentially inefficient architecture where the Par computation generates a trace of Par actions as a lazy data structure. This is great for separating out the scheduler logic, but the compiler is not fully deforesting (eliminating) the intermediate data structure.

There are various well-known ways to make this better. It's just taking us time to implement them. If you look at some of the recent development (on branches) on the github repository we are beginning to populate monad-par with some of the alternate scheduling strategies explored in its predecessor work ("Haskell CnC").

We are hoping to change the default scheduler in the next major release to something with a parfib behavior significantly closer to "raw" par/pseq.