[QA]Python字节码优化问题

jsnjzlw

　　这篇文章来自在Segmentfault 上面我提出的一个问题
　　问题背景： Python在执行的时候会加载每一个模块的PyCodeObject,其中这个对象就包含有opcode,也就是这个模块所有的指令集合，具体定义在源码目录的 /include/opcode.h 中定义了所有的指令集合，在执行的时候通过加载opcode完成指令的流水线执行过程，opcode也就是所有指令集合生成的字符串。执行体位于源码目录的 /Python/ceavl.c 中PyEval_EvalFrameEx()函数就是虚拟机的执行体函数，它会加载指令集合并完成运算。
　　问题描述： 在PyEval_EvalFrameEx()函数中，同样是通过标准状态机模型完成的指令解析，一个巨大无比的switch结构，类似这样：

　　在C中,switch语句的执行是逐条对比的，也就是说每一条指令在执行的时候都需要从头对比，因为这里的指令集合是不平均分布的，但是我们可以假设每个指令平均需要匹配n次，n > 1,其实是远远大于1的。
　　具体问题： 是否可以做优化，为什么作者没有做优化? 如果不采用switch状态机，因为指令码也是有编号的，是否可以直接采用类hashtable的形式来做?
　　@felix021 回答了这个问题：



修改方案
做了个测试，基于python 2.7.3，把PyEval_EvalFrameEx这个函数里的case都改成了label，然后利用gcc的labels as values特性，将里面用到的118个opcode与对应的label构成数组：
static void *label_hash[256] = {NULL};
static int initialized = 0;
if (!initialized)
{   
#include "opcodes.c"
#include "labels.c"
int i, n_opcode = sizeof(opcode_list) / sizeof(*opcode_list);
for (i = 0; i < n_opcode; i++)
label_hash[opcode_list] = label_list;
initialized = 1;
}
然后把 switch (opcodes) 改成
void *label = label_hash[opcode];
if (label == NULL)
goto default_opcode;
goto *label;
并逐个替换每个case里的break。
编译后通过了所有的测试（除了test_gdb，这个跟未修改版一样，都是没有sys.pydebug），也就是说这个修改是正确的。
性能测试
接下来的问题是性能……这个该怎么测试呢……没有好的想法，所以随便找了两段代码：
直接loop 5kw次：
i = 50000000
while i > 0:
i -= 1
修改前运行4次：[4.858, 4.851, 4.877, 4.850]，去掉最大的一次，平均4.853s
修改后运行4次：[4.558, 4.546, 4.550, 4.560]，去掉最大的一次，平均4.551s
性能提升 (100% - (4.551 / 4.853)) = 6.22%
递归Fibonacci，计算第38个
def fib(n):
return n if n  MAX_OP) {
goto *handle_max_op;
}
else {
goto *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的解释器，经过多年的打磨，优化那是刚刚的。

　　后来据 方说，Python3.3+以后的确是用到了labelHash来优化，需要根据不同的编译环境来做。