如果我定义 Kolakoski序列为
kolakoski :: () -> [Int]
kolakoski () = 1 : 2 : helper ()
where
helper () = 2 : concat (zipWith replicate (helper ()) (cycle [1, 2]))
并使用以下方法找到第 500,000,000 项：
kolakoski () !! 500000000
我发现当使用ghc -O编译时，它会迅速消耗大量内存。但是关闭优化后几乎不会使用内存。哪种优化导致了这个问题，如何关闭它？
kolakoski版本将使用约70k：
$ ghc --make Kolakoski-Unit && ./Kolakoski-Unit +RTS -s
2
288,002,359,096字节分配在堆中
1,343,933,816字节在GC期间复制
67,576字节最大常驻内存（422个样本）
52,128字节最大slop
2MB总内存使用量（由于碎片化而丢失0MB）
总时间（经过）平均暂停时间 最大暂停时间
Gen 0 551615 colls, 0 par 1.89秒 2.30秒 0.0000秒 0.0001秒
Gen 1 422 colls, 0 par 0.02秒 0.02秒 0.0001秒 0.0001秒
INIT 时间 0.00秒 （ 0.00秒 经过）
MUT 时间 37.34秒 （ 37.25秒 经过）
GC 时间 1.91秒 （ 2.33秒 经过）
EXIT 时间 0.00秒 （ 0.00秒 经过）
Total 时间 39.25秒 （ 39.58秒 经过）
%GC 时间 4.9% （5.9% 经过）
分配速率 每MUT秒7,712,197,063字节
生产力 总用户的95.1%，总经过时间的94.3%
经过优化后，它使用约4GB（尽管任务管理器中的实际内存使用量高达约6GB）。
$ ghc --make Kolakoski-Unit -O && ./Kolakoski-Unit +RTS -s 2 堆内存分配了64,000,066,608字节 在GC过程中复制了27,971,527,816字节 最大的驻留空间是3,899,031,480字节（34个采样） 最大的浪费空间是91,679,728字节 使用的总内存为9549MB（由于碎片而丢失的内存为0MB）
总时间（已流逝） 平均暂停时间 最长暂停时间 Gen 0 122806 次遍历, 0个并行运行 8.67秒 9.48秒 0.0001秒 0.0148秒 Gen 1 34 次遍历, 0个并行运行 11.55秒 69.78秒 2.0524秒 56.2970秒
初始化时间为0.00秒（已流逝） MUT时间为8.80秒（已流逝） GC时间为20.22秒（已流逝） EXIT时间为0.03秒（已流逝） 总时间为29.05秒（已流逝）
%GC时间为69.6%（89.5%流逝）
内存分配速率为7,275,318,406字节每秒
生产率占总用户时间的30.4%，占总流逝时间的10.0%
如果我们使用基于列表的版本并且没有启用优化，内存消耗与启用优化时非常相似:
kolakoskiList :: [Int]
kolakoskiList = 1 : 2 : helper
where
helper = 2 : concat (zipWith replicate helper (cycle [1, 2]))
$ ghc --make Kolakoski-List && ./Kolakoski-List +RTS -s 2 堆中分配了 96,000,143,328 字节 在 GC 过程中复制了 26,615,974,536 字节 最大驻留内存为 3,565,429,808 字节 (34 次样本) 最大空闲内存为 83,610,688 字节 使用的总内存为 8732 MB (由于碎片化而丢失的内存为 0 MB)
总时间 (实际) 平均暂停时间 最长暂停时间 Gen 0 184252 次收集, 0 个并行 9.98 秒 10.16 秒 0.0001 秒 0.0006 秒 Gen 1 34 次收集, 0 个并行 10.45 秒 21.61 秒 0.6357 秒 12.0792 秒
初始化时间 0.00 秒 ( 0.00 秒 实际) MUT 时间 12.02 秒 ( 11.88 秒 实际) GC 时间 20.44 秒 ( 31.77 秒 实际) 退出时间 0.05 秒 ( 0.69 秒 实际) 总时间 32.50 秒 ( 44.34 秒 实际)
%GC 时间 62.9% (71.7% 实际)
每秒分配率 7,989,608,807 字节每 MUT 秒
生产率 总用户时间的 37.1%, 总实际时间的 27.2%
现在，我们可以查看GHC标志参考，了解在-O上自动设置的标志。由于列表版本似乎与优化版本执行相同的操作，因此人们可能认为GHC将kolakoski转换为kolakoskiList：
kolakoskiOptimized _ = kolakoskiList
我们可以使用 -ddump-simpl -dsuppress-all 命令在核心模块中进行检查：
==================== Tidy Core ====================
Result size of Tidy Core = {terms: 45, types: 30, coercions: 0}
kolakoski
kolakoski =
\ ds_d10r ->
case ds_d10r of _ { () ->
: (I# 1)
(: (I# 2)
(letrec {
helper_aNo
helper_aNo =
\ ds1_d10s ->
case ds1_d10s of _ { () ->
: (I# 2)
(concat
(zipWith
(replicate) (helper_aNo ()) (cycle (: (I# 1) (: (I# 2) ([]))))))
}; } in
helper_aNo ()))
}
main
main = print $fShowInt (!! (kolakoski ()) (I# 500000000))
main
main = runMainIO main
即使你不熟悉 GHC 的内核，你也可以看到 kolakoski 和你的原始版本基本相同。现在将其与 -O -ddump-simpl -dsupress-all 进行比较：
==================== Tidy Core ====================
Result size of Tidy Core = {terms: 125, types: 102, coercions: 9}
kolakoski6
kolakoski6 = I# 1
kolakoski5
kolakoski5 = I# 2
Rec {
go_r1NG
go_r1NG =
\ ds_a14B _ys_a14C ->
case ds_a14B of _ {
[] -> [];
: ipv_a14H ipv1_a14I ->
case _ys_a14C of _ {
[] -> [];
: ipv2_a14O ipv3_a14P ->
case ipv_a14H of _ { I# n#_a13J ->
case tagToEnum# (<=# n#_a13J 0) of _ {
False ->
let {
lvl2_s1N3
lvl2_s1N3 = : ipv2_a14O ([]) } in
letrec {
xs_a1LH
xs_a1LH =
\ m_a1LO ->
case tagToEnum# (<=# m_a1LO 1) of _ {
False -> : ipv2_a14O (xs_a1LH (-# m_a1LO 1));
True -> lvl2_s1N3
}; } in
++ (xs_a1LH n#_a13J) (go_r1NG ipv1_a14I ipv3_a14P);
True -> ++ ([]) (go_r1NG ipv1_a14I ipv3_a14P)
}
}
}
}
end Rec }
lvl_r1NH
lvl_r1NH = : kolakoski5 ([])
lvl1_r1NI
lvl1_r1NI = : kolakoski6 lvl_r1NH
Rec {
xs'_r1NJ
xs'_r1NJ = ++ lvl1_r1NI xs'_r1NJ
end Rec }
Rec {
kolakoski3
kolakoski3 = : kolakoski5 kolakoski4
kolakoski4
kolakoski4 = go_r1NG kolakoski3 xs'_r1NJ
end Rec }
kolakoski2
kolakoski2 = : kolakoski5 kolakoski3
kolakoski1
kolakoski1 = : kolakoski6 kolakoski2
kolakoski
kolakoski = \ ds_d13p -> case ds_d13p of _ { () -> kolakoski1 }
这个版本包含了多个顶层CAF，它们会在整个程序的生命周期中一直存在。所以你确实生成了列表的前五亿个值并将其保存下来。
现在，发生了什么？函数内部的某些内容向外漂移了。让我们再次检查标志引用。有一个有前途的标志，被-O隐含：
-ffull-laziness打开完全惰性（将绑定项向外浮动）。被-O隐含。
那就是导致问题的标志。事实上，你可以使用ghc --make -O -fno-full-laziness Kolakoski-Unit.hs来获得原始的内存消耗：
$ ghc --make Kolakoski-Unit.hs -O -fno-full-laziness && ./Kolakoski-Unit +RTS -s
2
192,001,417,688 字节在堆上分配
637,962,464 字节在 GC 中复制
66,104 最大居住空间（151 个样本）
43,448 最大课余量
2 MB 总内存使用量（由于碎片而丢失 0 MB）
总时间（已过去的时间） 平均暂停 最大暂停
Gen 0 368364 次垃圾回收， 0 个并行 1.34 秒 1.32 秒 0.0000 秒 0.0002 秒
Gen 1 151 次垃圾回收， 0 个并行 0.00 秒 0.01 秒 0.0001 秒 0.0003 秒
初始化 时间 0.00 秒 （ 0.00 秒 已过去）
MUT 时间 27.89 秒 （ 28.13 秒 已过去）
GC 时间 1.34 秒 （ 1.33 秒 已过去）
退出 时间 0.00 秒 （ 0.00 秒 已过去）
总时间 时间 29.25 秒 （ 29.46 秒 已过去）
%GC 时间 4.6% （4.5% 已过去）
分配速率 6,884,084,443 字节每秒每MUT
生产率 95.4% 的总用户时间，94.7% 的总经过时间
kolakoski转换为一个带有虚拟参数的函数是聪明的...但 GHC 更聪明。;-) - Daniel Wagner