高級(jí)語(yǔ)言程序中的數(shù)據(jù)結(jié)構(gòu)優(yōu)化

1、中南大學(xué)本科生畢業(yè)論文（設(shè)計(jì)）論文翻譯 題 目 數(shù)據(jù)結(jié)構(gòu)可視化實(shí)驗(yàn)平臺(tái) 學(xué)生姓名 祝 杰 指導(dǎo)教師 余 臘 生 學(xué) 院 信息科學(xué)與工程學(xué)院 專業(yè)班級(jí) 計(jì)科0902班 完成時(shí)間 2013年4月 14高級(jí)語(yǔ)言程序中的數(shù)據(jù)結(jié)構(gòu)優(yōu)化基于分級(jí)的可擴(kuò)展編譯器新方向Tiark Rompf Arvind K.Sujeeth Nada AminKevin J. Browny Vojin Jovanovic HyoukJoong Leey Manohar Jonnalagedda Kunle Olukotuny Martin Odersky瑞士洛桑理工大學(xué): first.lastepfl.chOracle實(shí)驗(yàn)室斯

2、坦福大學(xué): asujeeth, kjbrown, hyouklee, 摘要高層次的數(shù)據(jù)結(jié)構(gòu)是現(xiàn)代編程的基石，同時(shí)也阻礙了編譯器優(yōu)化。為了解釋用戶或庫(kù)定義的數(shù)據(jù)結(jié)構(gòu)，編譯器需要具備可擴(kuò)展性。擴(kuò)展編譯器的通用機(jī)制分為兩類。前端宏，分級(jí)或部分評(píng)估系統(tǒng)，可用于在程序進(jìn)入編譯器前以編程的方式刪除抽象，進(jìn)行相應(yīng)的具象化。此外，有些編譯器通過(guò)在編譯過(guò)程中添加新的變型或增加新的中間表示（IR）類型來(lái)擴(kuò)展編譯內(nèi)部的運(yùn)作。這兩者單獨(dú)都不足以處理高層次的數(shù)據(jù)結(jié)構(gòu)所帶來(lái)的挑戰(zhàn)。本文展示了一種新穎的方式將兩者結(jié)合起來(lái)，這種方式所產(chǎn)生效益遠(yuǎn)遠(yuǎn)大于兩者效益之和。分段技術(shù)不僅可以用于前端，我

3、們?cè)趦?nèi)部編譯器變型中也可以使用分段。這些內(nèi)部類型通過(guò)程序的執(zhí)行來(lái)創(chuàng)建變型IR。總所周知，分段可以簡(jiǎn)化程序的生成，并可以通過(guò)同樣的方式簡(jiǎn)化程序的轉(zhuǎn)換。把轉(zhuǎn)化定義為階段IR解釋器比在IR轉(zhuǎn)化器上實(shí)現(xiàn)低級(jí)的IR要來(lái)得簡(jiǎn)單。通過(guò)自定義IR節(jié)點(diǎn)，很多被表示為從IR節(jié)點(diǎn)到分級(jí)程序片段的重寫(xiě)的優(yōu)化可以被整合成一個(gè)變型，以緩和無(wú)序問(wèn)題。推理性的重寫(xiě)可以在循環(huán)結(jié)構(gòu)周?chē)３謽?lè)觀的判斷。我們演示了幾個(gè)使用了這種架構(gòu)而且功能特別強(qiáng)大的程序優(yōu)化方式，它們面向以下數(shù)據(jù)結(jié)構(gòu)：一個(gè)新的循環(huán)融合和砍伐森林算法，結(jié)構(gòu)數(shù)組到數(shù)組的結(jié)構(gòu)之間的轉(zhuǎn)換，面向多樣并行設(shè)備的對(duì)象扁平化和代碼生成。我們通過(guò)一些展現(xiàn)出巨大加速的不平凡的案例研究來(lái)

