一种用于JIT'ing算法和数据结构与LLVM方法

llvm_dragon

你好人,我总是张贴关于Python和EvoComp(Pyevolve),但这次是关于C,LLVM,搜索算法和数据结构。这篇文章描述了实现一个想法的努力:以JIT(动词)算法和由它们所使用的,一起的数据结构。

AVL树简介

下面是一个简短的介绍,以AVL树维基百科:

在计算机科学中,AVL树是一个平衡树,它是被发明第一个这样的数据结构。在AVL树,任何节点的两个子子树的高度最多由一个不同;因此,它也被认为是高度平衡。查找,插入和删除都以O(日志ñ)时间的平均和最坏情况下,两个,其中n是节点在树中的号码之前,该操作。插入和缺失可能需要树由一个或多个树旋转来重新平衡。

问题和想法

当我们有一个数据结构和算法来处理(插入,删除和查找),其结构,我们的算法的本地代码通常是满的开销;例如,在一个AVL树(平衡二叉树),开销出现在:检查,如果我们真的有左或右节点,而对于遍历查找节点,接入节点内的节点,等这方面的负担造成不必要的组装业务,其在转,创建本机代码的开销,甚至当编译器优化。此开销对我们的算法的性能直接影响(这种传统的做法,当然,给我们一个非常灵活的结​​构和复杂性(亚洲金博宝没有大O)容易处理,但我们为它付出:性能损失)。

But if you think a little more on how we can improve the lookup performance and how we can remove that overhead from the native code, you’ll discover that we can simply translate the data structure and the algorithm in the native code ITSELF, let me explain it a little better (I will always use the AVL Tree example), when we are looking for a key in an AVL tree, we do something like this (遗憾的GT - 大于 - 和LT - 小于 - ,WordPress的混乱与HTML):

lookup_key = 10;//我们正在搜索节点的关键=树的根;而真{如果(lookup_key == node.key)返回节点;如果(lookup_key LT node.key){如果我们没有左节点,返回False;别的节点= node.left_child;}如果(lookup_key GT node.key){如果我们没有一个合适的节点,返回False;别的节点= node.right_child;}}

正如你可以注意到,这是所有AVL树尺寸的通用算法。在这里我们的方法来开销连同数据结构删除和JIT的算法。让我们做一个例子,这里是AVL树,我们将转换为代码:

jit_avl

这AVL树,当翻译成代码,可以看作是这样的:

lookup_key = 10;如果(lookup_key == 2)返回2;如果(lookup_key LT 2){如果(lookup_key == 1)返回1;否则返回-1;}如果(lookup_key GT 2){如果(lookup_key == 5)返回5;如果(lookup_key LT 5){如果(lookup_key == 4)返回4;否则返回-1;}如果(lookup_key GT 5){如果(lookup_key == 6)返回6;否则返回-1;}}

如果你比较该算法与现有一个,你会注意区别:这种算法是算法和数据结构本身。它像展开了传统的AVL查找算法的循环。

To codegen an AVL Tree into this code, it’s not very simple as it seems, because to codegen it with LLVM, we must use a a restricted Intermediate Representation (IR), this IR of LLVM uses a RISC-like instruction set, so we must convert this algorithm above into that IR using conditional branching and comparison instructions for later encapsulate it in a function.

实施

我已经使用了LLVM 2.6和C绑定来实现这个算法。对于AVL树结构,我已经使用了GLib的AVL实施我已经使用了相同的结构做性能对比。LLVM的C绑定都没有记录,看到这个帖子的最后的音符,如果你愿意使用它们。
整个源代码可在SVN信息库

我实现了这样的CODEGEN IR:

我第一次CODEGEN一个分支,当我们正在寻找不存在的AVL重点,这个分支被称为BRNULL打电话,只是返回-1整数,这意味着查找功能都没有发现的关键。

然后,我先序AVL树的遍历的每个节点添加到栈,并弹出每个项目创建的每个两个分支:EQ [关键],DIF [关键]。例如,对于键“1”,余创建EQ1和DIF1,对于键2,I创建EQ2和DIF2,ANS等。后来,当我们弹出堆栈中的最后一个项目,我们插入一个特殊的“入口”分支,这将是在IR功能的入口点。

