AOT 和 JIT

一个程序的编译过程可以是步骤迭代式的，即每一轮步骤结束后得到的结果都可独立运行，比如，先构造AST再输出字节码，中间状态AST也是可以解释执行的。由于编译的本质就是代码转换，因此对一个语言可以有多个独立的编译器，每个负责一轮步骤

AOT Compiler和JIT Compiler就是针对编译形式做的分类： 
AOT：Ahead Of Time，指在运行前编译，比如普通的静态编译 
JIT：Just In Time，指在运行时编译，边运行边编译，比如java虚拟机在运行时就用到JIT技术

JIT可能知道的人多些，AOT这个名词就相对少见一些了，其实除了JIT，剩下的都是AOT。wiki上JIT的解释也比AOT详尽很多，如果按wiki上的理解，一般来说，是从形式上来区分这两个概念，即看编译是不是在“运行时”进行

然而，这两个概念又有模糊性，问题在于这个“运行时”怎么来区分，比方说，从这个概念来看，python是用到JIT技术的，因为：

...   
import a   
...

当执行到import a的时候，当然是运行时，这时候如果只找到了a.py，则会进行编译工作，并生成a.pyc，这就是python的JIT特性，但是一般来说，认为python的JIT是psyco、pypy之类，并不认为python本身的动态性属于JIT范畴，或者说，它的这种“形式上”的JIT特性不纳入讨论范围。其他脚本语言，动态语言也有类似的情况。具体原因我觉得有几点 首先被主流理论认定的JIT编译器对于被其编译的语言来说属于附加品，也就是说，就算去掉JIT，并不影响语言本身的运行，例如java，如果关闭JIT，依然可以解释执行，而上述python的运行时import的特性虽然形式上符合JIT，但这个机制是语言本身规定的，如果去掉，语言（的主流实现）就不完整了。反过来说，如果python采用源码直接解析执行，则编译为字节码的行为就可以看做是JIT，因为做不做都不影响解析执行过程 其次，python的这种编译并非每次执行都会进行，因为一般来说会生成字节码结果pyc文件存在磁盘，它更像是对java源代码转class文件这一过程的惰性化，在需要的时候进行 最后，JIT会消耗运行时资源，可能导致进程卡顿，而java等语言之所以引入JIT，是因为JIT对字节码编译后能以更快的速度运行，卡顿的时间能补救回来，因此从工程角度讲，JIT几乎就等于是运行时优化（虽然从概念和形式上并非如此），而python的import就只有卡顿，对速度没啥好处 于是，虽然从概念来说，上面的例子的确符合JIT，但一般来说也不这么认为，出发角度问题，说python自带JIT特性或没有JIT都算说得通的

之所以先举这个例子，因为我觉得能体现AOT和JIT概念的对立和统一，对立是形式上的，以“运行”为分界线，而统一则是说，其实所有需要执行的指令序列，都是需要先编译再执行的，比如import a，这个相对于整个进程当然是JIT，但相对于a.py这个模块（python进程首次import某个模块时会执行它）不妨看做AOT，如果有人觉得这么做不妥，那换个更明显的例子，如果一个python程序的所有import都在进程开启时立即运行，然后才进入执行，那按照概念来说，这是JIT，因为进程已经开始运行了，但是，为什么不能看做是先编译再执行的AOT模式，只是整个过程被批处理化了呢？

带着这个问题再考虑很多资料（包括wiki）对JIT的另一个描述，JIT是在运行时将解释执行的语言（比如字节码）编译成机器指令，以提高运行速度。这个看法在前面的某篇也提过，的确很多JIT编译器，比如java的就是这么干的（我们下面就拿java举例），但是，既然字节码编译成机器指令可以提高速度，为何一定要放在运行时进行，做成AOT模式不是可以运行得更流畅吗，而且还能一次编译，N次执行，为啥非要做成运行时做，JIT本来是要提高运行速度，但这岂不是降低了效率？

这种看法是有道理的，事实上，java的确有一些AOT编译器，可以将字节码甚至java源码直接编译成机器指令的可执行文件，微软当初的VJ++似乎就这么搞的，和sun打了很久的架，sun还喊出了pure java（纯粹的java，即按照sun的设计理念和标准来实现java）的口号，有兴趣可以去搜一下这段历史，挺搞笑的

另一方面，sun的jvm虽然采用了JIT编译，但同时也提供了client和server模式，在server模式下，虚拟机在一开始执行的时候会先尽可能多地对字节码进行编译，且优化程度也尽量高，这样可以使得服务器在运行过程中能尽量少卡顿，根据上面的讨论，这实际上相当于AOT批处理了。client模式下则不会这样做，主要是为了尽量缩短启动延迟，提高用户体验

