网站建设需要做什么,专属头像制作素材图片,wordpress实时交流插件,西安企业网站开发简介#xff1a; 作者#xff1a;长别
1. 前言
随着IT基础设施的发展#xff0c;现代的数据处理系统需要处理更多的数据、支持更为复杂的算法。数据量的增长和算法的复杂化#xff0c;为数据分析系统带来了严峻的性能挑战。近年来#xff0c;我们可以在数据库、大数据系…简介 作者长别
1. 前言
随着IT基础设施的发展现代的数据处理系统需要处理更多的数据、支持更为复杂的算法。数据量的增长和算法的复杂化为数据分析系统带来了严峻的性能挑战。近年来我们可以在数据库、大数据系统和AI平台等领域看到很多性能优化的技术技术涵盖体系结构、编译技术和高性能计算等领域。作为编译优化技术的代表本文主要介绍基于LLVM的代码生成技术简称Codeden。 LLVM是一款非常流行的开源编译器框架支持多种语言和底层硬件。开发者可以基于LLVM搭建自己的编译框架并进行二次开发将不同的语言或者逻辑编译成运行在多种硬件上的可执行文件。对于Codegen技术来说我们主要关注LLVM IR的格式以及生成LLVM IR的API。在本文的如下部分我们首先对LLVM IR进行介绍然后介绍Codegen技术的原理和使用场景最后我们介绍在阿里云自研的云原生数据仓库产品AnalyticDB PostgreSQL中Codegen的典型应用场景。 2. LLVM IR简介及上手教程
在编译器理论与实践中IR是非常重要的一环。IR的全称叫做Intermediate Representation翻译过来叫“中间表示”。 对于一个编译器来说从上层抽象的高级语言到底层的汇编语言要经历很多个环节(pass)经历不同的表现形式。而编译优化技术有很多种每种技术作用的编译环节不同。但是IR是一个明显的分水岭。IR以上的编译优化不需要关心底层硬件的细节比如硬件的指令集、寄存器文件大小等。IR以下的编译优化需要和硬件打交道。LLVM最为著名是它的IR的设计。得益于巧妙地IR设计LLVM向上可以支持不同的语言向下可以支持不同的硬件而且不同的语言可以复用IR层的优化算法。 上图展示了LLVM的一个框架图。LLVM把整个编译过程分为三步1前端把高级语言转换为IR。(2中端在IR层做优化。(3) 后端把IR转化为对应的硬件平台的汇编语言。因此LLVM的扩展性很好。比如你要实现一个名为toyc的语言、希望运行在ARM平台上你只需要实现一个toyc-LLVM IR的前端其他部分调LLVM的模块就可以了。或者你要搞一个新的硬件平台那么只需要搞定LLVM IR-新硬件这一阶段然后该硬件就可以支持很多种现存的语言。因此IR是LLVM最有竞争力的地方同时也是学习使用LLVM Codegen的最核心的地方。 2.1 LLVM IR基本知识
LLVM的IR格式非常像汇编对于学习过汇编语言的同学来说学会使用LLVM IR进行编程非常容易。对于没学过汇编语言的同学也不用担心汇编其实并不难。汇编难的不是学会而是工程实现。因为汇编语言的开发难度会随着工程复杂度的提升呈指数级上升。接下来我们需要了解IR中最重要的三部分指令格式、Basic Block CFG还有SSA。完整的LLVM IR信息请参考https://llvm.org/docs/LangRef.html。 指令格式。LLVM IR提供了一种类似于汇编语言的三地址码式的指令格式。下面的代码片段是一个非常简单的用LLVM IR实现的函数该函数的输入是5个i32类型(int32)的整数函数的功能是计算这5个数的和并返回。LLVM IR是支持一些基本的数据类型的比如i8、i32、浮点数等。LLVM IR中得变量的命名是以 %开头默认%0是函数的第一个参数、%1是第二个参数依次类推。机器生成的变量一般是以数字进行命名如果是手写的话可以根据自己的喜好选择合适的命名方法。LLVM IR的指令格式包括操作符、类型、输入、返回值。例如 %6 add i32 %0, %1的操作符号是add、类型是i32、输入是%0和“%1”、返回值是%6。总的来说IR支持一些基本的指令然后编译器通过这些基本指令的来完成一些复杂的运算。例如我们在C中写一个形如“A * B C”的表达式在LLVM IR中是通过一条乘法和一条加法指令来完成的另外可能也包括一些类型转换指令。 define i32 ir_add(i32, i32, i32, i32, i32){%6 add i32 %0, %1%7 add i32 %6, %2%8 add i32 %7, %3%9 add i32 %8, %4ret i32 %9
}
Basic Block CFG。了解了IR的指令格式以后接下来我们需要了解两个概念Basic Block(基本块简称BB)和Control Flow Graph(控制流图CFG)。下图(左)展示了一个简单的C语言函数下图中是使用clang编译出来的对应的LLVM IR下图右是使用graphviz画出来的CFG。结合这张图我们解释下Basic Block和CFG的概念。 在我们平时接触到的高级语言中每种语言都会有很多分支跳转语句比如C语言中有for, while, if等关键字这些关键字都代表着分支跳转。开发者通过分支跳转来实现不同的逻辑运算。汇编语言通常通过有条件跳转和无条件跳转两种跳转指令来实现逻辑运算LLVM IR同理。比如在LLVM IR中br label %7意味着无论如何都跳转到名为%7的label那里这是一条无条件跳转指令。br i1 %10, label %11, label %22是有条件跳转意味着这如果%10是true则跳转到名为%11的label否则跳转到名为%22的label。 在了解了跳转指令这个概念后我们介绍Basic Block的概念。一个Basic Block是指一段串行执行的指令流除了最后一句之外不会有跳转指令Basic Block入口的第一条指令叫做“Leading instruction”。除了第一个Basic Block之外每个Basic Block都会有一个名字(label)。第一个Basic Block也可以有只是有时候没必要。例如在这段代码当中一共有5个Basic Block。Basic Block的概念解决了控制逻辑的问题。通过Basic Block, 我们可以把代码划分成不同的代码块在编译优化中有的优化是针对单个Basic Block的有些是针对多个Basic Block的。 CFG(Control Flow Graph 控制流图)其实就是由Basic Block以及Basic Block之间的跳转关系组成的一个图。例如上图所示的代码一共有5个Basic Block箭头列出了Basic Block之间的跳转关系共同组成了一个CFG。如果一个Basic Block只有一个箭头指向别的Block那么这个跳转就是无条件跳转否则是有条件跳转。CFG是编译理论中一个比较简单而且很基础的概念CFG更进一步是DFGData Flow Graph数据流图很多进阶的编译优化算法都是基于DFG的。对于使用LLVM进行Codegen开发的同学理解CFG的概念即可。 SSA。SSA的全称是Static Single Assignment静态单赋值这是编译技术中非常基础的一个理念。SSA是学习LLVM IR必须熟悉的概念同时也是最难理解的一个概念。细心的读者在观察上面列出的IR代码时会发现每个“变量”只会被赋值一次这就是SSA的核心思想。因为从编译器的角度来看编译器不关心“变量”编译器是以“数据”为中心进行设计的。每个“变量”的每次写入都生成了一个新的数据版本编译器的优化是围绕数据版本展开的。接下来我们用如下的C语言代码来解释这一思想。 上图左展示了一段简单的C代码上图右是这短代码的SSA版本也就是“编译器眼中的代码”。在C语言中我们知道数据都是用变量来存储的因此数据操作的核心是变量开发者需要关心变量的生存时间、何时被赋值、何时被使用。但是编译器只关心数据的流向因此每次赋值操作都会生成一个新的左值。例如左边代码只有一个a, 但是在右边的代码有4个变量因为a里面的数据一共有4个版本。除了每次赋值操作会生成一个新的变量最后的一个phi节点会生成一个新的变量。在SSA中每个变量都代表数据的一个版本。也就是说高级语言以变量为核心而SSA格式以数据为核心。SSA中每次赋值操作都会生成一个版本的数据因此在写IR的时候时刻牢记IR的变量和高层语言不同一个IR的变量代表数据的一个版本。Phi节点是SSA中的一个重要概念。在这个例子当中a_4的取值取决于之前执行了哪个分支如果执行了第一个分支那么a_4 a_1, 依次类推。Phi节点通过判断这段代码是从哪个Basic Block跳转而来选择合适的数据版本。LLVM IR自然也是需要开发者写Phi节点的在循环、条件分支跳转的地方往往需要手写很多phi节点这是写LLVM IR时逻辑上比较难处理的地方。 2.2 学会使用LLVM IR写程序
熟悉LLVM IR最好的办法就是使用IR写几个程序。在开始写之前建议先花30分钟-1个小时再粗略阅读下官方手册https://llvm.org/docs/LangRef.html熟悉下都有哪些指令的类型。接下来我们通过两个简单的case熟悉下LLVM IR编程的全部流程。 下面是一个循环加法的函数片段。这个函数一共包含三个Basic Blockloop、loop_body和final。其中loop是整个函数的开始loop_body是函数的循环体final是函数的结尾。在第5行和第6行我们使用phi节点来实现结果和循环变量。
define i32 ir_loopadd_phi(i32*, i32){br label %looploop:%i phi i32 [0,%2], [%newi,%loop_body]%res phi i32[0,%2], [%new_res, %loop_body]%break_flag icmp sge i32 %i, %1br 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, 1br label %loopfinal:ret i32 %res;
}
下面是一个数组冒泡排序的函数片段。这个函数包含两个循环体。LLVM IR实现循环本身就比较复杂两个循环嵌套会更加复杂。如果能够用LLVM IR实现一个冒泡算法基本上就理解了LLVM的整个逻辑了。
define void ir_bubble(i32*, i32) {%r_flag_addr alloca i32, align 4%j alloca i32, align 4%r_flag_ini add i32 %1, -1store i32 %r_flag_ini, i32* %r_flag_addr, align 4br label %out_loop_head
out_loop_head:;check breakstore i32 0, i32* %j, align 4%tmp_r_flag load i32, i32* %r_flag_addr, align 4%out_break_flag icmp sle i32 %tmp_r_flag, 0br i1 %out_break_flag, label %final, label %in_loop_headin_loop_head:;check break%tmpj_1 load i32, i32* %j, align 4%in_break_flag icmp sge i32 %tmpj_1, %tmp_r_flagbr i1 %in_break_flag, label %out_loop_tail, label %in_loop_bodyin_loop_body:;read swap%tmpj_left load i32, i32* %j, align 4%tmpj_right add i32 %tmpj_left, 1%left_addr getelementptr inbounds i32, i32* %0, i32 %tmpj_left%right_addr getelementptr inbounds i32, i32* %0, i32 %tmpj_right%left_val load i32, i32* %left_addr, align 4%right_val load i32, i32* %right_addr, align 4;swap check%swap_flag icmp sge i32 %left_val, %right_val%left_res select i1 %swap_flag, i32 %right_val, i32 %left_val %right_res select i1 %swap_flag, i32 %left_val, i32 %right_valstore i32 %left_res, i32* %left_addr, align 4store i32 %right_res, i32* %right_addr, align 4br label %in_loop_endin_loop_end:;update j%tmpj_2 load i32, i32* %j, align 4%newj add i32 %tmpj_2, 1store i32 %newj, i32* %j, align 4br label %in_loop_head
out_loop_tail:;update r_flag %tmp_r_flag_1 load i32, i32* %r_flag_addr, align 4%new_r_flag sub i32 %tmp_r_flag_1, 1store i32 %new_r_flag, i32* %r_flag_addr, align 4br label %out_loop_head
final:ret void
}
我们把如上的LLVM IR用clang编译器编译成object文件然后和C语言写的程序链接到一起即可正常调用。在上面提到的case中我们只使用了i32、i64等基本数据类型LLVM IR中支持struct等高级数据类型可以实现更为复杂的功能。 2.3 使用LLVM API实现Codegen
编译器本质上就是调用各种各样的API根据输入去生成对应的代码LLVM Codegen也不例外。在LLVM内部一个函数是一个class一个Basic Block试一个class, 一条指令、一个变量都是一个class。用LLVM API实现codegen就是根据需求用LLVM内部的数据结构去实现相应的IR。 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 API实现codegen的例子。其实这就是个用C写IR的过程如果知道如何写IR的话只需要熟悉下这套API就可以了。这套API提供了一些基本的数据结构比如指令、函数、基本块、llvm builder等然后我们只需要调用相应的函数去生成这些对象即可。一般来说首先我们先生成函数的原型包括函数名字、参数列表、返回类型等。然后我们在根据函数的功能确定都需要有哪些Basic Block以及Basic Block之间的跳转关系然后生成相应的Basic。最后我们再按照一定的顺序去给每个Basic Block填充指令。逻辑是这个流程和用LLVM IR写代码是相仿的。
3. Codegen技术分析
如果我们用上文所描述的方法生成一些简单的函数并且用C写出对应的版本进行性能对比我们就会发现LLVM IR的性能并不会比C快。一方面计算机底层执行的是汇编C语言本身和汇编是非常接近的了解底层的程序员往往能够从C代码中推测出大概会生成什么样的汇编。另一方面现代编译器往往做了很多优化一些大大减轻了程序员的优化负担。因此使用LLVM IR进行Codegen并不会获得比手写C更好的性能而且使用LLVM Codegen有一些明显的缺点。想要真正用好LLVM我们还需要熟悉LLVM的特点。 3.1 缺点分析
缺点1开发难。实际开发中几乎不会有工程使用汇编作为主要开发语言因为开发难度太大了有兴趣的小伙伴可以试着写个快排感受一下。即使是数据库、操作系统这样的基础软件往往也只是在少数的地方会用到汇编。使用LLVM IR开发会有类似的问题。比如上文展示的最复杂例子是冒泡算法。开发者用C写个冒泡只需要几分钟但是用LLVM IR写个冒泡可能要一个小时。另外LLVM IR很难处理复杂的数据结构比如结构体、类。除了LLVM IR中的那些基本数据结构外新增一个复杂的数据结构非常难。因此在实际的开发当中采用Codegen会导致开发难度指数级上升。 缺点2调试难。开发者通常通过单步跟踪的方式去调试代码但是LLVM IR是不支持的。一旦代码出问题只能是人肉一遍一遍看LLVM IR。如果懂汇编的话可以通过单步跟踪生成的汇编进行调试但是汇编语言和IR之间并不是简单的映射关系因此只能一定程度上降低调试难度并不完全解决调试的问题。 缺点3: 运行成本。生成LLVM IR往往很快但是生成的IR需要调用LLVM 中的工具进行优化、以及编译成二进制文件这个过程是需要时间的请联想一下GCC编译的速度。在数据库的开发过程中我们的经验值是每个函数大约需要10ms-100ms的codegen成本。大部分的时间花在了优化IR和IR到汇编这两步。 3.2 适用场景
了解了LLVM Codegen的缺点我们才能去分析其优点、选择合适场景。下面这部分是团队在开发过程中总结的适合使用LLVM Codegen的场景。 场景1Java/python等语言。上文中提到过LLVM IR并不会比C快但是会比Java/python等语言快啊。例如在Java中有时候为了提升性能会通过JNI调用一些C的函数提升性能。同理Java也可以调用LLVM IR生成的函数提升性能。 场景2硬件和语言不兼容。LLVM支持多种后端比如X86、ARM和GPU。对于一些硬件与语言不兼容的场景可以利用LLVM实现兼容。例如如果我们的系统是用Java语言开发、想要调用GPU可以考虑用LLVM IR生成GPU代码然后通过JNI的方法进行调用。这套方案不仅支持NVIDIA的GPU也支持AMD的GPU而且对应生成的IR也可以在CPU上执行。 场景3逻辑简化。以数据库为例数据库执行引擎在执行过程中需要做大量的数据类型、算法逻辑相关的判断。这主要是由于SQL中的数据类型和逻辑很多是在数据库开发时无法确定的只能在运行时决定。这一部分过程也被称为“解释执行”。我们可以利用LLVM在运行时生成代码由于这个时候数据类型和逻辑已经确定我们可以在LLVM IR中删除那些不必要的判断操作从而实现性能的提升。 4. LLVM在数据库中的应用
在数据库当中团队是用LLVM来进行表达式的处理接下来我们以PostgreSQL数据库和云原生数据仓库AnalyticDB PostgreSQL为对比解释LLVM的应用方法。
PostgreSQL为了实现表达式的解释执行采用了一套“拼函数”的方案。PostgreSQL中实现了大量C函数比如加减法、大小比较等不同类型的都有。SQL在生成执行计划阶段会根据表达式符号的类型和数据类型选择相应的函数、把指针存下来等执行的时候再调用。因此对于 a 10 and b 5这样的过滤条件假设a和b都是int32PostgreSQL实际上调用了“Int8AndOp(Int32GT(a, 10), Int32LT(b, 5))”这样一个函数组合就像搭积木一样。这样的方案有两个明显的性能问题。一方面这种方案会带来比较多次数的函数调用函数调用本身是有成本的。另一方面这种方案必须要实现一个统一的函数接口函数内部和外部都需要做一些类型转换这也是额外的性能开销。Odyssey使用LLVM 进行codegen可以实现最小化的代码。因为在SQL下发以后数据库是知道表达式的符号和输入数据的类型的因此只需要根据需求选取相应的IR指令就可以了。因此只需要三条IR指令就可以实现这个表达式然后我们把表达式封装成一个函数就可以在执行的时候调用了。这次操作把多次函数调用简化成了一次函数调用大大减少了指令的总数量。
// 样例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;
在数据库中表达式主要出现在几个场景。一类是过滤条件通常出现在where条件中。一类是输出列表一般跟在select之后。有些算子比如join、agg等它的判断条件中也可能会出现一些比较复杂的表达式。因此表达式的处理是会出现在数据库执行引擎的各个模块的。在AnalyticDB PostgreSQL版中开发团队抽象出了一个表达式处理框架通过LLVM Codegen来处理这些表达式从而提高了执行引擎的整体性能。 5. 总结
LLVM作为一个流行的开源编译框架近年来被用于数据库、AI等系统的性能加速。由于编译器理论本身门槛较高因此LLVM的学习有一定的难度。而且从工程上还需要对LLVM的工程特点和性能特征有比较准确的理解才能找到合适的加速场景。阿里云数据库团队的云原生数据仓库产品AnalyticDB PostgreSQL版基于LLVM实现了一套运行时的表达式处理框架能够有效地提高系统在进行复杂数据分析时地性能。
原文链接 本文为阿里云原创内容未经允许不得转载。
