Haskell是否有内在的“垃圾成本”？

Question

在运行GHC编译的程序时，我经常会在GC中花费大量的周期。

这些数字往往比我的JVM经验所建议的高几个数量级。特别是，GC“复制”的字节数似乎比我正在计算的数据量大得多。

非严格语言和严格语言之间的这种区别是根本的吗？

Answer 1

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 [] = ...

请注意，几乎所有这种分配和复制都发生在堆上，而不是堆栈上。

现在，让我们比较这两种方法。乍一看，罪魁祸首确实是懒惰的评价。我们在各地创建这些代码，如果严格的评估就没有必要，对吧？但是，让我们更仔细地查看这些重击之一。sat_u在的定义中考虑重击foo。它是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。

类似地，在对in的调用foo中some_caller，我们没有在堆栈上推送常量并在堆栈上调用原语以将结果推送到堆栈中，而是通过在堆上创建thunk来评估参数子表达式，每个thunk都包含一个指向信息表/代码的指针以进行调用这些参数的原语和返回值的空格；更新框架替换了JVM版本中隐含的堆栈簿记和结果复制。

最终，重排和更新帧是GHC替代基于堆栈的参数和结果传递，局部变量和临时工作区的。JVM堆栈框架中发生的许多活动都在GHC堆中发生。

现在，JVM堆栈框架和GHC堆中的大多数东西很快就变成了垃圾。主要区别在于，在JVM中，在运行时将重要内容（例如，返回值）复制出来之后，函数返回时会自动丢弃堆栈帧。在GHC中，需要对堆进行垃圾收集。正如其他人指出的那样，GHC运行时基于以下想法：绝大多数堆对象将立即变为垃圾：快速缓冲分配器用于初始堆对象分配，而不是每次函数返回时都复制重要的东西（对于JVM），垃圾收集器会在凹凸堆变满时将其复制出来。

显然，上面的玩具示例是荒谬的。特别是，当我们开始谈论在Java对象和Haskell ADT而不是上运行的代码时，事情将会变得更加复杂Ints。但是，它只是用来说明直接比较GHC和JVM之间的堆使用情况和GC周期的意义不大。当然，由于JVM和GHC方法在根本上太不同了，因此实际上似乎无法进行精确的核算，并且证明将是真实的性能。至少，要逐一比较GHC堆使用情况和GC统计信息，这需要考虑JVM在操作数堆栈之间推入，弹出和复制值所花费的部分周期。特别是，至少有一部分JVMreturn 指令应计入GHC的“已复制字节”。

至于“懒惰”对堆使用（尤其是堆“垃圾”）的贡献，似乎很难隔离。Thunk确实扮演着双重角色，以替代基于堆栈的操作数传递和延迟评估机制。从懒惰到严格的转变当然可以减少垃圾-可以先创建评估后的闭包，而不是先创建一个thunk然后再对其进行评估，然后再将其评估到另一个闭包（例如，构造函数），但这仅意味着您的简单程序在堆上分配了惊人的172 GB，也许严格的版本“ only”分配了适度的84 GB。

据我所知，惰性求值对“复制的字节”的特定贡献应该是最小的-如果闭包在GC时很重要，则需要将其复制。如果仍然是未经评估的重击，将复制该重击。如果已经过评估，则只需要复制最后的闭包。如果有的话，由于复杂结构的重击比其评估版本小得多，因此延迟通常应减少复制的字节。取而代之的是，通常在严格性上的最大胜利是它允许某些堆对象（或堆栈对象）更快地变为垃圾，因此我们最终不会出现空间泄漏。