haskell - 编译器优化(例如 ghc -O2)可以更改程序的顺序(时间或存储)吗？

Question

我感觉答案是肯定的，而且这不仅限于 Haskell。例如，尾部调用优化将内存需求从 O(n) 更改为 O(l)，对吗？

我真正关心的是:在 Haskell 上下文中，在推理程序的性能和大小时，期望了解编译器优化的哪些内容？

在Scheme中，你可以认为一些优化是理所当然的，比如TCO，只要你使用的是符合规范的解释器/编译器。

Answer 1

是的，特别是 GHC 执行严格性分析，这可以将具有意外惰性的程序的空间使用量从 O(n) 大幅减少到 O(1 )。

例如，考虑这个简单的程序:

$ cat LazySum.hs
main = print $ sum [1..100000]

由于 sum 并不假定加法运算符是严格的，(它可能与 Num 实例一起使用，其中 (+)是懒惰的)，会导致分配大量的thunk。如果未启用优化，则不会执行严格性分析。

$ ghc --make LazySum.hs -rtsopts -fforce-recomp
[1 of 1] Compiling Main             ( LazySum.hs, LazySum.o )
Linking LazySum ...
$ ./LazySum +RTS -s
./LazySum +RTS -s 
5000050000
      22,047,576 bytes allocated in the heap
      18,365,440 bytes copied during GC
       6,348,584 bytes maximum residency (4 sample(s))
       3,133,528 bytes maximum slop
              15 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:    23 collections,     0 parallel,  0.04s,  0.03s elapsed
  Generation 1:     4 collections,     0 parallel,  0.01s,  0.02s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    0.01s  (  0.03s elapsed)
  GC    time    0.05s  (  0.04s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    0.06s  (  0.07s elapsed)

  %GC time      83.3%  (58.0% elapsed)

  Alloc rate    2,204,757,600 bytes per MUT second

  Productivity  16.7% of total user, 13.7% of total elapsed

但是，如果我们在启用优化的情况下进行编译，严格性分析器将确定，由于我们对 Integer 使用已知严格的加法运算符，因此编译器知道它是安全的提前评估 thunk，因此程序在恒定空间中运行。

$ ghc --make -O2 LazySum.hs -rtsopts -fforce-recomp
[1 of 1] Compiling Main             ( LazySum.hs, LazySum.o )
Linking LazySum ...
$ ./LazySum +RTS -s
./LazySum +RTS -s 
5000050000
       9,702,512 bytes allocated in the heap
           8,112 bytes copied during GC
          27,792 bytes maximum residency (1 sample(s))
          20,320 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:    18 collections,     0 parallel,  0.00s,  0.00s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    0.01s  (  0.02s elapsed)
  GC    time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    0.01s  (  0.02s elapsed)

  %GC time       0.0%  (2.9% elapsed)

  Alloc rate    970,251,200 bytes per MUT second

  Productivity 100.0% of total user, 55.0% of total elapsed

请注意，如果我们自己添加严格性，即使没有优化，我们也可以获得恒定的空间:

$ cat StrictSum.hs 
import Data.List (foldl')
main = print $ foldl' (+) 0 [1..100000]
$ ghc --make StrictSum.hs -rtsopts -fforce-recomp
[1 of 1] Compiling Main             ( StrictSum.hs, StrictSum.o )
Linking StrictSum ...
$ ./StrictSum +RTS -s
./StrictSum +RTS -s 
5000050000
       9,702,664 bytes allocated in the heap
           8,144 bytes copied during GC
          27,808 bytes maximum residency (1 sample(s))
          20,304 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:    18 collections,     0 parallel,  0.00s,  0.00s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    0.00s  (  0.01s elapsed)
  GC    time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    0.00s  (  0.01s elapsed)

  %GC time       0.0%  (2.1% elapsed)

  Alloc rate    9,702,664,000,000 bytes per MUT second

  Productivity 100.0% of total user, 0.0% of total elapsed

严格性往往是比尾部调用更大的问题，aren't really a useful concept in Haskell ，因为Haskell的评估模型。