STUArray s i e - утечка пространства только тогда, когда я == Int?

Question

Меня смущает поведение следующего отрубленного:

import Data.Int
import Data.Array.ST
import Control.Monad.ST

{-# INLINE fib #-}
fib _ 0 = return 0
fib _ 1 = return 1
fib c n = do
  f1 <- memo c (fib c) (n-1)
  f2 <- memo c (fib c) (n-2)
  return (f1+f2)

newtype C a = C a

{-# INLINE memo #-}
memo (C a) f k = do
  e <- readArray a k
  if e == (-1)
     then do
       v <- f k
       writeArray a k v
       return v
     else return e

evalFib :: Int -> Int
evalFib n = runST $ do
  a <- newArray (0,n) (-1) :: ST s (STUArray s Int Int)
  fib (C a) n

main = print $ evalFib 120000

Когда скомпилировано с -O2 переполнение стека (показывает 20M используемой памяти). Заблуждение заключается в том, что на самом деле он работает должным образом (без переполнения стека и использования 9М памяти), если выполнено любое из следующих изменений:

• Int64 используется вместо Int: (давая evalFib :: Int64 -> Int а также STUArray s Int64 Int). На самом деле любой Int* (Int32, Int16и т. д.) будет делать то же самое, что и Word или же Word*;
• newtype C a удаляется с картинки;
• data C a = C !a используется вместо newtype

Я пытаюсь разобраться в этом поведении: это ошибка в модуле GHC/ массив (он показывает идентичное поведение в 7.4.2 а также 7.6.2) или так должно работать?

PS Самое смешное, что когда я пытаюсь скомпилировать ghc array.hs -O2 -fext-core чтобы увидеть разницу в ядре, обе версии GHC перестали работать с "ghc: panic! (произошло" невозможное ")". Не повезло и здесь..

Answer 1

Глядя на ядро ​​из 7.6.1, с -O2 а также -dsuppress-uniques, функция, которая делает работу, Main.main_$spoly_$wa структурно (почти) идентичен ли я int или же Int64 как тип индекса. Поскольку ядро ​​длинное и сложное, вот diff выход:

$ diff Int_core.dump-simpl Int64_core.dump-simpl 
11,12c11,12
<           (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int)
<           (Main.C (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int))
---
>           (Data.Array.Base.STUArray s GHC.Int.Int64 GHC.Types.Int)
>           (Main.C (Data.Array.Base.STUArray s GHC.Int.Int64 GHC.Types.Int))
26,27c26,27
<             (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int)
<             (Main.C (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int)))
---
>             (Data.Array.Base.STUArray s GHC.Int.Int64 GHC.Types.Int)
>             (Main.C (Data.Array.Base.STUArray s GHC.Int.Int64 GHC.Types.Int)))

Разные типы индексов, они, конечно, разные.

