实现了快速的JIT编译器:Julia、PyPy、LuaJIT、Graal等

2020-07-06 05:13:06

这篇文章详细介绍了5+JIT和各种优化策略,并讨论了它们如何与不同的JIT协同工作。这篇博文中的信息是深度优先的,因此有许多重要的概念可以跳过。

有关JIT编译器的背景信息,请参阅JIT编译器深度介绍:JIT不是非常及时的。如果标题对你没有意义,那么它可能值得浏览一下。

我经常描述一种优化行为,并声称它可能存在于其他编译器中。虽然我并不总是检查一个优化是否存在于另一个JIT中(它有时是模棱两可的),但如果我知道它在那里,我总是会明确声明。我还将提供代码示例来说明可能在哪里进行优化,但是该代码不一定会进行优化,因为另一个优化将优先进行。可能也有一些过于简单化的地方,但我认为大多数这样的帖子都不会有太多的简单化。

LuaJIT使用一种称为跟踪的方法。PyPy执行元跟踪,这涉及到使用系统生成跟踪解释器和JIT。PyPy和LuaJIT不是Python或Lua的参考实现,而是它们自己的项目。我会将LuaJIT描述为惊人的快速,它将自己描述为最快的动态语言实现之一--我完全相信这一点。

为了确定何时开始跟踪,解释循环将查找要跟踪的";HOT&34;循环(";HOT&34;代码的概念对JITS是通用的!)。然后,编译器将跟踪循环,记录执行的操作,以编译优化良好的机器码。在LuaJIT中,使用LuaJIT独有的类似指令的IR在跟踪上执行编译。

PyPy将在1619次执行后开始跟踪一个函数,并在另外1039次执行后编译它,这意味着一个函数必须执行大约3000次才能开始加速。这些常量是由PyPy团队仔细调优的(很多常量一般都是为编译器调优的!)。

动态语言使优化变得很困难。下面的代码可以通过更严格的语言静态消除,因为False总是False。然而,在Python2中,这在运行前是无法保证的。

对于任何正常的程序,条件总是为假。不幸的是,false的值可能会被重新赋值,因此如果语句在循环中,它可能会在其他地方重新定义。在本例中,PyPy将构建一个警卫。当保护失败时,JIT将退回到解释循环。然后,PyPy使用另一个常量(200),称为跟踪迫切性来决定是否编译新路径的其余部分,直到循环结束。该子路径称为网桥。

PyPy还将所有这些常量公开为可以在执行时调整的参数,以及用于展开(展开循环)和内联的配置!它还公开了一些钩子,这样我们就可以看到什么时候进行了编译。

在上面,我设置了一个带有编译挂钩的普通Python程序来打印编译类型。它还在末尾打印一些数据,我可以在那里看到警卫的人数。对于上面的代码,我得到了一个循环和66个警卫的编译。当我将if语句替换为只在for循环下传递时,我只剩下59个警卫。

将这两行添加到for循环中后,我将获得两个编译,新的编译类型为#39;bridge';!

元跟踪背后的概念是“编写解释器,免费获得编译器!”或者更神奇的是,“把你的解释器变成JIT编译器!”这显然是一件很棒的事情,因为编写编译器很难,所以如果我们能免费得到一个很棒的编译器,那就是一笔不错的交易。PyPy&34;有一个解释器和一个编译器,但是没有显式的传统编译器实现。

PyPy有一个名为RPython的工具链(它是为PyPy构建的)。它是一个用于实现解释器的框架程序。它是一种语言,因为它指定了Python语言的子集,即强制执行静态类型之类的操作。这是一种编写解释器的语言。它不是一种用类型化Python编写代码的语言,因为它不关心或不具有标准库或包之类的东西。任何RPython程序都是有效的Python程序。RPython程序被转换成C语言,然后编译。因此,RPython元编译器作为编译后的C程序存在。

元跟踪中的“元”来自这样一个事实,即跟踪是在解释器的执行上,而不是在程序的执行上。解释器的行为或多或少与任何解释器一样,增加了跟踪自己的操作的能力,并通过更新解释器(本身)的路径来优化这些跟踪。随着进一步的跟踪,解释器所采用的路径变得更加优化。如果一个非常优化的解释器采用特定的优化路径,则在该路径中使用的编译后的RPython机器码可以用作编译。

