一種Java字節(jié)碼靜態(tài)調(diào)整的方法及應(yīng)用

1、    一種Java字節(jié)碼靜態(tài)調(diào)整的方法及應(yīng)用        蔣 凡，楊建國 時間:2008年05月14日     字 體: 大 中 小        關(guān)鍵詞:<"cblue" " target='_blank'>多維<"cblue" " target='_

2、blank'>存儲結(jié)構(gòu)<"cblue" " target='_blank'>測試結(jié)果<"cblue" " target='_blank'>三種<"cblue" " target='_blank'>應(yīng)用程序            摘要： 提出了一種改善J2ME中<"cblue&

3、quot; " title="多維">多維數(shù)組運算效率的方法。該方法不占用額外的內(nèi)存，不需要修改虛擬機，通過靜態(tài)修改已經(jīng)編譯好的Java 字節(jié)碼提高多維數(shù)組運算效率。實驗表明，本方法比現(xiàn)有針對J2SE的多維數(shù)組運算效率解決方法更適用于J2ME環(huán)境。關(guān)鍵詞： Java J2ME JVM 多維數(shù)組 Java字節(jié)碼J2ME廣泛應(yīng)用在嵌入式系統(tǒng)中，其中有不少基于多維數(shù)組的運算1。而Java語言的以下兩個機制是制約這類運算效率的瓶頸。(1)Java用包含數(shù)組的數(shù)組來存儲多維數(shù)組，而不同于CC+使用一塊連續(xù)的空間進行存儲，如圖1所示。對于一個n維數(shù)組，當(dāng)需要訪問其中的某

4、一個元素時，總共需要n+2次訪問堆中的對象。第1和第2次訪問該數(shù)組所屬類的對象和數(shù)組對象；第3到第n+1次逐級訪問代表每一維的數(shù)組對象；最后1次才能到達所需要訪問的數(shù)組元素。如果相鄰兩次訪問數(shù)組的元素不屬于同一維，則很可能導(dǎo)致緩存失效，從而降低運算效率。(2)Java中采用了嚴格的異常機制，以保證在發(fā)生異常之前的運算都遵從用戶程序。在進行多維數(shù)組訪問時，要對每一維的下標進行空指針檢查和下標越界檢查，并在有異常發(fā)生時進行相應(yīng)的處理。這一機制從兩個方面影響了程序的運行效率：捕獲和處理異常需要占用大量的運算；阻止了代碼優(yōu)化，特別是影響了廣泛應(yīng)用于多維數(shù)組訪問的循環(huán)代碼的優(yōu)化2。因此，需要通過改變J2

5、ME中多維數(shù)組的存儲和訪問方式或者改變異常機制來改進J2ME程序的運行效率。1 已有的解決方案目前，針對J2SE的Java多維數(shù)組來提高運算效率的方法主要有以下<"cblue" " title="三種">三種：(1)使用特殊類庫。這一解決方案由IBM Ninja 項目組提出3。該方案基于現(xiàn)有編譯和優(yōu)化技術(shù)，定義了專門用來處理多維數(shù)組運算的數(shù)據(jù)結(jié)構(gòu)和函數(shù)，易于實現(xiàn)且高效，但需占用額外的內(nèi)存來存儲特殊類庫，并且會消耗更多時間來動態(tài)加載程序。(2)動態(tài)改變多維數(shù)組在內(nèi)存中的<"cblue" " titl

6、e="存儲結(jié)構(gòu)">存儲結(jié)構(gòu)。該方案通過降低緩存失效率來提高程序的整體效率。其實現(xiàn)方法是在程序運行過程中監(jiān)測緩存失效率，并在需要時動態(tài)調(diào)整多維數(shù)組在內(nèi)存中的存儲結(jié)構(gòu)，使得相鄰的兩次多維數(shù)組操作所涉及的數(shù)組元素在內(nèi)存中處于相鄰的物理空間。調(diào)整算法已由F.Li，P給出4。這一方案需要額外的內(nèi)存空間來完成存儲結(jié)構(gòu)動態(tài)調(diào)整，同時需要操作系統(tǒng)對緩存失效率進行實時監(jiān)測，實施起來有一定困難。(3)修改Java虛擬機。該方案通過修改Java虛擬機來提高效率。其策略是去除多維數(shù)組操作中進行的指針有效性檢查和數(shù)組下標越界檢查5。由于不同的嵌入式系統(tǒng)所使用的Java虛擬機不同，所以需要對不同

