haskell - Haskell：并行列表计算

问题描述

我正在尝试执行此视频 ( https://www.youtube.com/watch?v=rlwSBNI9bXE& ) 中显示的倒计时问题，我认为尝试并行运行会是一个好问题？

data Op =
    Add
  | Sub
  | Mul
  | Div deriving (Eq)

data Expr = 
    Val Int 
  | App Op Expr Expr

--{ helper functions }  

solutions' :: [Int] -> Int -> [Expr]
solutions' ns n =
  [e | ns' <- choices ns, (e, m) <- results ns', m == n]

我尝试关注其他一些关于如何做到这一点的帖子，并想出了类似的东西

instance NFData Op where
  rnf Add = Add `deepseq` ()
  rnf Sub = Sub `deepseq` ()
  rnf Mul = Mul `deepseq` ()
  rnf Div = Div `deepseq` ()

instance NFData Expr where
  rnf (Val a)     = a `deepseq` ()
  rnf (App o l r) = (rnf  o) `deepseq` (rnf l) `deepseq` (rnf r)

solutions' :: [Int] -> Int -> [Expr]
solutions' ns n =
  ([e | ns' <- choices ns, (e, m) <- results ns', m == n]
    `using` parList rdeepseq)

它可以编译，但是当我尝试运行它时程序崩溃了。老实说，我真的只是在猜测我写的东西。

如何让它并行运行？

当我在 GHCI 中运行时

>λ= r = (solutions' [1,3,7,10,25,50] 765)
(0.00 secs, 0 bytes)
>λ= mapM_ print r
*** Exception: stack overflow
>λ=

如果我编译 ghc ./Countdown.hs +RTS -N8 -s

然后运行可执行文件，它不会终止。

标签： haskell

解决方案

好的，所以我只是点击了视频中的一个随机时间戳，幸运的是，我得到了一张描述问题所在的幻灯片。

对于我们的示例，3300 万个可能的表达式中只有大约 500 万个是有效的。

所以，这意味着你正在评估

_fiveMillionList `using` parList rdeepseq

现在，(`using` parList _strat)工作方式是它立即强制整个列表的脊椎。当您开始评估您的表达式时，parList强制列表的所有单元格存在。此外，正如@DavidFletcher 所指出的，您的并行性实际上是无用的。因为过滤在下方using，所以强制列表的整个脊椎也强制所有 3300 万个Exprs 存在，因为您需要知道有多少元素通过了(==)测试，因此您需要创建Exprs 来测试它们。它们不需要全部同时存在，但最终有 500 万个（不包括其中Expr递归包含的 s），再加上 500 万个(:)构造函数，将保存在内存中。雪上加霜的是，您继续以哑火花的形式再制造 500 万个物体。而且，所有这些都是由对Evalmonad(>>=)函数的 500 万次调用精心策划的。我不确定其中哪一个在内存中驻留了足够长的时间以导致堆栈溢出，但我很确定这parList是罪魁祸首。

或许尝试更合理Strategy。我认为您几乎被迫使用parBuffer，因为您需要懒惰。使用parBuffer n strat，如果您评估一个(:)-cell，则该策略可确保n - 1已触发下一个元素。因此，从本质上讲，它“领先于”从列表头部开始的任何消费者，维护并行评估元素的缓冲区。类似的东西parBuffer 1000 rdeepseq应该没问题。

您的NFData实例可能需要一些工作。它们不是问题，但它们并没有真正表现出对评估如何工作的充分理解。我就把它们留在这里：

instance NFData Op where
  -- (seq/deepseq) x y is defined by
  -- "if you want to evaluate (seq/deepseq) x y to WHNF, then you must
  -- evaluate x to WHNF/NF, then evaluate y to WHNF."
  -- but e.g. Add is already in WHNF and NF, so seq Add and deeqseq Add are no-ops
  -- the actual evaluation is already finished by the case in rnf's equations
  -- you could even write rnf x = x `seq` (), but I think it's best to be explicit
  rnf Add = ()
  rnf Sub = ()
  rnf Mul = ()
  rnf Div = ()

instance NFData Expr where
  rnf (Val a)     = a `deepseq` ()
  -- rnf o, rnf l :: ()
  -- WHNF and NF are the same thing for the type (); all constructors are nullary
  -- therefore (deepseq (rnf x) y) = seq (rnf x) y
  -- but then seq (rnf x) y = deepseq x y {by definition}
  rnf (App o l r) = o `deepseq` l `deepseq` rnf r

haskell - Haskell：并行列表计算

问题描述

解决方案

推荐阅读