haskell - monad-par 示例中 parfib 的空间分析

Question

通读时parfib.hs code在 github 上，我看到了关于 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 Action 的踪迹作为惰性数据结构。这对于分离调度程序逻辑非常有用，但编译器并没有完全砍伐(消除)中间数据结构。

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

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