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。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!