顺便说一句，对于JIT将字节码编译成机器指令，wiki的描述比较暧昧，有时候用machine code，有时候用native code，比方说我们用java实现一个A语言的虚拟机，解释A的字节码执行，并将字节码编译成java自己的字节码，这也是JIT，因为A跑在jvm上，则java字节码就看做是native code，而machine code这个machine也不见得是真实机器，jvm也是一种机器

由于JIT编译耗费运行时间，则对于某些优化点就无法做到百分百支持，必须在代码优化和执行卡顿之间做一个权衡，AOT就没有这个问题，另外，AOT可以做到编译后持久化到存储，而JIT一般是每运行一次就会搞一遍重复的编译

如果我们不考虑AOT本身耗费的时间（比如编译一次，N次运行），也不考虑使用上的方便性（AOT可能会有多次编译过程），那是不是可以认为，AOT编译可以完全替换JIT编译，JIT就完全没必要了，实际情况当然不是这样，JIT还是有它的优势和必要性的，否则研究它的那群人岂不都是傻子

从动静态来看这个问题，AOT是静态编译，而JIT是运行时动态编译，则JIT的优势在于，它不但能看到静态信息（代码），还能看到运行时的情况，这就是JIT的优势。接下来讨论的JIT是一种狭义的JIT，即在AOT搞不定的地方使用的JIT，而非上述形式上的

关于JIT的优势，wiki上给出了四点理由，但有意思的是，其中有两条连它自己都承认并非只有JIT能做，也就是说至少理论上，用AOT实现（或部分实现）是可行的，这四条是： 一、JIT可以根据当前的硬件情况实时编译成最优机器指令，比如cpu中如果含FPU，MMX，SSE2，或者Intel cpu的并行计算特性，则可以做到同一份字节码，在不同机器运行时最大限度利用硬件资源。而如果是AOT编译一个程序放出去给不同用户使用，就只能去兼容特性最少的cpu，或者内部实现多个版本 二、JIT可以根据当前进程实际运行状态，将字节码编译成适合最优化的机器指令序列。wiki认为静态编译也可以通过分析profile来实现这方面的优化（可能有点麻烦） 三、当程序需要支持动态链接时，即在静态编译阶段，可能不知道运行时会引入什么样的代码来和程序协作执行，这时候就只能依靠JIT 四、考虑到垃圾收集，JIT可以根据进程中的内存实际情况来调整代码，使得cache能更充分地使用，wiki认为静态编译也可以做到，但JIT做起来更容易实现

对于第一条，JIT的确可以实现这种优化，但是AOT一样可以实现，虽然AOT编译一个程序给不同用户执行无法做到，但是可以编译字节码发布，用户使用时再根据当前机器再做一次AOT 对于第二条，首先我认为大多数程序的运行状态不会经常变动，比如同一个程序有时候是整数计算居多，有时候是浮点计算居多，一般来说程序应用场景是固定的；其次对于特定场景也可以AOT 对于第三条，的确动态链接的全文静态优化AOT无法做到，但是如上篇所说，必要时候我们可以直接砍掉语言的动态性，再者静态编译时候也不是什么都感知不到，比如C语言做静态链接时，至少是知道头文件的，动态性没那么强 对于第四条，AOT也是有可能实现的，虽然麻烦很多。另一方面，静态编译时也有指令乱序来提高cache使用效果，再者这块也和垃圾收集算法、程序本身的局部性有很大关系，如果程序本身写的烂，这个调整效果可能也比较有限

所以我觉得，这四条虽然都有道理，但没精确说到点子上。再来审视这个问题，我们可以看出，从理论上讲，AOT可以完全代替JIT，因为一个进程的状态是有限的，AOT可以预测所有可能情况并进行优化，实际运行时的状态不会超出AOT的预测，采用最优代码执行即可，而JIT在这里的优势就是，它能精准地得知运行时状态，而不是像AOT那样预测，成本更低，如果一个AOT优化的成本过高，则应该选择JIT。AOT不是不能做，而是不可行

JIT相关的资料，相比wiki我更推荐这篇论文：《Representation-based Just-in-time Specialization and the Psyco prototype for Python》 by Armin Rigo，这个论文是以python和其JIT插件库psyco为例来分析，论文题目中的单词Specialization可谓画龙点睛，它指出至少在动态类型语言中，JIT的关键作用之一是特化，用上篇的话说，就是动态行为静态化，而这些场景中AOT不可行的原因是它很难找到特化的方向，而枚举所有特化是不可行的

