menu
  • 首页 首页 icon
  • 工具库 工具库 icon
    • IP查询 IP查询 icon
  • 内容库 内容库 icon
    • 快讯库 快讯库 icon
    • 精品库 精品库 icon
    • 问答库 问答库 icon
  • 更多 更多 icon
    • 服务条款 服务条款 icon

Dart VM 运行原理

武飞扬头像
steadyuan
帮助1人

本文译自 Dart SDK 中 Dart VM 相关文章

介绍

Dart VM 是用于本机执行 Dart 代码的组件集合，包括以下内容：

  • 运行时系统
    • 对象模型、类型表示
    • GC
    • SnapShots
  • 核心库本地方法
  • 开发优化组件（通过服务协议访问）
    • Debugging
    • Profiling
    • Hot-reload
  • 即时编译（JIT）和 预编译（AOT）管道
  • 解释器
  • ARM 指令模拟器

"Dart VM" 命名是有历史原因的。从某种意义上说，Dart VM 是一个虚拟机，它为高级编程语言提供了一个执行环境，但这并不意味着在 Dart VM 上执行时总是对 Dart 进行解释或 JIT 编译。例如，可以使用 Dart VM AOT 管道将 Dart 代码编译为机器码，然后在称为预编译运行时（precompiled runtime） 的 Dart VM 精简版本中执行，该版本不包含任何编译器组件，无法动态加载 Dart 源码。

如何运行代码

Dart  VM 有多种方式执行代码，例如：

  • 源码或 Kernel binary（JIT）
  • Snapshot
    • AOT snapshot
    • AppJIT snapshot

这些方式的主要区别在于 VM 何时以及如何将 Dart 源码转换成可执行的代码，而其执行的运行时环境基本一样。

学新通

VM中的所有 Dart 代码都运行在 isolate 中，isolate 可以理解为一个独立的 Dart 空间，拥有自己的全局状态并且通常拥有自己的控制线程（mutator thread） 。isolate 会分组进 isolate group，组内 isolate 共享一个 GC 管理的堆内存，用以存储 isolate 分配的对象。组内的 isolate 共享堆内存的实现细节无法从 Dart 代码观察到。即使是同一组内的 isolate 也不能直接共享任何可变状态，只能通过端口传递的消息进行通信（不要和网络端口混淆）。

同一组内的 isolate 共享相同的 Dart 程序。使用 Isolate.spawn 可在组内生成一个 isolate，使用 Isolate.spawnUri 则会开启一个新的组。

thread（操作系统的线程） 和 isolate 之间的关系有点模糊，并且高度依赖于 VM 如何嵌入到应用程序中。因此仅保证如下内容：

  • 一个 thread 一次只能进入一个 isolate 。如果想要进入其他的 isolate ，就必须先离开当前的 isolate；
  • 一次只能有一个 mutator 线程与 isolate 关联。mutator 线程是一个执行 Dart 代码、使用 VM 公共 C API 的线程。

然而同一个 thread 可以先进入一个 isolate，执行 Dart 代码，然后离开这个 isolate 再进入另一个 isolate。另外，许多不同的 thread 可以进入一个 isolate 中，并在其中执行 Dart 代码，只是不能同时执行。

isolate 除了可以关联一个 mutator 线程外，还可以关联多个辅助线程，例如：

  • 后台 JIT 编译线程
  • GC 清理线程
  • 并发 GC 标记线程

VM 内部使用线程池 dart::ThreadPool 来管理线程，代码是围绕任务 dart::ThreadPool::Task 概念构建的，而不是围绕线程的概念。例如，在GC VM 向全局 VM 线程池发送 dart::ConcurrentSweeperTask 后，不是生成一个专用线程来执行后台清理，线程池要么选择一个空闲线程，要么在没有线程可用情况下生成一个新线程去实现。类似的，isolate 消息处理的事件循环的实现实际上并不生成专用的事件循环线程，而是在新消息到达时向线程池发送 dart::MessageHandlerTask 任务。

源码导读

类 dart::Isolate 表示 isolate，dart::IsolateGroup 表示 isolate 组，类 dart::Heap 表示 isolate 组的堆。类 dart::Thread 描述了关联到 isoloate 的线程的状态。注意 Thread 这个名称有点令人困惑，因为作为 mutator 关联同一 isolate 的所有线程都会复用相同的 Thread 实例。请参阅 Dart_RunLoop 和 dart::MessageHandler 了解 isolate 消息处理的默认实现。

从源码运行（JIT）

本节介绍当你从命令行执行Dart 时会发生什么：

// hello.dart
main() => print('Hello, World!');

$ dart hello.dart
Hello, World!

自 Dart 2 版本后，VM 不能直接从源码执行 Dart，取而代之的是只能执行包含序列化的内核抽象语法树（Kernel ASTs） 的内核二进制文件（Kernel binaries，也称 dill 文件） 。将 Dart 源码转换为内核AST的任务由 Dart 编写的 CFE（common front-end）  处理，并在不同的 Dart 工具之间共享（如VM，dart2js，Dart Dev Compiler）。

学新通

为了保留直接从源码执行 Dart 的便利性，提供了一个辅助 isolate 叫 kernel service，负责将 Dart 源码编译成内核二进制文件，然后 VM 运行生成的内核二进制文件。

学新通

然而这种组合并不是 CFE 和 VM 运行 Dart 代码的唯一方法。例如，Flutter 将编译和执行完全分开，将他们放在不同的设备上：编译在开发人员机器（主机）上进行，执行在目标移动设备上运行，目标移动设备接收由 Flutter 工具发送给它的内核二进制文件。

学新通

请注意，Flutter 工具并不处理 Dart 本身的解析，相反，他会生成另一个持久化进程 frontend_server，它本质上是 CFE 和一些特定于 Flutter 的 Kernel-To-Kernel 转换的封装。frontend_server 将 Dart 源码编译成内核文件，然后 Flutter 工具将其发送到设备。当开发人员请求热重载时，frontend_server 进程的持久化将发挥作用：在这种情况下，frontend_server 可以重用之前编译的 CFE 状态，并重新编译实际更改的库。

