49

GHC 如何处理由多个线程（显式线程或评估火花的内部线程）访问的 thunk？是否会发生多个线程评估相同的 thunk、重复工作？或者，如果 thunk 是同步的，如何使性能不受影响？

4

3 回答 3

44

从@Lambdageek 链接的博客文章、 GHC 评论和GHC 用户指南中，我将以下内容拼凑在一起：

GHC 试图阻止重新评估 thunk，但由于线程之间的真正锁定代价高昂，并且 thunk 通常是纯粹的并且重新评估无害，它通常以草率的方式执行此操作，无论如何重复工作的可能性很小。

它用来避免工作的方法是用blackhole替换 thunk，这是一个特殊的标记，告诉其他线程（或有时，线程本身；这就是<<loop>>检测发生的方式）正在评估 thunk。

鉴于此，至少有三种选择：

  • 默认情况下，它使用“惰性黑洞”，这仅在线程即将暂停之前完成。然后它“遍历”它的堆栈并为新的 thunk 创建“真正的”黑洞，使用锁定来确保每个 thunk 只有一个线程将其黑洞化，如果它发现另一个线程已经黑洞化了一个 thunk，则中止自己的评估。这更便宜，因为它不需要考虑评估时间太短以至于完全适合两个暂停之间的 thunk。

  • 使用-feager-blackholing-flag，一旦 thunk 开始评估，就会创建黑洞，如果您正在执行大量并行操作，则用户指南建议这样做。然而，由于锁定每个 thunk 的成本太高，这些黑洞是更便宜的“急切”的，它们不与其他线程同步（尽管如果没有竞争条件，其他线程仍然可以看到它们）。只有当线程暂停时，这些才会变成“真正的”黑洞。

  • 第三种情况，博客文章特别提到，用于特殊功能，例如unsafePerformIO，对于这种情况，多次评估 thunk是有害的。在这种情况下，线程使用具有真正锁定的“真正”黑洞，但通过在真正评估之前插入人工线程暂停来立即创建它。

于 2015-08-12T19:48:42.260 回答
22

总结评论中链接的文章：GHC 中的 thunk 在多个线程之间并不是严格的原子：在竞争条件下，多个线程可能会评估相同的 thunk，从而重复工作。但是，这在实践中并不是什么大问题，因为：

  1. 保证纯度意味着就程序语义而言，是否对 thunk 进行两次评估都无关紧要。unsafePerformIO在这种情况下，这可能是一个问题，但事实证明unsafePerformIO要小心避免重新运行相同的 IO 操作。

  2. 因为所有值都是 thunk，所以大多数 thunk 都非常小，所以偶尔复制工作来强制一个在程序速度方面并不是什么大问题。例如，您可能会想象复制成本很高，last [1,2..10000000]因为整个计算成本很高。但当然，最外面的 thunk 只是解析为另一个 thunk，例如：

    case [1,2..10000000] of 
  [x] -> x
  (_:xs) -> last xs
  [] -> error "empty list"

    如果两个线程重复工作以将调用转换last为对的使用case，那么在宏伟的计划中这是相当便宜的。

于 2015-08-12T19:40:16.353 回答
13

是的，有时可以由多个线程评估相同的 thunk。GHC 运行时试图最小化重复工作的可能性，因此在实践中很少见。请参阅“Haskell on a Shared-Memory Multiprocessor”论文了解底层细节，主要是“Lock-free thunk evaluation”部分。（顺便说一句，我会向每位专业的 Haskell 开发人员推荐这篇论文。）

于 2015-08-12T19:43:54.670 回答