Runtime feedback in a meta-tracing JIT for efficient dynamic languages

Introduction

对于面向对象的动态语言，最困难的部分之一就是优化其对象模型。Meta-Tracing JIT为实现动态语言的语言解释器提供Tracing JIT，而不是为动态语言本身提供跟踪JIT，这使得对象模型对于跟踪器及其优化是透明的，动态语言的语义不必在JIT中复制实现。同时，允许在动态语言实现中使用一些注解来指导Meta-Tracing，该过程不是完全自动的，但可以有很好的加速效果。这篇主要就是说明两个在PyPy项目中广泛使用的注解，以改进Python解释器的性能，特别是对象模型的性能。

核心思路就是对于变化非常慢的值（读多写少），使用动态编译可以在运行时观察到的具体值并利用它们。具体地说，如果存在，则可以编译同一代码的多个专用版本，每个实际值对应一个版本。

  • A hint to turn arbitrary variables into constants in the trace byfeeding back runtime information into compilation.
  • A way to annotate operations which the constant folding opti-mization then recognizes and exploits.
  • A worked-out example of a simple object model of a dynamiclanguage and how it can be improved using these hints.
  • This example also exemplifies general techniques for refactor-ing code to expose constant folding opportunities of likely run-time constants.

Hints for Controlling Optimization

本文的核心介绍两种提示（hint），用于加速执行。如果应用得当，这些技术可以通过预计算部分运行时发生的事情来实现真正的加速，否则会陷入slow path，带来更高的成本。

Constant fold

一种是针对变量的promotion行为，用于在范围更广的代码路径上进行常量折叠的优化。

def f1(x, y):
	z = x * 2 + 1
	return z + y

# trace code
"""
v1 = x1 * 2
z1 = v1 + 1
v2 = z1 + y1
return(v2)
"""

如果通过观察发现入参x总是很少变化，我们可以添加一个提示来提升x

def f1(x, y):
	promote({x: 4})
	z = x * 2 + 1
	return z + y

# trace code
"""
guard(x1 == 4)
v1 = x1 * 2
z1 = v1 + 1
v2 = z1 + y1
return(v2)
"""

# optimized code
"""
guard(x1 == 4)
v2 = 9 + y1
return(v2)
"""

这里需要guard的执行代价低于被折叠的算术操作的代价。

Operation Fold

跟Constant Fold类似，Operation同样可以被折叠，这种被称为trace-elidable，如果调用的函数满足trace-elidable（某些paper里也叫elidable function），意味着使用相同参数对函数的连续调用总是返回相同的结果，并且函数功能无副作用或幂等作用。根据此定义，对该函数的调用可以直接替换成调用结果。

举例来讲

class A(object):
  def __init__(self, x, y):
    self.x = x
    self.y = y
  
  def f(self, val):
    promote(self)
    self.y = self.c() + val
    
  @elidable
  def c(self):
    promote(self.x)
    return self.x * 2 + 1

# promotion {self: 0xb73984a8}
"""
guard(a1 == 0xb73984a8)
v1 = A.c(a1)
v2 = v1 + val1
a1.y = v2
"""

# promotion {self: 0xb73984a8, self.x: 4}
"""
guard(a1 == 0xb73984a8)
v2 = 9 + val1
a1.y = v2
"""

首先promote的是self，为了保证函数f中的调用self.c就是下面声明的版本，进而继续假设访问的self.x的值为4，如此就可以将self.c()的函数调用折叠。

Together

Making Instance Attributes Faster

将上述两种优化一起使用时，最直观的好处就是可以加快对于attribute的访问。

class Instance(object):
  def __init__(self, cls):
    self.__class__ = cls
    self.attrs = [ None ] * cls.attr_size()
    for attr_name in cls.attr_names():
      attr_hash = hash(attr_name)
      while True:
      	index = attr_hash % cls.attr_size()
        if self.attrs[index] == None:
          self.attrs[index] = (attr_name, None)
          break
        else:
          attr_hash >>= 1
  
  def get_attr(self, name):
    attr_hash = hash(name)
    while True:
      index = attr_hash % len(self.attrs)
      if self.attrs[index][0] == name:
        return self.attrs[index][1]
      else:
        attr_hash >>= 1

以上述为例，采用dict的方式实现一个Instance，那么对于一个指定的实例，并且self.attrs的容量没有变化的情况下（变化的情况是有额外的，没有在class中声明的属性产生），它的每个属性的在self.attrs中的下标应该是保持不变的。这意味着，如果self相同，可以使用直接的下标来访问属性。

a = inst.get_attr("a")

# trace code: promotion {index_of_a : 0}
"""
guard(inst1 == 0xb73984a8)
a1 = inst1.attrs[0][1]
"""

Versioning of Classes

除了属性意外，我们更希望的是Class.find_method方法是可折叠的。但这不可能，因为更改类本身总是有可能的。每次类更改时，find_method都可能返回一个新值。因此，我们为每个类提供一个Version对象，每当类发生变化（即方法字典变化）时，该对象就会改变。这意味着对于给定的（名称、版本）对，调用Methods.get()的结果总是相同的。

Real-World Considerations

现实世界中，由于Python的object模型要复杂得多，因此需要做一些额外的工作。

需要解决的第一个问题是Python支持(多)继承。因此，在类中查找方法需要考虑整个方法解析顺序中的所有类。这使得类的版本控制更加复杂。如果更改了类，则其版本也会更改。同时，从它继承的所有类的版本也需要递归更改。这使得变更代价高昂，但它们应该是罕见的。另一方面，复杂类层次结构中的方法查找与上面的简单对象模型中一样，可以进行优化。

另一个优化是，在实践中，实例的形状与其类相关。在PyPy的Python解释器中，我们将实例存储在对应的类上，这可以有效减少trace过程中的guard。