4、驗(yàn)證我們的方法。分類和主題描述D.3.4編程語(yǔ)言：處理器-代碼生成，優(yōu)化，運(yùn)行時(shí)環(huán)境；D.1.3編程技術(shù)：并發(fā)程序設(shè)計(jì)-并行程序設(shè)計(jì)通用術(shù)語(yǔ)設(shè)計(jì)，語(yǔ)言，性能關(guān)鍵詞分級(jí)，代碼生成，數(shù)據(jù)結(jié)構(gòu)，可擴(kuò)充編譯程序/ 向量object Vector def fromArrayT:Numeric(a: ArrayT) =new Vector val data = a def zerosT:Numeric(n: Int) =Vector.fromArray(Array.fill(n)(i = zeroT)abstract class VectorT:Numeric val data: ArrayTdef +(

5、that: VectorT) =Vector.fromArray(data.zipWith(that.data)(_ + _) ./ 矩陣abstract class MatrixT:Numeric . / 復(fù)數(shù)case class Complex(re: Double, im: Double) def +(that: Complex) = Complex(re + that.re, im + that.im)def *(that: Complex) = .圖 1. 高等級(jí)的Scala線性代數(shù)包的框架1. 引言將高級(jí)語(yǔ)言程序編譯成低級(jí)語(yǔ)言程序是很難的，特別是因?yàn)檫@樣的程序，使用了高層次的抽象和

6、定義。編譯器無(wú)法看穿這些抽象和定義（“抽象代價(jià)”），它不能推理出領(lǐng)域特有的屬性（“通用瓶頸”）。數(shù)據(jù)結(jié)構(gòu)和操作集是其中最重要的抽象，也是目前被認(rèn)為最難使用到優(yōu)化編譯程序中的。讓我們考慮在Scala中的高級(jí)語(yǔ)言編程實(shí)例。我們要實(shí)現(xiàn)一個(gè)稠密線性代數(shù)包。圖1顯示了一個(gè)通過(guò)Array擴(kuò)展而來(lái)的Vector和Matrix的框架，框架內(nèi)部使用了高級(jí)操作集（fill，zipWith）。Vector和Matrix包含數(shù)值類型（模板類Numeric）。我們同時(shí)定義復(fù)數(shù)為一個(gè)新的數(shù)字類型。有了這些定義，我們可以像這樣編寫(xiě)程序：def diag(k:Int) = k * Matrix.identity(n)val

7、m1 = (v1+v2).transpose * (v1+v2)val m2 = diag(l)if (scale) println(m1*m2) / = m1*(k*id) = k*m1*id = k*m1else println(m1) / 不需要計(jì)算 m2這樣的代碼優(yōu)雅而高級(jí)，展示了Scala如何將注意力集中在抽象和歸納發(fā)展生產(chǎn)力的提高。不幸的是，代碼將運(yùn)行得很慢，比已經(jīng)調(diào)整過(guò)只使用數(shù)組和while循環(huán)的低級(jí)實(shí)現(xiàn)方式慢一到兩個(gè)數(shù)量級(jí)（見(jiàn)第5部分）。到底是什么回事？部分原因是：1）無(wú)論是Scala編譯器還是JVM中的及時(shí)編譯器都無(wú)法將諸如公共子表達(dá)式或冗余代碼消除（CSE，DCE），通用優(yōu)

8、化成非平凡的矩陣或矢量計(jì)算。2) 編譯器對(duì)于像m*id = m（其中m是一個(gè)矩陣, id是單位矩陣）這樣可以進(jìn)行優(yōu)化的特定領(lǐng)域的規(guī)則沒(méi)有任何概念。3) 在函數(shù)式編程風(fēng)格中，編程過(guò)程中會(huì)產(chǎn)生很多中間對(duì)象。4) 統(tǒng)一的JVM堆分配的對(duì)象無(wú)法表示復(fù)數(shù)。為了使編譯器能夠理解高級(jí)語(yǔ)言的抽象和定義，我們需要一種機(jī)制來(lái)擴(kuò)展編譯器以便于它能夠處理這些抽象。有兩個(gè)常見(jiàn)的方法。第一種是在程序編譯前進(jìn)行翻譯，這樣編譯器就不需要知道這些抽象和定義。這是宏系統(tǒng)和分段的原理。部分求值（PE）也可以在程序編譯前對(duì)其進(jìn)行詳細(xì)說(shuō)明。第二種選擇是教會(huì)編譯器領(lǐng)域相關(guān)的規(guī)則。通常，編譯器的可擴(kuò)展性被理解為增加新的階段的一種手段。一些

9、可擴(kuò)展的編譯器還允許添加新的IR類型，但新的節(jié)點(diǎn)與現(xiàn)有的通用的優(yōu)化互相之間如何影響一般都沒(méi)有明確。然而，兩種方法都不足以單獨(dú)解決高級(jí)數(shù)據(jù)結(jié)構(gòu)與抽象定義帶來(lái)的挑戰(zhàn)?；氐轿覀兊睦?，如果我們只有階段或宏，表達(dá)m * id，也就是m，在到達(dá)編譯器前就會(huì)被擴(kuò)展為循環(huán)，所以我們無(wú)法對(duì)m進(jìn)行化簡(jiǎn)。在一般情況下，有限的形式化簡(jiǎn)可以添加（見(jiàn)C+ expression templates51）如果想要添加進(jìn)來(lái)的化簡(jiǎn)生效，所有的通用的編譯器優(yōu)化（CSE，常數(shù)傳遞，等）也會(huì)需要被復(fù)制。在另一方面，如果我們已經(jīng)能夠添加新的編譯器關(guān)口，我們可以添加一個(gè)把m * id優(yōu)化為m的關(guān)口，但是我們需要另一個(gè)把矩陣乘法擴(kuò)展成循環(huán)

10、的關(guān)口。這些關(guān)口需要被實(shí)現(xiàn)成低級(jí)IR到IR的轉(zhuǎn)換，這比僅僅使用普通的（多級(jí)）的計(jì)算表達(dá)來(lái)表達(dá)目標(biāo)代碼的宏觀或分段的方法難多了。把優(yōu)化實(shí)現(xiàn)為單獨(dú)的關(guān)口的方式在許多優(yōu)化被獨(dú)立添加時(shí)會(huì)引起關(guān)口排序的問(wèn)題。我們認(rèn)為，我們真正需要的是最好的兩個(gè)世界：一方面，我們想要將操作符號(hào)化以便于他們能夠適應(yīng)于轉(zhuǎn)換規(guī)則。另一方面，我們也要使用分段來(lái)以編程方式定義轉(zhuǎn)換的結(jié)果。此外，在使用優(yōu)化時(shí)我們需要一種方法來(lái)定義轉(zhuǎn)換的獨(dú)立性以避免階段排序問(wèn)題。貢獻(xiàn)在本文中，我們提出了一個(gè)可擴(kuò)展編譯器的框架，解決了這一挑戰(zhàn)，同時(shí)盡量降低表達(dá)優(yōu)化和轉(zhuǎn)換的編碼量。通過(guò)采用分段技術(shù)的中間語(yǔ)言以及一種不會(huì)產(chǎn)生階段排序問(wèn)題的方法整合獨(dú)立的指定優(yōu)

