Dart VM AOT模式进阶笔记

本文原始地址： https://www.jianshu.com/p/88a940a46a21
转载需附上原始地址

AOT去虚化原理

Java等基于JIT的高级语言保持高性能的秘诀，其中很重要的一条就是去虚化devirtualization。在Java和Dart这类完全面向对象的语言中，每个方法都默认是虚函数，通过去虚化来避免虚函数开销至关重要。少部分可以通过在编译期分析出对象的具体类型来实现（完全去虚化），而大部分去虚化还是需要依靠JIT收集运行期信息对类型进行猜测（条件去虚化）。

可以想见的是，AOT模式在运行时很难实现去虚化过程。最早的Dart 1.0 AOT由于类型系统缺陷，连编译期去虚化都做不到，因此性能血崩。但从Dart2.0开始，Dart对类型系统大改并在AOT模式加入了switchable call机制缓解了这个问题。

Switchable Call

Switchable call本质是一个借助Dart AOT的轻量runtime实现的弱化版JIT的代码替换功能。由于代码生成能力受限，其优化策略较为死板，而且无法实现内联，是一个简单的状态机。

第一次执行到虚函数的调用现场时，调用现场处于未链接unlinked状态。未链接状态的指令默认是调用runtime的DRT_UnlinkedCall函数。

DRT_UnlinkedCall会检查对象类型，并根据其类型返回对应函数的单态monomorphic版本的指针。这步查找的过程和正常的虚函数查表的开销一致。所谓单态版本，就是在目标函数前方加入一条类型检查语句，确保对象类型和预期的类型（上一次调用时的类型）完全一致。事实上，Dart里所有方法的二进制码，在存储时都会在头部额外附加单态类型检查的指令。正常调用会跳转到类型检查指令之后（也就是真正的函数的开始），单态版本的调用则是跳转到类型检查指令之前。

之后如果再次执行到这个调用现场，此时调用现场的指令已经指向单态版本，如果内部类型检查通过，单态版本的开销等于正常函数调用+一个类型比对。

但如果后续调用时对象类型出现改变，单态版本内部的类型检查失败，则会跳转到runtime的DRT_MonomorphicMiss函数，返回单目标SingleTarget版本。单目标版本生成的前提是，此次调用与之前调用尽管类型不同，但是对应的虚函数目标一致。单目标版本会检测当前类型是否属于目标一致的子类（通过对比单目标查询后缓存的ID范围，检测方法见下节“AOT类型检测”），若一致，则调用父类版本的函数。单目标态的开销等同于两层函数调用+一个类型范围对比。

如果单目标版本条件未被满足，则返回线性搜索内联缓存linear cache inline cache版本。线性搜索版本会用数组记录历史上出现的类型与对应的虚函数，并在之后的调用中在数组中搜索历史结果，如果未找到则添加新纪录。

如果线性搜索版本的数组容量超出上限，则回归最原始的表状结构，将历史记录组织为表，称为宏态Megamorphic版本。到这种状态时与放弃去虚化的性能差别已经存疑，个人猜测这种方式除了对缓存稍微友好一些，性能可能并无明显区别。

Switchable Call机制的性能特点

Switchable call是一个简单、单向的状态机。可以看出其特点是

零延迟：AOT状态下所有代码已编译完成，只有查虚函数表的延迟
预热极快：第一次调用即触发单态，单态版本早已AOT编译完成
单态性能高：只有一个普通函数调用和类型（int）比对的额外开销
节约内存：单态版本的二进制码就是在函数本体的二进制码前添加了类型检查指令；一个方法的所有调用现场各自保存历史缓存，而目标函数的各种版本都是公用的。
预热完成之后性能逐渐劣化：一开始时单态的性能最高。随着运行时类型的变化，性能会越来越低。而且这个过程是单向不可逆的。如果情况足够糟糕，最终会劣化到几乎没有去虚化。

