J2ME廣泛應用在嵌入式系統(tǒng)中，其中有不少基于多維數(shù)組的運算^[1]。而Java語言的以下兩個機制是制約這類運算效率的瓶頸。
　　(1)Java用包含數(shù)組的數(shù)組來存儲多維數(shù)組，而不同于CC++使用一塊連續(xù)的空間進行存儲，如圖1所示。對于一個n維數(shù)組，當需要訪問其中的某一個元素時，總共需要n+2次訪問堆中的對象。第1和第2次訪問該數(shù)組所屬類的對象和數(shù)組對象；第3到第n+1次逐級訪問代表每一維的數(shù)組對象；最后1次才能到達所需要訪問的數(shù)組元素。如果相鄰兩次訪問數(shù)組的元素不屬于同一維，則很可能導致緩存失效，從而降低運算效率。

　　(2)Java中采用了嚴格的異常機制，以保證在發(fā)生異常之前的運算都遵從用戶程序。在進行多維數(shù)組訪問時，要對每一維的下標進行空指針檢查和下標越界檢查，并在有異常發(fā)生時進行相應的處理。這一機制從兩個方面影響了程序的運行效率：捕獲和處理異常需要占用大量的運算；阻止了代碼優(yōu)化，特別是影響了廣泛應用于多維數(shù)組訪問的循環(huán)代碼的優(yōu)化^[2]。
　　因此，需要通過改變J2ME中多維數(shù)組的存儲和訪問方式或者改變異常機制來改進J2ME程序的運行效率。
1 已有的解決方案
　　目前，針對J2SE的Java多維數(shù)組來提高運算效率的方法主要有以下三種" title="三種">三種：
　　(1)使用特殊類庫。這一解決方案由IBM Ninja 項目組提出^[3]。該方案基于現(xiàn)有編譯和優(yōu)化技術，定義了專門用來處理多維數(shù)組運算的數(shù)據(jù)結構和函數(shù)，易于實現(xiàn)且高效，但需占用額外的內(nèi)存來存儲特殊類庫，并且會消耗更多時間來動態(tài)加載程序。
　　(2)動態(tài)改變多維數(shù)組在內(nèi)存中的存儲結構" title="存儲結構">存儲結構。該方案通過降低緩存失效率來提高程序的整體效率。其實現(xiàn)方法是在程序運行過程中監(jiān)測緩存失效率，并在需要時動態(tài)調(diào)整多維數(shù)組在內(nèi)存中的存儲結構，使得相鄰的兩次多維數(shù)組操作所涉及的數(shù)組元素在內(nèi)存中處于相鄰的物理空間。調(diào)整算法已由F.Li，P給出^[4]。這一方案需要額外的內(nèi)存空間來完成存儲結構動態(tài)調(diào)整，同時需要操作系統(tǒng)對緩存失效率進行實時監(jiān)測，實施起來有一定困難。
　　(3)修改Java虛擬機。該方案通過修改Java虛擬機來提高效率。其策略是去除多維數(shù)組操作中進行的指針有效性檢查和數(shù)組下標越界檢查^[5]。由于不同的嵌入式系統(tǒng)所使用的Java虛擬機不同，所以需要對不同系統(tǒng)上的Java虛擬機做相應的修改。
　　可見，以上三種解決方案對于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ù)組，從而在運行時獲得JVM堆中一塊連續(xù)的存儲空間。同時修改所有對多維數(shù)組的引用。當把一個d維數(shù)組轉化為一個1維數(shù)組時，對數(shù)組中的每一個元素需要使用2×d個變量來訪問：1個變量A包含該數(shù)組的引用；一個(d-1)維的向量w記錄原數(shù)組前(d-1)維的權值，向量w中的第m個值標明原多維數(shù)組第m維空間的大?。涣硗庖粋€d維向量i，記錄所訪問元素在原多維數(shù)組中的下標值。令M代表指向原多維數(shù)組的引用，w_m代表向量w中的第m個元素值，i_n代表下標向量i的第n個值，則M所指向的多維數(shù)組中的一個元素可以通過如下表達式進行訪問：
　　M[i₀][i₁]...[i_d]=A[w₀*i₀+w₁*i₁+...+w_d-1*i_d-1+i_d]
2.2 調(diào)整過程
　　首先建立一個Opreation結構鏈表OpList，用來記錄對字節(jié)碼進行調(diào)整的位置和具體操作。Operation 結構定義如下：
　　Structure Operation{
　　filed1 index；//本操作所處的字節(jié)碼字節(jié)地址
　　filed2 operation content；//具體操作定義
　　}
　　分三部分掃描字節(jié)碼文件，將每一次調(diào)整操作的位置和操作內(nèi)容記錄在OpList中。掃描結束之后，根據(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ù)多個′[′的常量說明，則為對多維數(shù)組的說明，作相應處理
???? //將constantpool index和new Operation儲存到OpList；記錄change″[( [ )*″to ″[″的操作；
　　End If
　　End For
　　(2)處理類方法內(nèi)部多維數(shù)組初始化和調(diào)用過程。對于初始化操作，首先計算數(shù)組容量，生成相同容量和類型的一維數(shù)組初始化代碼，代替多維數(shù)組初始化代碼；對多維數(shù)組元素的引用，首先根據(jù)2.1節(jié)所示調(diào)整規(guī)則重新計算數(shù)組元素下標，然后調(diào)整本次引用所處的外層循環(huán)，并修改相關代碼屬性，包括length、ine_number_table_
　　length、max_locals和code_length等。算法如下：
　　For each command in one method section Do
　　　If　是多維數(shù)組初始化命令 Then
　　　　　計算數(shù)組容量，生成容量計算指令；
　　　　　生成相應的1維數(shù)組初始化指令；
　　　End If
　　　If 訪問多維數(shù)組元素 Then
　　　計算對應的一維數(shù)組下標，生成計算指令；
　　　修改外層循環(huán)代碼；
　　　End If
　　　生成包含操作位置和內(nèi)容的Operation結構，并插入OpList；
　　End For
　　If 修改了本方法代碼 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
　　　復制srcFile中startIndex至operation.index字節(jié)到newFile中；
　　　根據(jù)opration.content生成調(diào)整代碼，并寫入到newFile中；
　　　startIndex=operation.index；
　　End For
2.3 應用舉例
　　為使說明簡單明了，以程序1為例說明整個調(diào)整過程。程序1展示了按列逐個訪問2維矩陣元素的代碼。
　　首先處理字節(jié)碼常量池部分。用一個一維數(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ù)組容量計算、去除冗余代碼、修改相關函數(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ù)組實例的引用。在方法內(nèi)部，對多維數(shù)組的引用，只需修改其下標計算過程和由此引起的循環(huán)指標變化。代碼片斷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é)碼大小和整體結構沒有發(fā)生變化，且提高了運算效率。
3 實驗及結果分析
　　本節(jié)的所有結果都是基于K虛擬機(KVM)得出的。表1列出了所用的幾個測試基準及相關參數(shù)。這些基準測試廣泛應用于與Java數(shù)值計算相關的性能測試中，具有一定的權威性。為使其在KVM上正確運行，首先對原基準測試程序進行簡單調(diào)整，然后使用SUN公司提供的J2ME Wireless Toolkit 2.2進行編譯，得到初始字節(jié)碼，再使用字節(jié)碼靜態(tài)調(diào)整工具對這些字節(jié)碼進行處理得到最后的執(zhí)行代碼，最后在KVM上分別運行。測試結果" title="測試結果">測試結果如表2所示。

　　結果表明，通過使用本文所提出的Java字節(jié)碼靜態(tài)調(diào)整策略，在不改變原程序運行環(huán)境的情況下，明顯提高了基于多維數(shù)組的Java程序執(zhí)行效率。
　　本文提出了一種通過靜態(tài)修改Java字節(jié)碼中的多維數(shù)組運算指令和相關指令以及屬性的方法，來提高基于多維數(shù)組運算的J2ME應用程序" title="應用程序">應用程序的運行效率。該方法不占用額外的內(nèi)存，不需要Java虛擬機和其他類庫支持?；鶞蕼y試結果表明，該方法明顯提高了程序效率，比較適用于J2ME應用程序。
參考文獻
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