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

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

　　結果表明，通過使用本文所提出的Java字節碼靜態調整策略，在不改變原程序運行環境的情況下，明顯提高了基于多維數組的Java程序執行效率。
　　本文提出了一種通過靜態修改Java字節碼中的多維數組運算指令和相關指令以及屬性的方法，來提高基于多維數組運算的J2ME應用程序" title="應用程序">應用程序的運行效率。該方法不占用額外的內存，不需要Java虛擬機和其他類庫支持。基準測試結果表明，該方法明顯提高了程序效率，比較適用于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，February 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