简而言之,PyPy中的“编译器”正在编译您的解释器,这就是PyPy有时被称为元编译器的原因。编译器较少用于您试图执行的程序,而是用于编译优化解释器的跟踪!

元竞速可能会让人困惑,所以我写了一个非常糟糕的元竞速程序,它只能理解a=0和a++来说明。

#用RPython为代码中的行编写的解释器:if line==";a=0";:alloc(a,0)elif line==";a++";:Guard(a,";is_int";)#注意在Python中,类型是未知的,但被RPython解释后,类型是已知的Guard(a,";>;0";)int_add(a,1)。

#热循环众多日志中的跟踪a=alloc(0)#警卫可以离开a=int_add(a,1)a=int_add(a,2)#优化要编译的跟踪a=alloc(2)#执行此跟踪的代码段是编译后的代码。

但是编译器不是什么特殊的独立单元,它是内置在解释器中的!所以解释器循环实际上应该是这样的。

对于代码中的行:如果跟踪。IS_COMPILED(行):RUN_COMPILED(跟踪。编译(行))继续ELIF轨迹。IS_OPTIMIZED(行):编译(跟踪。优化(行))继续elif line==";a=0";#.。

HotSpot(以查找HotSpot命名)是随Java标准安装一起提供的VM,实际上其中有多个编译器用于分层策略。HotSpot是开源的,有250,000行代码,其中包含编译器和三个垃圾收集器。它在成为一个优秀的JIT方面做得非常棒,有一些基准测试使HotSpot可以与C++Imp相提并论(哦,天哪,这上面有这么多星号,你可以在谷歌上找到所有的争论)。虽然HotSpot不是跟踪JIT,但它采用了类似的方法,即有一个解释器,分析,然后编译。HotSpot所做的工作没有一个具体的名称,尽管最接近的分类可能是Tiering JIT。

HotSpot中使用的策略启发了许多后续的JIT,语言VM的结构,特别是Javascript引擎的开发。它还创造了一波JVM语言,如Scala、Kotlin、JRuby或Jython。JRuby和Jython是Ruby和Python的有趣实现,它们将源代码编译成JVM字节码,然后让Hotpot执行它。这些项目在加速Python和Ruby等语言方面相对成功(Ruby比Python更快),而不必像PyPy那样实现整个工具链。HotSpot的独特之处还在于它是动态程度较低的语言的JIT(尽管从技术上讲它是JVM字节码的JIT,而不是Java)。

GraalVM是一种JavaVM,甚至更多,用Java编写。它可以运行任何JVM语言(Java、Scala、Kotlin等)。它还支持原生映像,以允许AOT编译的代码通过称为底层VM的东西。Twitter的很大一部分Scala服务都是使用Graal运行的,所以它一定相当不错,尽管是用Java编写的,但在某些方面比JVM要好。

但是等等,还有更多!GraalVM还提供了Truffle,这是一个通过构建抽象语法树(AST)解释器来实现语言的框架。使用Truffle,没有像传统JVM语言那样创建JVM字节码的显式步骤,相反,Truffle只需使用解释器并与Graal通信,通过分析和称为部分求值的技术直接创建机器码。部分求值超出了这篇博客文章的范围,tl;dr它遵循元竞赛的“编写解释器,免费获取编译器”的理念,但采用了不同的方法。

TruffleJS,Javascript的Truffle实现在选定的基准测试上优于JavaScript V8引擎,这真的令人印象深刻,因为V8已经有了无数年的开发,Google金钱+资源涌入,以及一些疯狂的熟练人员在致力于它。TruffleJS在大多数方面仍然不比V8(或其他JS引擎)“更好”,但它是Graal前景光明的标志。

JIT实现的一个常见问题是支持C扩展。标准解释器,如Lua、Python、Ruby和PHP都有一个C API,允许用户用C构建包,从而使执行速度大大加快。常用的包(如numpy)或标准库函数(如rand)都是用C语言编写的。这些C扩展对于让这些解释语言在实践中快速运行至关重要。

由于各种原因,很难支持C扩展支持,最明显的原因是API是以内部实现细节为模型的。此外,当解释器用C编写时,支持C扩展会更容易,因为JRuby不支持C扩展,但有Java扩展API。PyPy最近推出了对C扩展的测试版支持,不过我不确定它的可用性,这在很大程度上要归功于Hyrum定律。LuaJIT确实支持C扩展,以及C扩展中的附加特性(LuaJIT非常棒!)。

