logo标签列表

STUArray s i e - 当i == Int时是否会出现空间泄露？

haskellspace-leak
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等）都可以做到，以及Word或Word*；
  • newtype C a从图中删除；
  • 使用data C a = C !a代替newtype
我试图弄清楚这种行为：这是GHC / array模块中的错误（在7.4.2和7.6.2中显示相同的行为），还是应该这样工作？

PS 有趣的是，当我尝试使用ghc array.hs -O2 -fext-core编译它以查看两个GHC版本产生的core的差异时，两个版本都会失败并显示“ghc: panic！（发生了‘不可能’的事情）”。这里也没有运气。

请使用-ddump-simpl而不是-fext-core。 - Don Stewart
1
将来再添加一些类型签名如何？ - leftaroundabout
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 类型中运气好。但我认为这可能是一个“错误”，可能是各种数字类型的重写规则中存在问题。

查看简化器的输出，我们可以看到在 Int64 类型和 Int 类型中触发了不同的重写规则。由于底层函数通常由 Int 索引，因此通过使用常见的 Int 类型，您最终会运用不同的优化。在这种情况下，足以混淆严格性分析器。

与往常一样，普适的规则适用：给编译器更多提示，您将获得更好的代码。

问题在于 Int 和 Int64、Int32、Word、Word64 等有什么特别之处。此外，如果我们切换到 IO 单子中，! 将无法帮助我们（使用 Int 仍会溢出），而 Int64 可以解决这个问题。因此，了解为什么会发生这种情况是很好的。 - Ed'ka
它在IO单子中像ST单子一样适用于我。http://hpaste.org/82879 - Don Stewart
哦，对不起，我在尝试其他东西时弄乱了我的代码。是的，在IO中它确实有效。但是，为什么只有Int？ - Ed'ka
5

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

对于索引类型Int，GHC会产生更具信息量的错误提示，以便处理越界索引，因为它需要有效索引的下限和上限。(在instance Ix Int64中，未覆盖index的默认实现。)

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 thunk稍微大一点。

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

  • 删除newtype包装器
  • 使函数严格遵循数组（通过叹号模式或data C a = C !a）

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

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

感谢您提供优秀的答案和复杂问题的精细分析！ - Niklas B.
非常好的回答！是的，所有版本都会在某个时候出现堆栈溢出，但我的原始代码使用 Int 只比 Int64 慢了3倍，因此才有这个问题。 - Ed'ka
@Ed'ka 这是一个有趣的问题。一开始让我完全困惑，花了几分钟盯着核心才开始理解。 - Daniel Fischer
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接