一种Java字节码静态调整的方法及应用

　摘　要： 提出了一种改善J2ME中多维数组运算效率的方法。该方法不占用额外的内存，不需要修改虚拟机，通过静态修改已经编译好的Java 字节码提高多维数组运算效率。实验表明，本方法比现有针对J2SE的多维数组运算效率解决方法更适用于J2ME环境。
　　关键词： Java J2ME JVM 多维数组 Java字节码

　　J2ME广泛应用在嵌入式系统中，其中有不少基于多维数组的运算[1]。而Java语言的以下两个机制是制约这类运算效率的瓶颈。
　　(1)Java用包含数组的数组来存储多维数组，而不同于CC++使用一块连续的空间进行存储，如图1所示。对于一个n维数组，当需要访问其中的某一个元素时，总共需要n+2次访问堆中的对象。第1和第2次访问该数组所属类的对象和数组对象；第3到第n+1次逐级访问代表每一维的数组对象；最后1次才能到达所需要访问的数组元素。如果相邻两次访问数组的元素不属于同一维，则很可能导致缓存失效，从而降低运算效率。

　　(2)Java中采用了严格的异常机制，以保证在发生异常之前的运算都遵从用户程序。在进行多维数组访问时，要对每一维的下标进行空指针检查和下标越界检查，并在有异常发生时进行相应的处理。这一机制从两个方面影响了程序的运行效率：捕获和处理异常需要占用大量的运算；阻止了代码优化，特别是影响了广泛应用于多维数组访问的循环代码的优化[2]。
　　因此，需要通过改变J2ME中多维数组的存储和访问方式或者改变异常机制来改进J2ME程序的运行效率。
1 已有的解决方案
　　目前，针对J2SE的Java多维数组来提高运算效率的方法主要有以下三种：
　　(1)使用特殊类库。这一解决方案由IBM Ninja 项目组提出[3]。该方案基于现有编译和优化技术，定义了专门用来处理多维数组运算的数据结构和函数，易于实现且高效，但需占用额外的内存来存储特殊类库，并且会消耗更多时间来动态加载程序。
　　(2)动态改变多维数组在内存中的存储结构。该方案通过降低缓存失效率来提高程序的整体效率。其实现方法是在程序运行过程中监测缓存失效率，并在需要时动态调整多维数组在内存中的存储结构，使得相邻的两次多维数组操作所涉及的数组元素在内存中处于相邻的物理空间。调整算法已由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代表指向原多维数组的引用，wm代表向量w中的第m个元素值，in代表下标向量i的第n个值，则M所指向的多维数组中的一个元素可以通过如下表达式进行访问：
　　M[i0][i1]...[id]=A[w0*i0+w1*i1+...+wd-1*id-1+id]
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上分别运行。测试结果如表2所示。

　　结果表明，通过使用本文所提出的Java字节码静态调整策略，在不改变原程序运行环境的情况下，明显提高了基于多维数组的Java程序执行效率。
　　本文提出了一种通过静态修改Java字节码中的多维数组运算指令和相关指令以及属性的方法，来提高基于多维数组运算的J2ME应用程序的运行效率。该方法不占用额外的内存，不需要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