一旦将内核二进制文件加载到 VM 中，就会对其进行解析，以创建表示各种程序实体的对象。解析过程是懒加载的：首先只加载有关库和类的基本信息。源自内核二进制文件的每个实体都保留一个指向二进制文件的指针，以便以后可以根据需要加载更多信息。

Note

内部 VM 对象的定义，比如那些表示类和函数的定义，分为两部分：头文件 runtime/VM/object.h 中的类 Xyz 定义了 c 方法，而头文件 runtime/VM/raw_object.h 中的类 UntaggedXyz 定义了内存布局。例如 Class 和 UntaggedClass 指定描述 Dart 类的 VM 对象，Filed 和 UntaggedFiled 指定描述 Dart 类中的 Dart 字段的 VM 对象，等等。将在介绍运行时系统和对象模型时回到这一点。插图省略了Untagged…前缀，使他们更紧凑。

学新通

关于类的信息只有在运行以后需要时才被完全反序列化（例如查找类成员，分配实例等）。在这个阶段，从内核二进制文件中读取类成员。但是，在这个阶段不反序列化完整的函数体，只反序列化它们的签名。

学新通

此时，已经从内核二进制文件中加载了足够的信息，以便运行时成功解析和调用方法。例如，它可以解析和调用库中的 main 函数。

源码导读

package:kernel/ast.dart 定义了描述内核AST的类。package:front_end 处理解析 Dart 源码并从中构建内核AST。dart::kernel::KernelLoader:: LoadEntrieProgram 是一个入口点，用于将内核AST反序列化为相应的VM对象。pkg/vm/bin/kernel_service.dart 实现了内核服务 isolate。runtime/vm/kernel_isolate.cc 将Dart实现粘合到VM的其余部分。package:vm 承载了大多数基于内核的虚拟机特定功能，例如各种 Kernel-to-Kernel 的转换。

最初，所有函数的主体都有一个占位符，而不是实际的可执行代码：它们指向 LazyCompileStub，它简单的要求运行时系统为当前函数生成可执行代码，然后对新生成的代码进行尾调用。

学新通

当函数第一次编译时，是通过非优化编译器（unoptimizing compiler） 来完成的。

学新通

非优化编译器分两步生成机器码:

  1. 遍历函数体的序列化 AST 以生成函数体的控制流图（CFG） 。CFG 由填充了中间语言（IL） 指令的基本块组成。在这个阶段使用的 IL 指令类似于基于栈的虚拟机指令：它们从栈中获取操作数，执行操作，然后将结果推入相同的栈。

Note

实际上，并不是所有的函数都有实际的 Dart / Ketnel AST 主体，例如，在 c 中定义的原生函数或由 Dart VM 生成的人工 tear-off 函数，在这些情况下，IL 只是凭空创建的，而不是从内核AST生成的。

  1. 使用一对多的 IL 指令降级，将生成的 CFG 直接编译为机器码：每个 IL 指令扩展为多个机器语言指令。

在此阶段不执行任何优化。非优化编译器的主要目标是快速生成可执行代码。

这也意味着非优化编译器不会尝试在内核二进制文件中解析任何未解析的调用，因此调用（MethodInvocation 或 PropertyGet AST 节点）会被编译成完全动态的方式。VM 目前不使用任何形式的基于虚拟表或接口表的调度，而是使用内联缓存（inline caching） 实现动态调用。

内联缓存的核心思想是将方法解析的结果缓存在调用点特定的缓存中。VM 使用的内联缓存机制包括:

  • 一个调用点特定的缓存（dart::UntaggedICData 对象），它将接收者的类映射到一个方法，如果接收者属于匹配的类，则应该调用该方法。缓存还存储一些辅助信息，例如调用频率计数器，跟踪给定类在此调用点出现的频率;
  • 一个共享的查找存根（lookup stub），用于实现方法调用的快速路径。此存根搜索给定的缓存以查看它是否包含与接收者类匹配的条目。如果找到该条目，则存根会增加频率计数器并尾部调用缓存的方法。否则，存根将调用实现方法解析逻辑的运行时系统助手。如果方法解析成功，则更新缓存，后续调用将不需要进入运行时系统。

下图说明了与 animal.toFace() 调用点关联的内联缓存的结构和状态，该缓存使用 Dog 实例执行了两次，使用 Cat 实例执行了一次。

学新通

非优化编译器本身就足以执行任何的 Dart 代码。只是它生成的代码相当慢，因此 VM 还实现了自适应优化（adaptive optimizing） 编译管道。自适应优化背后的思想是使用运行程序的执行概况来驱动优化决策。

当未优化的代码运行时，它会收集以下信息：

  • 内联缓存收集在调用点观察到的接收器类型的信息
  • 与函数和函数内的基本块相关的执行计数器跟踪代码的热点区域

当与函数关联的执行计数器达到一定的阈值时，将该函数提交给后台优化编译器（background optimizing compiler） 进行优化。

优化编译器的开始方式与非优化编译器的开始方式相同：遍历序列化的内核AST，为正在优化的函数构建未优化的 IL。然而，优化编译器不是直接将该 IL 降级为机器码，而是将未优化的 IL 转换为基于优化 IL 的静态单赋值 SSA（static single assignment） 形式。然后，基于 SSA 的 IL 根据收集的类型反馈进行推测优化，并通过一系列经典和特定于 Dart 的优化：例如内联、范围分析、类型传播、表示选择、存储到负载和负载到负载转发、全局值编号、分配下沉等。最后，使用线性扫描寄存器分配器和简单的一对多降级 IL 指令将优化的 IL 降级为机器码。

一旦编译完成，后台编译器请求 mutator 线程进入一个安全点，并将优化后的代码附加到函数上。

Note

一般来说，在托管环境（VM）中的线程被认为处于安全点，当与它相关的状态（例如栈帧，堆等）是一致的，并且可以在线程本身不中断的情况下访问或修改时。通常，这意味着线程要么暂停，要么在托管环境之外执行一些代码，例如运行非托管本机代码。有关更多信息，请参阅 GC 页面。

下次调用这个函数时，它将使用优化后的代码。有些函数包含非常长的循环，对于这些函数，在函数仍在运行时从未优化的代码切换到优化的代码执行是有意义的。这个过程被称为栈替换 OSR（on stack replacement） ，它的名字来源于这样一个事实，即函数的一个版本的栈帧被透明地替换为同一函数的另一个版本的栈帧。

