让我们来比较一下实际数字。如果不进行优化,你的
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