是否可以直接采用类hashtable的形式来做?

问题背景: Python在执行的时候会加载每一个模块的PyCodeObject,其中这个对象就包含有opcode,也就是这个模块所有的指令集合,具体定义在源码目录的 /include/opcode.h 中定义了所有的指令集合,在执行的时候通过加载opcode完成指令的流水线执行过程,opcode也就是所有指令集合生成的字符串。执行体位于源码目录的 /Python/ceavl.c 中PyEval_EvalFrameEx()函数就是虚拟机的执行体函数,它会加载指令集合并完成运算。

问题描述: 在PyEval_EvalFrameEx()函数中,同样是通过标准状态机模型完成的指令解析,一个巨大无比的switch结构,类似这样:

http://img2.mukewang.com/64520c72000124e513500708.jpg

在C中,switch语句的执行是逐条对比的,也就是说每一条指令在执行的时候都需要从头对比,因为这里的指令集合是不平均分布的,但是我们可以假设每个指令平均需要匹配n次,n > 1,其实是远远大于1的。

具体问题: 是否可以做优化,为什么作者没有做优化? 如果不采用switch状态机,因为指令码也是有编号的,是否可以直接采用类hashtable的形式来做?


九州编程
浏览 87回答 1
1回答

慕妹3146593

比较稀疏的switch(指case的值之间相差得比较大)确实是需要一次次地比较才能选定到底应该进入哪个分支。不过CPython的这个ceval.c里的switch是非常稠密的,case之间的值相差都是1,因此流行的编译器(gcc/msvc/llvm-clang)都能够将这个switch转化为简单的indirect branch,比如以x86-64,linux,gas syntax为例:cmp&nbsp;$MAX_OP,&nbsp;%opcodeja&nbsp;.handle_max_op jmp&nbsp;*.op_dispatch_table(,%opcode,8)翻译成C的话,大致意思是这样:static&nbsp;void&nbsp;*op_dispatch_table[]&nbsp;=&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&&handle_NOP, &nbsp;&nbsp;&nbsp;&nbsp;&&handle_LOAD_FAST,&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;etc&nbsp;etc...};if&nbsp;(opcode&nbsp;>&nbsp;MAX_OP)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;goto&nbsp;*handle_max_op; }else&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;goto&nbsp;*op_dispatch_table[opcode]; }所以其实并不会像你所说的那样逐条比较。Interpreter的优化是很有意思的。switch看似高效,但是实际上由于生成的代码会在同一个地方进行所有的indirect branch(分支目标可以是任何地方),处理器的分支预测就变得毫无用处了。分支预测在CPython这种基于栈的解释器里非常重要,这是因为大部分的OPCODE都较短,opcode dispatch(也就是分支预测)花的时间经常能占到大头。在大家常用的Sandy Bridge处理器里,分支预测失败相当于15个cycle,而IPC(每cycle能执行的CPU指令)在分支预测成功的情况下一般能达到3。相比之下,LOAD_FAST这种小型的OPCODE仅仅只用到了不到10个CPU指令.. 也就是说,分支预测所花的时间,甚至能占到整个code运行时间的80%。因此,CPython使用了另外两个优化技巧,一是对常用连续指令的预测,二是如果编译器支持则使用indirect threading。连续指令的预测,指的是由于Python中,有很多指令经常成对出现(比如在if x < y then xxx else xxx里会出现COMPARE_OP -> POP_JUMP_IF_FALSE)。这种情况下,前一个OPCODE并不需要依靠switch来执行后一个OPCODE,它可以自己跳到后一个OPCODE上去,需要做的只是检查一下后一个OPCODE是不是自己所想要的而已。这里需要添加两个分支,但是这两个分支一个是条件判断,一个是直接跳过去,所以处理器的分支预测可以在这里发挥作用。在ceval.c里,如果你看到了PREDICT(...)的字样,那就说明这里有连续指令的预测了。indirect threading,指的是将indirect branch放在每个OPCODE处理的结尾部分。这样一来,每个OPCODE就会获得处理器针对自己下一个指令的分支预测。虽然这依然是indirect branch,但是由于每个OPCODE分开预测,这大大提高了预测的准确度。CPython2.7并没有用到这个优化。CPython3+会根据编译器支持与否,来开关这个选项。CPython的解释器,经过多年的打磨,优化那是刚刚的。
打开App,查看更多内容
随时随地看视频慕课网APP

相关分类

Python