11、化，我們?nèi)诤狭瞬僮骷淖兞藬?shù)據(jù)布局，對(duì)高級(jí)對(duì)象進(jìn)行了深度優(yōu)化，我們的方法極大地提升了高級(jí)程序的速度。為了說(shuō)明我們的系統(tǒng)在較高的水平下如何工作，我們?cè)賮?lái)考慮線性代數(shù)的例子。通過(guò)分期我們從最初的程序中獲得一個(gè)中間表達(dá)式。為了避免采用純分期或宏觀的方法，我們?cè)诓煌膶哟螒?yīng)用優(yōu)化，我們將盡可能多的優(yōu)化放在同一個(gè)關(guān)口以避免諸多傳統(tǒng)的階段排序問(wèn)題。線性代數(shù)庫(kù)的作者，通過(guò)重寫(xiě)將符號(hào)表達(dá)式重寫(xiě)為分段的程序片段的規(guī)則來(lái)實(shí)現(xiàn)線性代數(shù)優(yōu)化。該系統(tǒng)通過(guò)積極假設(shè)，當(dāng)事實(shí)證明中間轉(zhuǎn)換不準(zhǔn)確時(shí)則回滾，來(lái)進(jìn)行重寫(xiě)。這種策略消除了由于一個(gè)優(yōu)化模塊不得不對(duì)另外一個(gè)模塊的結(jié)果進(jìn)行悲觀假設(shè)而引起的階段排序問(wèn)題。一旦在線性代數(shù)的層面

12、無(wú)法進(jìn)行更深的優(yōu)化，我們就只能考慮由數(shù)組和循環(huán)組成的低級(jí)表達(dá)方式。我們把這種“昏暗的”轉(zhuǎn)換實(shí)現(xiàn)成了中間程序的分段解釋器。由于解釋器也使用分段，它創(chuàng)建了新的程序，看起來(lái)似乎像是程序轉(zhuǎn)化器。默認(rèn)情況下，解釋器會(huì)將每個(gè)表達(dá)式映射到一個(gè)在結(jié)構(gòu)上相當(dāng)?shù)谋磉_(dá)式。該庫(kù)的作者將線性代數(shù)運(yùn)算映射到它的低級(jí)表示。在這一水平上，該系統(tǒng)在組合關(guān)口，重新應(yīng)用全局優(yōu)化方面應(yīng)用另一套優(yōu)化，來(lái)更好的利用改變表達(dá)式帶來(lái)的新機(jī)會(huì)。這個(gè)過(guò)程可以重復(fù)進(jìn)行任意次。特別是，我們做出了如下貢獻(xiàn)： 我們使用分段構(gòu)建可擴(kuò)展多關(guān)口的編譯器同時(shí)可以有效地把模塊化的優(yōu)化整合成單一關(guān)口：分段IR解釋器作為IR轉(zhuǎn)換和推理重寫(xiě)允許將獨(dú)立指定優(yōu)化進(jìn)行整合的

13、同時(shí)保持樂(lè)觀的假設(shè)。 我們使用基于圖的中間表示可能包含結(jié)構(gòu)化的復(fù)合表達(dá)式。拆分和合并復(fù)合表達(dá)式使我們能夠重用現(xiàn)有的優(yōu)化（例如，DCE刪除數(shù)據(jù)結(jié)構(gòu)中未使用的部分）。這種方法擴(kuò)展了強(qiáng)大的數(shù)據(jù)格式轉(zhuǎn)換（例如，陣列結(jié)構(gòu)到結(jié)構(gòu)數(shù)組）。 我們提出了一種新的能夠統(tǒng)一處理水平和垂直融合和非對(duì)稱結(jié)構(gòu)的遍歷（flatMap，groupBy）的數(shù)據(jù)并行循環(huán)融合算法。 我們通過(guò)一些不平凡的案例演示了該編譯器架構(gòu)如何解決與數(shù)據(jù)結(jié)構(gòu)相關(guān)的棘手的優(yōu)化問(wèn)題。我們初期的工作建立在Lightweight Modular Staging(LMS) 39之上，并且會(huì)隨著工作的進(jìn)行標(biāo)注與之相似的和不同的工作。推理重寫(xiě)的方法是基于Len

14、er，Grove和Chambers的工作29。2. 背景 許多計(jì)算可以自然地根據(jù)執(zhí)行的頻率和信息的可用性來(lái)分成不同的階段。Taha和Sheard46建立了多級(jí)編程（簡(jiǎn)稱MSP），他們將階段分得十分明確，允許程序員在下一個(gè)階段求表達(dá)式的值（也叫表達(dá)式分段）?，F(xiàn)階段作為一個(gè)高效的代碼生成器，在運(yùn)行時(shí)產(chǎn)生下一個(gè)階段的程序。分段和部分求值20密切相關(guān)，它將程序分成輸入確定的一些部分?；诒疚牡哪康?，我們可以把部分求值（尤其是綁定時(shí)間分析（BTA）當(dāng)成自動(dòng)分級(jí)，把分級(jí)當(dāng)成程序員控制的部分求值。一個(gè)關(guān)鍵的區(qū)別是，部分求值嚴(yán)格地使程序?qū)ｉT(mén)化，通常有著健全的保障。然而，在像MetaOCaml7這樣的MSP語(yǔ)言

15、中添加分級(jí)注釋使得分段的階段劃分時(shí)更加自由但是需要一定的注意以保證不改變計(jì)算的結(jié)果。大部分關(guān)于分段和部分求值的研究都是為了簡(jiǎn)化編譯器的開(kāi)發(fā)。例如，把解釋器專門(mén)化成一個(gè)特定的程序能夠產(chǎn)生一個(gè)去除了解釋器（第一個(gè)Futamura投影15）的已編譯程序。自適應(yīng)的部分求值器可以通過(guò)解釋器和編譯器生成器來(lái)生成編譯器。本文的論述中使用Scala和輕量級(jí)模塊化分段（LMS）39，一種理論上的分段方法。與基于準(zhǔn)引號(hào)的專用MSP語(yǔ)言相反，LMS只使用類型來(lái)區(qū)分計(jì)算階段。屬于第二階段的表達(dá)式在第一階段中有類型RepT，當(dāng)在第二階段時(shí)，會(huì)得到類型為T(mén)的運(yùn)算。普通類型T的表達(dá)式將在第一階段求值，在第二階段中則變成了常