学新通

源码导读

编译器源码位于 runtime/vm/compiler 目录下。编译管道入口点是 dart::CompileParsedFunctionHelper::Compile。IL定义在 runtime/vm/compiler/backend/il.h 中。内核到 IL 的转换从 dart::kernel::StreamingFlowGraphBuilder::BuildGraph开始，这个函数还处理各种人工函数的 IL 构造。dart::compiler:: StubCodeCompiler::GenerateNArgsCheckInlineCacheStub 生成内联缓存存根的机器码，而 dart::InlineCacheMissHandler 处理 IC 错误。runtime/vm/compiler/compiler_pass.cc 定义了优化编译器传递及其顺序。dart::JitCallSpecializer 完成大多数基于类型反馈的优化。

需要强调的是，通过优化编译器生成的代码是在基于应用程序执行概要的推测性假设下进行优化的。例如，仅观察到单个类 C 作为接收者的实例的动态调用点将被转换为直接调用，并在此之前检查接收者是否具有预期的类 C。然而，这些假设可能会在稍后的程序执行过程中被违反：

void printAnimal(obj) {
  print('Animal {');
  print('  ${obj.toString()}');
  print('}');
}

// Call printAnimal(...) a lot of times with an intance of Cat.
// As a result printAnimal(...) will be optimized under the
// assumption that obj is always a Cat.
for (var i = 0; i < 50000; i  )
  printAnimal(Cat());
// Now call printAnimal(...) with a Dog - optimized version
// can not handle such an object, because it was
// compiled under assumption that obj is always a Cat.
// This leads to deoptimization.
printAnimal(Dog());

无论何时，优化的代码做出一些乐观的假设，这些假设可能在执行过程中被违反，它都需要防范这种违反，并能够在它们发生时进行恢复。

这个恢复过程被称为反优化（deoptimization） ：每当优化版本遇到它无法处理的情况时，它就简单地将执行转移到未优化函数的匹配点并继续在那里执行。函数的非优化版本不做任何假设，可以处理所有可能的输入。

Note

在正确的位置输入未优化的函数绝对是至关重要的，因为代码有副作用（例如，在上面的函数中，在我们已经执行了第一次打印之后，反优化发生了）。将反优化的指令匹配到 VM 中未优化代码中的位置是使用 deopt ids 完成的

VM 通常在反优化后丢弃函数的优化版本，然后再使用更新的类型反馈重新优化它。

VM 通过两种方式保护编译器做出的推测性假设：

  • 内联检查（例如 CheckSmi，CheckClass IL 指令），用于在编译器做出此假设的使用点验证假设是否成立。例如，当将动态调用转换为直接调用时，编译器会在直接调用之前添加这些检查。发生在这种检查上的反优化称为急切反优化（eager deoptimization） ，因为它在到达检查时立即发生。
  • 全局保护，当运行时改变了优化代码所依赖的东西时，指示运行时丢弃优化代码。例如，优化编译器可能会观察到某些类 C 从未被扩展，并在类型传播过程中使用此信息。然而，随后的动态代码加载或类终结可能会引入 C 的子类，从而使假设无效。此时，运行时需要查找并丢弃在假设 C 没有子类的情况下编译的所有优化代码。运行时可能会在执行堆栈上发现一些现在无效的优化代码——在这种情况下，受影响的帧被标记为反优化，并且在执行返回到它们时将被反优化。这种反优化被称为惰性反优化（lazy deoptimization） ：因为它被延迟到控制返回到优化的代码时发生。

源码导读

反优化器在 runtime/vm/deopt_instructions.cc 中。它本质上是一个反优化指令的迷你解释器，它描述了如何从优化代码的状态重建未优化代码的所需状态。反优化指令由 dart::CompilerDeoptInfo::CreateDeoptInfo 为编译期间优化代码中每个潜在的反优化位置生成。

从 Snapshots 运行

VM 能够将 isolate 的堆或更准确地说，驻留在堆中的对象图序列化为二进制 snapshot。然后，snapshot 可用于在启动 VM isloate 时重新创建相同的状态。

学新通

snapshot 的格式是低级别的，针对快速启动进行了优化 —— 它本质上是一个要创建的对象列表，以及如何将它们连接在一起的指令。这是 snapshot 背后的最初想法：与解析 Dart 源码并逐渐创建内部 VM 数据结构不同，VM 可以直接启动一个 isolate，并从快照中快速解压缩所有必要的数据结构。

Note

快照的想法源于 Smalltalk 图像，而后者又受到 Alan Kay 的硕士论文的启发。Dart VM 正在使用集群序列化格式，该格式类似于论文 《Parcels: a Fast and Feature-Rich Binary Deployment Technology》 和 《Clustered serialization with Fuel》 中描述的技术。

最初 snapshot 不包括机器码，但是后来开发 AOT 编译器时添加了这个功能。开发 AOT 编译器和带代码 snapshot 的动机是允许 VM 在由于平台级别限制而无法使用 JIT 的平台上使用。

带代码的 snapshot 与普通 snapshot 的工作方式几乎相同，但有一点不同：它们包含一个代码部分，与 snapshot 的其余部分不同，该代码部分不需要反序列化。该代码部分的布局方式允许它在映射到内存后直接成为堆的一部分。

学新通

源码导读

runtime/vm/app_snapshot.cc 处理快照的序列化和反序列化。一系列 API 函数 Dart_CreateXyzSnapshot[AsAssembly] 负责写出堆的快照（例如，Dart_CreateAppJITSnapshotAsBlobs 和 Dart_CreateAppAOTSnapshotAsAssembly）。另一方面，Dart_CreateIsolateGroup 可选地获取快照数据以启动 isolate。

从 APPJIT snapshots 运行

引入 AppJIT snapshot 是为了减少大型 Dart 应用程序（如 dartanalyzer 或 dart2js）的 JIT 预热时间。当这些工具用于小项目时，它们花费在实际工作上的时间与 VM 花费在 JIT 编译这些应用程序上的时间一样多。

