Haskell 中的垃圾 thunk 是否存在固有的“携带成本”?

2024-03-29

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

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

非语言和严格语言之间的这种差异是根本性的吗?


tl;dr:JVM 在堆栈帧中执行的大部分操作,GHC 在堆上执行。如果您想将 GHC 堆/GC 统计信息与 JVM 等效项进行比较,您确实需要考虑someJVM 用于将参数压入堆栈或在堆栈帧之间复制返回值的字节/周期的一部分。

长版:

针对 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

调用/跳转到(+) and (*)由于涉及到类型类,“基元”实际上比我想象的更复杂。例如,跳转到(+)看起来更像是:

    push CONTINUATION(\f -> f x u)         // continuation, 24 bytes on stack
    jump: (+) dNumInt                      // get the right (+) from typeclass instance

如果你打开-O2,GHC 优化了这个更复杂的调用,但它也优化了这个示例中有趣的所有其他内容,因此为了论证,让我们假设上面的伪代码是准确的。

Again, 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。它的大小为 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 and z到操作数堆栈上,我们将它们加载到堆分配的 thunk 中。我们没有将结果从操作数堆栈弹出到堆栈帧的本地存储中并管理堆栈帧和返回地址,而是在 thunk 中为结果留出空间,并在将控制权转移到堆栈之前将 16 字节更新帧推送到堆栈上。bar.

同样,在调用foo in 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 的“复制字节数”。

至于“惰性”对堆使用(尤其是堆“垃圾”)的贡献,似乎很难隔离。 Thunk 确实扮演着双重角色,既可以替代基于堆栈的操作数传递,又可以作为延迟求值的机制。当然,从惰性到严格的转变可以减少垃圾——而不是首先创建一个 thunk 然后最终将其评估为另一个闭包(例如,构造函数),您可以直接创建评估的闭包——但这只是意味着而不是您的简单程序在堆上分配了令人兴奋的 172 GB,也许严格版本“仅”分配了适度的 84 GB。

据我所知,惰性求值对“复制字节”的具体贡献应该是最小的——如果闭包在 GC 时很重要,则需要复制它。如果它仍然是一个未评估的 thunk,则该 thunk 将被复制。如果它已被评估,则只需复制最终的闭包。如果有的话,由于复杂结构的 thunk 比它们的评估版本小得多,所以惰性通常应该reduce复制的字节数。相反,严格的通常的巨大胜利是它允许某些堆对象(或堆栈对象)更快地变成垃圾,这样我们就不会导致空间泄漏。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

Haskell 中的垃圾 thunk 是否存在固有的“携带成本”? 的相关文章

