赞
踩
JIT(Just-in-time compilation)动态编译
传统数据库后端编码是一套通用的代码,实现通用的数据处理,eg:
可以看出,单个 SQL 中,很多之前的“变量”,已经成为“常量”,如果我们在知道用户的 SQL 的之后再 “coding”,会少很多条件判断,少很多无关代码,效率自然会高很多。
LLVM,一个自由软件项目,是一种编译器的基础建设,以 C++ 写成。它是为了任意一种编程语言写成的程序,利用虚拟技术,创造出编译时期,链接时期,运行时期以及“闲置时期”的最优化。
LLVM特性
目前比较流行的数据分析数据库中使用 JIT 技术的有
产品 | 简介 |
HyPer | 高性能内存数据库 |
Impala | Cloudera公司主导开发的新型查询系统 |
Postgres Professional | PostgreSQL 的一个发行版 |
gpdb | 基于 PostgreSQL 的 MPP 产品 |
如下图所示LLVM编译器框架
Clang的发音是/ˈklæŋ/
可以将clang和lld都看做是LLVM的组成部分
LLVM由一些库和工具组成,正因为它的这种设计思想,使它可以很容易和IDE集成(因为IDE软件可以直接调用库来实现一些如静态检查这些功能),也很容易构建生成各种功能的工具(因为新的工具只需要调用需要的库就行)
最初时,LLVM的前端是GCC,我们也可以开发自己的前端,和LLVM后端配合起来,实现我们自定义的编程语言的编译器。
LLVM IR是LLVM的中间表示,这是LLVM中很重要的一个东西,链接
大多数的优化都依赖于LLVM IR展开,LLVM的一个设计思想是优化可以渗透在整个编译流程中各个阶段,比如编译时、链接时、运行时等
在LLVM中,IR有三种表示
(1)一种是可读的IR,类似于汇编代码,但其实它介于高等语言和汇编之间,这种表示就是给人看的,磁盘文件后缀为.ll;
(2)第二种是不可读的二进制IR,被称作位码(bitcode),磁盘文件后缀为.bc;
(3)第三种表示是一种内存格式,只保存在内存中,所以谈不上文件格式和文件后缀,这种格式是LLVM之所以编译快的一个原因,它不像gcc,每个阶段结束会生成一些中间过程文件,它编译的中间数据都是这第三种表示的IR。
三种格式是完全等价的,我们可以在Clang/LLVM工具的参数中指定生成这些文件(默认不生成,对于非编译器开发人员来说,也没必要生成),可以通过llvm-as和llvm-dis来在前两种文件之间做转换。
LLVM IR linker,IR的链接器
为了实现链接时优化,LLVM在前端(Clang)生成单个代码单元的IR后,将整个工程的IR都链接起来,同时做链接时优化。
LLVM backend就是LLVM真正的后端
LLVM核心,包括编译、汇编、链接这一套,最后生成汇编文件或者目标码。
这里的LLVM compiler和gcc中的compiler不一样,这里的LLVM compiler只是编译LLVM IR。
LLVM
Clang
通常我们在命令行上调用的clang工具,是Clang驱动程序,因为LLVM本质上只是一个编译器框架,所以需要一个驱动程序把整个编译器的功能串起来,clang能够监控整个编译器的流程,即能够调用到Clang和LLVM的各种库,最终实现编译的功能。
BTW,其实gcc也是驱动程序,由它将cc、as、ld等程序驱动起来。
如果由clang来监控运行,则整个IR的阶段,IR的表示形式都是内存形式,这样就不会在编译过程中产生中间文件,提高了编译的效率。
另一种方法是调用LLVM的工具,类似于gcc中的cc、as、ld一样,LLVM也有自己的工具,这样工具之间运行需要用户来控制输入输出,这时的IR表示形式就是硬盘格式,可以是LLVM汇编(.ll),也可以是位码(.bc)。
LLVM工具
llc -filetype=asm main.bc -O0 -o main.s
llc -filetype=obj main.bc -O0 -o main.o
(.bc文件换成.ll文件也可以)
llvm-mc
这是微观意义上的LLVM汇编器,它输入汇编文件,输出目标文件。同时,它也可以反汇编,指定特殊参数(–disassemble)就行。
可以发现,llc和llvm-mc都会调用到输出目标文件的库,也就是MCObjectStreamer。
链接
lli
这个工具是LLVM IR的解释器,也是一个JIT编译器。
我其实从这里才知道,原来谈C语言是一门编译型语言,并不客观,因为LLVM可以把C语言翻译成LLVM IR,然后解释执行,与Java的那一套类似,这也是最初LLVM编写时的实现(一个虚拟机运行IR)
llvm-link
第一种是LLVM先通过前端把每个源文件单独翻译成IR级别,然后用llvm-link链接成一个IR,然后再经过优化、后端等步骤生成目标文件,使用llvm-link的同时,可以使用链接时优化。不过需要注意,这种方式同样需要最终调用链接器,将这个目标文件链接成可执行文件。
第二种是LLVM通过前端把每个源文件单独翻译后,再单独经过优化、后端等工作,将每个源文件生成目标文件,之后再调用链接器,将所有目标文件链接成可执行文件。
llvm-link main.bc sum.bc -o sum.linked.bc
llvm-as
这是针对LLVM IR的汇编器,其实名字里带as,实际上不是gcc那个as,它的功能是将.ll文件翻译为.bc文件,LLVM项目里,.ll称为LLVM汇编码,所以llvm-as也就是IR的汇编器了。
llvm-dis
与llvm-as刚好相反,IR的反汇编器,用来将.bc文件翻译为.ll文件。
clang
clang能够调用起来整个编译器的流程,也就是上边其他工具调用的库,它很多都同样会调用。
clang通过指定-emit-llvm参数,可以配合-S或-c生成.ll或.bc文件,这样我们就能把Clang的部分和LLVM的后端分离开来独立运行,对于观察编译器流程来说,很实用。
clang -emit-llvm -c main.c -o main.bc
clang -emit-llvm -S main.c -o main.ll
gcc的编译器,输入是源代码,输出是汇编代码,相当于是LLVM中Clang一级加上IR linker再加上LLVM compiler中的生成汇编代码部分
gcc的汇编器,输入是汇编代码,输出是目标文件,相当于是LLVM中的llvm-mc
gcc的链接器,输入是目标文件,输出是最终可执行文件,相当于LLVM中的Linker,所以Clang驱动程序调起来的链接器还是系统链接器,可以选择使用gcc的ld。
在编译器理论与实践中,IR是非常重要的一环。IR的全称叫做Intermediate Representation,翻译过来叫“中间表示”。
LLVM框架
LLVM把整个编译过程分为三步:
IR中最重要的三部分,指令格式、Basic Block & CFG,SSA
LLVM IR中得变量的命名是以 "%"开头,默认%0是函数的第一个参数、%1是第二个参数,依次类推;
LLVM IR的指令格式包括操作符、类型、输入、返回值;
LLVM IR是支持一些基本的数据类型的,比如i8、i32、浮点数等
define i32 @ir_add(i32, i32, i32, i32, i32)
{
%6 = add i32 %0, %1操作符号是"add"、类型是"i32"、输入是"%0"和“%1”、返回值是"%6"
%7 = add i32 %6, %2
%8 = add i32 %7, %3
%9 = add i32 %8, %4
ret i32 %9;
}
Basic Block & CFG
Basic Block(基本块,简称BB)和Control Flow Graph(控制流图,CFG)
下图(左)展示了一个简单的C语言函数,下图(中)是使用clang编译出来的对应的LLVM IR,下图(右)是使用graphviz画出来的CFG。
C语言中的for, while, if等关键字都代表着分支跳转,
比如在LLVM IR中"br label %7"意味着无论如何都跳转到名为%7的label那里,这是一条无条件跳转指令。
"br i1 %10, label %11, label %22"是有条件跳转,意味着这如果%10是true则跳转到名为%11的label,否则跳转到名为%22的label。
除了第一个Basic Block之外,每个Basic Block都会有一个名字(label)。
Basic Block解决了控制逻辑的问题,一个Basic Block是指一段串行执行的指令流。
除了第一个Basic Block之外,每个Basic Block都会有一个名字(label),例如在这段代码当中一共有5个Basic Block。
CFG(Control Flow Graph, 控制流图)其实就是由Basic Block以及Basic Block之间的跳转关系组成的一个图。
例如如图所示的代码,一共有5个Basic Block,箭头列出了Basic Block之间的跳转关系,共同组成了一个CFG。
如果一个Basic Block只有一个箭头指向别的Block,那么这个跳转就是无条件跳转,否则是有条件跳转。
CFG是编译理论中一个比较简单而且很基础的概念,CFG更进一步是DFG(Data Flow Graph,数据流图),很多进阶的编译优化算法都是基于DFG的。
SSA。
SSA的全称是Static Single Assignment(静态单赋值),每个“变量”只会被赋值一次,这就是SSA的核心思想。
因为从编译器的角度来看,编译器不关心“变量”,编译器是以“数据”为中心进行设计的。
每个“变量”的每次写入,都生成了一个新的数据版本,编译器的优化是围绕数据版本展开的。
eg:如图(左)展示了一段简单的C代码,如图(右)是这短代码的SSA版本,也就是“编译器眼中的代码”
编译器只关心数据的流向,因此每次赋值操作都会生成一个新的左值。
在SSA中,每个变量都代表数据的一个版本。也就是说,高级语言以变量为核心,而SSA格式以数据为核心。
。Phi节点是SSA中的一个重要概念。
在这个例子当中,a_4的取值取决于之前执行了哪个分支,如果执行了第一个分支,那么a_4 = a_1, 依次类推。
Phi节点通过判断这段代码是从哪个Basic Block跳转而来,选择合适的数据版本。
LLVM IR自然也是需要开发者写Phi节点的,在循环、条件分支跳转的地方,往往需要手写很多phi节点
define i32 @ir_loopadd_phi(i32*, i32) { br label %loop loop: %i = phi i32 [0,%2], [%newi,%loop_body]; %res = phi i32[0,%2], [%new_res, %loop_body] %break_flag = icmp sge i32 %i, %1 br i1 %break_flag, label %final, label %loop_body loop_body: %addr = getelementptr inbounds i32, i32* %0, i32 %i %val = load i32, i32* %addr, align 4 %new_res = add i32 %res, %val %newi = add i32 %i, 1 br label %loop final: ret i32 %res; }
编译器本质上就是调用各种各样的API,根据输入去生成对应的代码,LLVM Codegen也不例外。
Value *constant = Builder.getInt32(16); Value *Arg1 = fooFunc->arg_begin(); Value *val = createArith(Builder, Arg1, constant); Value *val2 = Builder.getInt32(100); Value *Compare = Builder.CreateICmpULT(val, val2, "cmptmp"); Value *Condition = Builder.CreateICmpNE(Compare, Builder.getInt1(0), "ifcond"); ValList VL; VL.push_back(Condition); VL.push_back(Arg1); BasicBlock *ThenBB = createBB(fooFunc, "then"); BasicBlock *ElseBB = createBB(fooFunc, "else"); BasicBlock *MergeBB = createBB(fooFunc, "ifcont"); BBList List; List.push_back(ThenBB); List.push_back(ElseBB); List.push_back(MergeBB); Value *v = createIfElse(Builder, List, VL);
LLVM IR的性能并不会比C快
缺点
适用LLVM Codegen的场景
优化频繁调用的存取层
void MaterializeTuple(char* tuple) { for (int i = 0; i < num_slots_; ++i) { char* slot = tuple + offsets_[i]; switch(types_[i]) { case BOOLEAN: *slot = ParseBoolean(); break; case INT: *slot = ParseInt(); break; case FLOAT: … case STRING: … // etc. } } } 当知道表结构后, 动态生成的代码就简单了。 按照顺序解析数据,不需要做数据类型的判断,直接在获取对应偏移的数据,跳过不需要获得的列,是能够优化 CPU 的点。随着处理的行数增加,节省的计算量是惊人的。 void MaterializeTuple(char* tuple) { *(tuple + 0) = ParseInt(); // i = 0 *(tuple + 4) = ParseBoolean(); // i = 1 *(tuple + 5) = ParseInt(); // i = 2 }
表达式计算
select funx(((1 + a.b) + a.a )) /2 from a 他的执行过程是 expr(root) // funroot funx(data) // funx data (/) 2 // fundivision data (+) a.a // funadd 1 (+) a.b // funadd 可以看到,表达式越复杂,递归调用越深。执行的函数个数越多。 然而,在获取到查询计划之后再“写”代码,就简单了,只需要这样 llvm_expr_fun1 { tmp = 1 (+) a.b; tmp1 = tmp + a.a; tmp3 = tmp1 / 2; tmp4 = funx(tmp3); } 好处: (1)递归改顺序执行 (2)整个过程一个函数调用完成,性能提高明显。 整个优化方式适合 OLTP 和 OLAP 场景,我们可以像保存查询计划那样保存 LLVM 生成的表达式函数
优化执行器流程
select *
from R1,R3,
( select R2.z,
count(*)
from R2
where R2.y=3
group by R2.z
) R2
where R1.x=7
and R1.a=R3.b
and R2.z=R3.c
initialize memory of ona=b, onc=z, and Gz for each tuple t in R1 if t:x = 7 materialize t in hash table of ona=b for each tuple t in R2 if t:y = 3 aggregate t in hash table of Gz for each tuple t in Gz materialize t in hash table of onz=c for each tuple t3 in R3 for each match t2 in onz=c [t3:c] for each match t1 in ona=b [t3:b] output t1 ◦t2 ◦t3
结论
PostgreSQL为了实现表达式的解释执行,采用了一套“拼函数”的方案
// 样例SQL select count(*) from table where a > 10 and b < 5;
// PostgreSQL解释执行方案:多次函数调用
result = Int8AndOp(Int32GT(a, 10), Int32LT(b, 5));
// AnalyticDB PostgreSQL方案:使用LLVM codegen生成最小化底层代码
%res1 = icmp ugt i32 %a, 10;
%res2 = icmp ult i32 %b, 5;
%res = and i8 %res1, %res2;
在数据库中,表达式主要出现在几个场景。
JIT 指的是即时编译,
PostgreSQL 需要JIT 技术的原因
PostgreSQL 中JIT 的实现概述
PostgreSQL 中支持的JIT 功能
与JIT 相关的GUC 参数
目前JIT 功能开启所需要的代价没有很好的办法进行建模,也没有很好的方法来估计,所以导致JIT 功能无法作为代价估计模型中一种可量化的代价。
安装
./configure --with-llvm LLVM_CONFIG=/opt/rh/llvm-toolset-7/root/usr/bin/llvm-config CLANG=/opt/rh/llvm-toolset-7/root/usr/bin/clang
不开启JIT与开启JIT的测试
不开启 postgres=# create table test (id serial); CREATE TABLE postgres=# insert INTO test (id) select * from generate_series(1, 10000000); INSERT 0 10000000 postgres=# set jit=off; SET postgres=# explain select count(*) from test; QUERY PLAN ----------------------------------------------------------------------------------------- Finalize Aggregate (cost=97331.43..97331.44 rows=1 width=8) -> Gather (cost=97331.21..97331.42 rows=2 width=8) Workers Planned: 2 -> Partial Aggregate (cost=96331.21..96331.22 rows=1 width=8) -> Parallel Seq Scan on test (cost=0.00..85914.57 rows=4166657 width=0) (5 rows) komablog=# explain analyze select count(*) from test; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------- Finalize Aggregate (cost=97331.80..97331.81 rows=1 width=8) (actual time=490.420..493.668 rows=1 loops=1) -> Gather (cost=97331.58..97331.79 rows=2 width=8) (actual time=490.392..493.659 rows=3 loops=1) Workers Planned: 2 Workers Launched: 2 -> Partial Aggregate (cost=96331.58..96331.59 rows=1 width=8) (actual time=488.083..488.084 rows=1 loops=3) -> Parallel Seq Scan on test (cost=0.00..85914.87 rows=4166687 width=0) (actual time=0.214..292.559 rows=3333333 loops=3) Planning time: 0.057 ms Execution time: 493.716 ms (8 rows) 开启 postgres=# set jit = 'on'; SET postgres=# show jit_above_cost; jit_above_cost ---------------- 100000 (1 row) postgres=# show jit_inline_above_cost; jit_inline_above_cost ----------------------- 500000 (1 row) postgres=# show jit_optimize_above_cost; jit_optimize_above_cost ------------------------- 500000 (1 row) postgres=# explain select count(*) from test; QUERY PLAN ----------------------------------------------------------------------------------------- Finalize Aggregate (cost=97331.43..97331.44 rows=1 width=8) -> Gather (cost=97331.21..97331.42 rows=2 width=8) Workers Planned: 2 -> Partial Aggregate (cost=96331.21..96331.22 rows=1 width=8) -> Parallel Seq Scan on test (cost=0.00..85914.57 rows=4166657 width=0) (5 rows) postgres=# explain analyze select count(*) from test; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------- Finalize Aggregate (cost=97331.43..97331.44 rows=1 width=8) (actual time=415.747..415.748 rows=1 loops=1) -> Gather (cost=97331.21..97331.42 rows=2 width=8) (actual time=415.658..418.129 rows=3 loops=1) Workers Planned: 2 Workers Launched: 2 -> Partial Aggregate (cost=96331.21..96331.22 rows=1 width=8) (actual time=409.043..409.044 rows=1 loops=3) -> Parallel Seq Scan on test (cost=0.00..85914.57 rows=4166657 width=0) (actual time=0.148..250.496 rows=3333333 loops=3) Planning Time: 0.054 ms Execution Time: 418.175 ms (8 rows) postgres=# set jit_above_cost = 10; set jit_inline_above_cost = 10; set jit_optimize_above_cost = 10; SET SET SET postgres=# show max_parallel_workers_per_gather; max_parallel_workers_per_gather --------------------------------- 2 (1 row) postgres=# explain analyze select count(*) from test; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------- Finalize Aggregate (cost=97331.43..97331.44 rows=1 width=8) (actual time=441.672..441.672 rows=1 loops=1) -> Gather (cost=97331.21..97331.42 rows=2 width=8) (actual time=441.547..446.028 rows=3 loops=1) Workers Planned: 2 Workers Launched: 2 -> Partial Aggregate (cost=96331.21..96331.22 rows=1 width=8) (actual time=434.128..434.129 rows=1 loops=3) -> Parallel Seq Scan on test (cost=0.00..85914.57 rows=4166657 width=0) (actual time=0.161..251.158 rows=3333333 loops=3) Planning Time: 0.057 ms JIT: Functions: 9 Options: Inlining true, Optimization true, Expressions true, Deforming true Timing: Generation 1.096 ms, Inlining 109.551 ms, Optimization 22.201 ms, Emission 19.127 ms, Total 151.974 ms Execution Time: 446.673 ms (12 rows) postgres=# set max_parallel_workers_per_gather = 0; SET postgres=# explain analyze select count(*) from test; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------ Aggregate (cost=169247.71..169247.72 rows=1 width=8) (actual time=1172.932..1172.933 rows=1 loops=1) -> Seq Scan on test (cost=0.00..144247.77 rows=9999977 width=0) (actual time=0.028..745.134 rows=10000000 loops=1) Planning Time: 0.046 ms JIT: Functions: 2 Options: Inlining true, Optimization true, Expressions true, Deforming true Timing: Generation 0.298 ms, Inlining 0.881 ms, Optimization 3.986 ms, Emission 3.788 ms, Total 8.952 ms Execution Time: 1173.292 ms (8 rows)
可以看出:
没有达到对应GUC 参数规定的cost,即使jit=on,JIT 也不会起作用。
JIT 对应功能的开启是有一定代价的,对于一些SQL 语句可能会有性能的下降,如上面的例子select count(*) from test。
JIT 会继承并行查询带来的性能提升。
参考:为什么编译原理被称为龙书?,有说llvmJIT对SQL解析优化提升PG查询性能数倍,SQL解析本身消耗占比不高吧,能有这么高提升?,作为编译优化技术代表的开源编译器框架LLVM,如何在数据库中应用?,PgSQL · 特性分析 · 浅析PostgreSQL 中的JIT,JIT 在数据仓库中的应用价值,LLVM基本概念入门
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。