你可以看到更多关于此实现通过查看功能的源代码被称为“translate_avl_tree“ 在里面SVN仓库

下面是一个AVL树创建尺寸5的IR,在AVL中的节点是[0,1,2,3,4]:

;的moduleId = '' 限定内部I32 @avllookup(I32){条目:%Equality6 = ICMP当量I32%0,1;[#用途= 1] BR I1%Equality6,标号%EQ1,标号%DIF1 BRNULL:;preds =%DIF0,%DIF2,%DIF4保留I32 -1 EQ4:;preds =%BR4保留I32 4 DIF4:;preds =%BR4 BR标记%BRNULL BR4:;preds =%DIF3%平等= ICMP当量I32%0,4;[#用途= 1] BR I1%平等,标号%EQ4,标号%DIF4 EQ2:;preds =%BR2保留I32 2 DIF2:;preds =%BR2 BR标记%BRNULL BR2:; preds = %DIF3 %Equality1 = icmp eq i32 %0, 2 ; [#uses=1] br i1 %Equality1, label %EQ2, label %DIF2 EQ3: ; preds = %BR3 ret i32 3 DIF3: ; preds = %BR3 %Equality2 = icmp sgt i32 %0, 3 ; [#uses=1] br i1 %Equality2, label %BR4, label %BR2 BR3: ; preds = %DIF1 %Equality3 = icmp eq i32 %0, 3 ; [#uses=1] br i1 %Equality3, label %EQ3, label %DIF3 EQ0: ; preds = %BR0 ret i32 0 DIF0: ; preds = %BR0 br label %BRNULL BR0: ; preds = %DIF1 %Equality4 = icmp eq i32 %0, 0 ; [#uses=1] br i1 %Equality4, label %EQ0, label %DIF0 EQ1: ; preds = %entry ret i32 1 DIF1: ; preds = %entry %Equality5 = icmp sgt i32 %0, 1 ; [#uses=1] br i1 %Equality5, label %BR3, label %BR0

这里是avllookup创建(点击放大)红外功能的点图:

IMG

在LLVM IR的条件分支的语法是:

%COND =

ICMP

当量I32%A,%B BR I1%COND,标号%IfEqual,标号%IfUnequal

该“条件”是跳转到另一个标签,如果条件的结果是成立的情况下,第一个标签(“IfEqual“)通过作为论据“BR”指令将成为下一个标签去,否则标签“IfUnequal”会成为下一个。该“ICMP”指令是比较指令,以获取更多信息,请参阅LLVM汇编语言参考。在上面的曲线图中,分支被表示为与所述标签的矩形流动以下(T = True时,F =假)的方向。

该“RET”是返回指令,它的语法是:

RET I32 5

;返回的5的整数值

这是自explicative。
翻译AVL树到IR的这个阶段是相当快使用LLVM API的时候,其实,它tooks只需0.64秒,CODEGEN 10.000节点的AVL树
在那之后,我执行了LLVM转型通行证在创建函数(请参见“run_passes”源代码),这个阶段是非常快的太多,亚洲金博宝它tooks 0.55秒至变换10.000节点的AVL树的IR(向下滚动,看到一些性能图表)。
所有这些阶段后,我们终于做了最好的一部分,我们JIT使用LLVM执行引擎产生的本地代码的功能。这个阶段的,可惜的是,JIT'ing算法,例如最慢的部分,花了4.20秒,JIT的AVL树4.000节点。但即使有这方面的开销编译AVL树功能,本机代码,我得到的25%的性能的平均在传统的AVL搜索算法。
按照在阶段中的每一个中度过,为JIT编译和新方法和传统的AVL搜索方法的比较次的图表。
第一个图表是的花费JIT'ing不同AVL树的大小的时间的曲线图:

graph_jit_compile

x轴是AVL树尺寸(树中的节点的数量),y轴是花费转换的时间(以秒计)AVL树本机代码。
第二曲线示出了花费创建使用AVL树(代码生成)和运行优化(LLVM通行证)的功能的时间:

llvm_passes_codegen

该图是自explicative。
而下图,是比较传统的AVL查找方法VS的JIT'ed AVL树查找图表:

jit_avl_vs_nonjit

x轴是AVL树尺寸(树中的节点的数量),并且y轴在亿个随机密钥查找花费的时间。
正如你所看到的,相比传统的AVL树查找使用JIT'ed AVL树查找(无需编译,运行通行证的开销,等等)执行(平均)28%更好
But if we consider the overhead of codegen+passes+JIT’ing the created function, for larger trees (> 4.000) nodes, when the green line (AVL JIT’ed Tree + overhead) crosses the blue line, the overhead of time spent in JIT’ing the function, becomes more slower than the traditional AVL lookup methods.

如何代码看起来像

看看的SVN信息库

结论

对于小AVL树(少于〜3.000节点),我们可以得到的26%,比传统方法的平均性能,对于AVL树超过3.000节点和小于4.000的节点,我们可以得到13%的平均业绩,但与AVL超过4.000的节点,我们在编译AVL树为本地代码比使用传统的AVL树查找的方法更慢的开销节点。

The successful performance of using this method to JIT search algorithms and data structures, can be very useful when you doesn’t have to JIT it so many times (when you change the AVL Tree), because when we insert or remove nodes from the AVL Tree, it must be reJIT’ed to reflect these changes.
But if you have some CPU idle time, you can adapt a hybrid algorithm to JIT it in this idle time and when you had changed the Tree and you had not yet JIT’ed the new data structure, you can simple use the traditional method, I think that this is the perfect situation for a method like this,因为你可以在上图看到,红线(新方法),与蓝线(传统方法)相比,总是有更好的表现,30%的附近!

其他用途和限制

这种方法可以用来JIT其他数据结构和算法,对AVL树只是什么可以做一个例子。我认为有,使我们可以比传统方法获得的性能超过30%的其他情形。
这个实施AVL树的限制是:
1)它采用的键和值的固定的数据类型(整数),但可以写一个更好的算法来CODEGEN不同的数据类型;
2)当您更改AVL树,你必须reJIT它;
3)使用的内存更大,因为你有两个传统的AVL树,LLVM IR并同时在内存中,或许有办法进一步提高这一JIT'ed功能;
4)这只是一个的PoC,该翻译算法和源的其他部分可以增强什么手段。

