monad-par例子中parfib的空间分析

Question

通过阅读github上的parfib.hs代码时,我看到了关于monadic版本的内存分配的评论:

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

是否有任何纸质或博客文章解释了这个巨大的内存占用？非monadic版本的内存分配在代码注释中记录为17GB(对于fib(42)).我搜索了Simon Marlow的par monad论文和演示,但我还没有看到对parfib的记忆足迹的任何分析.

Answer 1

我认为这是我在源代码中的评论。最大的问题是 monad-par 的默认实现使用了一种优雅但可能效率低下的架构，其中 Par 计算生成 Par 操作的痕迹作为惰性数据结构。这对于分离调度程序逻辑非常有用，但编译器并没有完全清除（消除）中间数据结构。

有多种众所周知的方法可以使这一点变得更好。我们只是需要时间来实施它们。如果您查看 github 存储库上的一些最新开发（在分支上），我们将开始使用其前身工作（“Haskell CnC”）中探索的一些替代调度策略来填充 monad-par。

我们希望在下一个主要版本中将默认调度程序更改为 parfib 行为显着接近“原始”par/pseq 的东西。