Могут ли оптимизации компилятора, такие как ghc -O2, изменить порядок (время или память) программы? - PullRequest
Новая
       13

Могут ли оптимизации компилятора, такие как ghc -O2, изменить порядок (время или память) программы?

9 голосов
/ 03 октября 2011

У меня такое ощущение, что ответ - да, и это не ограничивается Хаскеллом. Например, оптимизация хвостового вызова изменяет требования к памяти с O (n) на O (l), верно?

Мое точное беспокойство: в контексте Haskell, что ожидается понять об оптимизации компилятора при рассуждении о производительности и размере программы?

В Схеме вы можете принять некоторые оптимизации как должное, например TCO, при условии, что вы используете интерпретатор / компилятор, который соответствует спецификации.

1 Ответ

15 голосов
/ 03 октября 2011

Да, в частности, GHC выполняет анализ строгости , который может значительно сократить использование памяти программой с непреднамеренной ленью с O (n) до O (1) .

Например, рассмотрим эту тривиальную программу: 

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

Поскольку sum не предполагает строгости оператора сложения (он может использоваться с экземпляром Num, для которого (+) является ленивым), это приведет к выделению большого количества группировок. Без включенной оптимизации анализ строгости не выполняется. 

$ 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, который, как известно, является строгим, компилятор знает, что безопасно вычислять переданные значения времени, и поэтому программа работает в постоянном пространстве. 

$ 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

Строгость имеет тенденцию быть большей проблемой, чем хвостовые вызовы, которые не очень полезны в Haskell из-за оценочной модели Haskell.

...