[译文] 使用 PyPy 编写解释器：Part 2

添加 JIT

将 RPython 翻译成 C 当然相当酷，不过 PyPy 还有一个非常棒的功能，即为你的解释器生成 JIT 编译器。没错，通过一些关于你的解释器构成的提示，PyPy 能够生成并包含一个 JIT 编译器，这个 JIT 编译器在运行时，能够将我们的 BF 语言的解释代码翻译成机器指令。

那我们该做些什么让 PyPy 去生成 JIT 编译器呢？首先，它需要知道你的字节码的 evaluation loop 在哪里，它可以据此跟踪正在执行的目标语言（BF）指令。

我们还需要让它知道是什么定义了一个特定的 execution frame。因为我们的语言并没有真正的 stack frame，这可以归结为对于一个特定指令的执行，哪些是常量，而哪些不是。它们分别被称作 “green” 变量以及 “red” 变量。[译注 1]

下面的内容请参考我们的 example2.py 例子。

在我们的主循环里，共使用了 4 个变量：pc, program, bracket_map, tape。当然，pc, program 以及 bracket_map 是 green 变量，它们定义了特定指令的执行。如果 JIT 发现与之前相同的 green 变量组合，它知道自己跳回到了之前的指令，因此一定是在执行一个循环。变量 tape 是我们的 red 变量，它正是我们的指令所操作的数据。

让我们告诉 PyPy 这些信息。导入 JitDriver，并生成一个它的实例：

from pypy.rlib.jit import JitDriver
jitdriver = JitDriver(greens=['pc', 'program', 'bracket_map'], reds=['tape'])

然后在 mainloop 函数的 while 循环的最开头添加如下一行：

jitdriver.jit_merge_point(pc=pc, tape=tape, program=program, bracket_map=bracket_map)

我们还需要定义一个 JitPolicy。看，这就是所有我们需要做的，并不需要什么花哨的东西：

def jitpolicy(driver):
    from pypy.jit.codewriter.policy import JitPolicy
    return JitPolicy()

具体内容参见 example3.py

现在再次生成我们的解释器，不过要加上标志 –opt=jit：[译注 2]

$ python ./pypy/pypy/translator/goal/translate.py --opt=jit example3.py

当打开 JIT 后，翻译过程明显变长，在我的机器上大约需要 8 分钟，并且生成的二进制程序也相当大。现在试着再次运行 mandel.b 程序，你会发现差别很大，这次运行只需要 12 秒，而之前为 45 秒！

非常有趣是吧，通过 mandel.b 例子，你可以看到我们的 JIT 编译器在什么时候从解释代码切换到了机器代码。输出的头几行打印的还算快，不过之后，程序就跟飞起来了一样，打印速度也越来越快。

关于 tracing JIT compiler 的一点

现在是时候去了解一下 tracing JIT compiler 是如何工作的了。这里是一个简要的描述：解释器通常运行的是你所写的解释器代码，当它检测到目标语言（BF）的某个循环代码经常执行，那么这个循环将被认为 “hot”，并且被标记下来做跟踪。当下一次进入该循环时，解释器将进入跟踪模式（tracing mode），每一条执行的指令都会被记录下来。

当循环结束，跟踪也就停止了。对循环的跟踪记录将被送到一个优化器（optimizer），然后是汇编器（assembler），最终生成机器代码。这些机器代码将在随后的循环调用时被执行。

基于对解释器代码的某些假定（assumption），生成的机器代码通常会针对大多数情况进行优化。因此这些机器代码都会包含一些保护（guard），用来验证这些假定。如果某个保护检测失败，那么在运行时解释器将回退到普通的解释代码。

可以从这里了解更多关于 JIT 编译器的详细信息。

调试与跟踪日志

我们还能再做的更好一点吗？怎么才能看到 JIT 在做什么？让我们做两件事情。

首先，让我们添加一个 get_printable_location 函数，它将在调试跟踪日志时用到：

def get_location(pc, program, bracket_map):
    return "%s_%s_%s" % (
        program[:pc], program[pc], program[pc+1:]
    )
jitdriver = JitDriver(greens=['pc', 'program', 'bracket_map'], reds=['tape'],
                      get_printable_location=get_location)

这个函数的参数为那些 green 变量，并且返回一个字符串。在这里我们会打印出 BF 代码，并且将正在执行的指令用 ‘_‘ 包括起来。

下载 example4.py 并按与 example3.py 相同的方式生成解释器。

现在让我们打开跟踪日志来运行一个测试程序（test.b，将在一个循环内打印字母 ‘A’ 15 次）[译注 3]。

$ PYPYLOG=jit-log-opt:logfile ./example4-c test.b

现在再来看一下文件 ‘logfile’。这个文件阅读起来相当困难，这里是我对它最好的解释。

