标签: space-leak

我最近一直在玩作家莫纳德,我遇到了似乎是空间泄漏的事情.我不能说我完全理解这些事情,所以我想知道这里发生了什么,以及如何解决它.

首先,这是我如何触发此错误:

import Control.Monad.Writer
import Data.Monoid

foo :: Integer -> Writer (Sum Integer) Integer
foo 0 = return 0
foo x = tell (Sum x) >> foo (pred x)

main = print $ runWriter $ foo 1000000

我明白了:

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

为了更好地理解这一点,我在没有Writer或Sum的情况下重新实现了类似的功能,如果我保持良好和懒惰,我会得到同样的错误:

bar :: Integer -> (Integer, Integer)
bar x = bar' 0 x
    where bar' c 0 = (0, c)
          bar' c x = bar' (c + x) …

我将此代码键入解释器并快速占用内存:

last [1..10^7] `seq` ()

我不明白为什么这需要超过O(1)空间.如果我这样做(这应该是相同的,因为Show强制弱头正常形式,所以seq是多余的？):

last [1..10^7]

......工作正常

我无法在翻译之外重现这种情况.

这里发生了什么？

以下是一些测试用例:http: //hpaste.org/69234

注意事项:

• 通过在解释器中运行,我加载wtf.hs而不编译它,并输入wtf<n>ghci.
• 通过编译,我做到了ghc --make wtf.hs && ./wtf.
• last可以替换sum带有严格累加器的函数或在列表中找到最大元素的函数,并且仍然会发生空间泄漏
• 使用时,我还没有看到这种行为$!,而不是seq.
• 我尝试添加一个虚拟()参数,因为我认为这可能是一个CAF问题.没有改变.
• 这可能不是函数打开的问题Enum,因为我可以用wtf5它来重现行为,之后根本不会使用它Enum.
• 这可能不是一个问题Num,Int或者Integer,因为我可以重现的行为,而他们wtf14和wtf16.

我尝试使用Peano算法重现问题,将列表和整数从等式中取出(在10 ^ 9的末尾取出),但遇到其他共享/空间泄漏问题,我在尝试实现时不明白*.

我已多次读过Haskell中的懒惰评估有时会导致空间泄漏.什么样的代码会导致空间泄漏？如何检测它们？并且程序员可以采取哪些预防措施来避免它们？

该mapAndSum代码块下面的所有方式结合功能map和sum(不去管另一个sum是在主函数中应用,它只是用来使输出紧凑型).它map是懒惰地计算的,而sum使用累积参数计算.这个想法是,结果map可以在没有完整列表的情况下被消费,并且(仅)之后sum可以"免费"获得.main函数表示调用时我们遇到了无法反驳的模式问题mapAndSum.让我解释一下这个问题.

根据Haskell标准,无可辩驳的模式示例let (xs, s) = mapAndSum ... in print xs >> print s被翻译成

(\ v ->    print (case v of { (xs, s) -> xs })
        >> print (case v of { (xs, s) -> s }))
$ mapAndSum ...

因此,两个print调用都带有对整个对的引用,这导致整个列表保存在内存中.

我们(我的同事Toni Dietze和我)使用明确的case陈述解决了这个问题(比较"坏"与"好2").顺便说一句,发现这一点花了我们相当多的时间..!

现在,我们不理解的是双重的:

• 为什么mapAndSum首先工作？它还使用无可辩驳的模式,因此它也应该将整个列表保留在内存中,但显然不会.并且转换let为a case将使该函数表现为完全不受欢迎(到堆栈溢出的程度;没有双关语意图).

  我们看了GHC生成的"核心"代码,但就我们所能解释的那样,它实际上包含了与let上面相同的翻译.所以在这里没有任何线索,而是更多的混乱.

• 为什么"不好？" 关闭优化时工作,但打开优化时不工作？ …

我对以下剪切的行为感到困惑:

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 …

我是Haskell的新手,我正试图以流处理方式实现Euler的Sieve.

当我查看关于素数的Haskell Wiki页面时,我发现了一些神秘的流优化技术.在3.8维基的线性合并中:

primesLME = 2 : ([3,5..] `minus` joinL [[p*p, p*p+2*p..] | p <- primes']) 
  where
    primes' = 3 : ([5,7..] `minus` joinL [[p*p, p*p+2*p..] | p <- primes'])

joinL ((x:xs):t) = x : union xs (joinL t)

它说

" 根据Melissa O'Neill的代码,这里引入了双素数反馈,以防止不必要的记忆,从而防止内存泄漏."

怎么会这样？我无法弄清楚它是如何工作的.

On reflection, this entire question can be boiled down to something much more concise. I'm looking for a Haskell data structure that

• looks like a list
• has O(1) lookup
• has either O(1) element replacement or O(1) element append (or prepend... I could reverse my index lookups if that were the case). I can always write my later algorithms with one or the other in mind.
• has very little memory overhead

I'm trying to build an image file parser. The file …

我的空间泄漏发生在我的一个个人项目中.但我不希望有人在我的项目中解决它.我想了解它.

我通过编写这个算法来重现我的空间泄漏:

u是由以下定义的序列:

• u(0)= 1
• 你(1)= 2
• 你(2)= 1
• 你(4)= 3
• ...
• 你(19)= 11

在此之后,定义u:u(n)= u(n-5)+ u(n-10) - u(n-15)

在haskell中易于实现吗？

import System.Environment (getArgs)

u = [1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11]
        ++ zipWith3 go u' u'' u'''
    where u' = drop 15 u
          u'' = drop 10 u
          u''' = drop 5 u
          go a b c = a + b - c

main = do …

我想在Haskell中使用Vectors 编写Floyd-Warshall所有对最短路径算法的有效实现,以期获得良好的性能.

实现非常简单,但不使用三维| V |×| V |×| V | 矩阵,使用二维向量,因为我们只读过前一个k值.

因此,该算法实际上只是传递2D矢量的一系列步骤,并且生成新的2D​​矢量.最终的2D矢量包含所有节点(i,j)之间的最短路径.

我的直觉告诉我,确保在每个步骤之前评估先前的2D向量是很重要的,所以我使用了函数BangPatterns的prev参数fw和严格foldl':

{-# Language BangPatterns #-}

import           Control.DeepSeq
import           Control.Monad       (forM_)
import           Data.List           (foldl')
import qualified Data.Map.Strict     as M
import           Data.Vector         (Vector, (!), (//))
import qualified Data.Vector         as V
import qualified Data.Vector.Mutable as V hiding (length, replicate, take)

type Graph = Vector (M.Map Int Double)
type TwoDVector = Vector (Vector Double)

infinity :: Double
infinity = 1/0

-- …

我的 Haskell 程序中存在空间泄漏，我可以将其查明为一个最小的示例，如下所示。我希望以下代码（尽管不会终止，但我不在乎）在常量内存中运行，但事实并非如此：

head . filter (const False) $ (transpose [[1..]])

whilehead . filter (const False) $ [1..]确实在恒定内存中运行。

所以我猜这一定与在无限列表上使用“转置”有关。忽略更复杂的基础库实现，如果我们定义转置transpose xss = map head xss : transpose (map tail xss)，为什么会出现空间泄漏？map head xss我的假设是垃圾收集器可以释放以前在函数的每个步骤中消耗的内存filter。我想这map tail xss会以某种方式阻止这种情况发生？！无论如何，我可以添加某种严格性注释或类似的注释，transpose以便该简单的示例确实在恒定内存中运行吗？