具有快速随机性和纯度的并行计算？

Question

我的目标是使用parallel package中的parMap来并行计算，但我也想在我的抽样函数中添加一些随机性。

如果没有随机性，我的计算只是一些数字计算，因此它是纯的，我可以使用parMap。为了得到好的结果，我需要在每个步骤中进行多次抽样并平均结果。抽样需要随机化。

一个解决方案可能是使用random package，调用randoms，然后在计算过程中消耗该列表（通过将纯的惰性列表传递给计算，我将使其保持纯）。不幸的是，那是一个非常慢的随机数生成器，我需要很多随机数，所以我更喜欢使用mwc-random或mersenne-random（尽管我认为mersenne-random已经不再维护）。

使用像unsafePerformIO这样的东西与mwc-random一起编写像randoms这样的函数是否安全？就像这样：

randomsMWC :: Variate a => GenST s -> [a]
randomsMWC g = unsafePerformIO $ unsafeSTToIO $ randomsMWC' g
  where
  randomsMWC' g = do
    a  <- uniform g
    as <- unsafeInterleaveST $ randomsMWC' g
    return (a : as)

我需要使用并行数生成器吗？还是我需要咬紧牙关承认我的算法没有使用缓慢的随机包就不够纯粹？

有什么建议吗？谢谢！

- Jason Dagit

---

mersenne-random-pure64 既快速又允许多个生成器 - 因此您可以为每个线程拥有一个生成器。 - Don Stewart

@DonStewart 多个生成器对于并行Haskell来说完全没有用处。在并行代码中，没有使用线程特定资源的设施，也不应该有 - 这会引入非确定性。这确实是一个难题。 - Carl

Carl - 不是这样的。你可以以数据并行的方式复制随机生成器，避免对共享资源的争用。例如，可以考虑树形结构的约简。 - Don Stewart

Answer 1

如果单线程的随机源不会影响性能，你可以使用纯包装器mwc-random

import Control.Monad.ST.Lazy
import Control.Monad
import System.Random.MWC

rList :: Variate a => Seed -> [a]
rList s = runST $ do
  g <- strictToLazyST $ restore s
  advance g

advance :: Variate a => Gen s -> ST s [a]
advance g = do
  x <- strictToLazyST $ uniform g
  xs <- x `seq` advance g
  return (x:xs)

这里的rList接受一个种子，然后惰性地产生无限个确定性的懒数。我不确定strictToLazyST是否真的安全，但没有人反对它。我没有做任何基准测试，但我认为这应该很快。我假设mwc-random是线程安全的，因为生成器中编码了显式数据流，并且它可以在ST单子中使用。邀请某人使用上述技巧。我认为seq不是必需的，但它让我对strictToLazyST更加放心，因为我知道我有确定性的评估顺序（而且它仍然足够懒惰以工作）。

你仍然需要随机性（也就是IO）来生成真正的随机种子，但这应该让你保持大部分代码纯粹，并让你在必要时存储种子到文件或重复使用它。

GHCi:

λ: gen <- create
λ: x <- save gen
λ: drop 1 $ take 10 $ rList x :: [Int]
[4443157817804305558,-6283633474236987377,3602072957429409483,
 -5035101780705339502,-925260411398682800,423158235494603307,
 -6981326876987356147,490540715145304360,-8184987036354194323]

- Philip JF

Answer 2

我在Github上有一个不完全适用的软件包hsrandom123，可能会对此有所帮助。我开始实现这个包，以便为并行计算提供合适的随机数生成器（RNG）。它重新实现了来自C库random123的Philox和Threefry RNGs（那里也有一篇描述这些想法的论文）。

然而，我的库未发布的原因是：虽然实际的RNG实现已经完成，并且似乎产生了与C版本相同的结果，但我一直无法决定使用什么Haskell接口，并且该库几乎没有文档。如果需要更多信息或帮助使用它，请随时与我联系。

- kosmikus

---

有趣。如果尚未发布，我不认为我想使用它，但我期待将来尝试它。 - Jason Dagit