这个文件记录了我们的解释器所有执行过的跟踪过程，我们据此可以窥出有哪些代码是被编译成了机器代码。这些日志在查看还有哪些不必须的指令或空间可以优化时，会非常有用。

每个执行的跟踪都起始于类似如下这样一行：

[3c091099e7a4a7] {jit-log-opt-loop

结束于类似这样一行：

[3c091099eae17d jit-log-opt-loop}

再往下的一行将告诉你它所在的循环号，以及包括了多少个 ops。在我的情况下，第一个跟踪过程看起来如下所示：

[3c167c92b9118f] {jit-log-opt-loop
# Loop 0 : loop with 26 ops
[p0, p1, i2, i3]
debug_merge_point(‘+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.’, 0)
debug_merge_point(‘+<[>[>_+_<-]>.[<+>-]<<-]++++++++++.’, 0)
i4 = getarrayitem_gc(p1, i2, descr=<SignedArrayDescr>)
i6 = int_add(i4, 1)
setarrayitem_gc(p1, i2, i6, descr=<SignedArrayDescr>)
debug_merge_point(‘+<[>[>+_<_-]>.[<+>-]<<-]++++++++++.’, 0)
debug_merge_point(‘+<[>[>+<_-_]>.[<+>-]<<-]++++++++++.’, 0)
i7 = getarrayitem_gc(p1, i3, descr=<SignedArrayDescr>)
i9 = int_sub(i7, 1)
setarrayitem_gc(p1, i3, i9, descr=<SignedArrayDescr>)
debug_merge_point(‘+<[>[>+<-_]_>.[<+>-]<<-]++++++++++.’, 0)
i10 = int_is_true(i9)
guard_true(i10, descr=<Guard2>) [p0]
i14 = call(ConstClass(ll_dict_lookup__dicttablePtr_Signed_Signed), ConstPtr(ptr12), 90, 90, descr=<SignedCallDescr>)
guard_no_exception(, descr=<Guard3>) [i14, p0]
i16 = int_and(i14, -9223372036854775808)
i17 = int_is_true(i16)
guard_false(i17, descr=<Guard4>) [i14, p0]
i19 = call(ConstClass(ll_get_value__dicttablePtr_Signed), ConstPtr(ptr12), i14, descr=<SignedCallDescr>)
guard_no_exception(, descr=<Guard5>) [i19, p0]
i21 = int_add(i19, 1)
i23 = int_lt(i21, 114)
guard_true(i23, descr=<Guard6>) [i21, p0]
guard_value(i21, 86, descr=<Guard7>) [i21, p0]
debug_merge_point(‘+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.’, 0)
jump(p0, p1, i2, i3, descr=<Loop0>)
[3c167c92bc6a15] jit-log-opt-loop}

我将那些 debug_merge_point 行所包含的指令串去掉了一些，实在是太长了。

让我们看看它都做了些什么。这个跟踪过程有 4 个参数：2 个对象指针（p0 与 p1）以及 2 个整数（i2 与 i3）。看看我们添加的那些调试行（debug_merge_point），看起来它正在跟踪循环（[>+<-]）的执行。

它执行的第一个操作是在第四行所示的 ">"，但是紧接着又执行了下一个操作。">" 操作没有指令，并且看起来它被完全优化掉了。这个循环总是在磁带的同一部分上进行操作，磁带指针对这个跟踪过程来说是不变的。因此一个明确的前进操作是不必须的。

第 5 行到第 8 行是针对 "+" 操作的指令。首先它获得由指针 p1 指向的数组里的索引为 i2 的元素（第 6 行），加 1 后将它存入 i6（第 7 行），然后再存回数组（第 8 行）。

第 9 行开始 "<" 操作，但它是另一个 no-op 操作。现在看起来传给这个跟踪过程的 i2 与 i3 似乎是已经计算出的这个循环使用到的两个磁带指针。同样可以推导出来的是 p1 是磁带数组，不过不太清楚 p0 指的是什么。

第 10 到 13 行执行的是 "-" 操作：获取数组元素值（第 11 行），减 1（第 12 行），并将该值存回数组（第 13 行）。

接下来在第 14 行是 "]" 操作。第 15 到 16 行检测 i9 是否是 true（non-zero）。看，i9 是我们刚刚执行减法操作并存回到数组的值，现在被用作检测循环条件，这正如我们希望的那样（回忆一下 "]" 的定义）。第 16 行是一个保护检测，如果条件不满足，执行将跳到另外某个地方，在这里将跳到名为 <Guard2> 的过程，并且传递一个参数：p0。

假设我们通过了这个保护，第 17 到 23 行是对 bracket_map 进行字典查找操作，找到我们应该跳向的程序计数器（pc）。我不太清楚这些指令是在做什么，不过看起来有两个外部调用，以及 3 个保护。这些看起来相当昂贵，特别是我们知道 bracket_map 永远也不会变化（而 PyPy 并不知道）。待会儿你将看到我们如何来优化它。

第 24 行是对新获取到的指令指针加 1。第 25，26 行确保它不会超过程序的长度。

此外，第 27 行保护 i21，也就是刚刚递增的指令指针为 86。这是因为它将要跳回到开始（第 29 行），而指令指针为 86 是前提条件。

最后，循环结束于第 28 行，因此 JIT 可以跳到循环体 <Loop0> 去处理该情况（第 29 行），也就是又一次到循环的开头。它传递的参数是（p0, p1, i2, i3）。

优化

之前提到过，每一个循环执行都会做一个字典查找操作，找出匹配的中括号，以准备跳转。这是极其低效的，因为跳转的目标从这次执行到下次是不变的。这些信息是固定的，应该也被编译成机器代码。

问题在于查找操作针对的类型是字典，并且 PyPy 将它看作是不透明的。它并不知道这个字典不会被修改，或每次查询都会返回相同的东西。

我们需要做的是对翻译过程提供另一个提示，告诉它字典查找只是一个 pure function，也就是说，它的输出只依赖于它的输入，并且相同的输入总是会返回相同的输出。

我们要做的是，将字典查找操作包进一个函数里，并且用一个 PyPy 提供的 decorator （pypy.rlib.jit.purefunctioin）来修饰该函数：

@purefunction
def get_matching_bracket(bracket_map, pc):
    return bracket_map[pc]

这个版本参见 example5.py。

再次用相同的方法生成解释器，并观察运行速度。运行 mandel.b 现在只需 6 秒！（优化之前需 12 秒）

让我们看一下跟踪日志：

[3c29fad7b792b0] {jit-log-opt-loop
# Loop 0 : loop with 15 ops
[p0, p1, i2, i3]
debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0)
debug_merge_point('+<[>[>_+_<-]>.[<+>-]<<-]++++++++++.', 0)
i4 = getarrayitem_gc(p1, i2, descr=<SignedArrayDescr>)
i6 = int_add(i4, 1)
setarrayitem_gc(p1, i2, i6, descr=<SignedArrayDescr>)
debug_merge_point('+<[>[>+_<_-]>.[<+>-]<<-]++++++++++.', 0)
debug_merge_point('+<[>[>+<_-_]>.[<+>-]<<-]++++++++++.', 0)
i7 = getarrayitem_gc(p1, i3, descr=<SignedArrayDescr>)
i9 = int_sub(i7, 1)
setarrayitem_gc(p1, i3, i9, descr=<SignedArrayDescr>)
debug_merge_point('+<[>[>+<-_]_>.[<+>-]<<-]++++++++++.', 0)
i10 = int_is_true(i9)
guard_true(i10, descr=<Guard2>) [p0]
debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0)
jump(p0, p1, i2, i3, descr=<Loop0>)
[3c29fad7ba32ec] jit-log-opt-loop}

