Haskell可以评估而不是垃圾收集列表中的随机索引吗？

Question

据我所知,Haskell只有当某些东西超出范围时才会收集垃圾,因此顶级绑定只会被评估一次并且永远不会超出范围.因此,如果我在GHCI中运行此代码,将评估并保存前50个元素.

let xs = map f [0..]
take 50 xs

我的问题是当我执行以下代码段时会发生什么:xs !! 99.垃圾收集器保存了什么？可以

1. 保留索引0 - 49的结果,索引50 - 98的thunk,索引99的结果,索引100+的thunk
2. 保留索引0 - 49的结果,索引50+的thunk
3. 保留索引0 - 99的结果,索引100+的thunk

Answer 1

Haskell列表是由(:)("cons")单元组成的链表,并以[]("nil")值终止.我会画这样的细胞

 [x] -> (tail - remainder of list)
  |
  v
(head - a value)

因此,在考虑评估的内容时,需要考虑两个方面.首先是脊柱,即cons单元的结构,其次是列表包含的值.而不是50和99,让我们分别使用2和4.

ghci> take 2 xs
[0,1]

打印此列表会强制评估前两个缺点单元格以及其中的值.所以你的列表看起来像这样:

[x] -> [x] -> (thunk)
 |      |
 v      v
 0      1

现在,当我们

ghci> xs !! 4
3

我们没有要求第二或第三个值,但我们需要评估这些净值单元以获得第四个元素.所以我们一直强制脊柱到第4个元素,但我们只评估了第4个值,所以列表现在看起来像这样:

[x] -> [x] -> [x] -> [x] -> [x] -> (thunk)
 |      |      |      |      |
 v      v      v      v      v
 0      1   (thunk) (thunk)  4

此图片中的任何内容都不会被垃圾收集.但是,有时候这些thunk可能占用大量空间或引用大的空间,并将它们评估为普通值将允许释放这些资源.有关这些细微之处的小讨论,请参阅此答案.

Answer 2

我们问分析师.

我们将编译以下示例程序,该程序应该与您的GHCI会话大致相同.重要的是我们print的结果,如GHCI,因为这会强制计算.

f x = (-x)

xs = map f [0..]

main = do
    print (take 50 xs)
    print (xs !! 99)

我救了我的example.hs.我们将使用选项编译它以启用分析

ghc -prof -fprof-auto -rtsopts example.hs

时间档案

我们可以找出f时间配置文件应用了多少次.

profile +RTS -p

这会生成一个名为的输出文件example.prof,以下是有趣的部分:

COST CENTRE MODULE                     no.     entries
...
   f        Main                        78          51 

我们可以看到f被评估了51次,50次被评估print (take 50 xs),一次被评估print (xs !! 99).因此我们可以排除你的第三种可能性,因为f只评估了51次,所有指数都没有结果0-99

3. 保留索引0 - 99的结果,索引100+的thunk

堆结果的配置文件

分析堆上的内存有点棘手.堆分析器默认每隔0.1秒采样一次.我们的程序运行得如此之快,以至于堆分析器在运行时不会采集任何样本.我们将为程序添加一个旋转,以便堆分析器有机会获取样本.以下内容将旋转数秒.

import Data.Time.Clock

spin :: Real a => a -> IO ()
spin seconds =
    do
        startTime <- getCurrentTime 
        let endTime = addUTCTime (fromRational (toRational seconds)) startTime
        let go = do
            now <- getCurrentTime
            if now < endTime then go else return ()
        go

我们不希望垃圾收集器在程序运行时收集数据,因此我们将xs在旋转后添加另一种用法.

main = do
    print (take 50 xs)
    print (xs !! 99)
    spin 1
    print (xs !! 0)

我们将使用默认的堆分析选项运行它,该选项按成本中心对内存使用情况进行分组.

example +RTS -h

这会生成文件example.hp.我们将从文件中间拉出一个样本,其中数字是稳定的(当它在a中时spin).

BEGIN_SAMPLE 0.57
(42)PINNED  32720
(48)Data.Time.Clock.POSIX.CAF   48
(85)spin.endTime/spin/mai...    56
(84)spin.go/spin/main/Mai...    64
(81)xs/Main.CAF 4848
(82)f/xs/Main.CAF   816
(80)main/Main.CAF   160
(64)GHC.IO.Encoding.CAF 72
(68)GHC.IO.Encoding.CodeP...    136
(57)GHC.IO.Handle.FD.CAF    712
(47)Main.CAF    96
END_SAMPLE 0.57

我们可以看到f已经产生了816个字节的内存.对于"小" Integer,Integer消耗2个字的记忆.在我的系统中,一个字是8字节的内存,所以"小" Integer需要16个字节.因此,816/16 = 51产生的Integers f可能仍在记忆中.

我们可以检查所有此内存的实际使用为"小" Integer的要求由形状S 闭合说明用-hd.我们不能通过闭包描述和成本中心对内存使用进行分组,但我们可以将分析限制为单个成本中心-hc,在这种情况下,我们对f成本中心感兴趣

example +RTS -hd -hcf

这说明所有816个字节f都是由S#"小" Integer的构造函数使用的

BEGIN_SAMPLE 0.57
S#  816
END_SAMPLE 0.57

我们当然可以删除以下内容,因为Integer保留了51个结果,并且它预计只保持50 Integer秒

2. 保留索引0 - 49的结果,索引50+的thunk

堆结构和thunk的配置文件

这让我们有了选择

1. 保留索引0 - 49的结果,索引50 - 98的thunk,索引99的结果,索引100+的thunk

让我们猜一下这种情况会消耗多少内存.

通常,Haskell data类型需要1个字的内存用于构造函数,1个字用于每个字段.该[]类型的:构造函数有两个领域,因此预计需要的存储3个字或24个字节.:然后100 秒将占用2400字节的内存.当我们询问关闭描述时,我们将看到这是完全正确的xs.

关于thunk的大小很难说,但我们会试一试.指数值[50,98]将有49个风暴.这些thunks中的每一个可能都是Integer从发电机中拿出来的[0..].它还需要保持thunk的结构,不幸的是在分析时会发生变化.列表的其余部分也会有一个thunk.它将需要Integer生成列表的其余部分以及thunk的结构.

要求一个存储器击穿由闭合描述为xs成本中心

example +RTS -hd -hcxs

给我们以下样本

BEGIN_SAMPLE 0.60
<base:GHC.Enum.sat_s34b>    32
<base:GHC.Base.sat_s1be>    32
<main:Main.sat_s1w0>    16
S#  800
<base:GHC.Base.sat_s1bd>    1568
:   2400
END_SAMPLE 0.60

关于100 :s需要2400字节的内存,我们完全正确.有49 + 1 = 50"小" Integer小号S#占据为的thunk为49个未计算的值和用于所述列表中的剩余部分在thunk 800个字节.有1568个字节可能是未计算值的49个字节,然后每个字节为32个字节或4个字.还有另外80个字节我们无法准确解释为剩下的列表留下了thunk.

记忆和时间曲线都符合我们对该计划的信念

1. 保留索引0 - 49的结果,索引50 - 98的thunk,索引99的结果,索引100+的thunk