您好,我遇到了 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
.提前致谢。
最佳答案
这里发生的事情在以下签名中:
primes :: Integral a => [a]
类型类阻止
primes
从天真地记住。 primes :: [Int]
与 primes :: [Integer]
不一样.并且不能共享任何计算,因为 GHC 不能假设 Num
的所有实例遵循同样的逻辑。因此,每次使用 primes
最终以所选类型重新计算列表。但是当您启用优化时,GHC 会变得更加智能。当
primes
唯一使用与定义在同一个模块中,GHC 可以将其优化到它所使用的具体类型。然后计算在列表的使用之间共享。不过,它只在模块边界内执行此操作。模块的单独编译意味着如果
primes
被导出,它不能被专门化为一个具体的类型 - GHC 永远不知道它将编译的下一个模块是否可能使用 primes
在不同的类型。解决此问题的最简单方法是提供
primes
一种具体的类型。然后,即使是天真的使用它也会记住。
关于haskell - 为什么 ghc 由于优化标志而改变了评估方式?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25958007/