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)需要訪問其中的某一個(gè)元素時(shí)，總共需要n+2次訪問堆中的對(duì)象。第1和第2次訪問該數(shù)組所屬類的對(duì)象和數(shù)組對(duì)象；第3到第n+1次逐級(jí)訪問代表每一維的數(shù)組對(duì)象；最后1次才能到達(dá)所需要訪問的數(shù)組元素。如果相鄰兩次訪問數(shù)組的元素不屬于同一維，則很可能導(dǎo)致緩存失效，從而降低運(yùn)算效率。

　　(2)Java中采用了嚴(yán)格的異常機(jī)制，以保證在發(fā)生異常之前的運(yùn)算都遵從用戶程序。在進(jìn)行多維數(shù)組訪問時(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ù)組訪問的循環(huán)代碼的優(yōu)化^[2]。
　　因此，需要通過改變J2ME中多維數(shù)組的存儲(chǔ)和訪問方式或者改變異常機(jī)制來(lái)改進(jìn)J2ME程序的運(yùn)行效率。
1 已有的解決方案
　　目前，針對(duì)J2SE的Java多維數(shù)組來(lái)提高運(yùn)算效率的方法主要有以下三種" 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)存中的存儲(chǔ)結(jié)構(gòu)" title="存儲(chǔ)結(jié)構(gòu)">存儲(chǔ)結(jié)構(gòu)。該方案通過降低緩存失效率來(lái)提高程序的整體效率。其實(shí)現(xiàn)方法是在程序運(yùn)行過程中監(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ī)。該方案通過修改Java虛擬機(jī)來(lái)提高效率。其策略是去除多維數(shù)組操作中進(jìn)行的指針有效性檢查和數(shù)組下標(biāo)越界檢查^[5]。由于不同的嵌入式系統(tǒng)所使用的Java虛擬機(jī)不同，所以需要對(duì)不同系統(tǒng)上的Java虛擬機(jī)做相應(yīng)的修改。
　　可見，以上三種解決方案對(duì)于J2SE來(lái)說都是可行且高效的，但對(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)算效率。通過靜態(tài)調(diào)整Java字節(jié)碼，使其被JVM裝載之后，使多維數(shù)組能保存在一塊連續(xù)的內(nèi)存區(qū)域。這樣，對(duì)多維數(shù)組的引用就在一個(gè)循環(huán)過程中始終處于緩存內(nèi)，不需要在每次使用時(shí)進(jìn)行空引用和異常檢測(cè)。
2.1 調(diào)整規(guī)則
　　首先聲明用同等容量及類型的1維數(shù)組代替原多維數(shù)組，從而在運(yùn)行時(shí)獲得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)訪問：1個(gè)變量A包含該數(shù)組的引用；一個(gè)(d-1)維的向量w記錄原數(shù)組前(d-1)維的權(quán)值，向量w中的第m個(gè)值標(biāo)明原多維數(shù)組第m維空間的大?。涣硗庖粋€(gè)d維向量i，記錄所訪問元素在原多維數(shù)組中的下標(biāo)值。令M代表指向原多維數(shù)組的引用，w_m代表向量w中的第m個(gè)元素值，i_n代表下標(biāo)向量i的第n個(gè)值，則M所指向的多維數(shù)組中的一個(gè)元素可以通過如下表達(dá)式進(jìn)行訪問：
　　M[i₀][i₁]...[i_d]=A[w₀*i₀+w₁*i₁+...+w_d-1*i_d-1+i_d]
2.2 調(diào)整過程
　　首先建立一個(gè)Opreation結(jié)構(gòu)鏈表OpList，用來(lái)記錄對(duì)字節(jié)碼進(jìn)行調(diào)整的位置和具體操作。Operation 結(jié)構(gòu)定義如下：
　　Structure Operation{
　　filed1 index；//本操作所處的字節(jié)碼字節(jié)地址
　　filed2 operation content；//具體操作定義
　　}
　　分三部分掃描字節(jié)碼文件，將每一次調(diào)整操作的位置和操作內(nèi)容記錄在OpList中。掃描結(jié)束之后，根據(jù)OpList中的內(nèi)容修改字節(jié)碼文件。
　　(1)處理常量池。將多維數(shù)組類名定義字符串修改為1維數(shù)組類名定義形式。算法如下：
　　For each tag in constantpool Do
　　If(tag is CONSTANT_Utf8_info) and″[( [ )+″appears in tag.length*2 bytes Then
????? //如果出現(xiàn)連續(xù)多個(gè)′[′的常量說明，則為對(duì)多維數(shù)組的說明，作相應(yīng)處理
???? //將constantpool index和new Operation儲(chǔ)存到OpList；記錄change″[( [ )*″to ″[″的操作；
　　End If
　　End For
　　(2)處理類方法內(nèi)部多維數(shù)組初始化和調(diào)用過程。對(duì)于初始化操作，首先計(jì)算數(shù)組容量，生成相同容量和類型的一維數(shù)組初始化代碼，代替多維數(shù)組初始化代碼；對(duì)多維數(shù)組元素的引用，首先根據(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 Do
　　　If　是多維數(shù)組初始化命令 Then
　　　　　計(jì)算數(shù)組容量，生成容量計(jì)算指令；
　　　　　生成相應(yīng)的1維數(shù)組初始化指令；
　　　End If
　　　If 訪問多維數(shù)組元素 Then
　　　計(jì)算對(duì)應(yīng)的一維數(shù)組下標(biāo)，生成計(jì)算指令；
　　　修改外層循環(huán)代碼；
　　　End If
　　　生成包含操作位置和內(nèi)容的Operation結(jié)構(gòu)，并插入OpList；
　　End For
　　If 修改了本方法代碼 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)整代碼，并寫入到newFile中；
　　　startIndex=operation.index；
　　End For
2.3 應(yīng)用舉例
　　為使說明簡(jiǎn)單明了，以程序1為例說明整個(gè)調(diào)整過程。程序1展示了按列逐個(gè)訪問2維矩陣元素的代碼。
　　首先處理字節(jié)碼常量池部分。用一個(gè)一維數(shù)組定義取代原有的多維數(shù)組定義。處理前后字節(jié)碼如代碼片斷1和代碼片斷2所示。
　　程序1
　　int[][]x=new int[100][100]；
　　int tmp=0；
　　for(int i=0；i<100；i++){
　　　for(int j=0；j<100；j++){
　　　　　tmp+-x[j][i]；
　　　}
　　}
　　代碼片斷1：
　　01 00 01 78 　　　　　　　 const#6=Asciz x；
　　01 00 03 5B 5B 49　　　　　const#7=Asciz [[I；
　　0C 00 06 00 07　　　　　　 const#16=NameAndType #6：#7；
　　代碼片斷2：
　　01 00 01 78　　　　　　　　const#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ù)組容量計(jì)算、去除冗余代碼、修改相關(guān)函數(shù)和代碼屬性。處理前后字節(jié)碼如代碼片斷3和代碼片斷4。
　　代碼片斷3：
　　10 64 bipush 100
　　10 64 bipush 100
　　c5 00 02 02 multianewarray #2，2；
　　b5 00 03 putfield #3；
　　代碼片斷4：
　　11 27 10 sipush 10000
　　bc 0a newarray int
　　b5 00 02 putfield #3；
　　最后處理多維數(shù)組實(shí)例的引用。在方法內(nèi)部，對(duì)多維數(shù)組的引用，只需修改其下標(biāo)計(jì)算過程和由此引起的循環(huán)指標(biāo)變化。代碼片斷5和代碼片斷6分別列出了程序1所示代碼中兩層for循環(huán)的字節(jié)碼。
　　代碼片斷5：
　　10 64　　　　　　　　bipush 100
　　a2 00 2d　　　　　　 if_icmpge 45
　　03　　　　　　　　　 iconst_0
　　3d　　　　　　　　　 istore_2
　　1c　　　　　　　　　 iload_2
　　10 64　　　　　　　　bipush 100
　　a2 00 27　　　　　　 if_icmpge 39
　　2a　　　　　　　　　 aload_0
　　59 dup
　　代碼片斷6：
　　10 64　　　　　　　　 bipush 100　　　　3e　　　　　　istore_3
　　02 00 35　　　　　　 if_icmpge 53　　　ld　　　　　　iload_3
　　1c　　　　　　　　　　iload_2　　　　　 10 64　　　　 bipush 100
　　10 64　　　　　　　　 bipush 100　　　　a2 00 2f　　　if_icmpge 47
　　64　　　　　　　　　　isub　　　　　　　84 01 64　　　iinc 1，100
　　3c　　　　　　　　　　istore_1　　　　　2a　　　　　　aload_0
　　03　　　　　　　　　　iconst_0　　　　　59　　　　　　dup
　　經(jīng)處理，字節(jié)碼大小和整體結(jié)構(gòu)沒有發(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 Wireless Toolkit 2.2進(jìn)行編譯，得到初始字節(jié)碼，再使用字節(jié)碼靜態(tài)調(diào)整工具對(duì)這些字節(jié)碼進(jìn)行處理得到最后的執(zhí)行代碼，最后在KVM上分別運(yùn)行。測(cè)試結(jié)果" title="測(cè)試結(jié)果">測(cè)試結(jié)果如表2所示。

　　結(jié)果表明，通過使用本文所提出的Java字節(jié)碼靜態(tài)調(diào)整策略，在不改變?cè)绦蜻\(yùn)行環(huán)境的情況下，明顯提高了基于多維數(shù)組的Java程序執(zhí)行效率。
　　本文提出了一種通過靜態(tài)修改Java字節(jié)碼中的多維數(shù)組運(yùn)算指令和相關(guān)指令以及屬性的方法，來(lái)提高基于多維數(shù)組運(yùn)算的J2ME應(yīng)用程序" title="應(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 1998
2 Mikel Lujan，John R Gurd，T L Freeman et al.Elimination of java array bounds checks in the presence of indirection. Technical Report CSPP-13，Department of computer science， university of manchester，F(xiàn)ebruary 2002
3 J E Moreira，S P Midki_，M Gupta et al.The Ninja project.Communications of the ACM，2001；44(10)
4 F Li，P Agrawal，G Eberhardt et al.Improving memory performance of embedded Java applications by dynamic layout modifications.In：18th International Parallel and Distributed Processing Symposium(IPDPS′04)-Workshop 5，2004：159
5 R Bodik，R Gupta，V Sarkar.ABCD：Eliminating array bounds checks on demand.In：Proceedings of the ACM Conference on Programming Language Design and Implementation，2000：321