LLVM上的注意事项

LLVM是非常非亚洲金博宝常有趣和有用的项目,该代码生成和转换是非常快的!Unfortunatelly, just the JIT compile is a bit slow for large codes (like a large AVL Tree), but you should note that sometimes, JIT’ing a function just one time is enough to create a better performance, it depends of the dynamics of your problem.
可惜的是,我引述前,LLVM C绑定没有记载,但代码很干净亚洲金博宝和你有LLVM C ++ API的一个很好的文档。
有一些事情中,我花了一些时间:
1)您必须调用初始化函数使用LLVM的JIT执行引擎,否则你会得到空的错误字符串(很难后才找到原因嘿嘿):亚洲金博宝

LLVMLinkInJIT();LLVMInitializeNativeTarget();

2)如果设置了快速调用约定的函数,就像这样:

LLVMSetFunctionCallConv(FUNC,LLVMFastCallConv);

您必须设置属性“快速调用”在你的函数指针使用宏:

的typedef INT(* jit_avl_lookup_t)(INT)__attribute __((FASTCALL));

否则,你会得到非常非常奇怪的错误,亚洲金博宝像调用JIT'ed功能之前插入代码中的“printf”上,它可以改变函数返回的结果(这是真的!)

我希望你喜欢=)

- 基督教S. Perone

引用本文为:基督教S. Perone,“A为JIT'ing算法和数据结构与LLVM方法,”在亚洲金博宝未知领域,22/11/2009,//www.cpetem.com/2009/11/a-method-for-jiting-algorithms-and-data-structures-with-llvm/

6个想法“一种用于JIT'ing算法和数据结构与LLVM”

  1. 我喜欢这个主意编译二叉搜索树?你为什么要建立和AVL?你为什么不只是建立从数字的排序序列中的树?

发表评论

您的电子邮件地址不会被公开。

本网站使用的Akismet,以减少垃圾邮件。了解您的意见如何处理数据