AppJIT snapshot 可以解决这个问题：可以使用一些模拟训练数据在 VM 上运行应用程序，然后将所有生成的代码和 VM 内部数据结构序列化到 AppJIT snapshot 中。然后可以分发这个 snapshot，而不是以源码（或内核二进制文件）形式分发应用程序。如果实际数据上的执行配置文件与训练期间观察到的执行配置文件不匹配，那么从这个 snapshot 开始的 VM 仍然可以 JIT。

学新通

从 APPAOT snapshots 运行

AOT snapshot 最初是为无法进行 JIT 编译的平台引入的，但它们也可以用于快速启动和一致性性能（允许潜在的峰值性能损失）的情况。

Note

对于 JIT 和 AOT 的性能特征如何比较，通常会有很多混淆。JIT 可以访问正在运行的应用程序的精确的局部类型信息和执行概要，但是它必须付出预热时间。AOT 可以在全局范围内推断和证明各种属性（为此它必须付出编译时间），但它没有关于程序实际执行方式的信息 —— 另一方面，AOT 编译后的代码几乎不需要预热就能立即达到其峰值性能。目前 Dart VM JIT 具有最佳峰值性能，而 Dart VM AOT 具有最佳启动时间。

无法进行 JIT 意味着：

  • AOT snapshot 必须包含应用程序执行期间可能调用的每个函数的可执行代码
  • 可执行代码不得依赖于任何可能在执行期间被违反的推测性假设

为了满足这些需求，AOT 编译过程进行全局静态分析 TFA（type flow analysis），以确定应用程序的哪些部分可以从已知的一组入口点到达，分配了哪些类的实例，以及类型如何在程序中传播。所有这些分析都是保守的：这意味着它们会偏向于正确性 —— 这与 JIT 形成鲜明对比，JIT 可能在性能方面有所妥协，因为它总是可以将代码反优化为未优化的状态来实现正确的行为。

然后将所有可能可访问的函数编译为本机代码，而不进行任何推测性优化。然而，类型流信息仍然用于专门优化代码（例如，去虚拟化调用）。

一旦编译了所有函数，就可以获取堆的快照。

生成的快照可以使用预编译运行时（precompiled runtime） 运行，预编译运行时是 Dart VM 的一种特殊变体，它不包括 JIT 和动态代码加载功能等组件。

学新通

源码导读

package:vm/transformations/type_flow/transformer.dart 是基于 TFA 结果进行类型流分析和转换的切入点。dart::Precompiler::DoCompileAll 是 VM 中 AOT 编译循环的入口点。

运行系统

对象模型

类型表示

参考：Representation of Types

GC机制

Dart VM 有一个分两代的分代垃圾回收器。新生代由并行的、 stop-the-world 的半空间清理器（semispace scavenger） 收集。老年代是通过并发标记-并发清除（concurrent-mask-concurrent-sweep） 或并发标记-并行压缩（concurrent-mask-parallel-compact） 来收集。Dart VM 支持 become 的单向版本。

对象表示

对象指针指向直接对象或堆对象，由指针低位的标记来区分。Dart VM 只有一种直接对象 Smis（small integers） ，其指针标记为 0。堆对象的指针标记为 1。Smi 指针的高位是其值，堆对象指针的高位是其地址的最高有效位（最低有效位始终为 0，因为堆对象始终具有大于 2 字节的对齐方式）。

标记为 0 允许在 Smis 上执行许多操作，而无需取消标记和重新标记。

标记为 1 对堆对象访问没有影响，因为删除标签可以折叠到加载和存储指令使用的偏移量中。

堆对象始终以 double-word 增量分配。 老年代中的对象保持 double-word 对齐（address % double-word == 0），新生代中的对象保持 double-word 对齐偏移（address % double-word == word）。 这允许在不与边界地址进行比较的情况下检查对象的年龄，避免对堆放置的限制并避免从线程本地存储加载边界。 此外，清理器可以使用单个分支快速跳过当前对象和旧对象。

Pointer Referent
0x00000002 Small integer 1
0xFFFFFFFE Small integer -1
0x00A00001 Heap object at 0x00A00000，in old-space
0x00B00005 Heap object at 0x00B00004，in new-space

堆对象有一个 single-word 标头，它对对象的类、大小和一些状态标志进行编码。

在 64 位架构上，堆对象的标头还包含 32 位身份哈希字段。 在 32 位架构上，堆对象的身份哈希保存在单独的哈希表中。

句柄（Handles）

Dart VM 的 GC 是精确（precise）且移动式（moving）的。

如果当发生收集时，GC 准确地知道什么是堆中的指针，什么不是堆中的指针，则称 GC 是 ”精确的”。例如，在编译的 Dart 代码中，VM 跟踪哪些栈槽包含对象指针，哪些包含未装箱的值。这与 “保守” 收集器相反，后者认为任何指针大小的值都可能是指向堆的指针，尽管它可能只是一个未装箱的值。

在 “移动式” GC 中，对象的地址可能会改变，这就需要更新指向该对象的指针。在 Dart VM 中，对象可以在清理、压缩或 become 操作期间移动。移动的 GC 必须是精确的 GC：如果一个保守的 GC 更新了一个不保证是指针的值，当这个值实际上不是指针时，它将破坏执行。

VM 不知道哪些栈槽、全局变量或外部语言中的对象字段包含指向 Dart 堆的指针，包括 VM 自己用 c 实现的运行时。为了保持 GC 的精确性，外部语言通过 “Handles” 间接地引用 Dart 对象。句柄可以看作是指向指针的指针。它们是从 VM 分配的，GC 将在收集期间访问（并可能更新）句柄中包含的指针。

安全点（Safepoints）

任何可以分配、读取或写入堆的非 GC 线程或任务都称为 “mutator” （因为它可以改变对象图）。

GC 的某些阶段要求堆不被 mutator 使用：我们称之为 “安全点操作” 。安全点操作的示例包括在并发标记开始时标记根和整个清除器程序。

为了执行这些操作，所有的 mutator 需要暂时停止对堆的访问；我们说这些 mutator 已经到达了一个 “安全点” 。到达安全点的 mutator 在安全点操作完成之前不会恢复对堆的访问（离开安全点）。除了不能访问堆之外，安全点上的 mutator 不能持有任何指向堆的指针，除非这些指针可以被 GC 访问。对于 VM 运行时中的代码，最后一个属性意味着只持有句柄而不持有 ObjectPtr 或 UntaggedObject。可能进入安全点的位置的示例包括分配内存、堆栈溢出检查以及编译代码与运行时和本机代码之间的转换。