33,40d32
<           l :: GHC.Types.Int
<           [LclId]
<           l = GHC.Types.I# sc } in
<         let {
<           u :: GHC.Types.Int
<           [LclId]
<           u = GHC.Types.I# sc1 } in
<         let {

Для типа индекса IntGHC выдает несколько более информативные ошибки для индексов, выходящих за границы, для этого требуется нижняя и верхняя граница допустимых индексов. (Реализация по умолчанию index не отменяется в instance Ix Int64.)

45,46c37
<           GHC.Types.False ->
<             case poly_$w$j5 (GHC.Types.I# a) l u of wild2 { };
---
>           GHC.Types.False -> case GHC.Arr.hopelessIndexError of wild1 { };

Другая ошибка, indexError против hopelessIndexError, Следующие различия также касаются только ошибок индекса.

49,50c40
<               GHC.Types.False ->
<                 case poly_$w$j5 (GHC.Types.I# a) l u of wild2 { };
---
>               GHC.Types.False -> case GHC.Arr.hopelessIndexError of wild2 { };
58c48
<                     case poly_$w$j4 y (GHC.Types.I# sc2) of wild3 { };
---
>                     case poly_$w$j3 y (GHC.Types.I# sc2) of wild4 { };
62c52
<                         case poly_$w$j4 y (GHC.Types.I# sc2) of wild5 { };
---
>                         case poly_$w$j3 y (GHC.Types.I# sc2) of wild5 { };
77,78c67
<                                 GHC.Types.False ->
<                                   case poly_$w$j3 (GHC.Types.I# a1) l u of wild6 { };
---
>                                 GHC.Types.False -> case GHC.Arr.hopelessIndexError of wild6 { };
81,82c70
<                                     GHC.Types.False ->
<                                       case poly_$w$j3 (GHC.Types.I# a1) l u of wild7 { };
---
>                                     GHC.Types.False -> case GHC.Arr.hopelessIndexError of wild7 { };

Теперь еще раз другой тип индекса:

110c98
<                                                                       GHC.Types.Int
---
>                                                                       GHC.Int.Int64
152c140
<                                                 s GHC.Types.Int GHC.Types.Int>)>)
---
>                                                 s GHC.Int.Int64 GHC.Types.Int>)>)

И наконец, 0 а также 1 получили разные имена верхнего уровня.

177,178c165,166
<       0 -> (# sc5, lvl5 #);
<       1 -> (# sc5, lvl6 #)
---
>       0 -> (# sc5, lvl #);
>       1 -> (# sc5, lvl1 #)

Таким образом, весь код, который выполняет реальную работу, идентичен. Тем не менее, один вызывает переполнение стека (хотя только -K9M достаточно [-K8731K здесь достаточно, -K8730K нет]) а другой нет.

Разница действительно вызвана ошибками индекса. Код с Int Индексы выделяет два в штучной упаковке Intв каждом рекурсивном вызове, что Int64 код не выделяется, потому что

Main.main_$spoly_$wa [Occ=LoopBreaker]
  :: forall s.
     GHC.Prim.Int#
     -> GHC.Prim.Int#
     -> GHC.Prim.Int#
     -> GHC.Prim.MutableByteArray# s
     -> (GHC.Prim.~#)
          *
          (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int)
          (Main.C (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int))
     -> GHC.Prim.Int#
     -> GHC.Prim.State# s
     -> (# GHC.Prim.State# s, GHC.Types.Int #)

содержит две ссылки на массив.

Это использует больше стека, и эти в штучной упаковке IntДолжны быть собраны мусор, что приводит к гораздо большим показателям GC. Кроме того, thunk для ошибки индекса немного больше, чем hopelessIndexError санк.

Теперь, если вы поможете компилятору

• удаление оболочки нового типа
• сделать функцию строгой в массиве (по шаблонам взрыва или data C a = C !a)

или некоторыми другими способами, он производит лучший код, который управляет без переполнения стека для данного аргумента, поскольку существует только одна ссылка на массив в работнике, и, таким образом, распределение в штучной упаковке Intдля границ не нужно.

Обратите внимание, что этот алгоритм вызывает переполнение стека для немного больших аргументов даже с помощью компилятора.

Answer 2

Ваша первоначальная программа, как вы говорите, переполняется стеком:

$ ghc -O2 A.hs --make -rtsopts
$ ./A +RTS -s
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.
      21,213,928 bytes allocated in the heap
       3,121,864 bytes copied during GC
       5,400,592 bytes maximum residency (4 sample(s))
          20,464 bytes maximum slop
              20 MB total memory in use (0 MB lost due to fragmentation)

Хотя, если мы перейдем на Int64, он будет работать нормально:

$ time ./A
-2092835058118682368
./A  0.03s user 0.01s system 92% cpu 0.050 total

Так где же утечка?

Просто визуальная проверка вашего кода, есть очевидная проблема:

• fib ленив в аргументе массива

Вы также можете сделать вывод из поведения, которое вы видели:

newtype C a is removed from the picture;

data C a = C !a is used instead of newtype

Все из которых сервер, чтобы выставить массив для анализатора строгости.

Если вы сделаете FIB строгим в массиве:

{-# LANGUAGE BangPatterns #-}

{-# INLINE fib #-}
fib !_ 0 = return 0
fib !_ 1 = return 1
fib !c n = do
  f1 <- memo c (fib c) (n-1)
  f2 <- memo c (fib c) (n-2)
  return (f1+f2)

Тогда это просто работает:

$ time ./A
-2092835058118682368
./A  0.03s user 0.01s system 89% cpu 0.052 total

Так почему же он протекает с одним типом, а не с другим? Я думаю, вам просто повезло с Int64. Но я бы посчитал это "ошибкой", вероятно, в правилах перезаписи для различных типов num.

Посмотрев на вывод упростителя, мы получим совершенно другой прогон правил перезаписи в случае Int64 и Int. Поскольку базовые функции часто индексируются Int, в конечном итоге вы выполняете различные оптимизации, используя общий тип Int. В этом случае достаточно спутать анализатор строгости.

Как всегда, применяются общие правила: дайте компилятору больше советов, и вы получите лучший код.