26

我在 Haskell 中与惰性求值的斗争之一是难以推理内存使用情况。我认为复制 thunk 的能力会让我更容易做到这一点。这是一个例子。

让我们创建一个非常大的列表:

let xs = [1..10000000]

现在,让我们创建一个坏函数:

bad = do
    print $ foldl1' (+) xs
    print $ length xs

如果没有优化,这会占用几十 MB 的内存。垃圾收集器无法在折叠期间释放 xs,因为稍后计算长度时需要它。

是否可以像这样重新实现此功能:

good = do
    (xs1,xs2) <- copyThunk xs
    print $ foldl1' (+) xs1
    print $ length xs2

现在,xs1 和 xs2 将表示相同的值,但在内存中也相互独立,因此垃圾收集器可以在折叠期间释放内存,从而防止内存浪费。(我认为这会稍微增加计算成本?)

显然在这个简单的例子中,重构代码可以很容易地解决这个问题,但是如何重构似乎并不总是很明显。或者有时重构会大大降低代码的清晰度。

4

3 回答 3

20

前段时间我想知道同样的事情,并创建了这样一个 thunk-duplication 函数的原型实现。你可以在我的预印本“<a href="http://arxiv.org/abs/1207.2017" rel="noreferrer"> dup – Explicit un-sharing in haskell”中了解结果,并在 http://arxiv.org/abs/ /darcs.nomeata.de/ghc-dup。不幸的是,这篇论文在今年的 Haskell Symposium 和 Haskell 实施者研讨会上都没有被接受。

据我所知,这个问题没有现成的解决方案。仅作为单元参数技巧的脆弱变通方法可能由于一种或其他编译器优化而中断。

于 2012-07-26T20:05:08.353 回答
4

有趣的问题。我不知道如何实现copyThunk。但是您还可以做其他事情(抱歉,如果您已经知道这一点):

xsFunction :: () -> [Int]
xsFunction = const [1..10000000]

better = do
  print $ foldl1' (+) $ xsFunction ()
  print $ length $ xsFunction ()

在这里它绝对不会把表达式xsFunction ()放在一个 thunk 中,它会被计算两次,因此不会造成任何内存膨胀。


一个有趣的后续行动是:

  • 可以实现copyThunk吗?
  • Haskell 程序员是否应该在这种相对较低级别的优化中搞乱?我们不能假设 ghc 在这方面比我们聪明吗?
于 2012-07-26T19:25:37.623 回答
2

变成xs一个函数。这可能很难看,但很有效,因为它阻止了共享:

let xs () = [1..1000000]

good = do
    print $ foldl1' (+) (xs ())
    print $ length (xs ())
于 2012-07-26T19:25:34.977 回答