注意，mutator 可以位于安全点而不被挂起。它可能正在执行一个不访问堆的长任务。但是，它需要等待任何安全点操作完成，以便离开其安全点并恢复对堆的访问。

由于安全点操作不执行 Dart 代码，因此它有时用于只需要此属性的非 GC 任务。例如，当后台编译完成并希望安装其结果时，它使用安全点操作来确保 Dart 执行在安装期间不会看到中间状态。

清理 Scavenge

一种复制算法

是用于新生代的垃圾回收策略，主要用于回收临时分配的短期对象。算法会将内存分成两个 semi 空间（to-space，from-space），一个处于活跃状态，一个处于非活跃状态。垃圾回收器会将活动对象从一个半空间复制到另一个半空间，然后清理未使用的内存，非活跃变为活跃，循环此过程。复制算法不适合长期存活的对象。

参考切尼的算法

并行清理 Scavenge

FLAG_scavenger_tasks（默认为2）工作线程在单独的线程上启动。每个工作线程都竞争性的处理根集（root set）的部分（包括记忆集 remembered set）。当一个工作线程将对象复制到 to-space 时，它从一个工作线程本地的 bump 分配区域进行分配。同一个工作线程将处理被复制的对象。当一个工作线程将一个对象提升到老年代时，它从一个工作线程本地的空闲列表中进行分配，该列表对大的空闲块使用 bump 分配。提升的对象被添加到实现工作窃取的工作列表中，因此其他工作线程可以处理提升的对象。在对象被清空后，工作线程使用对比-转换（compare-and-swap）将转发指针安装到 from-space 对象的标头中。如果它输掉了竞争，它将取消分配刚刚分配的 to-space 或老年代空间对象，并使用获胜者的对象来更新它正在处理的指针。工作线程会一直运行，直到处理完所有的工作集，并且每个工作线程都处理了它的 to-space 对象和提升的工作列表的本地部分。

标记-清除

所有对象的头部都有一个称为 "标记位" 的位。在收集周期开始时，所有对象的这个位都被清除。

在标记阶段，垃圾收集器会访问每个根指针（root points）。如果目标对象是老年代对象且其标记位未设置，则会将标记位设置为已标记，并将目标对象添加到标记栈（grey set）。然后，垃圾收集器会移除并访问标记栈中的对象，标记更多的老年代对象，并将它们添加到标记栈，直到标记栈为空。在此阶段，所有可达对象的标记位都被设置，所有不可达对象的标记位都被清除。

在清除阶段，垃圾收集器会访问每个老年代对象。如果标记位未设置，则该对象的内存会被添加到空闲列表，以便将来的分配使用。否则，对象的标记位会被清除。如果某个页面上的所有对象都是不可达的，则该页面会被释放给操作系统。

新生代作为根集合

我们不会标记新生代对象，指向新生代对象的指针也会被忽略；相反，新生代中的所有对象都被视为根集的一部分。

这样做的好处是使两个内存空间的回收更加独立。特别是，并发标记永远不需要解引用新生代中的任何内存，从而避免了多种数据竞争问题，并且避免了在启动 scavenge 时暂停或以其他方式与并发标记同步的需要。

它的缺点是没有一个单独的收集器可以收集所有的垃圾。不可达的新生代对象引用的不可达的老年代对象将在清除器首先收集新生代对象之前不会被收集，而具有跨代周期的不可达对象将在整个子图提升到老年代之前不会被收集。增长策略必须小心地确保它不会在不穿插新生代收集的情况下执行老年代收集，例如当程序执行大部分直接分配到老年代的大分配时，或者老年代可以积累这种浮动垃圾并无限制地增长时。

标记-压缩

Dart VM 包括一个滑动压缩器。转发表通过将堆划分为块来紧凑地表示，每个块记录其目标地址和每个幸存的 double-word 的位向量。通过保持堆页面对齐，可以在常量时间内访问该表，因此可以通过屏蔽对象来访问任何对象的页头。

并发标记

为了减少对老年代 GC 暂停 mutator 的时间，我们允许在大部分标记工作期间继续运行 mutator。

屏障（Barrier）

在 mutator 和标记器同时运行的情况下，mutator 可能会将指向尚未标记的对象（TARGET）的指针写入已经标记并访问过的对象（SOURCE），从而导致 TARGET 的错误收集。为了防止这种情况，写屏障检查存储是否创建了从老年代对象到未标记的老年代对象的指针，并为此类存储标记目标对象。我们忽略来自新生代对象的指针，因为我们将新生代对象视为根对象，并将重新访问它们以完成标记。我们忽略源对象的标记状态，以避免昂贵的内存屏障，以确保对头和槽的重新排序访问不会导致跳过标记，并且假设在标记期间访问的对象可能在标记完成时保持活动。

这个屏障等同于：

StorePointer(ObjectPtr source, ObjectPtr* slot, ObjectPtr target) {
  *slot = target;
  if (target->IsSmi()) return;
  if (source->IsOldObject() && !source->IsRemembered() && target->IsNewObject()) {
    source->SetRemembered();
    AddToRememberedSet(source);
  } else if (source->IsOldObject() && target->IsOldObject() && !target->IsMarked() && Thread::Current()->IsMarking()) {
    if (target->TryAcquireMarkBit()) {
      AddToMarkList(target);
    }
  }
}

但我们将代际检查和增量检查与移位和掩码相结合。

enum HeaderBits {
  ...
  kOldAndNotMarkedBit,      // Incremental barrier target.
  kNewBit,                  // Generational barrier target.
  kOldBit,                  // Incremental barrier source.
  kOldAndNotRememberedBit,  // Generational barrier source.
  ...
};

static constexpr intptr_t kGenerationalBarrierMask = 1 << kNewBit;
static constexpr intptr_t kIncrementalBarrierMask = 1 << kOldAndNotMarkedBit;
static constexpr intptr_t kBarrierOverlapShift = 2;
COMPILE_ASSERT(kOldAndNotMarkedBit   kBarrierOverlapShift == kOldBit);
COMPILE_ASSERT(kNewBit   kBarrierOverlapShift == kOldAndNotRememberedBit);