16、數(shù)。普通的Scala類型系統(tǒng)傳播關(guān)于哪些表達(dá)式分段了的信息，從而作為本地的半自動(dòng)BTA。因此，LMS從自動(dòng)PE和手動(dòng)分段中獲得了不少好處。例子：零耗抽象遍歷Scala中的Array是在遍歷時(shí)需要循環(huán)和索引的JVM純數(shù)組。Scala的標(biāo)準(zhǔn)庫(kù)提供了一個(gè)foreach方法：array foreach i = println(i) foreach方法是通過(guò)隱式轉(zhuǎn)換來(lái)實(shí)現(xiàn)的：implicit def enrichArrayT(a: ArrayT) = new def foreach(f: T = Unit): Unit = var i = 0; while (i B（分段函數(shù)對(duì)象）類型和RepA=Rep

17、B（分段值上的函數(shù)）之間的不同。通過(guò)使用后者時(shí)，foreach確保函數(shù)的參數(shù)總是在分段時(shí)間內(nèi)求值和展開(kāi)。只允許刪除表達(dá)式樹(shù)的宏系統(tǒng)只能支持RepA = B類型。這限制了表現(xiàn)力并且無(wú)法保證高階函數(shù)在分段時(shí)間內(nèi)求值。在除了LMS框架，我們使用Scala虛擬編譯器32，它把幾個(gè)核心的語(yǔ)言功能重新定義為函數(shù)，從而使它們能夠重載。例如，下面的代碼/ 數(shù)組implicit def enrichArrayT(a: RepArrayT) = new def foreach(f: RepT = RepUnit): RepUnit = var i = 0; while (i RepT) =Array.fill(a

18、.length min b.length) i = f(a(i), b(i) / 向量trait VectorT extends Struct val data: ArrayT implicit def enrichVectorT:Numeric(a: RepVectorT) = new def +(b: RepVectorT) =Vector.fromArray(a.data.zipWith(b.data)(_ + _) ./ ( 與Array.fill 和Vector.fromArray所在定義的對(duì)象一起)圖 2, 分段數(shù)組和矢量操作var i = 0; while (i n) i = i

19、 + 1 會(huì)被解釋為如下：val i = _newVar(0); _while(i println(i) 中，在圖2中定義的分段函數(shù)foreach只會(huì)執(zhí)行compute()方法一次，而純粹的語(yǔ)法擴(kuò)展產(chǎn)生這種目標(biāo)代碼：while (i v在膨脹前的發(fā)生移除zero。讓我們想象一下，我們的系統(tǒng)能夠以這樣一種方式實(shí)現(xiàn)矢量加法操作，它可以檢查參數(shù)來(lái)查找Vector.zeros的調(diào)用。這將解決上述例子中的問(wèn)題，但如果我們稍微將使用情況復(fù)雜化一點(diǎn)，我們?nèi)詴?huì)面臨其他問(wèn)題：val v1 = .val v2 = Vector.zeros(n)v1 + v2處理這樣的程序，只是檢查（語(yǔ)法）參數(shù)是不足夠的。我們需要

20、將分期擴(kuò)展與某種形式的轉(zhuǎn)發(fā)數(shù)據(jù)流整合來(lái)傳播，否則加法的參數(shù)僅僅是一個(gè)標(biāo)識(shí)符。更深層次的問(wèn)題是，我們不得不使用單一的數(shù)據(jù)表示。即便我們將分段整合到一個(gè)可擴(kuò)展的編譯器中，我們?nèi)孕枳鞒鲆粋€(gè)決定：我們是應(yīng)該為了便于優(yōu)化把向量當(dāng)做擁有代數(shù)定律的象征性實(shí)體，實(shí)現(xiàn)成IR節(jié)點(diǎn)？還是將它們分段好讓編譯器只看到循環(huán)和數(shù)組而沒(méi)有抽象的開(kāi)銷(xiāo)？以下各節(jié)將論述將這些方法整合的機(jī)制，以及如何以一個(gè)更抽象的方式來(lái)對(duì)待數(shù)據(jù)結(jié)構(gòu)。3. 通過(guò)分級(jí)實(shí)現(xiàn)的程序轉(zhuǎn)化分段通常是一個(gè)用于生成程序的方法：由目標(biāo)程序建立的多級(jí)程序隨即再次正常編譯。我們發(fā)現(xiàn)，分段可以作為程序轉(zhuǎn)換的一個(gè)有效的工具。任何轉(zhuǎn)換可以細(xì)分成一種遍歷和生成部分。并不奇怪的是

21、，分段有助于生成部分。在我們的例子中，內(nèi)部編譯器關(guān)口為恰好分段的IR解釋器，它們將返回一個(gè)新的程序。通過(guò)這種方式，它們可以在程序執(zhí)行時(shí)建立程序轉(zhuǎn)換的結(jié)果。程序轉(zhuǎn)換的分段有很多好處。首先，建立一個(gè)（分段）IR解釋器比建設(shè)一個(gè)不平凡的IR到IR轉(zhuǎn)換器簡(jiǎn)單得多。其次，優(yōu)化可逐漸加入到一個(gè)分段的程序中，從圖2中的代碼開(kāi)始。第三，程序本身（或庫(kù)）受翻譯過(guò)程控制并且會(huì)影響到將產(chǎn)生什么樣的代碼。我們的方法中關(guān)鍵環(huán)節(jié)之一是區(qū)分兩種轉(zhuǎn)換：優(yōu)化和降低程序級(jí)別。降低程序級(jí)別是將程序翻譯成低級(jí)表示（如從線性代數(shù)到數(shù)組和循環(huán)的轉(zhuǎn)換）。 降低程序有著自然的順序，這使得他們能夠方便地安排單獨(dú)的關(guān)口中。相反，優(yōu)化沒(méi)有明確的順

22、序，而且容易導(dǎo)致階段排序問(wèn)題。因此，需要將它們結(jié)合來(lái)獲得更大的效果。此外，大多數(shù)降低程序級(jí)別是必需的，而優(yōu)化通常是可選的。當(dāng)然，兩者的區(qū)別并不始終明確，但許多變換只屬于其中一種。在任何情況下，重要的是所有適用的優(yōu)化應(yīng)該在降低程序級(jí)別前采用。否則，可能會(huì)錯(cuò)過(guò)高級(jí)的優(yōu)化機(jī)會(huì)。降低程序級(jí)別后，有可能仍有新的優(yōu)化機(jī)會(huì)。因此，我們的系統(tǒng)會(huì)執(zhí)行一序列的優(yōu)化，降低程序級(jí)別，再優(yōu)化操作，直到程序用最低級(jí)別的表示。 對(duì)于目標(biāo)代碼來(lái)說(shuō)最終的表示是未解析的。4. 數(shù)據(jù)結(jié)構(gòu)優(yōu)化高層次的數(shù)據(jù)結(jié)構(gòu)是現(xiàn)代編程的基石，同時(shí)也阻礙了編譯器優(yōu)化。我們通過(guò)兩個(gè)主要的編程范式來(lái)闡明編譯器在數(shù)據(jù)結(jié)構(gòu)方面遇到的主要問(wèn)題。OOP面向?qū)ο缶?/p>

23、程把每一個(gè)數(shù)據(jù)值看做一個(gè)對(duì)象。這是一個(gè)功能強(qiáng)大的模式，使得它易于擴(kuò)展語(yǔ)言新的功能。例如，在Scala中很容易添加復(fù)數(shù)類。但要付出相應(yīng)的代價(jià)：把每一個(gè)復(fù)數(shù)作為一個(gè)單獨(dú)的對(duì)象來(lái)分配效率不高。此外，我們用到復(fù)數(shù)數(shù)組時(shí)，如果我們用一個(gè)結(jié)構(gòu)數(shù)組表示將獲得了更好的性能。分段和嵌入式編譯器允許我們抽象出對(duì)象的抽象，推出組成對(duì)象的獨(dú)立數(shù)據(jù)片段，并可能以更有效的方式重新排列數(shù)據(jù)。FP函數(shù)式程序會(huì)產(chǎn)生大量的中間結(jié)果。這種情況在集合操作中特別嚴(yán)重。從理論上講，編譯器可以利用引用透明度。但是不純的函數(shù)式語(yǔ)言需要復(fù)雜的效果分析，若其中包含大量的抽象這將變得很困難。因?yàn)閯冸x了抽象，我們的分段程序要簡(jiǎn)單得多。我們可以做更好

