这个 运行 应该并行吗？
Should this run in parallel?
我的印象是 Haskell 会 运行 类似下面的程序并行（每个 a,b,c 组合将独立地通过所有 filter 推送).
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]]
但是当我 运行 程序时，我可以看到我机器上的四个线程中只有一个被使用了。
为什么我的期望是错误的？
Should this run in parallel?
不，因为默认情况下 GHC 不添加并行性（见下文）。此外，并行性不是一个方便的轨道炮，它可以解决任何问题（见下文）。
Why is my expectation wrong?
首先，使用 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，但是 a = 0 和 b = 500 没有 c。
我们最终得到以下列表：
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 将在我的 PC 上 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
TL;DR
将工作减少到其原始大小的极小值总是胜过 运行 过多的并行工作。
我的印象是 Haskell 会 运行 类似下面的程序并行（每个 a,b,c 组合将独立地通过所有 filter 推送).
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]]
但是当我 运行 程序时，我可以看到我机器上的四个线程中只有一个被使用了。
为什么我的期望是错误的？
Should this run in parallel?
不，因为默认情况下 GHC 不添加并行性（见下文）。此外，并行性不是一个方便的轨道炮，它可以解决任何问题（见下文）。
Why is my expectation wrong?
首先，使用 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，但是a = 0和b = 500没有c。
我们最终得到以下列表：
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 将在我的 PC 上 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
TL;DR
将工作减少到其原始大小的极小值总是胜过 运行 过多的并行工作。