StorePointer(ObjectPtr source, ObjectPtr* slot, ObjectPtr target) {
  *slot = target;
  if (target->IsSmi()) return;
  if ((source->header() >> kBarrierOverlapShift) &&
      (target->header()) &&
      Thread::Current()->barrier_mask()) {
    if (target->IsNewObject()) {
      source->SetRemembered();
      AddToRememberedSet(source);
    } else {
      if (target->TryAcquireMarkBit()) {
        AddToMarkList(target);
      }
    }
  }
}

StoreIntoObject(object, value, offset)
  str   value, object#offset
  tbnz  value, kSmiTagShift, done
  lbu   tmp, value#headerOffset
  lbu   tmp2, object#headerOffset
  and   tmp, tmp2 LSR kBarrierOverlapShift
  tst   tmp, BARRIER_MASK
  bz    done
  mov   tmp2, value
  lw    tmp, THR#writeBarrierEntryPointOffset
  blr   tmp
done:
数据竞争

对标头和槽的操作使用宽松的排序，不提供同步。

并发标记从一个获取-释放（acquire-release） 操作开始，因此在标记开始之前，mutator 的所有写操作对标记都是可见的。

对于在标记开始之前创建的老年代对象，在每个槽中，标记器可以看到标记开始时的值或槽中排序的任何后续值。任何包含指针的槽在对象的生命周期内都会继续包含一个有效的指针，所以无论标记符看到哪个值，它都不会将非指针解释为指针。（这里一个有趣的例子是数组截断，其中数组中的一些槽将成为填充对象的头。我们通过确保填充对象的头部看起来像一个 Smi 来确保并发标记是安全的。）如果标记符看到一个旧值，我们可能会失去一些精度并保留一个死对象，但我们仍然是正确的，因为新值已经被 mutator 标记了。

对于在标记开始后创建的老年代对象，标记器可能会看到未初始化的值，因为槽上的操作没有同步。为了防止这种情况，在标记期间，我们将老年代对象分配为黑色（已标记），这样标记器就不会访问它们。

新生代对象和根对象只在安全点期间访问，安全点会建立同步。

当 mutator 的标记块填满时，通过一个获取-释放操作将其转移给标记器，因此标记器将看到存储到块中的内容。

消除写屏障

只要堆中有存储 container.slot = value 时，我们需要检查存储是否创建了需要通知 GC 的引用。

scavenger 需要的分代写屏障检查：

  • container 是旧的并且不在记忆集中
  • value 是新的

发生这种情况时，必须将 container 插入记忆集中。

标记器需要的增量标记写屏障检查：

  • container 是旧的
  • value 是旧的，没有标记
  • 正在进行标记

发生这种情况时，我们必须在标记工作列表中插入 value。

当编译器可以证明这些情况不会发生，或者运行时可以补偿这些情况时，我们可以消除这些检查。编译器可以证明这一点

  • value 是一个常量。常量总是旧的，即使我们没有通过 container 标记它们，也会通过常量池标记它们。
  • value 是静态类型 bool。bool 类型的所有可能值（null, false, true）都是常量。
  • value 是已知的 Smi。Smi 不是堆对象。
  • container 是与 value 相同的对象。如果 GC 看到一个自引用，它永远不需要保留一个额外的对象，因此忽略一个自引用不会导致我们释放一个可访问的对象。
  • container 是已知的新对象，或者是已知的记忆集中的旧对象，如果正在进行标记，则标记。

如果 container 是分配（而不是堆加载）的结果，并且在分配和存储之间没有可以触发 GC 的指令，则可以知道容器满足最后一个属性。这是因为分配存根确保 AllocateObject 的结果要么是一个新空间对象（常见情况，bump 指针分配成功），要么已经被预先添加到记忆集和标记工作列表（不常见情况，进入运行时分配对象，可能触发 GC）。

container <- AllocateObject
<instructions that do not trigger GC>
StoreInstanceField(container, value, NoBarrier)

当 container 是分配的结果，并且没有指令可以在分配和存储之间创建额外的 Dart 帧时，我们可以进一步消除屏障。这是因为在 GC 之后，在退出帧下面的帧中的任何老年代对象都将被预先添加到记忆集和标记工作列表中（Thread::RestoreWriteBarrierInvariant）。

container <- AllocateObject
<instructions that cannot directly call Dart functions>
StoreInstanceField(container, value, NoBarrier)

弱引用

GC 支持各种弱引用和短暂引用。

  • 堆对象
    • WeakReference - 弱引用单个对象。
    • WeakProperty - 弱引用键。如果键是可达的，则值是可达的。也叫短暂引用。用于实现 Expando（也称为WeakMap）。
    • WeakArray - 弱引用可变数量的对象。用于实现弱规范集。
    • Finalizers - 弱引用单个对象，在对象被收集时运行回调。
  • 非堆对象
    • Dart_WeakPersistentHandle / Dart_FinalizableHandle - 弱引用单个对象，在对象被收集时运行回调。
    • 对象 id 环 - 引用由虚拟机服务分配 id 的对象。在小型 GC 期间是强引用，在大型 GC 期间是弱引用。
    • 弱表 - 将对象弱关联到整数。用于实现 Dart_GetPeer，在32位架构上标识哈希和规范化哈希。

当 GC 跟踪强引用时，它会维护一组遇到的弱引用集。一旦强引用的工作列表为空，将检查 WeakProperties 集合以查找任何可达的键，将相应的值添加到工作列表中。重复此操作，直到工作列表为空为止。（在最坏的情况下这是二次的。Dart VM 早期版本使用了观察集优化。实际情况中，情况是平稳的。）

终结器（Finalizers）

GC 在运行终结器时，根据对象的两种类型进行了处理。

  • FinalizerEntry
  • Finalizer（FinalizerBase， _FinalizerImpl， _NativeFinalizer）

FinalizerEntry 包含值、可选的分离键、标记（token，对终结器的引用）和 外部大小（external_size）。一个条目只弱引用值、分离键和终结器（类似于 WeakReference 只对目标保持弱引用）。