24、更簡(jiǎn)單的效果分析。一個(gè)簡(jiǎn)單的活躍度分析，可以將復(fù)制轉(zhuǎn)化為就地修改。一種新型的循環(huán)融合算法（數(shù)據(jù)并行且非對(duì)稱，包括flatMap和groupBy方法）刪除許多中間結(jié)果。5. 案例學(xué)習(xí)我們提出了幾個(gè)案例研究，以闡明我們的編譯器體系結(jié)構(gòu)，特別是在分段方面與數(shù)據(jù)結(jié)構(gòu)相關(guān)的高級(jí)優(yōu)化。所有的實(shí)驗(yàn)都在有兩個(gè)四核Xeon2.67GHz處理器和96GB的RAM的Dell Precision T7500n機(jī)器上運(yùn)行。Scala代碼運(yùn)行在Oracle Java SE運(yùn)行時(shí)環(huán)境1.7.0版和默認(rèn)配置的Hotspot64位服務(wù)器VM上。每個(gè)應(yīng)用程序我們都運(yùn)行了10次（使JIT活躍）并且報(bào)告最后5次運(yùn)行的平均時(shí)間。每次運(yùn)

25、行我們都只計(jì)算應(yīng)用程序計(jì)算部分所占的比例。6. 討論正如在第5節(jié)所示，我們的系統(tǒng)能夠?qū)崿F(xiàn)在較寬范圍不平凡高級(jí)語(yǔ)言程序上擁有較大幅度（在某種情況下甚至接近）的速度提升的排序。雖然我們不知道是否確實(shí)存在其他能夠在相同數(shù)量級(jí)的程序下產(chǎn)生可比較結(jié)果的系統(tǒng)，但這些結(jié)果讓我們懷疑通過(guò)其他的方式是否可以付出相同的代價(jià)來(lái)得到。我們的審稿人之一提出，更簡(jiǎn)單的設(shè)計(jì)能使優(yōu)化自動(dòng)化。例如，我們可以用一個(gè)特殊類表示零矢量來(lái)將向量和矩陣實(shí)現(xiàn)成類的層次結(jié)構(gòu)，而不是在IR模型中靜態(tài)地區(qū)分零矢量。這當(dāng)然是一種有效的設(shè)計(jì)，但它也有許多缺陷。首先，運(yùn)行時(shí)的區(qū)別帶來(lái)了解釋的開(kāi)銷(xiāo)，間接和虛擬調(diào)用，這也讓編譯器更難生成高效的代碼。其次，

