Impala学习--代码生成（Code Generation）

代码生成 (Code Generation)

1 概述

Cloudera Impala是在Apache Hadoop上的开源实时执行引擎，并为了性能优化而做了很多工作。本文将解释如何利用运行时的代码生成技巧，提高CPU的使用率，减少整体执行时间，以及为何整体性能可以提升3倍。

2 为何使用代码生成

对于一个query，优化执行性能的最理想状态，就是创造一个应用，只支持这个query的数据格式，和查询类型。

举例来说，最理想的状态下，执行一下query的速度：

select count(*) from tbl where col like %XYZ%

和

grep -c "XYZ" tbl

是相同的。

考虑另一个query：select sum(col) from tbl。如果表只有一列，类型是int64，可以用一下代码执行：

int64_t sum=0;
int64_t* values = (int64_t*)buffer;
for (int i=0; i < num_rows; ++i) {
    sum += values[i];
}

用以上两种方式执行query，通常比在通用的queryengine里执行要快的多（不考虑database使用索引等优化技术）。这主要是因为目前的queryengine存在以下的开销：

虚函数调用:

在不使用代码生成技术的情况下，表达式的求值过程中通常需要调用虚函数，例如eval。这主要取决于系统的实现，通常来说，总会有一群operator类，每一个operator类都会实现eval函数。在这种情况下，表达式计算本身的开销很小，而虚函数调用带来的开销通常就会比较大。

大量的switch case代码，需要对类型等进行判断:

尽管分支预测技术可以缓解这个问题，但是分支指令依然会降低执行pipeline的效率，以及影响指令级并行。

无法通过使用常量提高性能:

在Impala中，每一个tuple的的长度在编译时就已经计算好。例如col3在tuple中的offset时16。如果把这些常量写入代码中，则可以减少额外的内存访问的开销。

代码生成的目标就是，对每一个query，都使用和定制程序几乎相同的指令数，并得到相同的结果。避免因为支持更多的功能而导致的额外开销。

3 llvm

LLVM（Low Level Virtual Machine）是一组库，包含了编译器的building blocks。主要的模块包括：

AST -> IR generation
IR优化
IR -> machine code generation

LLVM的IR和Java的byte code很类似。IR一种二进制语言，LLVM把IR当作其内部模块的输入和输出LLVM也提供更高级的code object（instruction object，function object），使得可以更方便的对IR进行编程。包括对函数进行inline，移除指令，用常量替代一个计算，等等。Impala用到了LLVM中的IR优化，以及IR生成机器码。

除了LLVM，还有其他的生成代码的方式，但LLVM的效果更好：

直接生成可以执行的机器码:

尽管这个过程速度很快，但是生成机器码很容易出错，也很复杂，尤其是当函数数量增加时。同时，这种方法也无法享受编译器优化带来的性能提升。

生成c++代码，编译，并动态加载:

这种方法生成的代码可以经过编译器优化，并且生成高级语言相对简单。但通常编译c++代码需要几秒的时间，是比较慢的。

4 Impala使用IR

在进行完语意分析后，impala为每一个独立的操作生成其kernal代码。在代码生成时，由于已经知道了数据的类型，数据的layout。所以生成的代码中，会对循环等进行很多的优化。

LLVM提供两种生成IR的机制。1）使用IrBuilder API；2）使用clang编译器。这两种方法Impala都用到了。

使用IrBuilder生成IR
加载已经编译好的IR，仅加载query需要的函数。
把1和2的结果combine到一起。
通过LLVM的优化器，对IR进行优化。
JIT compile，把优化后的IR编译成机器码。LLVM会把它以函数指针的形势返回。

5 示例

select 
    l_returnflag,
    l_linestatus,
    sum(l_quantity),
    sum(l_extendedprice),
    sum(l_extendedprice * (1 - l_discount)),
    sum(l_extendedprice * (1 - l_discount) * (1 + l_tax)),
    avg(l_quantity),
    avg(l_extendedprice),
    avg(l_discount),
    count(1)
from
tpch.lineitem
where
    l_shipdate<='1998-09-02'
group by
    l_returnflag,
    l_linestatus

Impala会将这个query编译成一个算子树。对这个query来说，会有两个算子：scan算子，用于读取输入数据；聚合算子，计算sum和avg。

对于聚合算子，Impala会遍历所有每一条纪录，根据l_{returnflags和l}_{linestatus的值进行hash，}在hash table中查找，并重新计算sum和avg的结果。生成后的代码会把对每一条纪录的所有求值操作放在一个被inline的循环中。

下图时执行结果对比：

对于两种不同的dataset，性能头提高了3倍。而代码生成消耗的时间大概为150s。代码生成消耗的时间和采用的优化选项有很大关系。可以在impala shell中，使用set命令查看优化选项。

下表是更详细的对比：

Codegen on?	Time	Instructions	Branches	Branch Misses	Miss %
YES	0.63s	52,605,701,380	9,050,446,359	145,461,106	1.607
NO	1.7s	102,345,521,322	17,131,519,396	370,150,103	2.161

可以看到，采用代码生成可以减少一半的指令和一半的branch miss。

6 总结

我们在代码生生成上投入的精力已经得到了回报。随着我们继续的改进，我们期望得到更大的性能提升。列存储，更高效的编码方式，以及更大的缓存，这些技术会提高IO的性能。这时候，CPU的效率就将变得更加重要。

代码生成对于简单的query，带来的性能提升会更明显。对于query中带有复杂操作的，例如正则表达式，则性能提升会不那么显著。因为相对来说，正则表达本身的计算会占用更多时间。

在Impala 0.5中，还有一些代码没有使用代码生成技术。这些会在GA版本中得到改进。

Author: <kyle@localhost.localdomain>