Finalizers 包含所有条目、值被收集的条目列表以及对 isolate 的引用。

当一个条目的值被 GC 时，该条目被添加到收集的列表中。如果将任何条目移动到收集的列表中，则发送一条消息，该消息将调用终结器来对该列表中的所有条目调用回调。对于本机终结器，本机回调会立即在GC中调用。然而，我们仍然会向本机终结器发送一条消息，以清理所有条目和分离键。

当终结器被用户分离时，条目标记将被设置为条目本身，并从所有条目集中删除。这确保了如果条目已经移动到收集的列表中，则不会执行终结器。

为了加快分离速度，我们使用了从分离键到条目列表的弱映射。这确保了条目可以被 GC。

清理器和标记器都可以并行处理终结器条目。并行任务在收集的条目列表的头部使用原子交换，确保没有条目丢失。保证在处理条目时停止 Mutator 线程。这确保我们不需要为将条目移动到 finalizer 收集的列表中添加屏障。Dart 也使用原子交换读取和替换收集到的条目列表，从而确保 GC 不会在加载/存储之间运行。

当终结器收到处理已终结对象的消息时，该消息将使其保持活动状态。另一种设计是在终结器中预先分配一个指向终结器的 WeakReference，然后自己发送它。这将以额外的对象为代价。

如果终结器对象本身被 GC 时，则不会为任何附件运行回调。

在 isolate 关闭时，本机终结器会运行，但常规终结器不会运行。

Become 操作

Become 是一种原子操作，用于转发一组对象的标识。在执行堆遍历时，指向 before 对象的每个指针都被指向 after 对象的指针替换，并且每个 after 对象都获得相应 before 对象的标识哈希。在 Dart VM 中，它仅在重新加载期间用于将具有旧大小的旧程序和实例映射到具有新大小的新程序和实例。

这个操作可以追溯到早期的 Smalltalk 实现。它的复杂度是 O(1)，因为指针是间接通过对象表的，并且用于调整集合的大小。

还有一种不被 Dart VM 使用的变种，即交换身份而不是转发。如果需要在子图前面安装代理并保留对代理后面对象的引用，则此功能非常有用。在分页之前，这是一种获取虚拟内存的方法。

编译器

方法调用

目前，AOT 和 JIT 优化方法调用序列的方式存在很大差异。

JIT 保留了其 Dart 1 的根源，基本忽略了 Dart 2 的静态类型特性。在未优化的代码中，方法调用默认通过内联缓存来收集类型反馈。然后，优化编译器推测地将间接方法调用专门化为由类检查保护的直接调用。这个过程称为推测性去虚拟化（speculative devirtualization） 。不能去虚拟化的调用点分为两类。那些尚未执行的调用点将被编译为使用内联缓存并收集类型反馈以用于后续的重新优化。那些高度多态（megamorphic）的调用点被编译为使用变态调度（metamorphic dispatch）。

另一方面，AOT 则充分利用了 Dart 2 的静态类型特性。编译器使用 TFA 的结果来对尽可能多的调用点进行非虚拟化。这种去虚拟化不是推测性的：编译器只有在能够证明调用点总是调用特定方法时才会去虚拟化。如果编译器不能对调用点进行去虚拟化，则根据接收方的静态类型是否为动态类型来选择调度机制。动态接收器上的调用使用可切换的调用（switchable calls）。所有其他调用都要经过一个全局调度表 GDT（global dispatch table） 。

全局调度表（GDT）

Note

Dart VM 采用的方法和本节中描述的方法主要基于 Karel Driesen 和 Urs Holzle 在 《Minimizing row displacement dispatch tables》 中的见解。

想象一下，程序中定义的每个类都将其方法添加到全局字典中。例如，给定下面的类层次结构

class A {
  void foo() { }
  void bar() { }
}

class B extends A {
  void foo() { }
  void baz() { }
}

这本字典将包含以下内容：