26、雖然在某些情況下動(dòng)態(tài)信息可能會(huì)比靜態(tài)信息更加精確，但是在其他重要方面動(dòng)態(tài)優(yōu)化的可能非常有限：例如，目前并沒(méi)有明確的方法融合DCE或任何其他需要的非局部知識(shí)（活性，橫向融合）的優(yōu)化。審稿人提出的另一個(gè)問(wèn)題是，相比Spoofax 24或JetBrains MPS 19這些包括在語(yǔ)言工作臺(tái)上的目前技術(shù)水平的重寫(xiě)系統(tǒng)，分段是否真的簡(jiǎn)化了轉(zhuǎn)換。的確，這些系統(tǒng)令人印象深刻，我們相信他們服務(wù)于不同的目的，以編程方式刪除所有中間層抽象并且能夠強(qiáng)力保障殘留代碼的處理的能力，在程序優(yōu)化的背景下是很難夸大的。例如，通過(guò)高階函數(shù)和分段刪除的類型類實(shí)例，無(wú)需刪除專用的編譯器分析，圖3中的代碼就可以將符號(hào)表示的線性代數(shù)運(yùn)

27、算轉(zhuǎn)化為圖2中所示的相同的零耗遍歷。分段使我們能夠?qū)⒊绦颍ɑ蚰Ｐ停┺D(zhuǎn)化器當(dāng)成解釋器；這是一個(gè)優(yōu)勢(shì)因?yàn)榧幢銚碛辛己玫墓ぞ甙С郑褂靡环N有表現(xiàn)力的語(yǔ)言來(lái)編寫(xiě)一個(gè)解釋器比實(shí)現(xiàn)一個(gè)轉(zhuǎn)換器可以說(shuō)簡(jiǎn)單得多。一個(gè)重要方面是在語(yǔ)言上重用元語(yǔ)言的抽象定義。例如，我們最近關(guān)于使用LMS 27產(chǎn)生JavaScript的工作在分段期間重用了Scala的CPS轉(zhuǎn)換40來(lái)產(chǎn)生異步代碼，也即延續(xù)傳傳遞風(fēng)格（CPS）。相比之下，實(shí)現(xiàn)在Spoofax下的WebDSL 17，對(duì)每種目標(biāo)語(yǔ)言的語(yǔ)言結(jié)構(gòu)必須重新實(shí)現(xiàn)CPS轉(zhuǎn)換。處理一個(gè)基于圖形的IR相比表達(dá)式樹(shù)也有質(zhì)的區(qū)別。最重要的是，需要依賴信息的轉(zhuǎn)換更容易實(shí)現(xiàn)。例如，我們的融合

28、算法（4.4節(jié)），不需要循環(huán)來(lái)在語(yǔ)法上接近融合：def calcSum() = array.sumdef calcCount() = array.filter(_ 0).countprintln(sum: + calcSum()println(avg: + (calcSum() / calcCount()分段會(huì)將calcSum和calcCount的調(diào)用內(nèi)聯(lián)而融合算法會(huì)將遍歷整合到一個(gè)循環(huán)中。任何只考慮依賴遍歷表達(dá)式的算法將錯(cuò)過(guò)在這兩個(gè)println語(yǔ)句之間進(jìn)行水平融合的機(jī)會(huì)。這就是通常的情況下純前端基于比如C+表達(dá)式模板的方法。我們?cè)O(shè)計(jì)的另一個(gè)重要方面是如何對(duì)待降低程序等級(jí)（處理一個(gè)有一個(gè)獨(dú)立

29、的關(guān)口）和優(yōu)化（通過(guò)推理重寫(xiě)整合成化簡(jiǎn)關(guān)口）。我們相信這樣的區(qū)別對(duì)于通過(guò)避免階段排序問(wèn)題進(jìn)行優(yōu)化以及保證高層次的優(yōu)化在降低程序等級(jí)之前執(zhí)行是非常有必要的。最后，關(guān)于實(shí)現(xiàn)類似的結(jié)果程序員需要付出的努力的問(wèn)題。從我們的角度來(lái)看，最重要的方面是我們提出的優(yōu)化能否逐步實(shí)施，以及經(jīng)過(guò)優(yōu)化的庫(kù)能否被所有的客戶端重用。我們希望，終端用戶程序員不要經(jīng)常自己寫(xiě)轉(zhuǎn)換，如果他們需要可以重寫(xiě)。庫(kù)開(kāi)發(fā)人員如果要添加優(yōu)化，需要實(shí)現(xiàn)與我們展示的代碼（例如在圖3中）一樣的函數(shù)，他們也可以按照以下步驟來(lái)做：首先編寫(xiě)類似于圖1中的代碼，添加分段（圖2），如果這還不夠，添加進(jìn)一步的優(yōu)化（圖3）。延遲重寫(xiě)（第3.3），可進(jìn)一步降低冗

30、余。類型系統(tǒng)（在分段期間計(jì)算的非RepT表達(dá)式）和智能構(gòu)造函數(shù)（如果重寫(xiě)匹配則不創(chuàng)建IR節(jié)點(diǎn)）有利于保障優(yōu)化按照預(yù)期的方式執(zhí)行。作為調(diào)試幫助，轉(zhuǎn)換后的代碼可以在任何時(shí)候發(fā)出。6.1 相關(guān)工作關(guān)于可擴(kuò)展的編譯器的研究已經(jīng)持續(xù)很長(zhǎng)一段時(shí)間了，在Java世界中最近的例子是Polyglot33和JastAdd 13。Glasgow Haskell編譯器還允許自定義重寫(xiě)規(guī)則22。也有一些源自正式方法的庫(kù)專門(mén)化優(yōu)化方面細(xì)致的研究。ROSE 36是一個(gè)用于創(chuàng)建在庫(kù)抽象領(lǐng)域通過(guò)語(yǔ)義注釋來(lái)進(jìn)行自動(dòng)優(yōu)化的源到源翻譯器的框架。COBALT 30是一種用于實(shí)現(xiàn)對(duì)自動(dòng)正確性推理的優(yōu)化的特定領(lǐng)域的語(yǔ)言。Tate以及其他人

31、48提出了一種在轉(zhuǎn)換前后自動(dòng)根據(jù)例子程序執(zhí)行編譯器優(yōu)化的方法。Delite 5，28，41是除了LMS之外DSLs的又一個(gè)并行框架。Delite之前有一個(gè)多層IR的概念：在相同的時(shí)間一些IR節(jié)點(diǎn)可以從幾個(gè)不同的角度來(lái)看（例如，一個(gè)并發(fā)的循環(huán)，同時(shí)也可以是一個(gè)矩陣運(yùn)算）。這將導(dǎo)致問(wèn)題，因?yàn)椤霸缧r(shí)候”，更多的高層次的看法執(zhí)行，過(guò)時(shí)或已經(jīng)充分利用的信息未被丟棄，這就限制了編譯器的選擇。我們使用這項(xiàng)技術(shù)來(lái)擴(kuò)展Delite，在現(xiàn)有的類似OptiML44這樣的Delite DSLs中實(shí)現(xiàn)領(lǐng)域特殊化優(yōu)化（就像案例分析中提出的那些）。Delite也被用來(lái)作為本文案例分析中的并行執(zhí)行引擎。與Delite相比，

32、本文提出了一種通用擴(kuò)展編譯器架構(gòu)，它不僅限于領(lǐng)域特殊化的語(yǔ)言。以前關(guān)于LMS 38，39的出版物只提出了純前端，單一關(guān)口實(shí)例。在LMS中使用RepT類型來(lái)定義匯編時(shí)間，是受到早期關(guān)于無(wú)標(biāo)簽或多態(tài)性語(yǔ)言嵌入10，18的研究的啟發(fā)。我們的編譯器基礎(chǔ)設(shè)施以可重用的方式實(shí)現(xiàn)了一套先進(jìn)的優(yōu)化技術(shù)。相關(guān)工作包括采用了先進(jìn)的重寫(xiě)規(guī)則4，結(jié)合了分析與優(yōu)化9，29，53，以及用于消除中間結(jié)果12，54和循環(huán)融合16的技術(shù)的程序轉(zhuǎn)換?？梢蕴娲评碇貙?xiě)的一個(gè)有趣的選擇是相等等飽和47，它包括了許多種表達(dá)IR操作的方式。作為在程序轉(zhuǎn)換中使用部分求值的一個(gè)例子，Sperber和Thiemann 43作了閉包轉(zhuǎn)換和在一個(gè)

