Python 字节码优化问题

Question

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

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

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

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

附注： 如果此问题很2请亲提出宝贵的意见

Answer 1

修改方案

做了个测试，基于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[i]] = label_list[i];
    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 <= 2 else fib(n - 2) + fib(n - 1)
print fib(37)

修改前 [6.227, 6.232, 6.311, 6.241]，去掉最大的一次，平均6.233s

修改后 [5.962, 5.945, 6.005, 6.037]，去掉最大的一次，平均5.971s

性能提升 (100% - (5.971 / 6.233)) = 4.20%

结论

综合看来，这个小小的改动，的确可以提高5%左右的性能，不知道对各位而言意义有多大……

不过因为用到了只有GCC支持的、非C标准的特性，所以不方便移植。根据StackOverflow的这个帖子，MSVC可以在一定程度上支持，但是貌似很tricky。不知道这个在Python的发展历程中是否有人做过这样的尝试，也许官方会偏好可移植性？也许抽空可以发个帖子去问问。 根据 @方泽图 的说法（见他答案里的评论），Python 3.0+引入了这个优化。详情可以参见他的答案。

Answer 2

比较稀疏的switch（指case的值之间相差得比较大）确实是需要一次次地比较才能选定到底应该进入哪个分支。不过CPython的这个ceval.c里的switch是非常稠密的，case之间的值相差都是1，因此流行的编译器（gcc/msvc/llvm-clang）都能够将这个switch转化为简单的indirect branch，比如以x86-64，linux，gas syntax为例：

cmp $MAX_OP, %opcode
ja .handle_max_op
jmp *.op_dispatch_table(,%opcode,8)

翻译成C的话，大致意思是这样：

static void *op_dispatch_table[] = {
    &&handle_NOP,
    &&handle_LOAD_FAST,
    // etc etc...
};

if (opcode > 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的解释器，经过多年的打磨，优化那是刚刚的。