globalDispatchTable = {
  // Calling [foo] on an instance of [A] hits [A.foo].
  (A, #foo): A.foo,
  // Calling [bar] on an instance of [A] hits [A.bar].
  (A, #bar): A.bar,
  // Calling [foo] on an instance of [B] hits [B.foo].
  (B, #foo): B.foo,
  // Calling [bar] on an instance of [B] hits [A.bar].
  (B, #bar): A.bar,
  // Calling [baz] on an instance of [B] hits [B.baz].
  (B, #baz): B.baz
};

然后，编译器可以使用这样的字典来分派调用：方法调用 o.m(…)  将被编译成 globalDispatchTable[(classOf(o), #m)](o，…) 。

表示 GDT 的一种简单方法是按顺序对程序中的所有类和所有方法选择器进行编号，然后使用二维数组：gdt[(classOf(o), #m)]  变成 gdt[.cid][#m.id] 。此时，我们可以选择使用选择器主序（gdt[numClasses * #m.id .cid] ）或类主序（gdt[numSelectors * .cid #m.id] ）来平整化这个二维数组。

让我们看一下选择器主序。在这个表示中，我们说 numClasses * #m.id 为我们提供了选择器偏移量：GDT 中的偏移量，在 GDT 中存储了与此选择器对应的一行条目(每个类一个)。考虑下面的类层次结构：

class A {
  void foo() { }
}

class B extends A {
  void foo() { }
}

class C {
  void bar() { }
}

class D extends C {
  void bar() { }
}

类 A、B、C 和 D 将分别编号为 0、1、2 和 3，而选择器 foo 和 bar 将分别编号为 0 和 1。这将导致以下数组：

学新通

很明显，这样的表示相当低效：调度表最终会有很多 NSM (noSuchMethod)  条目。

幸运的是，Dart 2 静态类型系统为我们提供了压缩该表的方法。在 Dart 2 中，接收器的静态类型限制了编译器允许的选择器列表。这保证了任何非动态调用调用实际的方法，而不是 Object.noSuchMethod。因此，如果我们只对非动态调用点使用调度表，那么我们就不需要用 NSM 条目填充表中的空隙。

这引出了以下想法：我们可以不再顺序编号选择器，也不再使用 numClasses * sid 作为选择器偏移量，而是选择使选择器行交替并重用可用空隙的选择器偏移量。

让我们回顾一下前面有4个类的例子。我们可以简单地将两个选择器的偏移量分别赋值为 0 和 0，而不是将 foo 和 bar 分别赋值为 1 和 1 作为选择器偏移量，从而得到以下紧凑表

学新通

这是有效的，因为不可能在 A 或 B 上调用 bar，也不可能在 C 或 D 上调用 foo。这意味着，例如，A.foo 条目永远不会被 C 的实例作为接收者击中。

Note

严格地说，这种技术实际上并不需要静态类型，最初应用于 Smalltalk。这需要一个小技巧：每个方法都应该在序言中检查其选择器是否与导致该方法被调用的调用的选择器匹配。如果选择器不匹配，这意味着我们通过重用的 NSM 条目错误地到达了该方法。静态类型允许我们避免这种检查。

通过 GDT 调用编译到 Dart VM 中的以下机器码（X64示例）：

movzx cid, word ptr [obj   15] ; load receiver's class id
call [GDT   cid * 8   (selectorOffset - 16) * 8]

这里 GDT 是一个保留寄存器，包含指向 GDT 的有偏指针（X64上的 &GDT[16] ），selectorOffset 是我们调用的选择器的偏移量。跨架构的调用看起来很相似，尽管偏差的具体值（由 dart:: DispatchTable::kOriginElement 指定）取决于目标架构。对于较小的选择器，我们偏置 GDT 指针，使其具有更紧凑的调用序列编码，例如，在 X64 上，间接调用具有允许1字节 signed 立即偏移的编码。这意味着-128到127范围内的直接偏移量被表示为单个字节。对于无偏 GDT 指针，我们只能利用这个范围的一半，因为 selectorOffset 是一个无符号值。对于偏置 GDT，我们可以使用全范围 selectorOffset 15 仍然只需要一个字节编码。

源码导读

全局调度表的计算分布在工具链的不同部分。

TableSelectorAssigner 负责将选择器 id 分配给程序中的方法

dart::DispatchTableCallInstr 是一个通过 GDT 表示调用的 IL 指令

dart::AotCallSpecializer::ReplaceInstanceCallsWithDispatchTableCalls 是一个编译器传递，它用 GDT 调用代替非去虚拟化的方法调用

dart::FlowGraphCompiler::EmitDispatchTableCall 为通过 GDT 的调用发出特定于体系结构的调用序列

dart::compiler::DispatchTableGenerator 负责分配选择器偏移量和计算表的最终布局

可切换调用（Switchable Calls）

可切换调用是最初为 Dart 1 AOT 开发的内联缓存的扩展 —— 它们用于编译所有方法调用。当前 AOT 仅在使用动态接收器编译调用时使用它们。它们也在 JIT 中用于加速未优化代码中的调用

JIT 部分已经描述了与调用点关联的每个内联缓存由两部分组成：缓存对象（由 dart::UntaggedICData 实例表示）和要调用的本机代码块（例如内联缓存存根）。JIT 中的原始实现仅更新缓存本身，但是后来进行了扩展，允许运行时系统根据调用点观察到的类型更新缓存和存根目标。

学新通

初始情况下，AOT 中的所有动态调用都为未链接状态。当第一次到达这样的调用点时，SwitchableCallMissStub 被调用，它简单的调用运行时助手 dart::DRT_SwitchableCallMiss 来链接这个调用点。

如果可能，dart::DRT_SwitchableCallMiss 尝试将调用点转换为单态状态。在这种状态下，调用点变成直接调用，直接调用通过一个特殊的入口点进入方法，该入口点验证接收者是否具有期望的类。

学新通

在上面的例子中，我们假设 obj 是 C 的一个实例。第一次执行 obj.method() 时，方法被解析为 C.method。

下次我们执行相同的调用点时，它将直接调用 C.method，绕过方法查找过程。然而，它将通过一个特殊的入口点进入 C.method，该入口点将验证 obj 仍然是 C 的一个实例。如果不是这种情况，dart::DRT_SwitchableCallMiss 将被调用，并将更新调用点状态以反映未命中。

C.method 可能仍然是调用的有效目标，例如 obj 是类 D 的实例，它扩展了 C，但不覆盖 C.method。在这种情况下，我们检查调用点是否可以转换到单个目标状态，由 SingleTargetCallStub 实现（参见 dart::UntaggedSingleTargetCache ）。

学新通

这个存根受益于 AOT 编译器和 AppJIT snapshot 训练期间完成的深度优先类 id 分配。在这种模式下，使用深度优先遍历继承层次结构，为大多数类分配整数 id。如果 C 是一个具有子类 D0，...，Dn 的基类，并且这些子类都没有覆盖 C.method，那么 C.:cid <= classId(obj) <= max(D0.:cid, ..., Dn.:cid) 意味着 obj.method 解析为C.method。在这种情况下，我们可以比较类 id 是否属于一个特定的范围，这将涵盖 C 的所有子类。这正是 SingleTargetCallStub 所做的。

如果单目标情况不适用，调用点将切换到使用线性搜索内联缓存。这恰好也是 JIT 模式下调用点的初始状态（参见 ICCallThroughCode stub，dart::UntaggedICData 和 dart::DRT_SwitchableCallMiss）。

学新通

最后，如果线性数组中的检查次数超过阈值，则调用点切换为使用类似字典的结构（参见 MegamorphicCallStub, dart::UntaggedMegamorphicCache 和 dart::DRT_SwitchableCallMiss）。

学新通

来源文档

这篇好文章是转载于：学新通技术网

  • 版权申明： 本站部分内容来自互联网，仅供学习及演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，请提供相关证据及您的身份证明，我们将在收到邮件后48小时内删除。
  • 本站站名： 学新通技术网
  • 本文地址： /boutique/detail/tanhgaikif
系列文章
更多 icon
同类精品
更多 icon
继续加载
友情链接: 申请要求：权重≥3，IP≥1000，内容属同类网站; 申请邮件： luke.wu●vfv.cc 友情链接交换群： 友情链接交换群
外链价格: 【首页 30/月 - 300/年】【内页 50/月 - 500/年】【全站 70/月 - 700/年】 购买外链请加QQ群： 站长交流群