解释器的效率

上学时候似乎一直在词法分析和语法分析阶段徘徊,好像编译器的大头是Parsing似的,其实无关紧要,大多数时候手写递归下降就够了。AST之后的部分才是核心,代码生成还算了解,代码优化就没怎么看过了。前几天重看了一遍wingolog的博客,又看了一些解释器优化的资料,才后知后觉的发现一些其实比较浅显的东西。

解释器效率低下的主要原因是,除了执行指令本身的“有效工作”以外,有很多不能省去的“额外开销”。比如解释“result=op1+op2”,除了加载操作数,执行加法以外,其余都是额外开销。如果是直接解释AST,额外开销就是visit各种节点。如block节点,仅表示一个作用域,并不做任何实际工作,另外,遍历语法树时虚函数调用的开销也很大。如果是生成IR,那么执行IR的loop就必须非常高效。这个loop主要工作就是维护一个PC(program counter),执行指令,然后将PC指向下一条执行,跳转并执行。看似直接的过程,因为这是整个解释器的核心,“额外开销”在这个loop占的比例将极大的影响解释器的执行效率,所以需要(a)保证这个主循环所有关键变量都使用寄存器,需要(b)避免pc修改后,执行indirect branches,因为CPU执行这类jmp开销很大,很难进行分支预测,另外(c)主循环的代码要能放得进CPU的指令CacheLine中(似乎是64k吧)。如果指令集很大,通常会实现成一个大的switch语句,编译器并不善于优化这类代码,通过gcc的Labels-As-Values扩展可以避免(b),但是对于(a)(c)处理并不好,所以很多编译器如LuaJIT2就是手写汇编,缺点是每个平台都得写一遍。

上面说的是解释器,效率的核心点是降低“额外开销占比”,优化手段是充分利用寄存器、CPU的分支预测和指令Cache。要想彻底消除这些“额外开销”,就需要进行JIT了。当然中间还有一步是代码优化,还在看,先不写了。