为什么Haskell中没有隐式并行性？

Question

Haskell功能强大且纯粹,所以基本上它具有编译器能够处理隐式并行性所需的所有属性.

考虑这个简单的例子:

f = do
  a <- Just 1
  b <- Just $ Just 2
  -- ^ The above line does not utilize an `a` variable, so it can be safely
  -- executed in parallel with the preceding line
  c <- b
  -- ^ The above line references a `b` variable, so it can only be executed
  -- sequentially after it
  return (a, c)
  -- On the exit from a monad scope we wait for all computations to finish and 
  -- gather the results

示意性地,执行计划可以描述为:

               do
                |
      +---------+---------+
      |                   |
  a <- Just 1      b <- Just $ Just 2
      |                   |
      |                 c <- b
      |                   |
      +---------+---------+
                |
           return (a, c)

为什么编译器中没有使用flag或pragma实现这样的功能呢？有什么实际的原因？

Answer 1

这是一个长期研究的主题.虽然你可以在Haskell代码中隐式地导出并行性,但问题在于,对于当前的硬件来说,存在太多的并行性,太细粒度.

所以你最终会花费精力记账,而不是更快地运行.

由于我们没有无限的并行硬件,所以关键是要选择正确的粒度 - 太粗糙,而且会有空闲的处理器,太精简,而且开销也是不可接受的.

我们所拥有的是更粗粒度的并行性(火花),适用于生成数千或数百万个并行任务(因此不在指令级别),这些任务可以映射到我们今天通常可用的少数几个核心.

请注意,对于某些子集(例如,阵列处理),存在具有紧凑成本模型的全自动并行化库.

有关此背景,请参阅http://research.microsoft.com/en-us/um/people/tharris/papers/2007-fdip.pdf,其中介绍了插入par任意Haskell程序的自动化方法.

Answer 2

虽然你的代码块可能不是最好的例子,因为a和之间的隐式数据依赖b,值得注意的是这两个绑定在那里通勤

f = do
  a <- Just 1
  b <- Just $ Just 2
  ...

会给出相同的结果

f = do
  b <- Just $ Just 2
  a <- Just 1
  ...

所以这仍然可以以投机的方式并行化.值得注意的是,这不需要与monad有任何关系.例如,let我们可以并行地评估-block中的所有独立表达式,或者我们可以引入一个版本let.Common Lisp 的lparallel库就是这样做的.

现在,我绝不是这方面的专家,但这是我对这个问题的理解.一个主要障碍是确定何时并行化多个表达式的评估是有利的.启动单独的线程进行评估会产生开销,正如您的示例所示,可能会导致工作浪费.有些表达式可能太小,无法使并行评估成为开销.根据我的理解,即将出现一个表达式成本的完全准确度量将等于解决暂停问题,因此您将降级为使用启发式方法来确定要并行评估的内容.

然后,在问题上投入更多核心并不总是更快.即使在明确地将问题与可用的许多Haskell库并行化时,由于大量的内存分配和使用以及这对垃圾收集器和CPU缓存造成的压力,通常也不会通过并行计算表达式来看到很多加速.您最终需要一个漂亮的紧凑内存布局并智能地遍历您的数据.有16个线程遍历链接列表只会使你的内存总线陷入困境,实际上可能会让事情变慢.

至少,有效并行化的表达式对于许多程序员来说并不明显(至少不是这一点),因此让编译器有效地执行它并非易事.

Answer 3

简短的回答:有时并行运行的东西变慢,而不是更快.并确定何时以及何时不是一个好主意是一个尚未解决的研究问题.

但是,您仍然可以"突然使用所有这些核心,而不必担心线程,死锁和竞争条件".这不是自动的; 你只需要给编译器一些关于在哪里做的提示!:-D