为什么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是否isPrime 3再次调用素数,并且还检查5 .同样,对于几乎每个奇数,isPrime 3并且isPrime 5一次又一次地被调用.

因此,我认为,当我使用时-O0,primes并不是[2]每次isPrime调用时都进行缓存和构造.所以第一个问题是为什么-O0并-O1改变评估的行为.

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

但当我将代码移动到另一个文件时,问题再次出现.我刚搬到primes并isPrime以Prime.hs.

test.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,我一次又一次地看到2和3的-O3旗帜.总之,由于评价方式发生变化时,我无法创建总理库primes,并isPrime移动到一个模块(这让我吃惊)和-O3不使其工作.

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

我终于厌倦了调查这种有线行为.我总结说我不应该在模块中使用交叉引用的定义.我放弃了创建我的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具体类型.然后即使天真地使用它也会备忘.