haskell - 为什么 ghc 由于优化标志而改变了评估方式？

Question

您好，我遇到了 ghc 优化标志的有线行为。优化标志似乎改变了评估方式。总之，

我写了一个包含primes的代码和 isPrime通过相互引用来定义。

我发现该程序适用于 ghc -O3 ，但我无法使用 runhaskell得到结果。它花费太多时间。

我注意到当我使用 ghc -O1 时，结果立即显示为 -O3 , 但是由 ghc -O0 编译的可执行文件无法在一分钟内计算出结果。

我用了Debug.Trace.trace找到 primes每次 isPrime 时都会从其开始进行评估叫做。

我移动了 primes 的定义和 isPrime到另一个文件 Prime.hs .在主文件中，我导入了我的 Prime 库。不幸的是，ghc -O3 编译的可执行文件不会在一分钟内计算出结果。

这是描述。请看下面的代码。

main :: IO ()
main = print $ length $ filter isPrime [100000..1000000]

primes :: Integral a => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: Integral a => a -> Bool
isPrime n = n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

当我用 ghc -O3 编译代码时，可执行文件计算正确的结果 68906在 2 秒内。

 $ ghc -O3 test.hs
[1 of 1] Compiling Main             ( test.hs, test.o )
Linking test ...
 $ time ./test
68906
./test  1.24s user 0.02s system 79% cpu 1.574 total

但是，当我使用 -O0 ，我无法在一分钟内得到结果。请务必提前删除生成的文件。

 $ rm -f ./test ./test.o ./test.hi
 $ ghc -O0 test.hs
[1 of 1] Compiling Main             ( test.hs, test.o )
Linking test ...
 $ time ./test
^C
./test  64.34s user 0.94s system 94% cpu 1:08.90 total

我流产了。旗帜 -O1效果与 -O3 相同.

因此，让我们深入调查。我用了 Debug.Trace.trace .我追踪了 isPrime 的论点.

import Debug.Trace

main :: IO ()
main = print $ length $ filter isPrime [10..30]

primes :: (Show a, Integral a) => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: (Show a, Integral a) => a -> Bool
isPrime n = trace (show n) $ n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

当优化标志为 -O3 时, (或 -O1 )，输出如下。

10
11
3
5
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
7
30
6

这个结果是合理的(注意最后一行打印素数的数量；11、13、17、19、23、29)。

这是 -O0 的结果(或 runhaskell )

10
11
3
5
3
12
13
3
5
3
14
15
3
16
17
3
5
3
18
19
3
5
3
20
21
3
22
23
3
5
3
24
25
3
5
3
26
27
3
28
29
3
5
3
7
3
30
6

这个结果很有趣。 2 已经排在 primes 的头部.如果 isPrime 则检查 3 和 5一次又一次。当 isPrime 11被调用，如果是素数，则检查 3，并且还检查 5， isPrime 3被再次调用。同样，对于几乎所有奇数， isPrime 3和 isPrime 5被一次又一次地调用。

因此，我认为当我使用 -O0 , primes未缓存并从 [2] 构造每次都是 isPrime叫做。所以第一个问题是为什么 -O0和 -O1改变评估的行为。

这是另一个问题。好吧好吧，不过我很少用 -O0旗帜。在大多数情况下，我使用 -O2或 -O3优化标志所以我认为上述问题不会出现在许多用例中。

但是当我将代码移到另一个文件中时，问题又出现了。我刚搬了 primes和 isPrime到 Prime.hs。

测试.hs:

import Prime

main :: IO ()
main = print $ length $ filter isPrime [100000..1000000]

Prime.hs:

module Prime where

primes :: Integral a => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: Integral a => a -> Bool
isPrime n = n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

这一次，我无法获得 -O1 的结果。标志，甚至是 -O3旗帜。

 $ ghc -O3 test.hs
[1 of 2] Compiling Prime            ( Prime.hs, Prime.o )
[2 of 2] Compiling Main             ( test.hs, test.o )
Linking test ...
 $ time ./test
^C
./test  62.41s user 0.88s system 92% cpu 1:08.23 total

嗯，我又流产了。不知道这种方式对结果有没有影响，我用 -O3预编译了Prime.hs提前，但徒劳无功。我特此使用 Debug.Trace.trace我用 -O3 一次又一次地看到 2 和 3旗帜。简而言之，我无法创建 Prime 库，因为 primes 时评估方式发生了变化。和 isPrime被移动到一个模块中(这让我很惊讶)和 -O3不能让它工作。

所以第二个问题是，尽管 -O3标志，为什么模块中的东西被评估为由 -O0 编译旗帜？

我终于厌倦了调查这种有线行为。我得出结论，我不应该在模块中使用交叉引用的定义。我放弃了创建我的 Prime 库并开始使用 Data.Numbers.Primes .

提前致谢。

Answer 1

这里发生的事情在以下签名中:

primes :: Integral a => [a]

类型类阻止 primes从天真地记住。 primes :: [Int]与 primes :: [Integer] 不一样.并且不能共享任何计算，因为 GHC 不能假设 Num 的所有实例遵循同样的逻辑。因此，每次使用 primes最终以所选类型重新计算列表。

但是当您启用优化时，GHC 会变得更加智能。当 primes唯一使用与定义在同一个模块中，GHC 可以将其优化到它所使用的具体类型。然后计算在列表的使用之间共享。

不过，它只在模块边界内执行此操作。模块的单独编译意味着如果 primes被导出，它不能被专门化为一个具体的类型 - GHC 永远不知道它将编译的下一个模块是否可能使用 primes在不同的类型。

解决此问题的最简单方法是提供 primes一种具体的类型。然后，即使是天真的使用它也会记住。