是否可以直接采用类hashtable的形式来做？

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的形式来做?

Answer 1

比较稀疏的switch（指case的值之间相差得比较大）确实是需要一次次地比较才能选定到底应该进入哪个分支。不过CPython的这个ceval.c里的switch是非常稠密的，case之间的值相差都是1，因此流行的编译器（gcc/msvc/llvm-clang）都能够将这个switch转化为简单的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];
}

所以其实并不会像你所说的那样逐条比较。

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