一个典型的特化案例，也是论文中提到的，假设有一个函数f(x,y)，则对于x的输入x1,x2,x3...，我们可以特化这个函数为f1(y),f2(y),f3(y)...，其中fk(y)在功能上对应f(xk,y)，这样一来，每个fk可以单独地做优化，与其他函数无关，而特化后的函数列表至少不会比原来的f(x,y)慢。唯一的问题是，x的取值可能很多，比如x是一个int，则如果采用AOT方式来特化，则需要编译42亿多个函数，这显然是不现实的，但是JIT就有可能对这个场景做优化，原因在于，x的取值虽然很多，但在一个具体运行过程中范围相对小，甚至是很小，这符合二八定律

于是，在运行时我们可以对函数f做监控，统计每次输入的x的值，如果发现这些值的分布不平均，比如x为123的情况占大多数，则动态特化一个f123(y)，对其进行高度优化，然后修改f函数为：

func f(x, y):   
    if x == 123:   
        return f123(y)   
    ... //f的正常流程

于是只需要一个特化函数，就能带来运行时效率的提升，这就是JIT特化的优势

对很多程序来说，对这种数值做监控和特化可能性价比不高，因为不是每个函数的输入值范围都呈现不平衡状态，或者说不是那么明显，但上面这个例子中，x和y不一定是变量，也可以是类型，这样一来对动态类型语言就有很大的意义

前面讲过，在C++中可以用模板来实现鸭子类型，实质是通过代码替换来实现类型静态化，C++这个方式虽然效率高，但渠道是通过静态编译中的全文分析，是AOT编译，如果改成稍微动态性强一些的语言，就用不上了。在动态类型中，一个函数如果有k个参数，有n个可能类型，则AOT需要将一个函数扩展为n^k个特化实例，n和k稍大一点就不可操作了，何况本身就是动态类型，n的范围都不一定在编译期能知道

对这种场景，JIT就可以通过统计的方式来选择性地特化，这个的可行性和现实意义更大，原因在于，程序员在用动态类型写程序的时候，比如写一个函数：

func f(x, y):   
    return x + y

理论上，这个函数可以接受任意类型的x和y，只要x能和y相加即可，但具体到一个确定的程序，这个函数的业务意义一般是固定的，或者是做字符串拼接，或者是数值相加，很少说写一个函数，接收八竿子打不着的不同的类型还能运算，而且还是程序员刻意这么设计，就像前面讲过的C++模板的二义性一样，基本见不到这种需求，所以在函数的输入参数类型上，符合二八定律。于是对于上述代码，假设x和y绝大多数情况下都是整数，则进行特化（假设这个伪代码中不考虑整数溢出）：

func f(x, y):   
    if not (x instanceof int and y instanceof int):   
        //有一个不是整数，走原有流程   
        return x + y   
    //整数加法的特化流程   
    internal_code:   
        int ix = get_internal_int(x)   
        int iy = get_internal_int(y)   
        int iresult   
        asm:   
            push ... //当前状态压栈   
            mov eax, ix   
            mov ebx, iy   
            add eax, ebx   
            mov iresult, eax   
            pop ... //状态出栈   
        return build_int_object(iresult)

当然这只是个例子，如果只是为了一个加法，这多少有点小题大做，但如果f的逻辑较为复杂，优化就很明显了

还可以逆向思维一下，AOT难以实现特化的原因是无法考虑所有情况，但我们也没有必要考虑所有情况，实际上类型使用的二八定律本身也在另一个二八定律里，具体到int类型，一个绝大多数使用到的类型都是int的程序在所有程序中占绝大多数，至少在一个有限的领域是这样，因此干脆对于每个函数都只做int相关的特化，这样2^k种情况还算能接受（实际情况数比2^k低很多，因为很多参数如果被假定为int，会语法错误，就不用假设了），如果再做的好一点，还可以做成编译器选项，由用户来指定AOT的时候对哪个类型特化，这样就比较完美了

除类型的动态性外，其他动态性也可以类似讨论，仅拿上篇的例子，不赘述了：

for i in range(n):   
    print(i)   
转换为： 
[plain] view plaincopy
if not (range is builtins.range and print is builtins.print):   
    for i in range(n):   
        print(i)   
else:   
    internal_code:   
        long tmp = get_internal_long(n)   
        long i   
        //这里应该用汇编，仅表个意思   
        for (i = 0; i < tmp; ++ i):   
            print_long(i)

需要在程序启动时在builtins里面保存默认函数，用于检测当前运行环境是否被用户修改过，这样就兼顾了效率和动态性，跟上面一样，这里JIT或AOT实现都可以