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

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

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

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

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

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

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

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

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

9、個(gè)Opreation結(jié)構(gòu)鏈表OpList，用來(lái)記錄對(duì)字節(jié)碼進(jìn)行調(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ù)多個(gè)的常量說(shuō)明，則為對(duì)多維數(shù)組的說(shuō)明，作相應(yīng)處理? /將constantpool index和new Operation儲(chǔ)存到OpList；記錄change( )*to 的操作；End IfEnd For(2)處理類方法內(nèi)部多維數(shù)組初始化和調(diào)用過(guò)程。對(duì)于初始化操作，首先計(jì)算數(shù)組容量，生成相同容量和類型的一維數(shù)組初始化代碼，代替多維數(shù)組初始化代碼；對(duì)多維數(shù)組元素的引用，首先根

11、據(jù)2.1節(jié)所示調(diào)整規(guī)則重新計(jì)算數(shù)組元素下標(biāo)，然后調(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計(jì)算數(shù)組容量，生成容量計(jì)算指令；生成相應(yīng)的1維數(shù)組初始化指令；End IfIf 訪問(wèn)多維數(shù)組元素 Then計(jì)算對(duì)應(yīng)的一維數(shù)組下標(biāo)，生成計(jì)算指令；修改外層循環(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)整操作對(duì)字節(jié)碼文件進(jìn)行修改。算法如下：int startIndex=0；For each opration in OpList do復(fù)制srcFile中startIndex至operation.index字節(jié)到newFile中；根據(jù)opration.content生成調(diào)整代碼，并寫(xiě)入到newFile中；startIndex=operation.index；End For2.3 應(yīng)用舉例為使說(shuō)明簡(jiǎn)單明了，以程序1為例

13、說(shuō)明整個(gè)調(diào)整過(guò)程。程序1展示了按列逐個(gè)訪問(wèn)2維矩陣元素的代碼。首先處理字節(jié)碼常量池部分。用一個(gè)一維數(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ù)組初始化過(guò)程取代原多維數(shù)組初始化。包括數(shù)組容量計(jì)算、去除冗余代碼、修改相關(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ù)組實(shí)例的引用。在方法內(nèi)部，對(duì)多維數(shù)組的引用，只需修改其下標(biāo)計(jì)算過(guò)程和由此引起的循環(huán)指標(biāo)變化。代碼片斷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)沒(méi)有發(fā)生變化，且提高了運(yùn)算效率。3 實(shí)驗(yàn)及結(jié)果分析本節(jié)的所有結(jié)果都是基于K虛擬機(jī)(KVM)得出的。表1列出了所用的幾個(gè)測(cè)試基準(zhǔn)及相關(guān)參數(shù)。這些基準(zhǔn)測(cè)試廣泛應(yīng)用于與Java數(shù)值計(jì)算相關(guān)的性能測(cè)試中，具有一定的權(quán)威性。為使其在KVM上正確運(yùn)行，首先對(duì)原基準(zhǔn)測(cè)試程序進(jìn)行簡(jiǎn)單調(diào)整，然后使用SUN公司提供的J2ME Wireles

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

18、ot;應(yīng)用程序">應(yīng)用程序的運(yùn)行效率。該方法不占用額外的內(nèi)存，不需要Java虛擬機(jī)和其他類庫(kù)支持?；鶞?zhǔn)測(cè)試結(jié)果表明，該方法明顯提高了程序效率，比較適用于J2ME應(yīng)用程序。參考文獻(xiàn)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