不错！每个循环处理只是加，减，两次数组元素加载和存储，以及一个对退出条件的保护。这就是了，这个代码不再需要任何程序计数器的操作。

我不是优化方面的专家，这个提示也是由 Armin Rigo 在 pypy-dev 邮件列表上建议的。Carl Friedrich 有一系列关于如何优化解释器的很好的阐述，非常有帮助。

最后

我希望这个教程能够展示给你们：PyPy 除了是一个快速的 Python 实现以外，还能做些什么。

对于那些希望了解更多关于这个过程是如何工作的同学，这里是我推荐的一些学术论文，它们对这个过程有更深入的讲解。特别是：Tracing the Meta-Level: PyPy's Tracing JIT Compiler。参见：http://readthedocs.org/docs/pypy/en/latest/extradoc.html。

译注

【1】关于 green 变量与 red 变量，这个文档有进一步的解释，该文档解释 green 变量为 循环常量（loop constants），他们用来识别当前的循环；red 变量则是当前循环里用到的所有其它变量。

【2】在 Linux 下，PyPy 似乎需要 libffi.a（而不是 libffi.so）来生成带有 JIT 的解释器。在我的 Fedora 15 系统里，libffi-devel 包并不包含该静态库，需要手动编译 libffi 的源代码包。Ubuntu 11.04 不存在该问题。

【3】原文以及 bitbucket 上并没有给出 test.b 的源程序，下面是我根据跟踪日志里的调试语句，整理的一个 test.b 程序，运行它的结果与作者给出的日志内容基本是相同的，除了个别数字以外（不影响作者在这里的分析）。

++++++++[>++++++++>++++++++<<-]>>+<[>[>+<-]>.[<+>-]<<-]++++++++++.

参考

[译文] 使用 PyPy 编写解释器：Part 1