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

Question

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

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

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

Answer 1

tl;博士: 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中，并在将控制权转移到 bar之前将一个16字节的更新帧压入堆栈。

同样，在 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在操作数堆栈之间推送，弹出和复制值所花费的部分周期。特别是，至少JVM return指令的一部分应计入GHC的“已复制字节”。

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

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