haskell - STUArray s i e - 仅当 i == 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)。令人困惑的部分是，如果进行以下任何更改，它实际上会按预期工作(没有堆栈溢出和 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 版本都失败了“ghc: panic !('不可能'发生了)”。这里也没有运气..

Answer 1

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

$ 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 类型来执行不同的优化。在这种情况下，足以迷惑严格度分析器。

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