随机推荐

  • 如何通过 ID 以外的其他方式获取 Backbone.js 模型?

    Backbone js 通过 ID 获取模型的默认 RESTful 方法非常简单且直接 但是 我似乎找不到任何通过不同属性获取模型的示例 如何通过不同的属性获取 Backbone js 模型 var Widget Backbone Mode
  • 单个文件中的多个类:此处不允许修饰符 private

    我无法理解为什么这段代码不能编译 class A public static void main String args System out println hi private class B int a 我将内容保存在名为的文件中A
  • Azure ARM 模板嵌套模板部署不会更新资源\无法启动

    我有以下 ARM 模板结构 Parent Template Nested Template 1 Nested Template 6 所以我只有 2 层模板 父级模板和嵌套模板 假设我将父级部署到一个空资源组 一切正常 之后 我删除其中一项资
  • iOS - 通过区域设置更改 UIDatePicker 的语言

    我正在用 Herbrew 语言创建应用程序 iPhone 的语言可以是任何语言 但我的应用程序只能在 Herbrew 中运行 在 iOS 的 UIDatePicker 中 我们有一个属性 locale 它将更改它显示的语言 但在 iOS5
  • Java Swing 保存和加载工作区/设置

    我有一个 Java Swing 应用程序 其中包含一堆框架 而这些框架又主要包含显示大量数据的表格 由于在启动时安排所有窗口和表格总是很麻烦且耗时 因此我想实现 工作区 功能 以便用户可以保存首选项设置并在启动时选择自动将存储的工作区加载到
  • 找到未合并的 Git 分支?

    我有一个包含许多分支的 Git 存储库 其中一些已经合并 一些还没有 由于分支数量相当多 如何判断哪些分支尚未合并 我想避免必须进行 章鱼 合并和重新合并已经合并的分支 尝试这个 git branch merged master 它按照锡上
  • 为什么我的标签栏按钮无法在 iPad 上自动调整大小?

    我正在构建一个通用的 iOS 应用程序 iPad 版本使用 SplitViewController 在弹出视图中 我有一个带有两个按钮的 UITabBarController 当它在 iPhone 上运行时 TabBar 按钮正确拉伸以填充
  • MVC 3 中如何处理会话超时

    我遇到了频繁的会话超时问题 我想编写一个可以在每个控制器上使用的通用过滤器 过滤器应该重定向用户登录 并在登录后返回到用户发送最后一个请求的位置 你可以尝试这样的事情 public class SessionExpireAttribute
  • 错误 (407)“需要代理身份验证。”

    我有一个要求 比如 我想从 winforms 访问一个 url 登录页面 即 Web 我必须将凭据传递给该网址 并且响应应该是经过身份验证的网页 标记 的内容 我已经编写了一个函数 它将请求 url 并返回响应 但我收到错误代码 407 需
  • git Reset 文件和 git checkout 文件有什么区别?

    为什么 git 允许我重置文件 我以为我明白了reset 从某种意义上说 它正在移动头部 显然我错了 So git reset sha file似乎做同样的事情git checkout sha file 除了我看到的file在索引和工作目录
  • Kestrel 错误:地址已在使用中(dotnet 核心)

    摘要 它的工作原理是dotnet run 但它不起作用dotnet myappname dll 我的 Linux 技能有限 但我正在尝试按照书本进行操作 这样我就不会混淆事情 以下本教程 http www hanselman com blo
  • 在 iOS 14 中,Interface Builder 中设置的 UITextField backgroundColor 在运行时为零

    我有一个应用程序可以在 iOS 11 13 上正常运行 但是当我在 iOS 14 中运行它时 有几个其中的文本字段用零渲染 因此透明 背景颜色即使背景颜色在 Interface Builder 中明确设置为白色 我在代码中看不到任何使用可能
  • 如何在 PySide2 应用程序中嵌入 matplotlib 画布

    我正在尝试将 matplotlib 画布嵌入到 PySide2 应用程序中 我尝试使用这个例子 https matplotlib org examples user interfaces embedding in qt5 html http
  • 使用 bash 计算文件中每个单词的出现次数

    我想计算文件中每个单词的出现次数 但结果是错误的 bin bash usage count sh file declare a dict for word in cat 1 do if dict word then dict word 0
  • 在 Google 表格中两个数字之间的列中填写数字

    所以我试图填写 Google 表格中两个单元格之间的数字 我从 270 开始 在列中出现几个不确定且变化的空单元格后 我需要达到 180 我需要均匀地填充它们之间的单元格 但如何呢 如果您想将这些值粘贴到同一列中 您需要执行以下操作 那么公
  • Prolog - 递归列表构建

    对于我正在编写的程序 我需要创建一个列表列表 其中包含代表乘积的数字对和两个给定数字的总和 现在我有一个函数 我可以指定将列表添加到列表中的次数 稍后将使用完整功能进行扩展 这是我所拥有的 s1 0 X s1 Q X N is Q 1 mu
  • NFC 广播接收器问题

    我希望我的应用程序仅在激活时侦听 nfc 标签 为此 我尝试如下注册一个 nfc 侦听器 但没有成功 IntentFilter filter new IntentFilter android nfc action TECH DISCOVER
  • 使用查询生成器或 Eloquent 进行带有附加条件的 JOIN

    我正在尝试使用 Laravel 查询生成器的 JOIN 查询添加条件
  • Android 上的 Libgdx app.exit() 未关闭应用程序

    在我用 libGDX 开发的 Android 应用程序中 我使用Gdx app exit 当用户尝试退出游戏时 这会关闭游戏 但是当用户重新启动应用程序时 所有Textures被扰乱 超出了使用该应用程序的范围 我注意到 如果我从任务管理器
  • Haskell 中的垃圾 thunk 是否存在固有的“携带成本”?

    在运行 GHC 编译的程序时 我经常看到 GC 上花费了大量的周期 这些数字往往比我的 JVM 经验所建议的要高出一个数量级 特别是 GC 复制 的字节数似乎比我正在计算的数据量大得多 非语言和严格语言之间的这种差异是根本性的吗 tl dr