問題背景： Python在執(zhí)行的時(shí)候會(huì)加載每一個(gè)模塊的PyCodeObject,其中這個(gè)對(duì)象就包含有opcode,也就是這個(gè)模塊所有的指令集合，具體定義在源碼目錄的 /include/opcode.h 中定義了所有的指令集合，在執(zhí)行的時(shí)候通過加載opcode完成指令的流水線執(zhí)行過程，opcode也就是所有指令集合生成的字符串。執(zhí)行體位于源碼目錄的 /Python/ceavl.c 中PyEval_EvalFrameEx()函數(shù)就是虛擬機(jī)的執(zhí)行體函數(shù)，它會(huì)加載指令集合并完成運(yùn)算。問題描述： 在PyEval_EvalFrameEx()函數(shù)中，同樣是通過標(biāo)準(zhǔn)狀態(tài)機(jī)模型完成的指令解析，一個(gè)巨大無比的switch結(jié)構(gòu)，類似這樣：在C中,switch語(yǔ)句的執(zhí)行是逐條對(duì)比的，也就是說每一條指令在執(zhí)行的時(shí)候都需要從頭對(duì)比，因?yàn)檫@里的指令集合是不平均分布的，但是我們可以假設(shè)每個(gè)指令平均需要匹配n次，n > 1,其實(shí)是遠(yuǎn)遠(yuǎn)大于1的。具體問題： 是否可以做優(yōu)化，為什么作者沒有做優(yōu)化? 如果不采用switch狀態(tài)機(jī)，因?yàn)橹噶畲a也是有編號(hào)的，是否可以直接采用類hashtable的形式來做?
1 回答
慕妹3146593
TA貢獻(xiàn)1820條經(jīng)驗(yàn) 獲得超9個(gè)贊
比較稀疏的switch（指case的值之間相差得比較大）確實(shí)是需要一次次地比較才能選定到底應(yīng)該進(jìn)入哪個(gè)分支。不過CPython的這個(gè)ceval.c里的switch是非常稠密的，case之間的值相差都是1，因此流行的編譯器（gcc/msvc/llvm-clang）都能夠?qū)⑦@個(gè)switch轉(zhuǎn)化為簡(jiǎn)單的indirect branch，比如以x86-64，linux，gas syntax為例：
cmp $MAX_OP, %opcodeja .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];
}所以其實(shí)并不會(huì)像你所說的那樣逐條比較。
Interpreter的優(yōu)化是很有意思的。switch看似高效，但是實(shí)際上由于生成的代碼會(huì)在同一個(gè)地方進(jìn)行所有的indirect branch（分支目標(biāo)可以是任何地方），處理器的分支預(yù)測(cè)就變得毫無用處了。
分支預(yù)測(cè)在CPython這種基于棧的解釋器里非常重要，這是因?yàn)榇蟛糠值腛PCODE都較短，opcode dispatch（也就是分支預(yù)測(cè)）花的時(shí)間經(jīng)常能占到大頭。在大家常用的Sandy Bridge處理器里，分支預(yù)測(cè)失敗相當(dāng)于15個(gè)cycle，而IPC（每cycle能執(zhí)行的CPU指令）在分支預(yù)測(cè)成功的情況下一般能達(dá)到3。相比之下，LOAD_FAST這種小型的OPCODE僅僅只用到了不到10個(gè)CPU指令.. 也就是說，分支預(yù)測(cè)所花的時(shí)間，甚至能占到整個(gè)code運(yùn)行時(shí)間的80%。
因此，CPython使用了另外兩個(gè)優(yōu)化技巧，一是對(duì)常用連續(xù)指令的預(yù)測(cè)，二是如果編譯器支持則使用indirect threading。
連續(xù)指令的預(yù)測(cè)，指的是由于Python中，有很多指令經(jīng)常成對(duì)出現(xiàn)（比如在if x < y then xxx else xxx里會(huì)出現(xiàn)COMPARE_OP -> POP_JUMP_IF_FALSE）。這種情況下，前一個(gè)OPCODE并不需要依靠switch來執(zhí)行后一個(gè)OPCODE，它可以自己跳到后一個(gè)OPCODE上去，需要做的只是檢查一下后一個(gè)OPCODE是不是自己所想要的而已。這里需要添加兩個(gè)分支，但是這兩個(gè)分支一個(gè)是條件判斷，一個(gè)是直接跳過去，所以處理器的分支預(yù)測(cè)可以在這里發(fā)揮作用。在ceval.c里，如果你看到了PREDICT(...)的字樣，那就說明這里有連續(xù)指令的預(yù)測(cè)了。
indirect threading，指的是將indirect branch放在每個(gè)OPCODE處理的結(jié)尾部分。這樣一來，每個(gè)OPCODE就會(huì)獲得處理器針對(duì)自己下一個(gè)指令的分支預(yù)測(cè)。雖然這依然是indirect branch，但是由于每個(gè)OPCODE分開預(yù)測(cè)，這大大提高了預(yù)測(cè)的準(zhǔn)確度。CPython2.7并沒有用到這個(gè)優(yōu)化。CPython3+會(huì)根據(jù)編譯器支持與否，來開關(guān)這個(gè)選項(xiàng)。
CPython的解釋器，經(jīng)過多年的打磨，優(yōu)化那是剛剛的。
添加回答
舉報(bào)
0/150
提交
取消