The Impact of Meta-Tracing on VM Design and Implementation

Introduction

这篇主要介绍Meta-Level tracing(其实就是PyPy)所实现的一些优化设计(找个了Converge来对比,但是不太熟,就跳过不看了)。前面对于Meta-Tracing的介绍没啥好看的。有一句总结性的描述:

The fundamental difference between meta-tracing and non-meta-tracingJITs is that the latter JIT must be manually written. By tracing the actionsthe interpreter itself takes, a meta-tracing JIT can automatically create aJIT from the interpreter.

这也符合PyPy自身设计的初衷。

Optimising an RPython VM

接下来是正题,一些优化上的设计。

General RPython JIT optimisation techniques

一些通用的优化技术。

promoting values:来自于Partial Evaluation中的promotion。

Elidable functions:简单来说就是相同输入会获得相同输出的函数,但是与pure function并不想等。

Using trace optimiser friendly code:某些代码并不适合trace优化,比如list的append操作,如果是变长的情况下,每次都需要去检查是否有足够的长度继续指向append操作,这无疑会提高deopt的概率。最简单的处理办法比如使用定长的数据结构来代替它,或者对于不需要随机访问的情况下用linked list代替。

Optimising Instances

对于PyPy这样的语言VM来说,最重要的优化无疑是对object model的优化(包括instance、class、module)。

对于Python这样的语言来说,本质上,instance的行为类似于将槽名称(作为字符串)映射到值的字典,而class定义了实例之间的共享行为(反过来说,与其他OO语言不同的是class并不能决定每个instance的shape)。语言的行为更接近prototype-basedlanguages,比如Self。

尽管class并不能约束每个instance的形状,但是在实践中,他们之间不一致的情况是少数。所以通过立即访问来代替字符串映射来提升访问速度,这一做法任然是可行的。例如上图,可以通过固定slot的方式,将a.x的访问优化成a.slot[0]

此外,非正式研究表明,大多数instance的属性访问,集中在5个甚至更少。因此PyPy为5个插槽预分配空间,使其在大多数情况下无需分配任意大小的列表来存储插槽,当超出5个的时候再分配额外的变长插槽,如下图所示:

Python中的instance可以通过__dict__来访问全部properties。但是这样的语法会导致两个问题:一是字典是一个复杂的数据结构,需要额外的内存代价;

二是这会破坏很多优化的机会,比如上面的立即访问操作。因此,正常情况下PyPy任然使用列表的方式实现属性的立即访问,但是维护一个fake dict,当一个instance调用__dict__的时候,就会将属性使用字典重排。

这也体现了,随着更罕见、更动态的特性的使用,解释器是如何逐渐降低性能的。

Optimising Classes

对于class的优化的关注点则变成了如何降低反射调用method上。不过对于method的查找需要考虑继承关系,所以代价更加昂贵。

这里使用的优化方式叫类的版本化。对于一个特定版本的类,它对于某个字段的访问应该是一致的,那么查找只需要进行一次。这种技术使得在普通情况下在类中查找字段非常快速(在速度上与C++方法调用相当)。JIT将字段查找优化为单个保护,它只需要检查一个类版本;如果检查成功,则正确的结果已经知道并插入。

然而,如上所述,当类的字段频繁变化时(会导致版本频繁变化),性能将受到影响。例如有一个class field用于记录当前发生多少次实例化:

class C:
  counter = 0
  
  def __init__(self):
    C.counter += 1 # class version ++
   
  def f(self):
    pass
  
  def g(self):
    pass

# 修改导致class版本变化
a1 = A()
a2 = A()

PyPy在上面增加了一层额外的间接级别:类不再直接存储该字段的值,而是存储对包含该值的Cell。当随后更改该特定字段时,只会更改该Cell的内容,而不会更改整个类:因此不需要更改类的版本。

Optimising Modules

Module的优化基本跟class相同。

Discussion

这些优化例证了RPython VM需要考虑哪些使用模式是最频繁的。然后,按照这种使用方式修改解释器和数据结构,以便与JIT一起生成代码少、保护少的机器代码。所以在演进过程中部分解释器的手动重写是必要的,许多优化依赖于对解释器实现的语言的深入了解。

同时必须对真正的程序进行分析,以确定需要关注哪些案例。不同的基准(合成的或非合成的)可以在很大程度上改变对最重要使用场景的看法,必须谨慎选择。