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

标签: pypy 解释器 part | 发表时间:2011-08-09 14:43 | 作者:(author unknown) chuang
分享到:
出处:http://simple-is-better.com/

[译者前言]:本系列译文译自 PyPy Status Blog 刊登的 Writing an Interpreter with PyPy 系列文章,原文作者为 Andrew Brown,该系列文章的版权属于原文作者所有,在此向 Andrew Brown 以及 PyPy Status Blog 表示致谢。本文译自该系列的第二篇:Writing an Interpreter with PyPy, Part 2: Adding a JIT.

添加 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

# 来源:开源小厨


在微博上关注: 新浪, 腾讯   投稿

最新招聘

更多>>

相关 [pypy 解释器 part] 推荐:

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

- chuang - python.cn(jobs, news)
[译者前言]:本系列译文译自 PyPy Status Blog 刊登的 Writing an Interpreter with PyPy 系列文章,原文作者为 Andrew Brown,该系列文章的版权属于原文作者所有,在此向 Andrew Brown 以及 PyPy Status Blog 表示致谢.

HDR 摄影作品欣赏 Part 2

- Ian - Poboo
继续欣赏HDR摄影作品,喜欢的朋友可以欣赏第一部分.

HDR 摄影作品欣赏 Part 1

- 月七 - Poboo
分享一些搞清的 HDR 摄影作品,都是很棒的作品希望大家喜欢,由于照片比较多,这是第一部分 我们会明天分享第二部分. HDR 摄影作品欣赏 Part 2. Matthias Haker 摄影作品. Felicia Simion 摄影作品. Renaud Marion 摄影作品. 玩摄影的人你伤不起,贱友们找亮点.

WebGL 框架 API 横向评测 (Part 1)

- - HiWebGLHiWebGL
对于互联网来说,除了HTML5和CSS3之外,WebGL也是一项最有前途的正在进化的技术之一. 从简单的模型查看器到复杂的3D场景,由OpenGL ES驱动的网页结合CSS3和视频纹理也许会成为下一代互联网网页的主流. 由于应用广泛,富WebGL应用程序必须易于搭建和渲染,缩短响应时间,提供更好的可扩展性.

解释器Interpreter

- - 企业架构 - ITeye博客
所谓解释器模式就是定义一个语言的文法,并建立一个解释器来解释该语言中的句子. 比如:taglib标签,正则表达式都是采用的解释器. 解释器不仅仅只定义一种语法语义,更可以使用一个抽象语法树定义一个语言实例.     AbstractExpression: 抽象表达式. 声明一个抽象的解释操作,该接口为抽象语法树中所有的节点共享.

[Mac OS X] 大獅子的小發現 -- Part 2

- RaRo - appleseed, 蘋果核
上篇寫了一些新Lion的小發現,寫好之後才發現還有幾個漏網之魚沒放進去,所以現在再來寫篇衝一下發文數好了. 這個放大鏡功能很像Aperture的Loop,按一下「`」就會出現. 圖片的放大鏡是圓形的,放大鏡出現時,雙指縮放可以放大放大鏡的視野. 文件也可以叫出放大鏡,不過是方形的. 當文件或是圖片本身太大需要捲動時,雙指捲動可以捲動文件而放大鏡會乖乖的待在原地,很貼心.

【转贴备忘】[教程]iPhone 實機開發 Part 1 - HelloWorld

- zii - 博客园-oiramario
最近小弟開始在研究 iPhone 的開發,無奈找到的資料都是舊的,也不知道怎麼放到 iPhone 上,應該很多人都跟我有同樣的困擾吧!經過幾天的研究總算寫出第一個 HelloWorld,而且可以不用付99元美金就可以放到實機上執行. 今天先和大家分享怎麼放到手機上,以及基本的 Xcode 使用:. iPhone 港版16G+FW2.2+越獄.

在 SBCL 等开源 Lisp 平台上运行 CL-HTTP (part 1)

- 旺旺 - Chun Tian (binghe)
现在我来说明在 4 种开源 Common Lisp 平台上运行 CL-HTTP 的方法,四种平台分别是 SBCL、Clozure CL、CMUCL 和 Macintosh Common Lisp (MCL). 我相信我所提供的这些信息对某些 Common Lisp 爱好者来说将是梦寐以求的. 过去我也曾在博客里多次提到 CL-HTTP,多年来也一直在实际地学习和使用这个软件.

史上最全的苹果广告歌 Part II(2008年至今)

- 白肥 - 虾米音乐每日精选
2010/11 的The Beatles on iTunes Ads收录多首披头士经典歌曲,在此不一一列出. 2011.3更新虾米有的和没有的各两首. 两首有的:23 The Christmas Song -- Nat &quot;King&quot; Cole The Christmas Song.

能把牙膏挤得一点不剩的牙刷 Part 2

- maibaobei.2008 - 爱…稀奇~{新鲜:科技:创意:有趣}
还记得韩国设计师Jee Young Choi带来的那款能把牙膏挤得一点不剩的牙刷吗. 现在,设计师Catherine Werdel带来了另外一款类似的设计——看看谁更牛X一点呢:. 几乎用不了多少观察力就能发现二者之间的相同与不同,相同的是二者都在牙刷柄上开了条缝,然后用这缝穿过牙膏管的尾部就能把牙膏挤出来,不同的则是缝的位置,韩国设计师的作品将缝放在了尾部,而Werdel则将缝放在了中间——孰优孰劣.