Graal用Sulong解决了这个问题,Sulong是一个引擎,通过将LLVM Bitcode变成一种Truffle语言在GraalVM上运行LLVM Bitcode。LLVM是一个工具链,尽管我们需要知道的就是C可以编译成LLVM位代码(Julia也有一个LLVM后端!)。这有点奇怪,但基本上解决方案是用一种有40多年历史的完美的编译语言来解释它!当然,它并不像正确编译C语言那样快,但是这里隐藏着一些胜利。

LLVM Bitcode已经相当低级了,这意味着使用Jitcode的IR不如使用JingC的效率低,因为位代码可以与Ruby程序的其余部分一起优化,而编译后的C程序则不能。所有的分配移除、内联、死代码消除等都可以在C和Ruby代码上一起运行,而不是Ruby代码只调用C二进制代码。部分基准测试甚至让TruffleRuby C扩展比CRuby C扩展运行得更快。

要让这个系统工作,应该知道,Truffle AST是完全与语言无关的,并且在C、Java或Graal中的任何语言之间切换的开销最小。

Graal与Sulong一起工作的能力是其多语言功能的一部分,这提供了语言之间的高度互操作性。它不仅对编译器很有帮助,而且也是一种概念证明,可以在一个应用程序中轻松使用多种语言。

我们知道JIT附带一个解释器和一个编译器,并且它们从解释器移动到编译器以获得更快的速度。PyPy设置了采取相反路径的桥梁,尽管对于Graal和HotSpot来说,它们是去优化的。这两个术语指的并不是严格意义上的不同概念,但取消优化更多地指的是将其作为有意优化而不是动态语言必然性的解决方案传回解释器。HotSpot和Graal都积极利用反优化--Graal,特别是当工程师对编译有很大的控制,需要对编译进行更多的控制以进行优化时(比方说,与PyPy相比)。去优化也用在诸如V8这样的JS引擎中,我将对其进行大量讨论,因为它支持Chrome和Node.js中的Javascript。

快速取消优化的一个重要组成部分是确保从编译器切换到解释器的速度越快越好。最幼稚的实现将导致解释器必须“赶上”编译器,以便能够做出取消选择。在处理取消优化异步线程时存在额外的复杂性。为了取消优化,Graal将重新创建堆栈帧,并使用生成代码的映射返回到解释器。对于线程,使用Java线程中的安全点,这些安全点可以让线程不断地暂停并发出“嗨,垃圾收集器,我现在要停止吗?”因此,处理线程不会增加太多开销。这有点困难,但速度足够快,可以使取消优化成为一个很好的策略。

与PyPy桥接示例类似,函数的猴子补丁可以取消优化。那里的反优化实际上更优雅,因为它不是在守卫失败时发生的反优化,而是在发生猴子修补的地方添加反优化代码。

JIT去优化的一个很好的例子是转换溢出,它不是一个超级官方术语,但通常指的是特定类型(比如int32)在内部表示/分配,但需要变成int64。这是TruffleRuby和V8通过去优化所做的事情。

假设您在Ruby中设置var=0,您将得到int32(Ruby实际上将其称为Fixnum和Bignum,但我将继续使用int32和int64)。无论何时对var执行操作,都必须检查结果值是否溢出。然而,检查是一回事,编译处理溢出的代码是昂贵的,特别是考虑到数字操作是多么常见。

即使不查看已编译的指令,我们也可以看到这种取消优化如何简化了处理所需的代码量。

int a,b;int sum=a+b;if(溢出){long bigSum=a+b;return bigSum;}Else{return sum;}int a,b;int sum=a+b;if(溢出){取消优化!}。

对于TruffleRuby,它被设计为仅在第一次运行特定操作时取消优化,因此不会在操作持续溢出时花费每次取消选择的成本。

函数foo(a,b){return a+b;}for(var i=0;i<;1000000;i++){foo(i,i+1);}foo(1,2);

在V8中,即使是如此微不足道的事情也会触发取消选择!使用--trace-deopt和--trace-opt这样的选项,可以收集大量关于JIT的数据并修改行为(Graal也有非常全面的工具,不过我将使用V8,因为人们可能已经安装了Node)。

