在运行GHC编译的程序时,我经常看到在GC中花费了大量的周期。
这些数字往往比我的JVM经验所表明的要高一个数量级。特别是,GC“复制”的字节数似乎远远大于我正在计算的数据量。
非严格语言和严格语言之间的区别是否根本?
tl; dr:JVM在堆栈帧中执行的大部分工作,GHC在堆上执行。如果您想将GHC堆/ GC统计信息与JVM等效项进行比较,您实际上需要考虑JVM在堆栈上推送参数或在堆栈帧之间复制返回值所花费的字节/周期的一部分。
面向JVM的语言通常使用其调用堆栈。每个被调用的方法都有一个活动的堆栈帧,包括传递给它的参数的存储,附加的局部变量和临时结果,以及用于将参数传递给它并从其调用的其他方法接收结果的“操作数堆栈”的空间。
举个简单的例子,如果是Haskell代码:
bar :: Int -> Int -> Int
bar a b = a * b
foo :: Int -> Int -> Int -> Int
foo x y z = let u = bar y z in x + u
编译到JVM,字节代码可能类似于:
public static int bar(int, int);
Code:
stack=2, locals=2, args_size=2
0: iload_0 // push a
1: iload_1 // push b
2: imul // multiply and push result
3: ireturn // pop result and return it
public static int foo(int, int, int);
Code:
stack=2, locals=4, args_size=3
0: iload_1 // push y
1: iload_2 // push z
2: invokestatic bar // call bar, pushing result
5: istore_3 // pop and save to "u"
6: iload_0 // push x
7: iload_3 // push u
8: iadd // add and push result
9: ireturn // pop result and return it
请注意,调用内置基元(如imul
)和用户定义的方法(如bar
)涉及将参数值从本地存储器复制/推送到操作数堆栈(使用iload
指令),然后调用基元或方法。然后需要将返回值保存/弹出到本地存储(使用istore
)或使用ireturn
返回给调用者;偶尔,返回值可以保留在堆栈上,以作为另一个方法调用的操作数。此外,虽然字节代码中没有明确说明,但ireturn
指令涉及从被调用者的操作数堆栈到调用者的操作数堆栈的副本。当然,在实际的JVM实现中,可能会有各种优化来减少复制。
当其他东西最终调用foo
来产生计算时,例如:
some_caller t = foo (1+3) (2+4) t + 1
(未经优化的)代码可能如下所示:
iconst_1
iconst_3
iadd // put 1+3 on the stack
iconst_2
iconst_4
iadd // put 2+4 on the stack
iload_0 // put t on the stack
invokestatic foo
iconst 1
iadd
ireturn
同样,子表达式通过操作数堆栈上的大量推送和弹出进行评估。最终,foo
被调用,其参数被推入堆栈并且其结果被弹出以供进一步处理。
所有这些分配和复制都在此堆栈上进行,因此本示例中不涉及堆分配。
现在,如果使用GHC 8.6.4编译相同的代码(没有优化,并且为了具体而在x86_64架构上),会发生什么?好吧,生成的程序集的伪代码类似于:
foo [x, y, z] =
u = new THUNK(sat_u) // thunk, 32 bytes on heap
jump: (+) x u
sat_u [] = // saturated closure for "bar y z"
push UPDATE(sat_u) // update frame, 16 bytes on stack
jump: bar y z
bar [a, b] =
jump: (*) a b
调用/跳转到(+)
和(*)
“原语”实际上比我做出来的要复杂得多,因为涉及的类型类。例如,跳转到(+)
看起来更像是:
push CONTINUATION(\f -> f x u) // continuation, 24 bytes on stack
jump: (+) dNumInt // get the right (+) from typeclass instance
如果你打开-O2
,GHC会优化掉这个更复杂的调用,但它也会优化掉这个例子中有趣的一切,所以为了论证,让我们假装上面的伪代码是准确的。
再说一次,foo
在有人打电话之前没什么用处。对于上面的some_caller
示例,调用foo
的代码部分将类似于:
some_caller [t] =
...
foocall = new THUNK(sat_foocall) // thunk, 24 bytes on heap
...
sat_foocall [] = // saturated closure for "foo (1+3) (2+4) t"
...
v = new THUNK(sat_v) // thunk "1+3", 16 bytes on heap
w = new THUNK(sat_w) // thunk "2+4", 16 bytes on heap
push UPDATE(sat_foocall) // update frame, 16 bytes on stack
jump: foo sat_v sat_w t
sat_v [] = ...
sat_w [] = ...
请注意,几乎所有这些分配和复制都发生在堆上,而不是堆栈上。
现在,让我们比较这两种方法。乍一看,看起来罪魁祸首真是懒惰的评价。如果评估严格的话,我们会在所有地方创建这些thunk,对吗?但是让我们更仔细地看看其中一个。在sat_u
的定义中考虑foo
的thunk。它是32字节/ 4个字,具有以下内容:
// THUNK(sat_u)
word 0: ptr to sat_u info table/code
1: space for return value
// variables we closed over:
2: ptr to "y"
3: ptr to "z"
这个thunk的创建与JVM代码没有根本的不同:
0: iload_1 // push y
1: iload_2 // push z
2: invokestatic bar // call bar, pushing result
5: istore_3 // pop and save to "u"
我们没有将y
和z
推入操作数堆栈,而是将它们加载到堆分配的thunk中。我们不是将结果从操作数堆栈弹出到我们的堆栈帧的本地存储器中,而是管理堆栈帧和返回地址,我们在thunk中留下了结果空间,并将一个16字节的更新帧推送到堆栈上,然后将控制转移到bar
。
类似地,在foo
中对some_caller
的调用中,不是通过在堆栈上推送常量并调用基元来将结果推送到堆栈来评估参数子表达式,而是在堆上创建thunk,每个thunk都包含指向信息表/代码的指针用于调用那些参数的原语和返回值的空间;更新框架替换了JVM版本中隐含的堆栈簿记和结果复制。
最终,thunk和更新框架是GHC替代基于堆栈的参数和结果传递,局部变量和临时工作空间。在JVM堆栈帧中发生的许多活动都发生在GHC堆中。
现在,JVM堆栈框架和GHC堆上的大部分内容很快变成垃圾。主要区别在于,在JVM中,在运行时复制了重要的东西(例如,返回值)之后,当函数返回时,堆栈帧被自动抛出。在GHC中,堆需要进行垃圾回收。正如其他人所指出的那样,GHC运行时是围绕绝大多数堆对象将立即变为垃圾的想法构建的:快速缓冲分配器用于初始堆对象分配,而不是每次函数返回时都复制出重要的东西(对于JVM),当缓冲堆变满时,垃圾收集器会将其复制出来。
显然,上面的玩具例子很荒谬。特别是,当我们开始讨论在Java对象和Haskell ADT上运行的代码而不是Ints
时,事情会变得更加复杂。但是,它有助于说明GHC和JVM之间的堆使用和GC循环的直接比较并没有多大意义。当然,由于JVM和GHC方法在根本上是不同的,因此确切的会计似乎并不可能,并且证明将是真实世界的表现。至少,对GHC堆使用情况和GC统计数据进行逐项比较需要考虑JVM在操作数堆栈之间推送,弹出和复制值的某些周期。特别是,至少一部分JVM return
指令应该计入GHC的“字节复制”。
至于“懒惰”对堆使用(特别是堆“垃圾”)的贡献,似乎难以隔离。 Thunks确实扮演了双重角色,作为基于堆栈的操作数传递的替代,并作为延迟评估的机制。当然,从懒惰到严格的转换可以减少垃圾 - 而不是首先创建一个thunk然后最终将它评估到另一个闭包(例如,构造函数),你可以直接创建评估的闭包 - 但这只是意味着而不是你的简单程序在堆上分配令人兴奋的172千兆字节,也许严格版本“仅”分配一个适度的84千兆字节。
据我所知,延迟评估对“复制的字节”的具体贡献应该是最小的 - 如果一个闭包在GC时间很重要,它将需要被复制。如果它仍然是未评估的thunk,那么thunk将被复制。如果已经评估过,则需要复制最终的闭包。如果有的话,因为复杂结构的thunk比它们的评估版本要小得多,懒惰通常应该减少复制的字节数。相反,通常的严格胜利是它允许某些堆对象(或堆栈对象)变得垃圾更快,因此我们最终不会出现空间泄漏。
不,懒惰本身并不会导致GC中的大量复制。然而,程序员未能妥善管理懒惰当然可以这样做。例如,如果持久性数据结构由于延迟修改而最终充满了thunk的链,那么它将最终严重膨胀。
正如Daniel Wagner所提到的,您可能遇到的另一个主要问题是不可变性的成本。虽然在Haskell中使用可变结构进行编程当然是可能的,但是在可能的情况下使用不可变结构更加惯用。不可变结构设计有各种权衡。例如,设计用于持久使用时的高性能往往具有较低的分支因子以增加共享,这在短暂使用时会导致一些膨胀。