7、系統(tǒng)上的Java虛擬機做相應(yīng)的修改?？梢?，以上三種解決方案對于J2SE來說都是可行且高效的，但對于J2ME而言就不是這樣。本文提出了一種在可行性和高效性之間折衷的解決方案，并實現(xiàn)了一種靜態(tài)調(diào)整Java字節(jié)碼的工具原型。2 靜態(tài)調(diào)整方法及實現(xiàn)本文提出的方法旨在降低緩存失效率，避免JVM對空引用的檢測和異常處理，從而提高多維數(shù)組運算效率。通過靜態(tài)調(diào)整Java字節(jié)碼，使其被JVM裝載之后，使多維數(shù)組能保存在一塊連續(xù)的內(nèi)存區(qū)域。這樣，對多維數(shù)組的引用就在一個循環(huán)過程中始終處于緩存內(nèi)，不需要在每次使用時進行空引用和異常檢測。2.1 調(diào)整規(guī)則首先聲明用同等容量及類型的1維數(shù)組代替原多維數(shù)組，從而在運行時獲

8、得JVM堆中一塊連續(xù)的存儲空間。同時修改所有對多維數(shù)組的引用。當(dāng)把一個d維數(shù)組轉(zhuǎn)化為一個1維數(shù)組時，對數(shù)組中的每一個元素需要使用2×d個變量來訪問：1個變量A包含該數(shù)組的引用；一個(d-1)維的向量w記錄原數(shù)組前(d-1)維的權(quán)值，向量w中的第m個值標明原多維數(shù)組第m維空間的大??；另外一個d維向量i，記錄所訪問元素在原多維數(shù)組中的下標值。令M代表指向原多維數(shù)組的引用，wm代表向量w中的第m個元素值，in代表下標向量i的第n個值，則M所指向的多維數(shù)組中的一個元素可以通過如下表達式進行訪問：Mi0i1.id=Aw0*i0+w1*i1+.+wd-1*id-1+id2.2 調(diào)整過程首先建立一

9、個Opreation結(jié)構(gòu)鏈表OpList，用來記錄對字節(jié)碼進行調(diào)整的位置和具體操作。Operation 結(jié)構(gòu)定義如下：Structure Operationfi<"innerlink" " title="led">led1 index；/本操作所處的字節(jié)碼字節(jié)地址filed2 operation content；/具體操作定義分三部分掃描字節(jié)碼文件，將每一次調(diào)整操作的位置和操作內(nèi)容記錄在OpList中。掃描結(jié)束之后，根據(jù)OpList中的內(nèi)容修改字節(jié)碼文件。(1)處理常量池。將多維數(shù)組類名定義字符串修改為1維數(shù)組類名定義形式。算法如下

10、：For each tag in constantpool DoIf(tag is CONSTANT_Utf8_info) and( )+appears in tag.length*2 bytes Then? /如果出現(xiàn)連續(xù)多個的常量說明，則為對多維數(shù)組的說明，作相應(yīng)處理? /將constantpool index和new Operation儲存到OpList；記錄change( )*to 的操作；End IfEnd For(2)處理類方法內(nèi)部多維數(shù)組初始化和調(diào)用過程。對于初始化操作，首先計算數(shù)組容量，生成相同容量和類型的一維數(shù)組初始化代碼，代替多維數(shù)組初始化代碼；對多維數(shù)組元素的引用，首先根

11、據(jù)2.1節(jié)所示調(diào)整規(guī)則重新計算數(shù)組元素下標，然后調(diào)整本次引用所處的外層循環(huán)，并修改相關(guān)代碼屬性，包括length、ine_number_table_length、max_locals和code_length等。算法如下：For each command in one method section DoIf是多維數(shù)組初始化命令 Then計算數(shù)組容量，生成容量計算指令；生成相應(yīng)的1維數(shù)組初始化指令；End IfIf 訪問多維數(shù)組元素 Then計算對應(yīng)的一維數(shù)組下標，生成計算指令；修改外層循環(huán)代碼；End If生成包含操作位置和內(nèi)容的Operation結(jié)構(gòu)，并插入OpList；End ForIf 修

12、改了本方法代碼 Then記錄屬性變化(length、line_number_table_length、max_locals和code_length等)；End If(3)根據(jù)記錄的調(diào)整操作對字節(jié)碼文件進行修改。算法如下：int startIndex=0；For each opration in OpList do復(fù)制srcFile中startIndex至operation.index字節(jié)到newFile中；根據(jù)opration.content生成調(diào)整代碼，并寫入到newFile中；startIndex=operation.index；End For2.3 應(yīng)用舉例為使說明簡單明了，以程序1為例