触发deopt的是最后一行(foo(1,2)),这令人费解,因为完全相同的调用是在循环中进行的!消息是“Call的类型反馈不足”(您可以在这里找到取消原因的完整列表,有趣的是,其中包括一个“没有原因”的原因)。输出给我们一个输入框,它向我们显示文字1和2。

那么为什么要取消优化呢?V8应该足够智能,可以输入推断,即i的类型是整数,并且传入的文字也是整数。

我可以通过将最后一行替换为foo(i,i+1)来研究这个问题,但是我实际上仍然得到了一个取消优化,尽管这一次的消息是“二元操作的类型反馈不足”。为什么我会问为什么它和我在循环中用相同的变量运行的操作是一样的。

我的朋友,答案是迎风而来的堆上更换(OSR)。内联是一种强大的编译器优化(不仅仅是JIT),其中函数不再是函数,而是在调用点扩展内容。JIT可以通过在运行时更改代码来提高速度(编译语言只是静态内联)。

//打印内联详细信息的部分输出[使用turbofan OSR编译方法0x04a0439f3751<;JSFunction(SFI=0x4a06ab56121)>;]0x04a06ab561e9<;SharedFunctionInfo Foo>;:IsInline?调用位置#49处的true内联小函数:JSCall。

因此,V8将编译foo并确定它是可内联的,并使用OSR将其内联。但是,它只对循环中的代码执行此内联,因为它是热路径,而在执行此内联时,最后一行对于解释器来说并不真正存在。因此,V8对于函数foo仍然没有足够的类型反馈,因为它实际上并没有在循环中使用--内联版本是。如果I--no-use-OSR,那么反优化就不会发生--不管我是否传递了一个文字或i。然而,如果没有内联,即使是微不足道的百万次迭代也会明显变慢。JIT真正体现了没有解决方案,只有权衡取舍。取消优化的成本很高,但远没有方法查找的成本高,在这种情况下,内联更受欢迎。

衬里太有效了!我用几个额外的零运行上面的代码,在禁用内联的情况下速度慢了4倍。

虽然这是一篇关于JIT的博客文章,但是内联对于编译语言也非常有效。所有LLVM语言都将积极地内联(因为LLVM将内联),尽管Julia实际上没有内联LLVM,因为它不稳定。JIT可以内联来自运行时信息的启发式规则,并且可以使用OSR从非内联切换到内联。

需要考虑的工具链是LLVM,它提供了大量与编译器基础设施相关的工具。Julia使用LLVM(请注意,它是一个很大的工具链,每种语言的使用方式都不同),以及Rust、Swift和Crystal。可以说,这是一个重要而令人惊叹的项目,当然也支持JIT,但是还没有真正使用LLVM构建任何重要的动态JIT。JavaScriptCore的第四层编译器曾短暂使用过LLVM后端,但在不到两年的时间里就被替换了。一般来说,LLVM并不能很好地适应动态JIT,因为它不是为了应对动态的独特挑战而设计的。PyPy已经尝试了大约5到6次,但JSC实际上还是使用了它!使用LLVM,分配下沉和代码移动受到限制。强大的JIT特性,如范围推断(如类型推断,但也知道值的范围)是不可能的。最重要的是,LLVM具有非常昂贵的编译时间。

如果我们没有像其他人那样基于指令的IR,而是有一个大的图形,并且它可以自我修改,那会怎么样。

我们已经看过LLVM位码和Python/Ruby/Java风格的字节码作为IR-它们共享某种看起来像指令的语言的相同格式。HotSpot、Graal和V8有一个名为节点之海的IR(由HotSpot首创),本质上是一个较低级别的AST。人们可以想象节点的海洋是如何有效的IR,因为很多分析工作都是基于某条路径不经常被采用(或以特定模式被遍历)的概念。请注意,这些编译器AST不同于解析器AST。

我通常完全赞成在家里试一下!但是让图形浏览实际上有点困难,尽管很有趣,而且通常对理解编译器流程非常有帮助。例如,我不能阅读所有的图表,不仅受知识的限制,而且还受我大脑的计算能力的影响(这可以通过编译器选项来调节,以消除我不关心的行为)。

对于V8,您需要构建V8,然后使用带有标志--print-ast的D8工具。对于Graal,--vm.Dgr。

..