Dart中大部分局部变量的方法调用在编译期就可以被完全去虚化。编译期无法完全去虚化的调用，大部分都是同一个类型（单态），一类类型的同一个方法（单目标），都可以在switchable call机制下获得不错的去虚化提升。如果只是简单的类型继承关系，那么不必担心虚函数开销问题。只有少量类型与目标多变的调用会导致AOT性能的逐渐劣化，性能敏感的场合可以在设计继承关系时尽量避免。如果拿Dart写复杂后端应用（如果真的有人这么做的话），AOT是完全不适合的。

AOT类型检测

Java和Dart中快速判断某个对象是否是对应类型的子类型对性能也非常重要。主流JVM实现方法是缓存每个类型最近的父类型（距离小于7），对于更上层的父类型则去进行查表。Dart AOT则进行了一个非常巧妙的优化。

Dart AOT里类的加载顺序是确定的，而且是深度优先次序加载每个类型，按照加载的顺序依次赋予每个类型一个int型ID。所以对任意一个类型，它的所有子类的ID都是连续的，在一个范围以内。所以判断类型A是否是类型B的子类，只需要判断类型A的ID是否在对应的范围内，只需要两个大于小于判断和一个&&。Java由于允许动态加载类型，所以无法实现这个优化。

这个优化只能判断extends的继承关系而不能判断对接口的实现和mixin，但是条件去虚化过程中最依赖的就是对于继承关系的检测。对于接口和mixin，目前尚缺少官方文档说明，不过应有类似JVM的优化。

定长List与List.generate

Dart中List分为不定长Growable和定长Fixed-length。DartVM中不定长List是通过定长List实现的。每个不定长List的数据都储存在一个隐藏的定长List中（带有冗余空间）。当数据长度超出定长List的容量后，就会开辟新的更长的定长List来存放数据。

自然地，不定长List的所有操作的开销都大于定长List，因为最终都要转发给其背后的定长List。同时它们占用的内存也更大（冗余空间）。在AOT模式下性能的差距可能会更明显，因为Dart AOT的内联策略比JIT更加保守，这些转发操作可能不会被内联。

定长List的相关操作可以称为是Dart隐藏的一套API风格。尽管配套API相当的少而且隐蔽，但事实上，其表达能力与不定长List相当。

创建：List.filled(length, elem, growable: false)填充相同元素，List.generate(length, f, growable: false)填充任意元素
变换：map/where/expand...等操作结束得到的Iterable可以调用.toList(growable: false)获得定长结果
注：List/Set等Iterable均为长度已知的EfficientLengthIterable，经过map这类变换后依然得到EfficientLengthIterable，生成的定长List长度精确，一次分配到位，不存在任何空间/时间浪费。
连接：list1.followedBy(list2).toList(growable: false) 最低开销连接List
注：这种情况下EfficientLengthIterable依然使用
List.generate威力远超想象，多个List的合并，List元素的乱序变换。只要结果长度确定，最后都能用List.generate
注：在List.generate中可能会进行大量的索引index操作[]，这些开销可以忽略，因为即使是for in循环中Iterable的迭代最终也是通过暴力索引[]来获得元素的。在List.generate被内联特化后都会被优化。

长期以来，Dart中最便捷的定长List生成方法一直是

final list = List(5, growable: false);
for (var i=0; i<5; i++) {
  list[i] = ...;
}

然而这种操作在空安全Null Safety特性推出之后将面临严重的类型问题，因为List(5)返回类型的元素是可空的。而List.generate则要面对闭包开销、无法内联等困扰。在Dart2.9中，List.generate已经正确实现了闭包的内联和特化
，成为了DartVM上最快的定长List生成办法，其性能与for循环基本一致。在空安全特性引入后，List(5)风格的构造函数将被废弃，届时List.generate将成为事实上唯一的零开销数组构造方法。

正则表达式

Dart AOT 性能退化最严重的地方就是正则表达式。Dart的RegExp(String pattern)底层是一个用Dart实现的、独立的字节码解释器，其算法无法被直接翻译为机器码。字节码解释器在JIT模式下可以达到很好的性能，但在AOT模式下解释器复杂的动态特性使得AOT性能基本倒退回了最差状态。AOT模式下正则表达式最高可以慢65%。能用其他方法匹配的东西就不要写正则表达式。

部分参考：

https://mrale.ph/dartvm/
Github dart/sdk仓库