33、合適的解釋器上進(jìn)行離線部分求值的尾部調(diào)用的介紹。最近，Cook等人11通過(guò)對(duì)模式解釋器執(zhí)行部分求值進(jìn)行了模式轉(zhuǎn)換。部分評(píng)估一般意味著常量折疊和專業(yè)化，而我們的方法允許對(duì)編譯器進(jìn)行任意的優(yōu)化，在任意時(shí)刻計(jì)算分期/特殊化的時(shí)間以消除抽象開(kāi)銷(xiāo)，并能保障什么會(huì)變成殘留代碼（類型RepT殘留，T靜態(tài)）。6.2 結(jié)論 我們展示了一個(gè)編譯器架構(gòu)，它通過(guò)融合操作集，改變數(shù)據(jù)布局以及通過(guò)采用分段技術(shù)的中間語(yǔ)言以及一種不會(huì)產(chǎn)生階段排序問(wèn)題的方法整合獨(dú)立的指定優(yōu)化對(duì)高級(jí)對(duì)象進(jìn)行的深度優(yōu)化極大地提升了程序的速度。我們的系統(tǒng)結(jié)合了一些現(xiàn)有的新技術(shù)，提供的優(yōu)化效果要遠(yuǎn)大于各個(gè)部分之和。致謝我們感謝POPL審稿人的寶貴意見(jiàn)

34、和建議。贊助這項(xiàng)研究有歐洲研究委員會(huì)（ERC）的587327“DOPPLER”資助，DARPA（美國(guó)國(guó)防部先進(jìn)研究項(xiàng)目局）通過(guò)Oracle下的訂單US103282，DARPA的合同HR0011-11-C-0007“SEEC”，NSF（國(guó)家科學(xué)基金會(huì))資助SHF CCF-1111943，斯坦福大學(xué)普適并行實(shí)驗(yàn)室聯(lián)合計(jì)劃（由Oracle，AMD，Intel，NVIDIA支持）和Oracle額外的支持。參考文獻(xiàn)1 S. Ackermann, V. Jovanovic, T. Rompf, and M. Odersky. Jet: An embedded dsl for high performanc

35、e big data processing. BigData, 2012.http:/infoscience.epfl.ch/record/181673/files/paper.pdf.2 M. S. Ager, O. Danvy, and H. K. Rohde. Fast partial evaluation of pattern matching in strings. ACM Trans. Program. Lang. Syst., 28(4):696714, 2006.3 J. Auerbach, D. F. Bacon, P. Cheng, and R. Rabbah. Lime:

36、 a javacompatible and synthesizable language for heterogeneous architectures.OOPSLA, 2010.4 M. Bravenboer, A. van Dam, K. Olmos, and E. Visser. Program transformation with scoped dynamic rewrite rules. Fundam. Inf., 69:123178, July 2005.5 K. J. Brown, A. K. Sujeeth, H. Lee, T. Rompf, H. Chafi, M. Od

