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的解釋器，經過多年的打磨，優化那是剛剛的。