13、說明整個調(diào)整過程。程序1展示了按列逐個訪問2維矩陣元素的代碼。首先處理字節(jié)碼常量池部分。用一個一維數(shù)組定義取代原有的多維數(shù)組定義。處理前后字節(jié)碼如代碼片斷1和代碼片斷2所示。程序1intx=new int100100；int tmp=0；for(int i=0；i<100；i+)for(int j=0；j<100；j+)tmp+-xji；代碼片斷1：01 00 01 78 const#6=Asciz x；01 00 03 5B 5B 49const#7=Asciz I；0C 00 06 00 07 const#16=NameAndType #6：#7；代碼片斷2：01 00 01

14、78const#6=Asciz x；01 00 02 5B 49 const#7=Asciz I；0C 00 06 00 07 const#16=NameAndType #6：#7；然后處理數(shù)組初始化。使用1維數(shù)組初始化過程取代原多維數(shù)組初始化。包括數(shù)組容量計算、去除冗余代碼、修改相關(guān)函數(shù)和代碼屬性。處理前后字節(jié)碼如代碼片斷3和代碼片斷4。代碼片斷3：10 64 bipush 10010 64 bipush 100c5 00 02 02 multianewarray #2，2；b5 00 03 putfield #3；代碼片斷4：11 27 10 sipush 10000bc 0a newar

15、ray intb5 00 02 putfield #3；最后處理多維數(shù)組實例的引用。在方法內(nèi)部，對多維數(shù)組的引用，只需修改其下標計算過程和由此引起的循環(huán)指標變化。代碼片斷5和代碼片斷6分別列出了程序1所示代碼中兩層for循環(huán)的字節(jié)碼。代碼片斷5：10 64bipush 100a2 00 2d if_icmpge 4503 iconst_03d istore_21c iload_210 64bipush 100a2 00 27 if_icmpge 392a aload_059 dup代碼片斷6：10 64 bipush 1003eistore_302 00 35 if_icmpge 53ldil

16、oad_31ciload_2 10 64 bipush 10010 64 bipush 100a2 00 2fif_icmpge 4764isub84 01 64iinc 1，1003cistore_12aaload_003iconst_059dup經(jīng)處理，字節(jié)碼大小和整體結(jié)構(gòu)沒有發(fā)生變化，且提高了運算效率。3 實驗及結(jié)果分析本節(jié)的所有結(jié)果都是基于K虛擬機(KVM)得出的。表1列出了所用的幾個測試基準及相關(guān)參數(shù)。這些基準測試廣泛應(yīng)用于與Java數(shù)值計算相關(guān)的性能測試中，具有一定的權(quán)威性。為使其在KVM上正確運行，首先對原基準測試程序進行簡單調(diào)整，然后使用SUN公司提供的J2ME Wireles

17、s Toolkit 2.2進行編譯，得到初始字節(jié)碼，再使用字節(jié)碼靜態(tài)調(diào)整工具對這些字節(jié)碼進行處理得到最后的執(zhí)行代碼，最后在KVM上分別運行。<"cblue" " title="測試結(jié)果">測試結(jié)果如表2所示。結(jié)果表明，通過使用本文所提出的Java字節(jié)碼靜態(tài)調(diào)整策略，在不改變原程序運行環(huán)境的情況下，明顯提高了基于多維數(shù)組的Java程序執(zhí)行效率。本文提出了一種通過靜態(tài)修改Java字節(jié)碼中的多維數(shù)組運算指令和相關(guān)指令以及屬性的方法，來提高基于多維數(shù)組運算的J2ME<"cblue" " title=&qu

18、ot;應(yīng)用程序">應(yīng)用程序的運行效率。該方法不占用額外的內(nèi)存，不需要Java虛擬機和其他類庫支持?；鶞蕼y試結(jié)果表明，該方法明顯提高了程序效率，比較適用于J2ME應(yīng)用程序。參考文獻1 F Catthoor，S Wuytack，E E Greef et al.Custom memory management methodology-exploration of memory organization for embedded multimedia system design kluwer.June 19982 Mikel Lujan，John R Gurd，T L Freeman et al.Elimination of java array bounds checks in the presence of indirecti