37、ersky,and K. Olukotun. A heterogeneous parallel framework for domainspecific languages. PACT, 2011.6 J. A. Brzozowski. Derivatives of regular expressions. J. ACM, 11(4):481494, 1964.7 C. Calcagno, W. Taha, L. Huang, and X. Leroy. Implementing multistage languages using asts, gensym, and reflection.

38、In GPCE, 2003.8 J. Carette, O. Kiselyov, and C. chieh Shan. Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages. J.Funct. Program., 19(5):509543, 2009.9 C. Click and K. D. Cooper. Combining analyses, combining optimizations.ACM Trans. Program. Lang. Syst., 1

39、7:181196, March 1995.10 C. Consel and O. Danvy. Partial evaluation of pattern matching in strings. Inf. Process. Lett., 30(2):7986, 1989.11 W. R. Cook, B. Delaware, T. Finsterbusch, A. Ibrahim, and B. Wiedermann.Model transformation by partial evaluation of model interpreters.Technical Report TR-09-

40、09, UT Austin Department of Computer Science, 2008.12 D. Coutts, R. Leshchinskiy, and D. Stewart. Stream fusion: from lists to streams to nothing at all. In ICFP, 2007.13 T. Ekman and G. Hedin. The jastadd system - modular extensible compiler construction. Sci. Comput. Program., 69(1-3):1426, 2007.1

41、4 C. Elliott, S. Finne, and O. de Moor. Compiling embedded languages.In W. Taha, editor, Semantics, Applications, and Implementation of Program Generation, volume 1924 of Lecture Notes in Computer Science, pages 926. Springer Berlin / Heidelberg, 2000.15 Y. Futamura. Partial evaluation of computatio

42、n process - an approach to a compiler-compiler. Higher-Order and Symbolic Computation, 12(4):381391, 1999.16 C. Grelck, K. Hinckfu, and S.-B. Scholz. With-loop fusion for data locality and parallelism. IFL, 2006.17 D. M. Groenewegen, Z. Hemel, L. C. L. Kats, and E. Visser. WebDSL:a domain-specific l

43、anguage for dynamic web applications. In OOPSLA Companion, 2008.18 C. Hofer, K. Ostermann, T. Rendel, and A. Moors. Polymorphic embedding of DSLs. GPCE, 2008.19 JetBrains. Meta Programming System, 2009. URL 20 N. D. Jones, C. K. Gomard, and P. Sestoft. Partial evaluation and automatic program genera

44、tion. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1993.21 S. L. P. Jones, R. Leshchinskiy, G. Keller, and M. M. T. Chakravarty. Harnessing the Multicores: Nested Data Parallelism in Haskell. In FSTTCS, 2008.22 S. P. Jones, A. Tolmach, and T. Hoare. Playing by the rules: rewriting as a practica

45、l optimisation technique in ghc. Haskell, 2001.23 S. Karmesin, J. Crotinger, J. Cummings, S. Haney, W. Humphrey, J. Reynders, S. Smith, and T. J.Williams. Array design and expression evaluation in pooma ii. In ISCOPE, 1998.24 L. C. L. Kats and E. Visser. The Spoofax language workbench. Rules for dec

46、larative specification of languages and IDEs. In SPLASH/OOPSLA Companion, 2010.25 R. Kelsey and P. Hudak. Realistic compilation by program transformation. In POPL, 1989.26 K. Kennedy, B. Broom, A. Chauhan, R. Fowler, J. Garvin, C. Koelbel, C. McCosh, and J. Mellor-Crummey. Telescoping languages: A s

47、ystem for automatic generation of domain languages. Proceedings of the IEEE, 93(3):387408, 2005.27 G. Kossakowski, N. Amin, T. Rompf, and M. Odersky. Javascript as an embedded dsl. In ECOOP, 2012.28 H. Lee, K. J. Brown, A. K. Sujeeth, H. Chafi, T. Rompf, M. Odersky, and K. Olukotun. Implementing dom

48、ain-specific languages for heterogeneous parallel computing. IEEE Micro, 31(5):4253, 2011.29 S. Lerner, D. Grove, and C. Chambers. Composing dataflow analyses and transformations. SIGPLAN Not., 37:270282, January 2002.30 S. Lerner, T. D. Millstein, and C. Chambers. Automatically proving the correctn

49、ess of compiler optimizations. In PLDI, 2003.31 A. Mller. dk.brics.automaton finite-state automata and regular expressions for Java, 2010. http:/www.brics.dk/automaton/.32 A. Moors, T. Rompf, P. Haller, and M. Odersky. Scala-virtualized. PEPM, 2012.33 N. Nystrom, M. R. Clarkson, and A. C. Myers. Pol

50、yglot: An extensible compiler framework for java. In CC, 2003.34 N. Nystrom, D. White, and K. Das. Firepile: run-time compilation for gpus in scala. GPCE, 2011.35 S. Owens, J. Reppy, and A. Turon. Regular-expression derivatives reexamined. J. Funct. Program., 19(2):173190, Mar. 2009.36 D. J. Quinlan

51、, M. Schordan, Q. Yi, and A. Sbjrnsen. Classification and utilization of abstractions for optimization. In ISoLA (Preliminary proceedings), 2004.37 T. Rompf. Lightweight Modular Staging and Embedded Compilers: Abstraction Without Regret for High-Level High-Performance Programming. PhD thesis, EPFL,

52、2012.38 T. Rompf and M. Odersky. Lightweight modular staging: a pragmatic approach to runtime code generation and compiled dsls. GPCE, 2010.39 T. Rompf and M. Odersky. Lightweight modular staging: a pragmatic approach to runtime code generation and compiled dsls. Commun. ACM, 55(6):121130, 2012.40 T. Rompf, I. Maier, and M. Odersky. Implementing first-class