我的印象是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]]
但是当我运行程序时,我可以看到我机器上的四个线程中只有一个被利用了.
为什么我的期望错了？
Zet*_*eta 15
它应该并行运行吗？
不,因为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 永远大于 ab永远不会大于(1000 - a) / 2,否则没有合适的cc总是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
将工作减少到原始尺寸的微小优势总是胜过太多并行工作.