Haskell中的共享变量在parMap中的应用

Question

我有一个基本上做以下操作的计算机程序：

f :: [a] -> ([b],Bool)

实际上，这个函数可以被写成

f = foldr h ([],False) . map g
    where h (b,bool) (bs,boolSoFar) = (b:bs,bool || boolSoFar)

其中 g :: a -> (b,Bool) 是一个需要花费很长时间的函数。而且f通常用于小列表，因此尝试使用并行计算来计算映射可能是有趣的。这可以通过Control.Parallel.Strategies中的parMap来实现。因此我们现在使用：

f = foldr h ([],False) . parMap rseq g
    where h (b,bool) (bs,boolSoFar) = (b:bs, bool || boolSoFar)

这一切都很好。现在，您会注意到第一个f的定义中可以执行顺序优化。也就是说，我可以使用映射折叠融合将其写为单个折叠，从而只需一次循环即可。但是，那样做就失去了并行化带来的好处。

现在，有人可能会说，在第二个f的定义中再次循环列表并不那么糟糕，那为什么不直接这样做呢？我想的是，如果 Haskell 有可变变量，那么在 map 的主体中，就可以更新这个布尔变量（我想您需要锁定和解锁它）。有没有关于类似于这样做的建议？

- Jonathan Gallagher

---

我很怀疑使用可变变量来存储布尔值会使其更快。你是否在代码中运行过分析器以查看减速发生在哪里？你可能过于专注于优化简单的东西，而你的效率问题可能出现在其他地方。你确定 g 被并行评估了吗，还是创建了thunks并让单核foldr进行评估？ - bheklilr

嗨，感谢您的评论。实际上，我想知道这是否可能。我一直在使用分析工具进行测试等操作。显然，大部分时间都花在了映射上。我知道这一点，并且在问题中已经说明了。但是，在我的代码中，我已经看到了这种模式出现在不止一个地方，其中我会并行执行某些操作，然后按顺序执行其他操作——顺序部分是附加到计算末尾的内容，并且可以在并行部分中使用共享变量来完成。因此，我想知道如何在Haskell中实现这一点。 - Jonathan Gallagher

我刚写了一个相当幼稚的概念验证。使用了Chan而不是MVar，我会第一个承认这段代码并没有完全优化，但是map和parMap之间的差别微不足道，而与使用Chans的差别则慢了一个数量级。这是一个很好的例子，说明GHC可以自己处理事情，而无需引入复杂的线程机制。 - bheklilr

我如何判断我是否在并行创建thunks并像正常情况下通过foldr进行评估，还是实际上正在并行评估？ 我是否可以进行分析并查看设置并行执行的开销是否否定了并行处理的好处？ - Jonathan Gallagher

这里详细描述了一些技术，网址为http://www.haskell.org/haskellwiki/Performance/Strictness，但总的来说，有以下几种方法：a）模式匹配，b）严格的`$!`运算符，以及c）BangPatterns。个人而言，我喜欢使用`$!`，因为它简短而精炼，但并不是每种情况都适用，所以BangPatterns也非常有用，例如`let !result = expr in result`。 - bheklilr

Answer 1

这实际上将成为一个遍历懒惰写入器 Applicative，其中写入状态为 Bool，因为 (False, (||)) 形成一个幺半群。您还需要 unamb 包，以便在并行调用 g 的任何一次返回 True 时获取值。

import Control.Parallel.Strategies
import Data.Unamb

newtype EvalWB a = EvalWB { runEvalWB :: Eval (a, Bool) }

instance Functor EvalWB where
  fmap f (EvalWB m) = EvalWB $ fmap (\ ~(a, b) -> (f a, b)) m

instance Applicative EvalWB where
  pure a = EvalWB $ pure (a, False)

  EvalWB mf <*> EvalWB ma = EvalWB $ (\ ~(f, bf) ~(a, ba) -> (f a, por bf ba)) <$> mf <*> ma

然后你有

f :: [a] -> ([b], Bool)
f l = runEval $ runEvalWB $ traverse (\a -> EvalWB $ rpar $ g a) l

这个函数会并行遍历整个列表，惰性地累加值和标志。它使用 por 来在第一个 True 返回时进行短路处理。

- Zemyla

Answer 2

你不能使用State Monad吗？将函数f从以下形式改变：

f :: [a] -> ([b], Bool)

to:

f :: [a] -> State Bool [b]

你只需要通过一次列表折叠更新你的状态值，是吗？不过我不确定你是否可以在并行处理中应用它。我的 Haskell 知识有些有限。

- Cake

---

不，你不能并行执行这个操作。 - SamB

我想可能需要一些细节：你不能并行地执行它，因为 State 它是表示为s -> (a, s)，而状态通过 >>= 沿着计算传递，所以每个计算部分必须在相对于其他计算部分严格地排序。（其他 State 函子工作方式类似。） - SamB