GHC的暴力有多原子？

Question

GHC如何处理多个线程(显式线程或评估spark的内部线程)访问的thunk？是否会发生多个线程评估同一个thunk,重复工作？或者,如果thunks同步,如何,这样性能不会受到影响？

Answer 1

从@Lambdageek链接的博客文章,GHC评论和GHC用户指南我拼凑了以下内容:

GHC试图阻止重新评估的thunk,但由于线程之间真正锁定价格昂贵,而且的thunk通常是纯等无害重新评估,它通常这样的马虎态度,用小无论如何重复工作的机会.

它用于避免工作的方法是用黑洞替换thunk,这是一个特殊的标记,它告诉<<loop>>正在评估thunk的其他线程(或者有时,线程本身;这是检测发生的方式).

鉴于此,至少有三种选择:

• 默认情况下,它使用"lazy blackholing",这只在线程即将暂停之前完成.然后它"移动"它的堆栈并为新的thunk创建"真正的"黑洞,使用锁定来确保每个thunk只获得一个黑洞,并且如果它发现另一个线程已经黑洞一个thunk则中止它自己的评估.这样更便宜,因为它不需要考虑评估时间太短以至于完全适合两次暂停的thunk.

• 随着-feager-blackholing-flag,黑洞被创建,而不是只要一个thunk开始评估和用户指南建议,如果您已做了很多并行的.但是,因为每个thunk上的锁定都太昂贵,所以这些黑洞是更便宜的"渴望",它们与其他线程不同步(尽管如果没有竞争条件,其他线程仍然可以看到它们).只有当线程暂停时,这些才会变成"真正的"黑洞.

• 博客文章特别关注的第三种情况是用于特殊功能,例如unsafePerformIO,不止一次评估thunk 是有害的.在这种情况下,线程使用具有真实锁定的"真实"黑洞,但通过在真实评估之前插入人工线程暂停来立即创建它.

Answer 2

总结一下在评论中链接的文章: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,这在宏观方案中相当便宜.

Answer 3

是的,有时可以通过多个线程评估相同的thunk.GHC运行时试图最小化重复工作的可能性,因此在实践中很少见.有关低级别详细信息,请参阅"共享内存多处理器上的Haskell"文章,主要是"无锁定thunk评估"部分.(我会为每个专业的haskell开发人员推荐这篇论文.)