【Python】Python 字节码优化问题

问题背景:

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

问题描述:

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

【Python】Python 字节码优化问题

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

具体问题:

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

附注:

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

回答

修改方案

做了个测试,基于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+引入了这个优化。详情可以参见他的答案。

比较稀疏的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的解释器,经过多年的打磨,优化那是刚刚的。

以上是 【Python】Python 字节码优化问题 的全部内容, 来源链接: utcz.com/a/80225.html

回到顶部