13

我对以下片段的行为感到困惑：

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 内存在使用中）。令人困惑的部分是，如果进行以下任何更改，它实际上会按预期工作（没有堆栈溢出和 9M 内存正在使用） ：

  • Int64用于代替Int: （给出evalFib :: Int64 -> Int和STUArray s Int64 Int）。事实上，任何Int*( Int32, Int16, etc) 都可以像Wordor Word*;
  • newtype C a从图片中删除；
  • data C a = C !a被用来代替newtype

我试图弄清楚这种行为：它是 GHC/array 模块中的错误（它在7.4.2and中显示相同的行为7.6.2）还是应该以这种方式工作？

PS 有趣的是，当我尝试编译它ghc array.hs -O2 -fext-core以查看产生的核心差异时，两个 GHC 版本都以“ghc：恐慌！（'不可能'发生）”失败。这里也没有运气..

4

2 回答 2

11

正如您所说，您的初始程序堆栈溢出：

$ 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 类型的重写规则中。

查看 simplifier 的输出，我们得到在 Int64 情况下与 Int 情况下完全不同的重写规则运行。由于底层函数通常由 Int 索引，因此您最终会通过使用常见的 Int 类型来执行不同的优化。在这种情况下，足以迷惑严格度分析器。

与往常一样，一般规则适用：给编译器更多提示，你就会得到更好的代码。

于 2013-02-23T10:52:06.430 回答
5

从 7.6.1开始，无论我使用还是作为索引类型，使用-O2and-dsuppress-uniques完成工作的函数在Main.main_$spoly_$wa结构上（几乎）是相同的。由于核心又长又复杂，所以输出如下：intInt64diff

$ 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 {

对于 index type Int，GHC 会为越界索引产生更多信息错误，因为它需要有效索引的下限和上限。（ 的默认实现在 .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在代码未分配的每个递归调用中分配两个装箱的 s 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的 s 必须被垃圾收集，这会导致更大的 GC 数字。此外，索引错误的 thunk 比hopelessIndexErrorthunk 稍大。

现在，如果您通过以下方式帮助编译器

  • 删除 newtype 包装器
  • 使函数在数组中严格（通过 bang 模式或data C a = C !a）

或者其他一些方式，它可以生成更好的代码，在没有给定参数的堆栈溢出的情况下进行管理，因为在 worker 中只有一个Int对数组的引用，因此不需要为边界分配装箱的 s。

请注意，即使在编译器的帮助下，此算法也会导致稍大的参数出现堆栈溢出。

于 2013-02-23T23:15:24.827 回答