有趣的是，最近我也一直在开发Haskell版本的Random123，尽管我发誓之前进行了谷歌搜索，但没有找到其他任何Haskell实现。我的代码可以在github.com/Manticore/haskell-random123上找到，也可以在Hackage上找到Random123（不过既然你已经有了优先权，我准备放弃Hackage的条目）。 - fjarri

啊，太遗憾了，我们没有协调好工作。我的版本已经在 Github 上有一段时间了，但由于它还没有在 Hackage 上，我想很容易被忽视。我很快会看看你的版本。我想我会坚持使用 hsrandom123 这个名称。如果我们能就差异达成明确的协议，那么我们应该将它们包含在文档中，以便用户可以做出知情的选择。 - kosmikus

Answer 3

我的猜测是 mersenne-random 不是线程安全的，因此使用任何 unsafe... 和并行化将导致在多个线程中调用它时出现问题。（请参见GHC手册第8.2.4.1节。）

需要随机性的函数不是纯函数，它们需要一些随机来源，这些来源要么是外部的（硬件 - 如设备采样噪声），因此绑定到 IO，要么是伪随机数，需要在计算过程中保持某些状态。无论哪种方式，它们都不能成为纯 Haskell 函数。

我建议从将您的要求分离到特定的单子类型类开始，例如：

class Monad m => MonadParRand m where
    random      :: MTRandom a => m a
    parSequence :: [m a] -> m [a]

这将允许您编写主要代码，而不受特定实现的限制。或者，如果您感到大胆，可以使用monad-parallel并定义类似以下内容的东西：

class MonadParallel m => MonadParRand m where
    random      :: MTRandom a => m a

现在最棘手的部分是如何同时定义random和parSequence（或MonadParallel的bindM2）并使其快速运行。由于您控制着bindM2，因此可以管理线程的生成方式以及它们保留的状态。因此，您可以将缓冲区绑定到每个线程，从中获取随机数。如果缓冲区为空，则会进行同步调用mersenne-random（或另一个基于IO的数字生成器），填充缓冲区并继续执行。

（如果您实现了这样的内容，将其制作成独立的库将非常好。）

---

请注意，mersenne-random库中的randoms已经使用unsafeInterleaveIO生成了一个惰性列表，但我认为该列表只应从单个线程中使用。此外，它还有改进的余地。正如其注释中所述，它使用unsafeInterleaveIO并且存在一些开销：

这里确实有一些开销。考虑急切地填充块并逐个提取元素。

- Petr

---

一个接受 PRNG 并返回 PRNG 和其他内容的函数仍然是相当纯净的。 - Carl

@Carl 我明白了，这只是术语的问题。我使用“纯”的意思是“如果一个函数产生类型为a的值，则该函数的类型为a，则它是纯的”。你可能使用的是“如果一个函数产生类型为a的值，则该函数不涉及IO，则它是纯的”的意思。有关“纯”的含义的有趣和启发性文章是Conal Elliots The C language is purely functional。 - Petr

不，我使用它的意思是“输出仅由输入决定”。这才是“纯”的实际有用含义。 - Carl

@Carl 确实，这是一个明智的定义，我想指出的是，在这个意义上，所有 Haskell 函数都是纯函数（这就是为什么我们非常喜欢 Haskell），无论它们是否涉及 IO。例如，getLine 是一个真正的常量 - 它没有副作用，像在 const () $! getLine 中评估它一样什么也不做。它的输出是一个常量值，描述了一个动作，当 Haskell 运行时执行它时会做一些事情，但在函数被评估时不会发生。我们之所以认为它是“不纯”的，是因为我们通常关注它在执行时做了什么。 - Petr

Answer 4

为了完整性起见，让我解释一下我目前解决这个问题的方法。

我选择使用 async 包而不是 parallel，而不是尝试让计算变得纯粹。

如果我决定修改当前的解决方案以使其更加纯粹，我将首先尝试 Philip JF 建议的解决方案，所以我已经将他的答案标记为被接受的答案。

我的下一个挑战是找出如何近似最佳块大小，以便线程化减少时间而不是使其花费更长的时间 :)

- Jason Dagit