它应该并行运行吗？

我的印象是Haskell会同时运行一个类似下面的程序(每个a,b,c组合都会被filter独立地推送到所有s).

main = print $ 
       map (\(a,b,c) -> a * b * c) $
       filter (\(a,b,c) -> a^2 + b^2 == c^2) $
       filter (\(a,b,c) -> a + b + c == 1000) $
       filter (\(a,b,c) -> a < b && b < c) $
       [(a,b,c) | a <- [0..1000], b <- [0..1000], c <- [0..1000]]

但是当我运行程序时,我可以看到我机器上的四个线程中只有一个被利用了.

为什么我的期望错了？

它应该并行运行吗？

不,因为GHC默认不添加并行性(见下文).此外,并行性不是一种方便的轨道加农炮,它可以解决任何类型的问题(见下文).

为什么我的期望错了？

首先,使用runhaskell与使用GHCi大致相同:它没有使用优化,因为-O与--interactive它冲突,它没有给你额外的RTS选项,你不能使用所有那些很好的编译器标志,给你一点点果汁.

但即使您使用线程运行时编译代码,您也不会得到更快的可执行文件:

$ ghc --make -O2 -rtsopts -with-rtsopts -N -threaded SO.hs 
$ .\SO +RTS -s
[31875000]
   2,863,269,440 bytes allocated in the heap
       1,135,584 bytes copied during GC
         100,016 bytes maximum residency (2 sample(s))
          31,152 bytes maximum slop
               2 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0      5471 colls,  5471 par    0.266s   0.283s     0.0001s    0.0126s
  Gen  1         2 colls,     1 par    0.000s   0.001s     0.0004s    0.0007s

  Parallel GC work balance: 0.00% (serial 0%, perfect 100%)

  TASKS: 4 (1 bound, 3 peak workers (3 total), using -N2)

  SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)

  INIT    time    0.000s  (  0.001s elapsed)
  MUT     time   20.328s  ( 21.671s elapsed)     <-------
  GC      time    0.266s  (  0.284s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time   20.609s  ( 21.956s elapsed)

  Alloc rate    140,852,608 bytes per MUT second

  Productivity  98.7% of total user, 92.7% of total elapsed

那是因为GHC不会自动添加并行性.虽然只需翻转一个开关就可以了,但如果做错了,并行性会导致相当高的开销.例如,如果f :: Int -> T是一个复杂的函数,那么运行head $ filter p $ parallelMap f [1..100]可能就好了.但是head $ filter p $ parallelMap f [1..]不再打电话了.毕竟,Haskell是懒惰的.

现在您已经知道为什么Haskell中没有自动并行性,您可以做些什么来加速您的程序？首先,构建它:

triples :: [(Int, Int, Int)]
triples = filter pythagoras . filter smaller . filter sum1000 $ ts
  where 
    pythagoras (a,b,c) = a ^ 2 + b ^ 2 == c ^ 2
    sum1000    (a,b,c) = a + b + c == 1000
    smaller    (a,b,c) = a < b && b < c

    ts = [(a,b,c) | a <- [0..1000], b <- [0..1000], c <- [0..1000]]

main :: IO ()
main = print $ map (\(a,b,c) -> a * b * c) $ triples

现在,这比以前的程序更容易阅读.嗯.您生成一个列表,然后应用三个过滤器.等一等.sum1000而smaller似乎关闭.对于任何给定的范围内,即符合三元的数量smaller通常比较小,并且对于任何给定a和b,有只是一个 c是满足sum1000!

我们可以融合这两个条件同时得到以下的人a,b和c直接:

a永远不能大于332,因为我们不能拆分1000 - 333成b和c,这样smaller仍持有(667 = 333 + 334)

b 永远大于 a

b永远不会大于(1000 - a) / 2,否则没有合适的c

c总是1000 - a - b,但没有c为a = 0和b = 500.

我们最终得到以下列表:

triples :: [(Int, Int, Int)]
triples = filter pythagoras . filter smaller . filter sum1000 $ ts
  where
    pythagoras (a,b,c) = a ^ 2 + b ^ 2 == c ^ 2
    sum1000    (a,b,c) = a + b + c == 1000
    smaller    (a,b,c) = a < b && b < c

    ts = [(a,b,c) | a <- [0..332]
                  , b <- [a+1 .. (1000 - a)`div` 2]
                  , let c = 1000 - a - b]

-- Old list for documentation
--  ts = [(a,b,c) | a <- [0..1000], b <- [0..1000], c <- [0..1000]]

您也可以删除过滤器,但不要忘记检查b < c.

这要快得多,因为我们现在使用O(n²)方法而不是O(n³)方法.runhaskell SO.hs将在我的电脑上完成2秒后完成,如果我们实际编译它,我们最终会得到一个几乎立即完成的可执行文件:

$ ghc --make -O2 SO.hs
$ ./SO +RTS -s
[31875000]
         104,960 bytes allocated in the heap
           1,752 bytes copied during GC
          42,664 bytes maximum residency (1 sample(s))
          18,776 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0         0 colls,     0 par    0.000s   0.000s     0.0000s    0.0000s
  Gen  1         1 colls,     0 par    0.000s   0.000s     0.0005s    0.0005s

  INIT    time    0.000s  (  0.001s elapsed)
  MUT     time    0.000s  (  0.002s elapsed)  <----------------
  GC      time    0.000s  (  0.000s elapsed)
  EXIT    time    0.000s  (  0.001s elapsed)
  Total   time    0.000s  (  0.003s elapsed)

  %GC     time       0.0%  (13.9% elapsed)

  Alloc rate    0 bytes per MUT second

  Productivity 100.0% of total user, 0.0% of total elapsed

将工作减少到原始尺寸的微小优势总是胜过太多并行工作.