目录
在大数据系统的查询引擎这一分类中，我们追求的往往是更大的数据量、更快的运行效率。在业界的各大计算引擎设计实现，往往会出现两大类型的执行优化方案：
执行计划优化：执行计划优化的目标是通过多种规则选择最优的执行路径。其中执行计划优化又可细分为基于规则的优化和基于代价的优化。
运行时优化：运行时优化的目标是基于已确定的执行路径，尽可能的提高执行时效率。运行时优化又可细分为以下两种：
全局优化：从提升全局资源利用率、消除数据倾斜、降低IO等角度做优化，包括自适应执行(Adaptive Execution), Shuffle Removal等。
局部优化：优化具体的计算任务的执行效率，包括代码生成、线程时钟设置等等。
本文主要针对运行时优化，也成为Runtime优化中的代码生成技术进行介绍，包括相关背景、优化原理、使用工具类以及开源系统中实现方案的简析。
Java虚拟机是整个Java平台的基石，是Java技术用以实现硬件无关、操作系统无关的关键部分，是Java语言生出极小体积的编译代码的运行平台，是保障用户机器免于恶意代码损害的屏障。
Java虚拟机与Java语言并没有必然的联系，它只与特定的二进制文件格式--class文件格式所关联。
本章仅重点针对Java虚拟机中的字节码指令进行简要的介绍，它是代码生成优化中的关键影响因素。
Java虚拟机可操作性的数据类型可分为原始类型和引用类型，对应的值也分为原始值和引用值，它们可用于变量赋值、参数传递、方法返回和运算操作。编译器在生产class文件将会尽最大努力完成可能的类型检查，使得虚拟机在运行期间无需进行类型检查。
数据类型原始类型数值类型整数类型byte类型short类型int类型long类型char类型浮点类型float类型double类型boolean类型Java虚拟机中没有任何供boolean值专用的字节码指令编译之后使用int数据类型来代替returnAddress类型值指向一条虚拟机指令的操作码引用类型类类型数组类型接口类型null
Java虚拟机的指令由一个字节长度的、代表着某种特定操作含义的操作码（opcode）以及跟随其后的零至多个代表此操作所需参数的操作数（operand）所构成。
如果忽略异常处理，那么Java虚拟机的解释器通过下面这个伪代码的循环即可有效工作：
do {
自动计算pc寄存器以及从pc寄存器的位置取出操作码;
if (存在操作数) 取出操作数;
执行操作码所定义的操作;
} while (处理下一次循环)大多数的指令都包含了其所操作的数据类型信息，同时操作码长度只有一个字节，因此Java虚拟机的指令集并没有对每一种数据类型枚举所有的操作，而是通过类型转换来减少操作码的枚举数量。例如，大部分指令都不支持整数类型byte、char和short，编译器会在编译器或是运行期将byte和short类型的数据带符号扩展为相应的int类型数据。同时，没有任何指令支持boolean数据类型，它在执行时将被转换为int。
在字节码指令中，以下5条指令用于方法调用：
invokevirtual指令用于调用对象的实例方法，根据对象的实际类型进行分派。这也是Java语言中最常见的方法分派方式。
invokeinterface指令用于调用接口，它会在运行时搜索由特定对象所实现的这个接口方法，并找出适合的方法进行调用。
invokespecial指令用于调用一些需要特殊处理的实例方法，包括实例初始化方法、私有方法和父类方法。
invokestatic指令用于调用命名类中的类方法（static方法）
invokedynamic指令用于调用以绑定了invokedynamic指令的调用点对象（call site object）作为目标的方法。调用点对象是一个特殊的语法结构，当一条invokedynamic指令首次被Java虚拟机执行前，Java虚拟机将会执行一个引导方法（bootstrap method）并以这个方法的运行结果作为调用点对象。因此，每条invokedynamic指令都有独一无二的链接状态，这是它与其他方法调用指令的一个差异。
方法调用指令根据返回值的类型进行区分，包括ireturn（当返回值是boolean、byte、char、short和int类型时使用）、lreturn、freturn、dreturn和areturn，另外还有一条return指令供声明为void的方法、实例初始化方法、类和接口的类初始化方法使用。
每一个class文件都对应着唯一一个类或接口的定义信息，但是相对地，类或接口并不一定都必须定义在文件里（比如类或接口也可以通过类加载器直接生成）。每个class文件都由字节流组成。每个class文件对应一个如下的ClassFile结构。
|
|
字节数 |
属性 |
说明 |
备注 |
|---|---|---|---|---|
| u4 |
magic |
Magic的唯一作用是确定这个文件是否为一个能被虚拟机所接受的class文件。魔数值固定位0xCAFEBABE，不会改变。 |
|
|
| u2 |
minor_version |
副版本号 |
|
|
| u2 |
major_version |
主版本号 |
|
|
| u2 |
constant_pool_count |
常量池计数器，值等于常量池表中的成员数+1 |
|
|
| cp_info |
constant_pool [constant_pool_count-1] |
常量池，它包含class文件结构及其子结构引用所有字符串常量、类或接口名、字段名和其他常量。常量池中的每一项都具备相同的特征--第一个字节作为类型标记，用于确定该项的格式，这个字节成为tagbyte。 |
|
|
| u2 |
access_flags |
访问标识，用于表示某个类或接口的访问权限属性。 |
|
|
| u2 |
this_class |
类索引，值必须是对常量池表中某项的一个有效索引值。这个索引值处的成员必须为CONSTANT_Class_info类型结构体 |
|
|
| u2 |
super_class |
父类索引，要么是0，要么是对常量池表中某项的一个有效索引值。如果不为0，那么常量池中这个索引处的成员必须为CONSTANT_Class_info类型常量。 |
|
|
| u2 |
interfaces_count |
接口计数器，表示当前类或接口的直接超接口数量 |
|
|
| u2 |
interfaces [interfaces_count] |
每个成员的值必须是对常量池表中某项的有效索引值，同样索引处成员必须为CONSTANT_Class_info结构。 |
|
|
| u2 |
fileds_count |
字段计数器，表示当前class文件fields表的成员个数 |
|
|
| field_info |
fields [fileds_count] |
字段表，每个成员都必须是一个fields_info结构的数据项 |
|
|
| u2 |
methods_count |
方法计数器 |
|
|
| method_info |
methods [methods_count] |
方法表，每个成员都必须是一个method_info结构 |
|
|
| u2 |
attributes_count |
属性计数器，表示当前class文件属性表的成员个数 |
属性的定义规则是：set/get方法名，去掉set/get后，将剩余部分首字母小写得到的字符串就是这个类的属性。 |
|
| attribute_info |
attributes [attributes_count] |
属性表，每个项的值都必须是attribute_info结构 |
|
让我们来通过javap命令查看几个简单方法调用案例：
上图add12and13方法调用了同一实例类中的另一方法addTwo，而externalAdd12and13首先构造了一个其他类ExternalVirtual的实例，然后调用了ExternalVirtual实例中的addTwo方法。通过javap -p -v InvokeVirtual指令InvokeVirtual的字节码构造如下，这里我们重点关注字节码指令的结构：
首先，常量池中列出了所有的方法和类的引用，包括InvokeVirtual类自身的方法和它所构建并调用的方法。
其次，当前类的每个方法都具有自己的指令码调用块，根据指令码的功能具有可选的操作数。在实际执行时，Java虚拟机会像类似汇编的执行方式一样顺序执行。
我们可以看到在add12and13方法中，通过invokevirtual指令调用了addTwo方法，这一指令的操作数#2指向了常量池中的索引为2的方法引用MethodRef。
在externalAdd12and13方法中，首先根据invokespecial指令构建了ExternalVirtual的实例，并在第13行通过invokevirtual方法调用了ExternalVirtual实例中的方法，同样，实例构造和方法调用的操作数也都对应着常量池中的对应类和方法的引用。
看到这里，我们不难猜出，Java虚拟机在执行字节码遇到方法调用时的执行方式，常量池类似于字节码执行时的索引表，当字节码指令涉及到类或方法调用时，虚拟机会现根据操作数在常量池中查找对应的引用关系，再跳转执行对应的字节码块。例如，在调用ExternalVirtual.addTwo方法时，先通过操作数查找到MethodRef，其中包含了ExternalVirtual类的全限定名和方法名，然后虚拟机会根据全限定名找到对应的class文件和对应方法，再进行实际的执行。
而对于没有任何方法调用的addTwo方法，它的字节码则十分简单，直接顺序执行即可。
对于invoke相关的指令运行方式，和C++中的虚函数概念有一定相似之处。C++中的多态是通过虚函数来实现的，虚函数允许子类重新定义成员函数。
Java编程模型中没有虚函数的概念，但它的普通函数就相当于C++的虚函数，动态绑定是Java的默认行为如果Java中不希望某个函数具有虚函数特性，可以加上final关键字变成非虚函数。
而虚函数对于运行时效率影响最重要的一点是：虚函数会导致CPU预测失效，从而导致CPU性能的极大浪费。
在这里，我们先来看一下CPU预测的原理。CPU为了提高吞吐量采用了流水线机制，CPU pipeline有四个执行阶段：
读取指令Fetch
指令解码Decode
运行指令Execute
回写Write-back
如果没有流水线机制，一条指令大概会花费 4 个时钟周期，而如果采用流水线机制，当第一条指令完成Fetch后，第二条指令就可以进行Fetch了，极大提高了指令的执行效率。
上面是我们的期待的理想情况，而在现实环境中，如果遇到的指令是 条件跳转指令，只要当前面的指令运行到执行阶段，才能知道要选择的分支，显然这种 停顿 对于 CPU 的 pipeline 机制是非常不友好的。而 分支预测技术 正是为了解决上述问题而诞生的，CPU 会根据分支预测的结果，选择下一条指令进入流水线。待跳转指令执行完成，如果预测正确，则流水线继续执行，不会受到跳转指令的影响。如果分支预测失败，那么便需要清空流水线，重新加载正确的分支（实际上目前市面上所有处理器都采用了类似的技术）。
关于分支预测更详细的说明案例，可参考深入理解CPU的分支预测(Branch Prediction)模型。
到这里我们结合Java"虚函数"的字节码指令执行过程，就能了解，为什么虚函数会导致CPU预测失效，因为虚函数的调用过程是动态的，只有在运行时通过虚函数调用的操作数，即常量池的类/方法引用，CPU才能找到下一步的指令，自然无法执行CPU预测。
我们可以通过模拟一个简单的虚函数调用，来对比运行效率差距。如下所示，我们通过定义一个Operator接口，并实现AddOperator类执行加法操作来模拟虚函数调用过程，通过直接的加法计算模拟对应同样计算流程的非虚函数调用。
虚函数调用virtual和非虚函数调用nonVirtual对应的字节码计算流程如下：相比于右侧非虚函数的加法指令iadd，虚函数调用使用的invokeinterface指令，需要根据操作数转向常量池进行查找。
当测试数据量为1kw时，我们可以看到虚函数调用的耗时为非虚函数的3倍。
进一步，如果我们将虚函数调用中的for循环用IntStream替换（其中也涉及到接口调用），性能差距将会更加明显，达到68.75倍。
在了解了代码生成在虚函数调用方面带来的性能优化后，我们需要知道为什么代码生成是查询引擎中的一个典型的Runtime优化策略。这个问题的答案就在查询引擎的计算模型上。
首先我们来总结一下查询引擎的计算语义特性，查询引擎通常需要支持多种丰富的原子计算，以及一定语法规则范围内的计算自由组合，这也就决定了，查询引擎的计算模型必须能支持复杂的计算路径，同时还需要具有高度可扩展的原子算子。当前在查询引擎中，为了解决这一计算特性，最为通用的是火山模型。
Volcano Model是一种经典的基于行的流式迭代模型(Row-BasedStreaming Iterator Model)，在我们熟知的主流关系数据库中都采用了这种模型，例如Oracle，SQL Server, MySQL等，同时在大数据计算引擎中也广泛使用，如Spark、Presto等等。火山模型是查询引擎设计中绕不开的一种数据计算模型。
在Volcano模型中，所有的代数运算符(operator)都被看成是一个迭代器，它们都提供一组简单的接口：open()—next()—close()，查询计划树由一个个这样的关系运算符组成，每一次的next()调用，运算符就返回一行(Row)，每一个运算符的next()都有自己的流控逻辑，数据通过运算符自上而下的next()嵌套调用而被动的进行拉取。
火山模型为计算引擎带来的优势是：
计算算子足够独立，每个算子仅关注自身的输入输出即可，无需关注其他算子实现。
算子之间通过标准数据结构进行连接，支持灵活的计算路径组合。
但火山模型的实现必然会涉及到大量的虚函数调用，也给计算性能带来了考验。这也恰好是代码生成能发挥巨大作用的计算场景。
综合以上信息，在查询引擎中，代码生成在查询引擎优化策略中是非常重要的一环，绝大多数成功的查询引擎都具有代码生成的优化策略。
在查询引擎的代码生成场景中，我们往往是在查询运行阶段对其中某一部分的计算逻辑进行动态的代码生成，需要生成的代码甚至可能不是一个完整的类，只是一个方法或是表达式。因此无法使用静态的javac编译。代码生成工具可以分为两大类：
动态编译器：将代码片段实时的编译成为字节码，并加载到ClassLoader中调用或执行。
动态字节码构建：直接根据Java字节码规范构建出类/方法等字节码，并加载到ClassLoader中调用或执行。
这两种方法的区别主要在于构建复杂度和构建速度，动态编译器由于存在代码的解析和编译，相对来说响应较慢，但是动态编译器由于可直接接收字符串代码片段，可以生成较为复杂的执行代码。动态字节码构建免去了解析的成本，响应较快，但是由于使用此方法用户需直接和Java虚拟机规范进行严谨的构建，对用户来说成本较高，生成代码的复杂度优先。
接下来我们简要介绍分别介绍这两类代码生成工具中使用较广的两个工具。
Janino 是一个极小、极快的 开源Java 编译器（Janino is a super-small, super-fast Java™ compiler.）。Janino 不仅可以像 JAVAC 一样将 Java 源码文件编译为字节码文件，还可以编译内存中的 Java 表达式、块、类和源码文件，加载字节码并在 JVM 中直接执行。Janino 同样可以用于静态代码分析和代码操作。
项目地址：https://github.com/janino-compiler/janino
官网地址：http://janino-compiler.github.io/janino/
在使用前需要在pom.xml中引入如下依赖：
代码块
<dependency>
<groupId>org.codehaus.janino</groupId>
<artifactId>janino</artifactId>
<version>3.0.11</version>
</dependency> Janino的构建方式较为简单，我们可以自由选择构建以字符串形式输入的表达式、方法、类。
# 构建表达式
String express = "(1+2)*3";
ScriptEvaluator evaluator = new ExpressionEvaluator();
evaluator.cook(express);
Object res = evaluator.evaluate(null);
System.out.println(express + "=" + res);
# 构建方法
ScriptEvaluator se = new ScriptEvaluator();
se.cook(
""
+ "static void method1() {\n"
+ " System.out.println(\"run in method1()\");\n"
+ "}\n"
+ "\n"
+ "static void method2() {\n"
+ " System.out.println(\"run in method2()\");\n"
+ "}\n"
+ "\n"
+ "method1();\n"
+ "method2();\n"
+ "\n"
);
se.evaluate(null);
# 构建接口
Foo f = (Foo) ClassBodyEvaluator.createFastClassBodyEvaluator(
new Scanner(null, new StringReader("public int bar(int a, int b) { return a + b; }")),
Foo.class, // 实现的父类或接口
(ClassLoader) null // 这里设置为null表示使用当前线程的class loader
);
System.out.println("1 + 2 = " + f.bar(1, 2));
# 构建类
IScriptEvaluator se = new ScriptEvaluator();
se.setReturnType(String.class);
se.cook("import com.tang.janino.obj.BaseClass;\n"
+ "import com.tang.janino.obj.DerivedClass;\n"
+ "BaseClass o=new DerivedClass(\"1\",\"join\");\n"
+ "return o.toString();\n");
Object res = se.evaluate(new Object[0]);
System.out.println(res);ASM是一个针对Java语言的运行时和线下类生成和转换工具。ASM类库被设计工作在编译后的Java类文件中。同时，它也被设计的尽可能的快和轻量。尽可能的块对于运行期间使用ASM的应用来说很重要，旨在不要减低运行效率。并且尽可能地小对于在内存受限的环境中使用非常重要，并且避免使用ASM来膨胀小型应用程序或库的大小。
ASM不是唯一一个用来生成和转换编译后Java类文件的工具，但它是最新的、最有效的方法之一。它的主要优势如下：
简单、设计良好、模块化的API，易于使用。
它有很好的文档，并且有一个相关的Eclipse插件。
支持最新版Java, Java 7
轻量级，快速，鲁棒性
庞大的用户社区可以为新用户提供支持。
它的开放源码许可允许您以任何您想要的方式使用它。
ASM的核心原理是完全基于Java的class文件格式，将字节码作为一个结构体来进行解析、转换、生成。
ASM library提供了两个API来生成和转换编译后类文件：core API提供基于事件的类表示，而tree API提供基于对象的表示。
在基于事件的模型中，一个类用一系列事件表示，每个事件表示类的一个元素，例如它的头、字段、方法声明、指令等等。基于事件的API定义了一组可能的事件和它们必须发生的顺序，并提供了一个类解析器，该解析器为每个被解析的元素生成一个事件，以及一个类写入器，该类写入器从这些事件的序列生成编译的类。
使用基于对象的模型，类用对象树表示，每个对象表示类的一部分，如类本身、字段、方法、指令等，每个对象都引用表示其组成部分的对象。基于对象的API提供了一种方法，可以将表示类的事件序列转换为表示相同类的对象树，反之亦然，可以将对象树转换为等效的事件序列。换句话说，基于对象的API构建在基于事件的API之上。
这两个API可以与XML (SAX)的简单API和XML文档的文档对象模型(DOM) API进行比较:基于事件的API类似于SAX，而基于对象的API类似于DOM。基于对象的API构建在基于事件的API之上，就像DOM可以在SAX之上提供一样。
ASM同时提供两种API是因为它们各有所长，每种API都有它自身的优势和缺点：
基于事件的API和基于对象API相比，更快，并且需要更少的内存。因为它们不需要在内存中创建用于表示类和对象的树(SAX和DOM同理)
然而在基于事件的API上实现类转换功能更为困难，因为在给定的时间类中只有一个元素(对应于当前事件的元素)可用，而在基于对象的API中整个类在内存中都是可用的。
注意这两个API每次只会处理一个类，并且它们是互相独立的：类的层次结构不会被维护。并且如果一个类的改变影响了其他类，需要用户来对其他类进行处理。
下图为使用core API（基于事件）来生成一个自定义类的样例，我们可以发现它的构建元素和class文件结构基本是一致的。
当然，由于ASM对于字节码的深入，普通用户使用起来是具有一定难度的。因此，对应的也产生了一些基于ASM进行封装的类生成器，如presto中的bytecode，它们将字节码的生成用一种更容易理解和使用的方式开放给用户。
看到这里，我们好像会觉得，代码生成是一件很简单的事情，只要我们能熟练使用代码生成工具，就可以很轻易的达到我们的目的。但在实际查询引擎的复杂计算应用场景中，我们几乎不可能通过一个简单、独立的类/方法生成就能达到提升查询引擎效率的目的。
我们需要注意，查询引擎中对于火山模型的大量使用，一个查询流程可能涉及到多个算法的复杂组合，同时由于查询引擎的灵活查询方式，每一个查询流程的数据计算可能都大不相同。我们需要做到将多个算子的计算逻辑整合为一个并生成代码，还需要考虑算子之间灵活组合的场景。同时，我们还需要考虑，当一个JVM进程中大量使用代码生成，那么生成的大量动态代码是否会影响到JVM自身的性能。
总而言之，独立的代码生成，难度并不高，困难的点在于我们应该如何用代码生成在复杂的应用场景中发挥最大的性能提升作用，而不会引入沉重的实时构建成本以及性能问题。
本章选择了Spark和Presto简要概述代码生成的应用，不涉及到源码级别。深入到源码级别的解析将会在后面的文章中呈现。
Spark采用了动态代码编译的方式。Spark使用Janino来执行Expression级别和WholeStage级别的Codegen。虽然动态编译会带来一定的使用成本，但对于Spark的大数据量和相对较宽松的计算时效场景下，收益远比成本来的要高。
为了管理复杂的代码生成规则，Spark中的CodegenContext作为管理生成代码的核心类，涵盖以下功能：
1.命名管理。保证同一Scope内无变量名冲突。
2.变量管理。维护类变量，判断变量类型(应该声明为独立变量还是压缩到类型数组中)，维护变量初始化逻辑等。
3.方法管理。维护类方法。
4.内部类管理。维护内部类。
5.相同表达式管理。维护相同子表达式，避免重复计算。
6.size管理。避免方法、类size过大，避免类变量数过多，进行比较拆分。如把表达式块拆分成多个函数；把函数、变量定义拆分到多个内部类。
7.依赖管理。维护该类依赖的外部对象，如Broadcast对象、工具对象、度量对象等。
8.通用模板管理。提供通用代码模板，如genComp, nullSafeExec等。
相对于Spark，Presto更多在Ad-hoc场景使用，动态的代码编译对于Presto来说对查询实时性具有较大影响。因此Presto使用了一个基于ASM的字节码生成工具airlift-bytecode（facebook内部库）来进行字节码的构建。
bytecode对字节码的构建进行了封装，如下，对于一个for循环子句，直接提供了更贴近于应用开发者的构建方式，不再和最底层的字节码进行交互。
ForLoop loop = new ForLoop()
.initialize(i.set(0))
.condition(lessThan(i, 100))
.update(i.set(add(i, constantInt(1))))
.body(new BytecodeBlock()...);但字节码生成工具的复杂度造成了Presto代码生成逻辑的复杂度，目前的codegen还停留在表达式的级别，在局部的计算逻辑，以及整个算子仍然有很大的优化空间。
<<Java虚拟机规范>>