GHC 的 thunk 有多原子化？

Question

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

Answer 1

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

保证纯度意味着就程序语义而言，是否对 thunk 求值两次无关紧要。 unsafePerformIO 可能是个问题，但事实证明 unsafePerformIO 小心避免重新运行相同的 IO 操作。
因为所有的值都是thunk，大多数thunk都非常小，所以偶尔重复工作强制一个在程序速度方面不是什么大问题。您可能会认为复制 last [1,2..10000000] 是昂贵的，因为整个计算是昂贵的。但当然最外层的 thunk 只是解析为另一个 thunk，比如：
```
case [1,2..10000000] of 
  [x] -> x
  (_:xs) -> last xs
  [] -> error "empty list"
```
如果两个线程重复工作以将对 last 的调用转换为对 case 的使用，这在宏伟的计划中是相当便宜的。

Answer 2

是的，有时同一个 thunk 可以被多个线程计算。 GHC 运行时试图将重复工作的可能性降到最低，因此在实践中很少见。请参阅 "Haskell on a Shared-Memory Multiprocessor" 论文了解底层详细信息，主要是 "Lock-free thunk evaluation" 部分。（顺便说一句，我会向每位专业 haskell 开发人员推荐这篇论文。）

Answer 3

来自 the blog post @Lambdageek linked, the GHC Commentary and the GHC User's Guide 我拼凑了以下内容：

GHC 试图阻止重新评估 thunk，但由于线程之间的真正锁定是昂贵的，并且 thunk 通常是纯净的并且重新评估无害，它通常以草率的方式这样做，small 重复工作的机会。

它用于避免工作的方法是用 blackhole 替换 thunks，这是一种特殊的标记，可以告诉其他线程（或者有时，线程本身；这就是 <<loop>> 检测到）thunk 正在被评估。

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

默认情况下，它使用"lazy blackholing"，这仅在线程即将暂停之前完成。然后它 "walks" 它的堆栈并为新的 thunk 创建 "true" 黑洞，使用锁定来确保每个 thunk 只让一个线程黑洞它，如果它发现另一个线程已经黑洞了一个 thunk 就会中止自己的评估。这更便宜，因为它不需要考虑评估时间非常短以至于完全适合两次暂停之间的 thunk。
使用 -feager-blackholing-flag，一旦 thunk 开始计算，就会创建黑洞，如果您正在进行大量并行操作，用户指南建议这样做。然而，因为锁定每个 thunk 的成本太高，所以这些黑洞更便宜 "eager"，它们不与其他线程同步（尽管如果没有竞争条件，其他线程仍然可以看到它们）。只有当线程暂停时，这些才会变成 "true" 黑洞。
博客post特别提到的第三种情况，用于特殊功能，如unsafePerformIO，有害[=36] =] 多次评估 thunk。在这种情况下，线程使用了一个带有真正锁定的 "true" 黑洞，但通过在真正评估之前插入一个人工线程暂停来立即创建它。

GHC 的 thunk 有多原子化？

How atomic are GHC's thunks?

multithreading

haskell

lazy-evaluation

ghc

thunk